#
Bignum

An infinite-precision calculator and function library for Miranda

## Avoiding bottoming out

Bignum calculator's main drawback is that calculations can "bottom out"
which means that the calculation goes on forever without producing a
result, or blocks halfway through.
This happens when a calculation involving infinitely-long figures turns out
to give a finite-length result. Simple examples are subtracting an infinitely
long number from itself:
bn_e $bn_sub bn_e

("`a $bn_sub b`" is the infix version of the regular syntax
"`bn_sub a b`") or the classic "sum of three thirds":
bn_times 3 (bn_quot bn_1 3)

because the carry lookahead mechanism has to inspect an infinite list of
zeroes to know that the result really is zero, or an infinite list of
nines wondering whether there is going to be a carry into it or not.
For a more insidious example of this (and a way of avoiding it),
suppose you wanted to check the correctness of Dudeney's solution to the
problem of finding two rational numbers, other than 1 and 2, whose cubes
add up to 9.

(pn/pd)^3 + (qn/qd)^3 = 9

Dudeney's solution is
415280564497 676702467503
------------ and ------------
348671682660 348671682660

This appeared in his first book, "The Canterbury Puzzles" in 1907, and
its denominator is shorter than any other previously published solution.
As Martin Gardner observes, he did this without the aid of a modern
calculating machine, which makes his achievement almost a miracle!
A naive but useless attempt to verify this would be (as a Miranda script):

%include "bignum"
bn_pn = bn "415280564497"
bn_qn = bn "676702467503"
bn_d = bn "348671682660"
bn_dud = (bn_raise (bn_pn $bn_div bn_d) 3) $bn_add (bn_raise (bn_qn $bn_div bn_d) 3)

but the sum of two infinite-length bignums giving an finite-length result never
terminates. It just goes looking forever down an infinite list that starts out
8.99999999999999999999999... for a carry that would resolve its doubts about the
first digit.
You can make it work, however, by rearranging the formula

(pn/pd)^3 + (qn/qd)^3 = 9

as
(pn^3 + qn^3) / d^3 = 9

As a Miranda script:
%include "bignum"
bn_pn3 = bn_raise (bn "415280564497") 3
bn_qn3 = bn_raise (bn "676702467503") 3
bn_d3 = bn_raise (bn "348671682660") 3
dudeney = bn_div (bn_add bn_pn3 bn_qn3) bn_d3

which does indeed give 9.
(Though, to be fair, you don't have to use the bignum package to perform this
calculation. Miranda's native integers are infinitely precise, so you can use
the rearranged formula to get the top and bottom of the division as integers,
then check that the integer division is 9 and that the remainder is zero).

Martin Guy <martinwguy@gmail.com>, Catania, March 2004.