Big Numbers, Common Algorithms?

Question

I was wondering what big numbers are, and what are some common algorithms used to handle them. I heard this term mentioned in Coders at Work, where one was asked in an interview to create a library to work with big numbers.

Answer 1

Big numbers are usually full-precision integers or decimals, as opposed to floating point numbers (which can also store very large numbers, but with a very limited precision). They are mostly used in cryptography. Take for example RSA keys: Those are integers with 1024 or 2048 bits (roughly 300 or 600 decimal digits). They need to be long to make it unfeasible to break the encryption using brute-force calculations.

What a library needs to provide is support to store these numbers and perform calculations on them (e.g. addition, multiplication, integer division with rest)

Answer 2

These are numbers with variable bit-length, unlike numbers with predefined size (e.g. 4-bit integer type).

An example of a fast C++ library working with big numbers is NTL, also used especially for number theory and cryptography application. Another well-known tool is the unix bc calculator that by default works with unlimited precision. Some functional languages like Haskell use this type of numbers as well.

Example of approaches used for dealing with large number arithmetics is Karatsuba algorithm used for multiplication. In the docs of NTL you can find much more if you're interested ;)

Answer 3

There are bignum libraries like gmp - some provide arbitrary precision (...as much as your memory can handle), some have simply ridiculous limits - floating point variables of 256 bytes base, 256 bytes mantissa.

The methods are very similar to normal software emulation of FPU, simply iterating over way more bytes of data for each calculation, operations resembling how you calculate it on paper. If you have 256-byte integer, it can be treated as a normal 256 base256 digits number...

simple 256-byte integer addition (totally unoptimized... the numbers should keep lengths etc)

unsigned char x[256];
unsigned char y[256];
unsigned char sum[256];
int overflow=0,tmp;
for(unsigned char i=0;i<256;i++)
{
  tmp = x[i] + y[i] + ovr;
  sum[i] = tmp % 256;
  overflow = tmp / 256;
}