BigNum

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

BigNum, also commonly referred to BigInt or BigInteger, allows the use of very large numbers -- greater than the primitives allow in a basic programming language.

Versions of BigNum can be found, such as GMP for C, and Java comes with its own version of BigInteger.


Implementation[edit]

There are many similarities between working with BigNums and polynomials. This is because any integer a_{n}a_{{n-1}}\ldots a_{1}a_{0} in base B can be viewed as the polynomial a_{n}x^{n}+a_{{n-1}}x^{{n-1}}+\ldots +a_{1}x+a_{0}, evaluated at B. The following will start with base-10 examples for simplicity, followed by binary examples.

Addition and Subtraction[edit]

A "grade school" algorithm used to determine the sum or difference of two numbers. There are two algorithms:

Addition[edit]

Addition is the simple sum of two numbers. It is used when you want to use normal addition on two numbers of the same sign, or normal subtraction on two numbers with opposite signs. Use the "grade school" algorithm of lining the digits up, and adding them one by one, with a carry:

                  1         1         0
  1 2 3 4     1 2 3 4     1 2 3 4     1 2 3 4     1 2 3 4
+ 4 5 6 8   + 4 5 6 8   + 4 5 6 8   + 4 5 6 8   + 4 5 6 8
---------   ---------   ---------   ---------   ---------
                    2         0 2       8 0 2     5 8 0 2

The final sign will simply be what the like sign was to begin with.

Subtraction[edit]

Subtraction obtains the difference between two numbers. It is performed if you want to use normal addition on two numbers with opposite signs, or normal subtraction with two number of the same sign.

The subtraction algorithm is another "grade school" algorithm of lining the digits up, and subtract them one by one, borrowing when needed:

                  6       5   6       5   6
  6 3 7 5     6 3  15      13  15      13  15
- 1 7 2 6   - 1 7 2 6   - 1 7 2 6   - 1 7 2 6
---------   ---------   ---------   ---------
                  4 9       6 4 9     4 6 4 9

The final sign will match on which number is bigger.

For Base-10 subtraction to work, the larger number appears above the smaller number.

Binary addition[edit]

As with base-10, addition is performed from the least significant digit. The same applies with subtraction.

On fixed-width numbers, addition works on the same principles, and subtraction can be converted into addition simply by inverting each bit. There is no need to worry about negative numbers, unless they are tracked by an independant sign bit.

For variable-width numbers, you will need to make sure the number are being added correctly.

When you are dealing with addition segments that are equal to the bit-length of data registers, most programming languages may discard the carry bit. To recover it, check that the highest bits of your first two numers are set, and the hightest bit of the sum is not. (You will have to adjust if you are also using the carry flag in the addition.)


Binary subtraction[edit]

On fixed-width numbers, the procedure does not differ from regular addition.

Multiplication[edit]

The simple algorithm for multiplication is to shift, multiply, and add. This takes O(n^{2}) time.

  1 9 4     1 9 4     1 9 4       1 9 4
x 5 2 6   x 5 2 6   x 5 2 6     x 5 2 6
-------   -------   -------     -------
          1 1 6 4   1 1 6 4     1 1 6 4
                    3 8 8       3 8 8
                              9 7 0
                            -----------
                            1 0 2 0 4 4      

Multiplication of BigNums can also be done faster in O(n(\log n)^{{2+\epsilon }}), with Fast Fourier Transform, or, with relative ease, the Karatsuba Multiplication, which is O(n^{{log3}}), depending on the constants and method chosen.

Binary multiplication[edit]

For fixed width numbers, no special handling is required for signed or unsigned numbers.

Division[edit]

            1 8 8
      ___________
2 7 8 ) 5 2 3 8 0
       -2 7 8
        ------
        2 4 5 8
       -2 2 2 4
        -------
          2 3 4 0
         -2 2 2 4
         --------
            1 1 6

When you complete the division, there are two important numbers. The quotient on top is the result, while the remainder at the bottom becomes the modulus.

Binary division[edit]

BigNum in Programming Languages[edit]

Each of the following examples prints the result of 314159265358979 * 271828182845904 (which is 85397342226735418150399772016), followed by a newline.

C[edit]

#include <stdio.h>
#include <gmp.h>
/* make sure to invoke gcc with -lgmp */
int main()
{
  mpz_t a, b, r;
  mpz_init(a);
  mpz_init(b);
  mpz_init(r);
  mpz_set_str(a, "314159265358979", 10); /* the 10 represents the radix */
  mpz_set_str(b, "271828182845904", 10); /* gmp can do 2 to 36 */
  mpz_mul(r, a, b);
  mpz_out_str(stdout, 10, r);
  putchar('\n');
  return 0;
}

Factor[edit]

314159265358979 271828182845904 * .

Haskell[edit]

main = print (314159265358979 * 271828182845904)

Java[edit]

import java.math.BigInteger;
public class BigIntExample {
  public static void main(String[] args) {
    BigInteger a = new BigInteger("314159265358979");
    BigInteger b = new BigInteger("271828182845904");
    System.out.println(a.multiply(b));
  }
}

Perl[edit]

#!/usr/bin/perl
use bignum;
print 314159265358979 * 271828182845904, "\n";

PHP[edit]

<?php
echo bcmul('314159265358979', '271828182845904'), "\n";

Python 3+[edit]

print(314159265358979 * 271828182845904)

Rexx[edit]

numeric digits 40 /* Precision to 40 digits */
say 314159265358979 * 271828182845904

Ruby[edit]

puts 314159265358979 * 271828182845904

Scheme[edit]

(display (* 314159265358979 271828182845904))

Smalltalk[edit]

Transcript show: 314159265358979 * 271828182845904