[project @ 1996-07-25 21:02:03 by partain]
[nofib.git] / spectral / primetest / IntLib.lhs
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 %
12
13 In this module we define some useful functions on Integers.
14
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 $"
19
20 \subsection{Reading and Writing}
21
22 > readInteger :: String -> Integer
23 > readInteger s = read s
24
25 > showInteger :: Integer -> String
26 > showInteger i = show i
27
28 \subsection{Interconverting between bases}
29
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\]
34
35 > makeNumber :: Integer -> [Integer] -> Integer
36 > makeNumber b = foldl f 0 where f a x = a * b + x
37
38 The (left and right) inverse of @makeNumber@ is @chop@.
39
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
43
44 \subsection{Raising a number to a power}
45
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
50 Haskell library.
51
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)
61
62 [This coding of al-Kash\^{\i}'s algorithm is due to Joe Fasel.]
63
64 \subsection{Integer Cube roots}
65
66 The value $@y@=@cubeRoot x@$ is the integer cube root of @x@, {\it
67 i.e.} $@y@ = \lfloor \sqrt[3]{@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.
75
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
82
83 \subsection{Logarithm base 2}
84
85 The $@log2@ n$ is the @Integer@ $m$ such that $m = \lfloor\log_2
86 n\rfloor$.
87
88 > log2 :: Integer -> Integer
89 > log2 = genericLength . chop 2
90
91 This concludes the integer functions needed for the RSA algorithm.
92