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.

About these ads

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

  2. 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  -> 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:
    	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
    
  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 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))))))
    
  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))))))))
    

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 643 other followers

%d bloggers like this: