## Big Numbers: Getting Started

### May 24, 2011

We begin by specifying the radix for our digits:

`(define big-base 1000)`

Converting between Scheme’s native integers and our big numbers is similar to the `digits`

and `undigits`

functions of the Standard Prelude. Here is `integer->big`

:

`(define (integer->big int)`

(if (zero? int) (list 0)

(if (negative? int)

(let ((x (integer->big (- int))))

(cons (- (car x)) (cdr x)))

(let loop ((int int) (big '()))

(if (< int big-base)

(cons (+ (length big) 1)

(reverse (cons int big)))

(loop (quotient int big-base)

(cons (modulo int big-base) big)))))))

We handle zero as a special case, and negative numbers by calling `integer->big`

on the negation of the input integer. The heart of the function is the `loop`

that uses `quotient`

and `modulo`

to pick off each big-digit, stopping when the remaining part of the input is less than the radix.

`Big->integer`

is the inverse of `integer->big`

. It also handles zero and negative numbers as special cases; the main loop uses Horner’s Rule to accumulate the value of the polynomial:

`(define (big->integer big)`

(if (zero? (car big)) 0

(if (negative? (car big))

(- (big->integer (cons (- (car big)) (cdr big))))

(let loop ((bs (reverse (cdr big))) (n 0))

(if (null? bs) n

(loop (cdr bs) (+ (car bs) (* n big-base))))))))

The absolute value and negation functions look only at the signed magnitude in the head of the list:

`(define (big-abs big)`

(if (positive? (car big)) big (cons (- (car big)) (cdr big))))

(define (big-negate big) (cons (* (car big) -1) (cdr big)))

The tests for positive, negative and zero also only look at the signed magnitude in the head of the list.

`(define (big-positive? big) (positive? (car big)))`

(define (big-negative? big) (negative? (car big)))

(define (big-zero? big) (zero? (car big)))

The tests for odd and even look at least-significant big-digit; note that these tests assume that `big-base`

is even:

`(define (big-even? big)`

(or (big-zero? big) (even? (cadr big))))

(define (big-odd? big)

(not (or (big-zero? big) (even? (cadr big)))))

We’ll give two different forms for comparisons, since both are useful in different circumstances. `Big-compare`

takes two big numbers and returns -1 if the first is less than the second, 1 if the second is less than the first, and 0 if they are equal. `Big-compare`

first looks at the signed magnitudes of the two numbers; if the first is less than the second, it returns -1, and if the second is less than the first, it returns 1, making that determination without even looking at the digits of the two big numbers. If the signed magnitudes are equal, `big-compare`

runs through the two big numbers big-digit by big-digit, starting with the most significant big-digits, until there is a mismatch:

`(define (big-compare big1 big2)`

; big1 < big2 => -1 ; big1 = big2 => 0 ; big1 > big2 => 1

(cond ((< (car big1) (car big2)) -1)

((< (car big2) (car big1)) 1)

(else (let loop ((b1 (reverse (cdr big1)))

(b2 (reverse (cdr big2))))

(cond ((null? b1) 0)

((< (car b1) (car b2)) -1)

((< (car b2) (car b1)) 1)

(else (loop (cdr b1) (cdr b2))))))))

The other form for the comparison operators is the traditional <, > and so on. All of these call `big-compare`

to make the actual comparison:

`(define (big-eq? big1 big2)`

(zero? (big-compare big1 big2)))

(define (big-ne? big1 big2)

(not (zero? (big-compare big1 big2))))

(define (big-lt? big1 big2)

(negative? (big-compare big1 big2)))

(define (big-gt? big1 big2)

(positive? (big-compare big1 big2)))

(define (big-le? big1 big2)

(not (positive? (big-compare big1 big2))))

(define (big-ge? big1 big2)

(not (negative? (big-compare big1 big2))))

That’s all for today; we’ll do some arithmetic in the next exercise. You can run the program at http://programmingpraxis.codepad.org/3RnYkEqN.

Pages: 1 2

[…] Praxis – Big Numbers: Getting Started By Remco Niemeijer In today’s Programming Praxis exercise, our task is to implement the basics of a library for big numbers. […]

My Haskell solution (see http://bonsaicode.wordpress.com/2011/05/24/programming-praxis-big-numbers-getting-started/ for a version with comments):

A quick and dirty BigNum class:

;; radix must be >1 for bignums to be working

(define (int->bignum n #!optional (radix (expt 2 16)))

(if (zero? n)

'(0)

(let loop ((nl (abs n)) (l '()))

(if (< nl radix)

(cons ((if (positive? n) + -)

(1+ (length l)))

(cons nl l))

(loop (quotient nl radix)

(cons (modulo nl radix) l))))))

;

(define (bignum->int n #!optional (radix (expt 2 16)))

(if (zero? (car n))

0

((if (positive? (car n)) + -)

(let loop ((nl (cdr n)) (m 0))

(if (null? nl)

m

(loop (cdr nl)

(+ (* radix m)

(car nl))))))))

;

(define (bignum-abs n)

(cons (abs (car n))

(cdr n)))

;

(define (bignum-negate n)

(cons (- 0 (car n))

(cdr n)))

;

(define (bignum-positive? n)

(positive? (car n)))

;

(define (bignum-negative? n)

(negative? (car n)))

;

(define (bignum-zero? n)

(zero? (car n)))

;

(define (bignum-even? n)

(even? (car (reverse n))))

`(define (bignum-odd? n)`

(odd? (car (reverse n))))

;

(define (bignum-compare m n)

(if (and (null? m) (null? n))

0

(cond

((< (car m) (car n))

-1)

((> (car m) (car n))

1)

(else (bignum-compare (cdr m) (cdr n))))))

It seems to me your solution, in particular, `big-compare’ doesn’t handle the comparison of two negative big numbers of the same length correctly. By the way, could you please delete my previous comment which contains a dead link? My version is now on Google Code: https://code.google.com/p/prograxis/source/browse/bignum.scm

DAY: I deleted your earlier comment. Thanks for pointing out the bug. Here’s a fixed version: