How do you do computations on numbers with unlimited numbers of bits?

Question

In C, you can perform a simple:

int a = b + c;

Now, if a is larger than 2^32 (or maybe it's 2^31+1), you'd change the code to:

long a = b + c;

or

unsigned long a = b + c;

But how would you implement addition like:

bigint a = b + c;

where bigint is some sort of class/typedef/structure for storing and computing large integers (numbers that are hundreds of digits long). If you were just trying to add numbers together using a standard, hand-written decimal approach from elementary school, you can do infinitely long numbers in the equation. But come around to Computer Science, how can you use a binary, efficient approach where you can do infinitely long computations (provided enough RAM is available)

More so, is there a way of doing this that isn't terribly slow?

"How do you do computations on numbers with unlimited numbers of bits?" - hardly. — , Jun 28 '13 at 21:57
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries — Barmar, Jun 28 '13 at 21:57
google "arbitrary precision c++", you'll find [this question](http://stackoverflow.com/questions/4486882/whats-the-best-for-speed-arbitrary-precision-library-for-c) — tay10r, Jun 28 '13 at 21:57
Like @H2CO3 says, there are limits, given a finite universe. — Martin James, Jun 29 '13 at 00:06

score 0 · Answer 1 · answered Jun 28 '13 at 21:59

0

You can use a bigint library, or if you really feel ambitious, you can create a dynamic array to store your integers.

answered Jun 28 '13 at 21:59

jh314

27,144
16
62
82

score 0 · Answer 2 · answered Jun 28 '13 at 21:59

There are very fast ways to do this (tough still slower than math in CPU registers, mind you). Libraries for this already exist, but if you are interested in the implementation details I would suggest inspecting the source code of GMP (http://gmplib.org/), as well as reading (and doing the exercises in) Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms.

score 0 · Answer 3 · answered Jun 28 '13 at 22:03

"More so, is there a way of doing this that isn't terribly slow?"

Compared to fixed length, 16, 32, 64 and in some machines, 128-bit, it will ALL be quite slow, because the math has to be done in small steps. Addition and subtraction isn't too bad, just one or two clock-cycles per unit in the array (32 or 64 bit depending on architecture), but multiplication and division does get quite slow. As numbers get significantly large (more than a few thousand digits or so), you also run into problems of cache-misses, which slows the calculation.

But you can certainly get a bit better than storing digits in a ascii string.

How do you do computations on numbers with unlimited numbers of bits?

3 Answers3