1 \section{Some Integer Functions}
2 %$Log: IntLib.lhs,v$
3 %Revision 1.2  1996/07/25 21:32:53  partain
4 %Bulk of final changes for 2.01
5 %
6 %Revision 1.1  1996/01/08 20:04:20  partain
7 %Initial revision
8 %
9 %Revision 1.1  92/06/30  15:54:07  dlester
10 %Initial revision
11 %
13 In this module we define some useful functions on Integers.
15 > module IntLib (readInteger, showInteger, makeNumber, chop,
16 >                powerMod, cubeRoot, log2) where
17 > import List--1.3
18 > rcsid = "$Header: /srv/cvs/cvs.haskell.org/fptools/nofib/spectral/primetest/IntLib.lhs,v 1.2 1996/07/25 21:32:53 partain Exp$"
22 > readInteger :: String -> Integer
25 > showInteger :: Integer -> String
26 > showInteger i = show i
28 \subsection{Interconverting between bases}
30 We can make a large number from a list of numbers using @makeNumber@.
31 This satisfies:
32 $@makeNumber@ \, @b@ \, [x_0,\,x_1,\,\ldots,\,x_n] 33 = x_0.@b@^n + x_1.@b@^{n-1} + \cdots + x_n.@b@^0$
35 > makeNumber :: Integer -> [Integer] -> Integer
36 > makeNumber b = foldl f 0 where f a x = a * b + x
38 The (left and right) inverse of @makeNumber@ is @chop@.
40 > chop :: Integer -> Integer -> [Integer]
41 > chop b = chop' [] where chop' a n = if n == 0 then a else chop' (r:a) q
42 >                                     where (q,r) = n divMod b
44 \subsection{Raising a number to a power}
46 The following function @powerMod@ calculates @a^b mod m@. I suspect
47 that this is the critical function in the benchmarking process, and
48 given that it can be computed {\em without} a great deal of extra
49 storage, it should be a candidate for being a built-in within the
52 > powerMod :: Integer -> Integer -> Integer -> Integer
53 > powerMod a 0 m = 1
54 > powerMod a b m
55 >  = f a' (b-1) a'
56 >    where a' = a mod m
57 >          f a 0 c = c
58 >          f a b c = g a b where
59 >                    g a b | even b    = g ((a*a) mod m) (b div 2)
60 >                          | otherwise = f a (b-1) ((a*c) mod m)
62 [This coding of al-Kash\^{\i}'s algorithm is due to Joe Fasel.]
64 \subsection{Integer Cube roots}
66 The value $@y@=@cubeRoot x@$ is the integer cube root of @x@, {\it
67 i.e.} $@y@ = \lfloor \sqrt{@x@} \, \rfloor$. Given $@x@\geq 0$,
68 @y@ satisfies the following conditions:
69 $\begin{array}{lll} 70 @y@ &\geq & 0, \\ 71 @y@^3 &\geq & @x@, \mbox{ and}\\ 72 (@y@-1)^3 &<& @x@. 73 \end{array}$
74 My implementation uses Newton's method.
76 > cubeRoot :: Integer -> Integer
77 > cubeRoot x = until satisfy improve x
78 >              where satisfy y = y*y*y >= x && y'*y'*y' < x where y' = y-1
79 >                    improve y = (2*y*y*y+x) ddiv (3*y*y)
80 >                    ddiv a b  = if (r < b div 2) then q else q+1
81 >                                where (q,r) = divMod a b
83 \subsection{Logarithm base 2}
85 The $@log2@ n$ is the @Integer@ $m$ such that $m = \lfloor\log_2 86 n\rfloor$.
88 > log2 :: Integer -> Integer
89 > log2 = genericLength . chop 2
91 This concludes the integer functions needed for the RSA algorithm.