Big Numbers: Examples

July 5, 2011

All of these exercises are easy, just a matter of substituting the “big” functions for the normal arithmetic operators. Here’s factorial:

(define (big-factorial n)
  (let loop ((n (- n 1)) (k '(1 1)) (f '(1 1)))
    (display (big->string k)) (display " ")
    (display (big->string f)) (newline)
    (when (positive? n)
      (let ((k (big-plus k '(1 1))))
        (loop (- n 1) k (big-times f k))))))

> (big-factorial 50)

1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
21 51090942171709440000
22 1124000727777607680000
23 25852016738884976640000
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000
27 10888869450418352160768000000
28 304888344611713860501504000000
29 8841761993739701954543616000000
30 265252859812191058636308480000000
31 8222838654177922817725562880000000
32 263130836933693530167218012160000000
33 8683317618811886495518194401280000000
34 295232799039604140847618609643520000000
35 10333147966386144929666651337523200000000
36 371993326789901217467999448150835200000000
37 13763753091226345046315979581580902400000000
38 523022617466601111760007224100074291200000000
39 20397882081197443358640281739902897356800000000
40 815915283247897734345611269596115894272000000000
41 33452526613163807108170062053440751665152000000000
42 1405006117752879898543142606244511569936384000000000
43 60415263063373835637355132068513997507264512000000000
44 2658271574788448768043625811014615890319638528000000000
45 119622220865480194561963161495657715064383733760000000000
46 5502622159812088949850305428800254892961651752960000000000
47 258623241511168180642964355153611979969197632389120000000000
48 12413915592536072670862289047373375038521486354677760000000000
49 608281864034267560872252163321295376887552831379210240000000000
50 30414093201713378043612608166064768844377641568960512000000000000

Factorization by trial division first removes factors of 2, then loops through odd numbers starting from 3:

(define (big-factors n)
  (if (big-even? n)
      (cons '(1 2) (factors (big-quotient n '(1 2))))
      (let loop ((n n) (f '(1 3)) (fs '()))
        (cond ((big-lt? n (big-times f f))
                (reverse (cons n fs)))
              ((big-zero? (big-modulo n f))
                (loop (big-quotient n f) f (cons f fs)))
              (else (loop n (big-plus f '(1 2)) fs))))))

(map big->integer (big-factors (integer->big 11111111111111111111)))
(11 41 101 271 3541 9091 27961)

We’re limiting discussion because these algorithms are all familiar from previous exercises. Here’s the primality checker:

(define (big-prime? n)
  (define (witness? a n)
    (let loop ((r '(0)) (s (big-minus n '(1 1))))
      (if (big-even? s)
          (loop (big-plus r '(1 1)) (big-quotient s '(1 2)))
          (if (big-eq? (big-expm a s n) '(1 1)) #t
            (let loop ((j '(0)) (s s))
              (cond ((big-eq? j r) #f)
                    ((big-eq? (big-expm a s n) (big-minus n '(1 1))) #t)
                    (else (loop (big-plus j '(1 1)) (big-times s '(1 2))))))))))
  (cond ((big-lt? n '(1 2)) #f)
        ((big-even? n) (big-eq? n '(1 2)))
        (else (let loop ((k 20))
                (cond ((zero? k) #t)
                      ((not (witness? (big-rand '(1 1) n) n)) #f)
                      (else (loop (- k 1))))))))

> (big-prime? (integer->big (- (expt 2 89) 1)))
#t

Even though the algorithms are the same, they look quite different because big-numbers are called with function names instead of the normal operators. Here’s the Pollard rho algorithm:

(define (big-rho n)
  (define (factor n c)
    (define (f x) (big-modulo (big-plus (big-times x x) c) n))
    (let loop ((x '(1 2)) (y '(1 2)) (d '(1 1)))
      (cond ((big-eq? d '(1 1))
              (let ((x (f x)) (y (f (f y))))
                (loop x y (big-gcd (big-minus x y) n))))
            ((big-eq? d n) (factor n (big-plus c '(1 1))))
            (else d))))
  (sort big-lt?
    (let fact ((n n) (fs '()))
      (cond ((big-eq? n '(1 1)) fs)
            ((big-even? n) (fact (big-quotient n '(1 2)) (cons '(1 2) fs)))
            ((big-prime? n) (cons n fs))
            (else (let ((f (factor n '(1 1))))
              (append fs (fact f '()) (fact (big-quotient n f) '()))))))))

> (map big->integer (big-rho (integer->big 13290059)))
(3119 4261)

We used sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/abIROIpC.

About these ads

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: