How do I process enormous numbers?

Question

Suppose I needed to calculate 2^150000. Obviously that number is going to exceed the size of an int, float, or double. How can I make a data type that allows normal math functions but exceeds the basic number types?

If this is a "depends which language you use" kind of deal. I will say C#.

Answer 1

See

http://stackoverflow.com/questions/26094/most-efficient-implementation-of-a-large-number-class

for some leads.

Answer 2

Several languages have built in support for arbitrary large numbers. You could use Mathematica, for example. I tried your example in Mathematica, and the result has 45,155 digits. I tried the same example with bc on a Unix machine. bc supports extended precision, but not that extended; it bombed on the example.

Answer 3

I don't know C# but I do know the Ruby programming language has the BigDemical class that seems to allow numbers of unlimited size.

Answer 4

If C# is not cast in stone, and you want something that just works out of the box, then there are several options. The one I know best is Python, but I think that languages like Scheme and Ruby support large numbers, too.

Python: 2**150000. Prints the result after about 1 second.

If you want free mathematics software, look at Maxima or Sage.

Answer 5

Lisp is your friend. Default biginteger numbers.

Answer 6

I find it very frustrating to use a language without arbitrarily large numbers: it seems nonsensical to be able to use ordinary operators like addition on most numbers, but to have to switch to method calls on a BigInt instance simply because of its size.

A whole bunch of languages have more complete numeric towers, and seamlessly coerce when needed; e.g., Allegro Common Lisp evaluates and prints all 45,155 digits of (expt 2 150000) in 1ms.

cl-user(2): (time (expt 2 150000))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  1 msec
; space allocation:
;  2 cons cells, 18,784 other bytes, 0 static bytes

Answer 7

There is a product in C called calc which is an arbitrary precision calculator. I used it once when working as a researcher and found it fairly straightforward to use...

http://sourceforge.net/projects/calc/

It can be programmed for difficult or long calculations and can accept arguments from the command line. In interactive mode, it accepts one command at a time, and displays the answer.

Ordinarily the commands are simply expressions such as:

    3 * (4 + 1)

and calc will print:

    15

Calc does the arithmetic operators +, -, /, * as well as ^ (exponentiation), % (modulus) and // (integer divide).

For example:

    3 * 19 ^ 43 - 1

will produce:

    29075426613099201338473141505176993450849249622191102976

Calc values can be VERY large. For example:

    2 ^ 23209 - 1

will print:

    402874115778988778181873329071 ... loads of digits ... 3779264511

Hope this helps...

Answer 8

Python has a bignum library. If you need to implement a bignum library in another language you can at least use the Python one as reference for validating your work. Note that bignums have a few implementation gotchas that aren't immediately obvious if you don't know what you're looking for.

Answer 9

You might also consider using Frink, which is a language with the native capability of dealing with measurement units. It computes 2^150000 without difficulty, deals with fractions (e.g. 1/3+2/5 --> 11/15), computes 3 meters + 2 inch --> 3.0508 m and is a full programming language.

Frink - Copyright 2000-2008 Alan Eliasen, [email protected] http://futureboy.us/frinkdocs/