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.