ANN: A Scala package for tree-based unbounded natural and rational number arithmetic

[Paul Tarau]

I have placed at the Google code repository

http://code.google.com/p/giant-numbers/

a Scala package using a tree-based number representation that can host gigantic numbers (e.g. instance "towers of exponents" and sparse combinations of them) in a compressed form, while being able to perform efficiently arithmetic operations on them.

It provides an unusually compact representation for very large Mersenne and Fermat numbers as well as numbers derived from them like the "perfect numbers".
 
For instance, the largest known prime number (at the end of year 2012), the Mersenne prime

2^43112609 − 1

is represented as a small tree, in contrast with the millions of digits needed by its conventional representation.

The package contains:

- arithmetic operations on arbitrary size natural numbers (including also things like
  a prime generator, Miller-Rabin and Lucas-Lehmer primality tests)

- arithmetic operations on arbitrary size rational numbers

Rational numbers are stored at their information theoretical minimum via their Calkin-Wilf bijection to natural numbers.

Enjoy,

Paul Tarau