## 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

### 7 Responses to “Big Numbers: Getting Started”

1. […] 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. […]

```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  -> c
```
3. Mike said

A 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:

self.rep = [1 if value > 0 else -1 if value < 0 else 0]
value = value if value >= 0 else -value

while value:
self.rep.append(rem)
self.rep *= len(self.rep) - 1

def __abs__(self):
ret = BigNum()
ret.rep = self.rep[:]
if ret.rep < 0:
ret.rep = -ret.rep
return ret

def __neg__(self):
ret = BigNum()
ret.rep = self.rep[:]
ret.rep = -ret.rep
return ret

def __lt__(self, other):
if self.rep < other.rep:
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

def is_zero(self):
return self.rep == 0

def is_positive(self):
return self.rep > 0

def is_even(self):
return self.is_zero or not (self.rep & 1)

def is_odd(self):
return not self.is_zero() and (self.rep & 1)

def to_int(self):
value = 0
for part in reversed(self.rep[1:]):
value = self.radix * value + part
return value
```
4. Axio said

``` ;; 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)))))) ```

5. brdassign said
```(define (sign num)
(cond ((positive? num) 1)
((negative? num) -1)
(else 0)))

(define (int->bignum-iter rest acc)
(if (zero? rest)
(cons (* (length acc) (sign num))
(reverse acc))
(int->bignum-iter
(int->bignum-iter num '()))

(define (bignum->int-iter rest acc mult)
(if (null? rest)
(* acc (sign (car bignum)))
(bignum->int-iter
(cdr rest)
(+ acc (* (car rest) mult))
(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))))))
```
6. DAY said

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

7. programmingpraxis said

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))))))))
```