Big Numbers: Getting Started
May 24, 2011
Over the next few exercises we’ll be developing a library of functions that provide arithmetic on big numbers: integers that are too large to fit into a machine word. Most languages, including Scheme, provide big numbers, either natively or through a standard library, so you are unlikely to need a library for big numbers. On the other hand, coding big numbers is fun, and makes a good exercise. We’ll get started today by defining a representation for big numbers and writing a few small functions.
The first decision to make when writing a big number library is to choose the radix in which numbers are represented. With binary computers, it is most economical to make the radix the largest convenient power of two; for a 32-bit CPU, the preferred radix is 216, which means that single-place multiplication plus a carry never overflows a machine word. During development, we choose a radix of 1000 (“millenial digits”), which are convenient for debugging since the numbers are easily read by human eyes, but we’ll be careful not to rely on the radix, so that it is easy to switch to a larger radix when development is finished.
The second decision is how to represent numbers. A number is, of course, represented as a polynomial in the base of the radix, with the digits stored separately. We use a list, rather than an array, since lists are more natural in Scheme, and since lists don’t impose any additional limits on the size of the numbers. The exact representation we choose is called the signed magnitude representation, where the head of the list gives the number of digits in the list, as well as the sign of the number, and the tail of the list gives the digits themselves, least-significant digit first, always stored as a positive number. Thus, the number 12345678 is stored in our representation as the list (3 678 345 12) and the number -87654321 is stored as (-3 321 654 87), 1 is (1 1), -1 is (-1 1), and zero is (0). Among other things, this representation makes it easy to compare numbers: first compare the signed magnitude, and only compare the numbers digit-by-digit if the signed magnitudes are the same.
In today’s exercise we will implement the following procedures: functions to convert between big numbers and the native numbers of the underlying language, functions to take the absolute value of a big number and to negate a big number, predicates to identify positive, negative or zero big numbers and even or odd big numbers, and functions to compare two big numbers.
Your task is to implement those big number functions described using a signed-magnitude representation; we’ll write functions to do arithmetic on big numbers in future exercises. When you are finished, you are welcome to read or run a suggested solution, or to discuss the exercise or post your own solution in the comments below.
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))))))))