1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

------------------------------------------------------------------------------
--- A collection of common operations on integer numbers.
--- Most operations make no assumption on the precision of integers.
--- Operation `bitNot` is necessarily an exception.
---
--- @author Sergio Antoy
--- @version October 2016
--- @category general
------------------------------------------------------------------------------

module Integer
  ( (^), pow, ilog, isqrt, factorial, binomial
  , max3, min3, maxlist, minlist
  , bitTrunc, bitAnd, bitOr, bitNot, bitXor
  , even, odd ) where

infixr 8 ^

------------------------------------------------------------------
--                       Public Operations
------------------------------------------------------------------

--- The value of `a ^ b` is `a` raised to the power of `b`.
--- Fails if `b < 0`.
--- Executes in `O(log b)` steps.
---
--- @param a - The base.
--- @param b - The exponent.
--- @return `a` raised to the power of `b`.

(^) :: Int -> Int -> Int
a ^ b = pow a b

--- The value of `pow a b` is `a`
--- raised to the power of `b`.
--- Fails if `b < 0`.
--- Executes in `O(log b)` steps.
---
--- @param a - The base.
--- @param b - The exponent.
--- @return `a` raised to the power of `b`.

pow :: Int -> Int -> Int
pow a b | b>= 0 = powaux 1 a b
 where
  powaux n x y = if y == 0
                   then n
                   else powaux (n * if (y `mod` 2 == 1) then x else 1)
                               (x * x)
                               (y `div` 2)

--- The value of `ilog n` is the floor of the logarithm
--- in the base 10 of `n`.
--- Fails if `n <= 0`.
--- For positive integers, the returned value is
--- 1 less the number of digits in the decimal representation of `n`.
---
--- @param n - The argument.
--- @return the floor of the logarithm in the base 10 of `n`.

ilog :: Int -> Int
ilog n | n>0 = if n<10 then 0 else 1 + ilog (n `div` 10)

--- The value of `isqrt n` is the floor
--- of the square root of `n`.
--- Fails if `n &lt; 0`.
--- Executes in `O(log n)` steps, but there must be a better way.
---
--- @param n - The argument.
--- @return the floor of the square root of `n`.

isqrt :: Int -> Int
isqrt n | n >= 0 = if n == 0 then 0
                             else if n <  4 then 1
                                            else aux 2 n
 where
  aux low past = -- invariant low <= result < past
    if past == low+1
      then low
      else let cand = (past + low) `div` 2
           in if cand*cand > n then aux low cand else aux cand past

--- The value of `factorial n` is the factorial of `n`.
--- Fails if `n &lt; 0`.
---
--- @param n - The argument.
--- @return the factorial of `n`.

factorial :: Int -> Int
factorial n | n >= 0 = if n == 0 then 1 else n * factorial (n-1)

--- The value of `binomial n m` is `n*(n-1)*...*(n-m+1)/m*(m-1)*...1`.
--- Fails if `m &lt;= 0` or `n &lt; m`.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the binomial coefficient of `n` over `m`.

binomial :: Int -> Int -> Int
binomial n m | m > 0 && n >= m = aux m n `div` factorial m
  where aux x y = if x == 0 then 1 else y * aux (x-1) (y-1)

--- Returns the maximum of the three arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @param p - Argument.
--- @return the maximum among `n`, `m` and `p`.

max3 :: Ord a => a -> a -> a -> a
max3 n m p = max n (max m p)

--- Returns the minimum of the three arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @param p - Argument.
--- @return the minimum among `n`, `m` and `p`.

min3 :: Ord a => a -> a -> a -> a
min3 n m p = min n (min m p)

--- Returns the maximum of a list of integer values.
--- Fails if the list is empty.
---
--- @param l - The list of values.
--- @return the maximum element of `l`.

maxlist :: Ord a => [a] -> a
maxlist [n]      = n
maxlist (n:m:ns) = max n (maxlist (m:ns))

--- Returns the minimum of a list of integer values.
--- Fails if the list is empty.
---
--- @param l - The list of values.
--- @return the minimum element of `l`.

minlist :: Ord a => [a] -> a
minlist [n]      = n
minlist (n:m:ns) = min n  (minlist (m:ns))

--- The value of `bitTrunc n m` is the value of the `n`
--- least significant bits of `m`.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return `m` truncated to the `n` least significant bits.

bitTrunc :: Int -> Int -> Int
bitTrunc n m = bitAnd (pow 2 n - 1) m

--- Returns the bitwise AND of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise and of `n` and `m`.

bitAnd :: Int -> Int -> Int
bitAnd n m = if m == 0
               then 0
               else let p = 2 * bitAnd (n `div` 2) (m `div` 2)
                        q = if m `mod` 2 == 0 then 0 else n `mod` 2
                    in p + q

--- Returns the bitwise inclusive OR of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise inclusive or of `n` and `m`.

bitOr :: Int -> Int -> Int
bitOr n m = if m == 0
              then n
              else let p = 2 * bitOr (n `div` 2) (m `div` 2)
                       q = if m `mod` 2 == 1 then 1 else n `mod` 2
                   in p + q

--- Returns the bitwise NOT of the argument.
--- Since integers have unlimited precision,
--- only the 32 least significant bits are computed.
---
--- @param n - Argument.
--- @return the bitwise negation of `n` truncated to 32 bits.

bitNot :: Int -> Int
bitNot n = aux 32 n
 where
  aux c m = if c==0
              then 0
              else let p = 2 * aux (c-1) (m `div` 2)
                       q = 1 - m `mod` 2
                   in p + q

--- Returns the bitwise exclusive OR of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise exclusive of `n` and `m`.

bitXor :: Int -> Int -> Int
bitXor n m = if m == 0
               then n
               else let p = 2 * bitXor (n `div` 2) (m `div` 2)
                        q = if m `mod` 2 == n `mod` 2 then 0 else 1
                    in p + q

--- Returns whether an integer is even
---
--- @param n - Argument.
--- @return whether `n` is even.

even :: Int -> Bool
even n = n `mod` 2 == 0

--- Returns whether an integer is odd
---
--- @param n - Argument.
--- @return whether `n` is odd.

odd :: Int -> Bool
odd n = n `mod` 2 /= 0