Spigot Algorithm and Root Computing

The word spigot indicates that the "digits" (generally in a widened meaning) of the result number are extracted successively from left to right (as if pumped through a spigot) by using only integer arithmetic, as opposed to the iterative approach, where the result number as the whole is improved after each iteration step by using (high-precision) floating-point arithmetic. The approach of spigot computing as used in papers by S. Kamal Abdaly (Comm. ACM 13(1970)), S. Rabinowitz and S. Wagon (American Mathematical Monthly 102(3) (1995)), A. H. J. Sale (Comput. J. 11(1968)) is now systematized and correctness is formally proved; the way for achieving an arbitrary accuracy is shown.Then a method for computing roots of arbitrary rational numbers is developed. If a root is not rational, spigot approach is used to compute its decimal approximation with an arbitrary given accuracy; if the root is rational, its numerator and denominator are computed exactly. This method for root computing is absolutely reliable: it is both formally proved and tested by numerical examples.     

Spigot Algorithm and Reliable Computation of Natural Logarithm

The spigot approach used in the previous paper (Reliable Computing 7 (3) (2001), pp. 247–273) for root computation is now applied to natural logarithms. The logarithm ln Q with Q , Q > 1 is decomposed into a sum of two addends k ₁× ln Q ₁+k ₂× ln Q ₂ with k ₁, k ₂ , then each of them is computed by the spigot algorithm and summation is carried out using integer arithmetic. The whole procedure is not literally a spigot algorithm, but advantages are the same: only integer arithmetic is needed whereas arbitrary accuracy is achieved and absolute reliability is guaranteed. The concrete procedure based on the decomposition with p, q ( – {0}), p < q is simple and ready for implementation. In addition to the mentioned paper, means for determining an upper bound for the biggest integer occurring in the process of spigot computing are now provided, which is essential for the reliability of machine computation.