Canon : A Library for Handling Psychedelically Large Numbers in Haskell

Speaker: Fred Schneider

Abstract:

Originally presented in 2015, version 0.1.1.x has been greatly expanded to natively handle hyperoperations allowing one to do algebra with quantities like the infamous Graham's number.

Conceptually, this library has two pieces. It represent numbers in a factored form and can handle extremely large numbers (like googolplex = 10 ^ 10 ^ 100). Internally, certain operations are extremely efficient (e.g. multiplication) whereas others (addition) require heavy lifting internally.

The second piece deals with hyperoperations and the integral "hyperexpressions" making use of them.

Some background: Hyperoperation levels 1-3 are the commonplace: addition, multiplication and exponentiation.
Level 4 is power towers or tetration. For instance, 3 'tetrated' 4 is 3 ^ (3 ^ (3 ^ 3)) = 3 ^ 7625597484987
Level 5 is pentation. For example, 3 'pentated' 3 can be shown to equal 3 'tetrated' 27, a massive, massive number.

Imagine 3 'pentated' googol. This library allows you to do algebra with these expressions.

Levels 5 (pentation) through 50 are supported with operators. Arbitrary hyperoperation levels are supported allowing one to
work with numbers on the order of Graham's number.

Efficient math with such numbers presents myriad challenges and design considerations. The talk will do a deep dive.