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.

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

%d bloggers like this: