There's an elegant method for calculating certain transcendental numbers (like π, e) called a spigot algorithm; "spigot" as in a tap or valve controlling the flow of a liquid (or perhaps a gas?); such an algorithm for calculating the digits of e appeared in a paper by Sale in 1968 [1].
Spigot algorithms work with 'nice small integers' and start producing digits (of π in our case) right from the start [2,3], and so seems a good basis for the Transcendental Logic Circuit...
The following algorithm - which will form the heart of the Transcendental Logic Circuit - is a modification of the C spigot program given by Arndt and Haenel [2, p. 83], the aim being to make the thing work with integers that use 15 or fewer bits, producing (at least) 256 digits of π. The colour coding indicates the required size for each variable:
grey 2 bits
violet 4 bits
green 6 bits
blue 10 bits
orange 11 bits
brown 14 bits
red 15 bits
This level of bit-fastidiousness is not unimportant - unnecessary bits can have dramatic effects on the complexity of the hardware!
[1] A. H. J. Sale, The calculation of e to many significant digits, Comput. J. 11 (1968), pp. 229–230.
[2] Jörg Arndt, Christoph Haenel, Pi - Unleashed, Springer-Verlag Berlin, 2nd. ed., 2001, chap. 6.
[3] Stanley Rabinowitz and Stan Wagon, A Spigot Algorithm for the Digits of π, Am. Math. Monthly., Vol. 102, No. 3 (Mar., 1995), pp. 195-203.
No comments:
Post a Comment