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.
Programming Praxis 
[…] 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):
import Data.List data BigNum = B Int [Int] deriving (Eq, Show) base :: Integer base = 1000 instance Num BigNum where negate (B l ds) = B (-l) ds abs (B l ds) = B (abs l) ds signum (B l _) = fromIntegral $ signum l fromInteger n | n < 0 = negate $ fromInteger (-n) | otherwise = B (length ds) (map fromIntegral ds) where ds = tail $ f (n,0) f (0,m) = [m] f (d,m) = m : f (divMod d base) positive, negative, zero :: (Num a, Ord a) => a -> Bool positive = (> 0) negative = (< 0) zero = (== 0) bigOdd, bigEven :: BigNum -> Bool bigEven (B l ds) = l == 0 || even (head ds) bigOdd = not . bigEven fromBig :: BigNum -> Integer fromBig (B _ ds) = foldr (\x a -> fromIntegral x + base * a) 0 ds instance Ord BigNum where compare (B l1 ds1) (B l2 ds2) = case compare l1 l2 of EQ -> maybe EQ id . find (/= EQ) . reverse $ zipWith compare ds1 ds2 c -> cA quick and dirty BigNum class:
#this is so you don't have to define all the ordering functions (>, >=, ==, ...) from functools import total_ordering @total_ordering class BigNum: def __init__(self, value=0, radix=1000): self.radix = radix self.rep = [1 if value > 0 else -1 if value < 0 else 0] value = value if value >= 0 else -value while value: value,rem = divmod(value, radix) self.rep.append(rem) self.rep[0] *= len(self.rep) - 1 def __abs__(self): ret = BigNum() ret.rep = self.rep[:] if ret.rep[0] < 0: ret.rep[0] = -ret.rep[0] return ret def __neg__(self): ret = BigNum() ret.rep = self.rep[:] ret.rep[0] = -ret.rep[0] return ret def __lt__(self, other): if self.rep[0] < other.rep[0]: return True for s,o in reversed(zip(self.rep, other.rep)): if s < o: return True return False def __eq__(self, other): return self.rep == other.rep def __repr__(self): return "BigNum({})".format(self.rep) def __str__(self): return str(self.to_int()) def is_negative(self): return self.rep[0] < 0 def is_zero(self): return self.rep[0] == 0 def is_positive(self): return self.rep[0] > 0 def is_even(self): return self.is_zero or not (self.rep[1] & 1) def is_odd(self): return not self.is_zero() and (self.rep[1] & 1) def to_int(self): value = 0 for part in reversed(self.rep[1:]): value = self.radix * value + part return value;; 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))))))
(define (sign num) (cond ((positive? num) 1) ((negative? num) -1) (else 0))) (define (int->bignum num radix) (define (int->bignum-iter rest acc) (if (zero? rest) (cons (* (length acc) (sign num)) (reverse acc)) (int->bignum-iter (quotient rest radix) (cons (remainder rest radix) acc)))) (int->bignum-iter num '())) (define (bignum->int bignum radix) (define (bignum->int-iter rest acc mult) (if (null? rest) (* acc (sign (car bignum))) (bignum->int-iter (cdr rest) (+ acc (* (car rest) mult)) (* mult radix)))) (bignum->int-iter (cdr bignum) 0 1)) (define (bignum-abs bignum) (cons (abs (car bignum)) (cdr bignum))) (define (bignum-negate bignum) (cons (* (car bignum) -1) (cdr bignum))) (define (bignum-positive? bignum) (positive? (car bignum))) (define (bignum-negative? bignum) (negative? (car bignum))) (define (bignum-even? bignum) (even? (car (reverse (cdr bignum))))) (define (bignum-odd? bignum) (odd? (car (reverse (cdr bignum))))) (define (bignum-compare bignum1 bignum2) (cond ((and (null? bignum1) (null? bignum2)) 0) ((> (car bignum1) (car bignum2)) 1) ((< (car bignum1) (car bignum2)) -1) (else (bignum-compare (reverse (cdr bignum1)) (reverse (cdr bignum2))))))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:
(define (big-compare big1 big2) ; big1 < big2 => -1 ; big1 = big2 => 0 ; big1 > big2 => 1 (define (sign x) (if (negative? x) -1 (if (positive? x) 1 0))) (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)) (* (sign (car big1)) -1)) ((< (car b2) (car b1)) (* (sign (car big1)) 1)) (else (loop (cdr b1) (cdr b2))))))))