Community hub
0 subscribers7 pages, 0 posts
Recent from talks
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Spigot algorithm.
Nothing was collected or created yet.
Spigot algorithm
View on Wikipediafrom Wikipedia
A spigot algorithm is an algorithm for computing the value of a transcendental number (such as π or e) that generates the digits of the number sequentially from left to right providing increasing precision as the algorithm proceeds. Spigot algorithms also aim to minimize the amount of intermediate storage required. The name comes from the sense of the word "spigot" for a tap or valve controlling the flow of a liquid. Spigot algorithms can be contrasted with algorithms that store and process complete numbers to produce successively more accurate approximations to the desired transcendental.
Interest in spigot algorithms was spurred in the early days of computational mathematics by extreme constraints on memory, and such an algorithm for calculating the digits of e appeared in a paper by Sale in 1968.[1] In 1970, Abdali presented a more general algorithm to compute the sums of series in which the ratios of successive terms can be expressed as quotients of integer functions of term positions. This algorithm is applicable to many familiar series for trigonometric functions, logarithms, and transcendental numbers because these series satisfy the above condition.[2] The name "spigot algorithm" seems to have been coined by Stanley Rabinowitz and Stan Wagon, whose algorithm for calculating the digits of π is sometimes referred to as "the spigot algorithm for π".[3]
The spigot algorithm of Rabinowitz and Wagon is bounded, in the sense that the number of terms of the infinite series that will be processed must be specified in advance. The term "streaming algorithm"[4] indicates an approach without this restriction. This allows the calculation to run indefinitely varying the amount of intermediate storage as the calculation progresses.
A variant of the spigot approach uses an algorithm which can be used to compute a single arbitrary digit of the transcendental without computing the preceding digits: an example is the Bailey–Borwein–Plouffe formula, a digit extraction algorithm for π which produces base 16 digits. The inevitable truncation of the underlying infinite series of the algorithm means that the accuracy of the result may be limited by the number of terms calculated.
Example
[edit]This example illustrates the working of a spigot algorithm by calculating the binary digits of the natural logarithm of 2 (sequence A068426 in the OEIS) using the identity
To start calculating binary digits from, as an example, the 8th place we multiply this identity by 27 (since 7 = 8 − 1):
We then divide the infinite sum into a "head", in which the exponents of 2 are greater than or equal to zero, and a "tail", in which the exponents of 2 are negative:
We are only interested in the fractional part of this value, so we can replace each of the summands in the "head" by
Calculating each of these terms and adding them to a running total where we again only keep the fractional part, we have:
k A = 27−k B = A mod k C = B/k Sum of C mod 1 1 64 0 0 0 2 32 0 0 0 3 16 1 1/3 1/3 4 8 0 0 1/3 5 4 4 4/5 2/15 6 2 2 1/3 7/15 7 1 1 1/7 64/105
We add a few terms in the "tail", noting that the error introduced by truncating the sum is less than the final term:
k D = 1/k2k−7 Sum of D Maximum error 8 1/16 1/16 1/16 9 1/36 13/144 1/36 10 1/80 37/360 1/80
Adding the "head" and the first few terms of the "tail" together we get:
so the 8th to 11th binary digits in the binary expansion of ln(2) are 1, 0, 1, 1. Note that we have not calculated the values of the first seven binary digits – indeed, all information about them has been intentionally discarded by using modular arithmetic in the "head" sum.
The same approach can be used to calculate digits of the binary expansion of ln(2) starting from an arbitrary nth position. The number of terms in the "head" sum increases linearly with n, but the complexity of each term only increases with the logarithm of n if an efficient method of modular exponentiation is used. The precision of calculations and intermediate results and the number of terms taken from the "tail" sum are all independent of n, and only depend on the number of binary digits that are being calculated – single precision arithmetic can be used to calculate around 12 binary digits, regardless of the starting position.
References
[edit]- ^ Sale, AHJ (1968). "The calculation of e to many significant digits". The Computer Journal. 11 (2): 229–230. doi:10.1093/comjnl/11.2.229.
- ^ Abdali, S Kamal (1970). "Special Series Summation with Arbitrary Precision" (PDF). Communications of the ACM. 13 (9): 570. doi:10.1145/362736.362756.
- ^ Rabinowitz, Stanley; Wagon, Stan (1995). "A Spigot Algorithm for the Digits of Pi" (PDF). American Mathematical Monthly. 102 (3): 195–203. doi:10.2307/2975006. JSTOR 2975006. Retrieved 8 May 2013.
- ^ Gibbons, Jeremy (24 May 2004). "Unbounded Spigot Algorithms for the Digits of Pi" (PDF).
Further reading
[edit]- Arndt, Jorg; Haenel, Christoph, π unleashed, Springer Verlag, 2000.
- Weisstein, Eric W. "Spigot algorithm". MathWorld.
Spigot algorithm
View on Grokipediafrom Grokipedia
The spigot algorithm is a computational method for generating the decimal digits of irrational numbers such as π sequentially from left to right, using only integer arithmetic and without relying on previously computed digits or floating-point operations.[1] Developed initially by mathematician Stanley Rabinowitz in 1991 as a concise Fortran program capable of producing 1,000 digits of π in under 10 seconds on contemporary hardware, the approach was formalized and named by Rabinowitz and Stan Wagon in their 1995 paper published in The American Mathematical Monthly.[2][3]
The algorithm is based on a representation of π in a mixed-radix system with denominators 1/3, 2/5, 3/7, and so on, where π is depicted as a "stream" of digits all equal to 2.[1] In practice, it operates on an array initialized with values of 2, iteratively multiplying elements by 10 (or higher powers for multiple digits), performing right-to-left reductions modulo these denominators while propagating carries to the left, and extracting the next digit from the tens place of the leading element after each cycle.[1] This process ensures that each digit is computed independently, making the method suitable for parallelization and efficient for targeted digit extraction, though it is bounded—requiring a predetermined number of series terms for a given precision.[1]
Notable for its simplicity and elegance, the spigot algorithm has inspired extensions to other constants like e and logarithms, as well as unbounded variants that avoid fixed precision limits, such as those proposed by Jeremy Gibbons in 1994.[4] Its implementation in languages like Pascal or C can compute thousands of digits using modest integer sizes—for instance, 5,000 digits with numbers under 600 million—highlighting its practicality for educational and computational demonstrations of π's digits.[1]
Overview
Definition
A spigot algorithm is a computational method designed to generate the decimal digits of certain irrational or transcendental numbers, such as π or e, sequentially from the most significant digit (left to right) while requiring only a bounded amount of memory. Unlike conventional approaches that compute an approximation of the entire number using high-precision floating-point arithmetic and then extract all digits at once, a spigot algorithm produces each digit independently and discards it immediately after output, ensuring that storage needs do not grow with the number of digits computed.[1] The term "spigot" evokes the image of a faucet or spigot that drips digits one by one without recirculating or retaining previously produced values, emphasizing the stream-like, memory-efficient nature of the process. This sequential generation relies on integer arithmetic operations on small arrays, avoiding the need for arbitrary-precision real-number computations that scale poorly for large digit counts. As described in the seminal work introducing the concept, such algorithms "pump out digits one at a time and do not use the digits after they are computed."[1] The concept was coined in 1995 by mathematicians Stanley Rabinowitz and Stan Wagon, who developed an algorithm for π based on series summation techniques, marking a significant advancement in digit-by-digit computation for mathematical constants.[1]Key Properties
Spigot algorithms are characterized by their efficient use of memory, requiring only a fixed-size array or a number of terms proportional to the desired output length, rather than storing the entire value of the constant being computed.[1] This low memory footprint arises from the algorithms' reliance on bounded integer arithmetic, avoiding the need for high-precision floating-point representations that scale with the total number of digits.[4] A defining feature is the sequential generation of digits, where each digit is produced in order—typically from left to right in the decimal expansion—without recomputing or retaining previously output digits.[1] This "one-way" output process enables streaming applications, as the algorithm discards intermediate results immediately after use.[4] Spigot algorithms exist in bounded and unbounded variants. Bounded versions require specifying the number of digits in advance and allocate resources accordingly, such as an array of length roughly proportional to the digit count.[1] In contrast, unbounded variants can generate digits indefinitely by dynamically managing state and memory, making them suitable for continuous computation without predefined limits.[4] These algorithms are generally applicable to computing digits in any base b, though they are most commonly implemented for base-10 decimal representations of constants like π.[4] The digit extraction often involves modular arithmetic to isolate individual digits from partial sums.[1] While spigot algorithms are not competitive in speed with high-performance series like the Chudnovsky algorithm for computing large numbers of digits—due to their quadratic scaling with the number of digits—they excel in simplicity and are ideal for educational demonstrations or real-time streaming of digits on resource-constrained systems.[4][1]History
Early Algorithms
The early development of spigot-like algorithms began with efforts to compute digits of mathematical constants using efficient series summation techniques, prior to the formal introduction of the term "spigot." In 1968, A. H. J. Sale published an algorithm specifically for calculating the digits of e based on its Taylor series expansion, ∑(1/n!) from n=0 to ∞.[5] Sale's method employed iterative computation of each series term modulo increasing powers of 10, allowing the extraction of individual decimal digits without requiring the full precision of the entire sum at each step.[5] Building on this foundation, S. K. Abdali introduced a more general approach in 1970 through ACM Algorithm 393, which extended series summation to arbitrary precision for a broader class of series. Abdali's contribution generalized the technique to series where term ratios are quotients of integer-valued functions, enabling sequential digit-by-digit evaluation in a specified base using only integer arithmetic, thus avoiding the need for high-precision floating-point operations throughout the computation. This allowed for the production of the integer part and fractional digits one at a time, with parameters specifying the number of places, terms, and base (e.g., base 100000 for five digits per word). Despite these advances, early algorithms like Sale's and Abdali's were primarily demonstrated on e and select transcendental functions such as sine, with applications limited to series summation and not yet extended broadly to constants like π.[5]Development of the Term
The spigot algorithm for π was initially developed by Stanley Rabinowitz in 1991, who presented an abstract to the American Mathematical Society featuring a concise 14-line Fortran program capable of computing 1,000 decimal digits of π using only integer arithmetic.[2] The term "spigot algorithm" was coined in 1995 by mathematicians Stanley Rabinowitz and Stan Wagon in their seminal paper titled "A Spigot Algorithm for the Digits of π," published in The American Mathematical Monthly, volume 102, issue 3, pages 195–203.[6] This work formalized the concept specifically in the context of computing the decimal digits of π using the Machin-like arctangent series, marking a key advancement in digit-by-digit calculation methods.[6] Building upon earlier ideas in series summation, such as those by A. H. J. Sale for e and S. K. Abdali for arbitrary precision, Rabinowitz and Wagon introduced their innovation: an adaptation that employs an array of remainders to extract individual decimal digits of π sequentially, without requiring the computation or storage of preceding digits.[6] This approach allows for the "dripping" of digits one at a time, akin to water from a spigot, enabling efficient generation of specific digits for educational or demonstrative purposes.[6] The publication in a prestigious journal like The American Mathematical Monthly significantly popularized spigot algorithms, inspiring numerous implementations in programming languages and computational mathematics education, with the paper garnering over 80 citations in scholarly literature. Additionally, the authors briefly outlined potential extensions of the technique to other mathematical constants, such as e, highlighting its broader applicability beyond π.[6]Mathematical Foundations
Series Summation Technique
Spigot algorithms fundamentally rely on infinite series expansions to generate successive decimal digits of mathematical constants, leveraging representations such as the Taylor series for or the Leibniz arctangent series for . These expansions provide the mathematical basis for digit computation, where the series is restructured—often into a mixed-radix representation—to facilitate sequential output in base 10 without requiring the full value of the constant upfront. For π, the series is reformulated as a continued fraction-like structure in mixed bases (e.g., 1/3, 2/5, 3/7, ...), allowing π to be viewed as an infinite stream of 2's in that radix.[4][1] The technique transforms the continuous summation into a discrete, position-specific process, ensuring each digit emerges from partial sums while propagating influences accurately. The core process entails incremental summation of series terms using an array to track remainders from each term's contribution, where any fractional remainders are carried forward via modular operations to influence the next position. This carry-over mechanism mimics long division but operates on the series terms collectively, allowing the algorithm to build the decimal expansion iteratively from left to right. The adaptation involves scaling the entire state by powers of the base (typically 10) and incorporating the series denominators (factorials for e, linear for arctangent) into iterative multiplications and reductions, enabling the extraction of base-10 digits through repeated division and remainder handling.[1] Precision control is integral, as the method confines high-precision operations to the array elements representing term contributions and positions rather than the entire sum, thereby sidestepping the need for uniform arbitrary-precision arithmetic across all computations. This localized approach ensures that dominant early terms are handled with minimal overhead, while later terms affect only trailing positions. The structure supports efficient integer-only arithmetic, transforming the power series into a form amenable to bounded calculations.[4] Among the advantages, this technique enables digit isolation that precludes floating-point overflow during preliminary summations, as all operations remain within integer bounds scaled to the required digit count. It facilitates scalable computation for increasing precision without recomputing prior digits wholesale, promoting reliability in high-digit scenarios. Such properties underpin the adaptation of series for various constants, including applications to .[1]Digit Extraction via Modular Arithmetic
In spigot algorithms, digit extraction relies on modular arithmetic to isolate individual decimal digits of a constant while maintaining the precision of subsequent computations through preserved remainders. The core operation involves computing a weighted sum of prior remainders multiplied by specific coefficients derived from the underlying series representation, followed by division by 10 to yield the next digit. This process uses the floor function to obtain the integer part (the digit) and the modulo operation to retain the fractional contribution as a new remainder, ensuring that no computational information is lost across iterations.[7] The algorithmic step proceeds iteratively for each digit position: given an array of remainders from the previous step and coefficients tailored to the constant's series, compute the sum . The digit is then extracted as , and the updated remainder is , which is distributed back into the array for the next position. This "dripping" mechanism simulates the sequential outflow of digits, akin to water from a spigot, where the integer part is output and the remainder carries forward the unresolved fractional value. For constants like π, the coefficients arise from adaptations of arctangent series, but the extraction step remains general across spigot implementations.[1][4] Array-based implementations maintain an array of length proportional to the desired number of digits (typically for digits), initialized with initial remainders or values from the series. At each iteration, the array elements are updated by multiplying by the corresponding coefficients, summing the results, and applying the floor division and modulo operations to propagate carries and remainders rightward or leftward as needed. This structure allows efficient in-place updates using only integer arithmetic, avoiding floating-point precision issues. The mathematical basis guarantees no information loss because the modulo operation preserves the exact fractional part modulo 10, equivalent to shifting the decimal point without discarding data, thus bounding the error to less than after digits.[7][4] To illustrate the general extraction formula more formally, consider the computation at step : Here, are the remainders in the array before the -th iteration, and the new remainder is used to update the array for the next digit. This formulation ensures the algorithm's exactness, as each step refines the approximation without cumulative rounding errors.[4]Algorithms for π
Rabinowitz-Wagon Algorithm
The Rabinowitz-Wagon algorithm, developed by Stanley Rabinowitz and Stan Wagon, is a seminal spigot algorithm specifically designed for generating the decimal digits of π sequentially using only integer arithmetic. It derives from the series π = ∑_{k=0}^∞ [(k!)^2 / (2^{k+1} (2k+1)! )], reformulated into a mixed-radix representation where π is the "stream" 2.2222... in bases given by the denominators 1/3, 2/5, 3/7, and so on.[8][1] This allows efficient digit-by-digit extraction without floating-point operations or recomputation of prior digits, making it effective for producing thousands of digits on modest hardware. To prepare for computing n decimal digits of π, the algorithm initializes an array a of length ⌊10n / 3⌋ + 1, with all elements set to 2. This setup represents the initial value in the scaled mixed-radix system, with the length providing buffer for carries and sufficient precision to avoid truncation errors. The choice of length scales linearly with n due to the base-10 output, and operations remain within bounded integers (e.g., under 10^9 for moderate n).[8] The core computation proceeds in a loop for each digit position from 1 to n. Within each iteration:- Multiply every element a by 10 to advance to the next decimal place.
- Propagate carries from right to left: for i from length-1 down to 1, let d = 2i - 1; set q = a // d, r = a % d; set a = r and add q × (i - 1) to a[i-1]. This reduces each position modulo its radix denominator while carrying over the quotient scaled by the previous radix coefficient.
Step-by-Step Computation Process
The Rabinowitz-Wagon algorithm computes digits of π by maintaining an array representing the value in a mixed-radix system derived from the series ∑_{k=0}^∞ [(k!)^2 / (2^{k+1} (2k+1)! )], allowing sequential digit extraction through integer operations. To compute the first 4 decimal digits (yielding π ≈ 3.1415), a sufficient array length is len = ⌊40 / 3⌋ + 1 = 14, with the array initialized as a[0 to 13] = 2. This initialization captures the leading "2.222..." in radices 1/3, 2/5, ..., 26/55. The process incorporates the representation by multiplying by 10, extracting the next digit from the low end via predigits, and updating remainders to preserve the value modulo the radices. The full algorithm details are in the Rabinowitz-Wagon paper.[1] In iteration 1, multiply all a by 10 to get (20, 20, ..., 20). Then reduce from i=13 to 1: for each, q = a // (2i-1), r = a % (2i-1), a = r, a[i-1] += q × (i-1). After reductions, compute predigit p from a // 10, queue it, and output the released digit 1 (first decimal). Update remainders for next iteration. For iteration 2, repeat: multiply by 10, reduce right-to-left, extract predigit yielding digit 4 (second decimal), with possible carries in low indices. The process continues for iterations 3 and 4, yielding digits 1 and 5, with predigit adjustments propagating carries if p ≥ 10 (reset to 0, carry 1 to prior, turning 9s to 0s). For the first 4 digits with len=14, no major propagation affects output due to sufficient precision. The final predigit setup incorporates the integer part '3' before the decimal point. These steps demonstrate the algorithm's use of integer arithmetic to avoid precision issues, keeping values bounded by radix sizes.[1]Algorithms for Other Constants
For e
The spigot algorithm for the mathematical constant adapts the Taylor series expansion into a form that enables sequential digit extraction through modular arithmetic on factorial denominators. This representation leverages a mixed-radix system where the bases correspond to successive factorials, allowing the fractional part of to be expressed as a sequence of digits (primarily 1s after the integer part) that can be converted to base 10 without recomputing prior digits. The approach ensures that only integer operations are needed, making it efficient for high-precision computation on early computers. A. H. J. Sale introduced this method in 1968, initializing an array of length sufficient for the desired precision (on the order of entries to bound truncation error, though practical implementations often use slightly longer arrays for safety) with values representing the series terms: the first entry as 2 (for the integer part) followed by 1s for the subsequent coefficients. For each new decimal digit, the algorithm proceeds from the rightmost array entry to the left, multiplying each entry by 10 and reducing it modulo the appropriate factorial-related denominator (specifically, modulo for the -th position, simulating the scaling). Any quotient from the reduction is carried over as an addition to the next leftward entry, propagating adjustments across the array. This process extracts the next digit as the final carry or quotient at the left end, while updating remainders for the following iteration.[1] Applying the algorithm yields the initial digits of as 2.71828..., confirming its accuracy; for instance, computing the first five decimal places requires an array of about 10-15 entries, with each digit step involving operations across the array, highlighting the method's scalability for the era's hardware limitations while avoiding full series resummation.[1]For Square Roots and Logarithms
Spigot algorithms have been extended to compute square roots of integers, such as √2 or more generally √n, by adapting digit-recurrence techniques to produce digits sequentially without requiring the full precision of prior digits. A notable 2023 extension formalizes this approach using a nested binomial-like expansion for the square, where the square root is represented as a decimal expansion whose square matches n modulo increasing powers of 100, enabling digit-by-digit extraction through iterative subtractions. This method draws from historical digit-by-digit square root algorithms but aligns with spigot principles by localizing computations to extract one or two digits at a time via modular arithmetic.[9] The core algorithm for √n proceeds by pairing decimal digits (processing two at a time for efficiency, equivalent to working modulo 100) and maintaining a current pair ⟨P, Q⟩, initialized for example as ⟨5n, 5⟩ for the integer part. Iterative refinement uses two rules: if P ≥ Q, apply Rule A by setting the next pair to ⟨P - Q, Q + 10⟩ and increment a digit counter; if P < Q, apply Rule B by setting ⟨100P, 10Q - 45⟩ without incrementing. The number of Rule A applications between Rule B steps yields the next pair of digits, effectively solving quadratic congruences like finding d such that (20D + d)^2 ≡ remainder mod 100, where D is the accumulated root so far, through repeated subtractions rather than direct solving. This process uses only additions and subtractions, making it suitable for manual or abacus computation, and converges to arbitrary precision by continuing the pairing. For √3, starting with ⟨15, 5⟩, the sequence produces pairs leading to digits 1 (integer), then 73, 20, 50, approximating 1.73205 after four pairs.[9] For logarithms, spigot algorithms adapt series summation techniques to extract decimal digits of constants like ln(2), leveraging the Mercator series in a form that avoids floating-point issues through integer arithmetic. The efficient series for ln(2) is given by which is evaluated in Horner form to facilitate modular digit extraction: Digits are computed by maintaining an accumulator in a mixed-radix representation, where each term 1/(n · 2^n) contributes to the sum modulo 10^d for d digits, scaled by a factor f = 10^{number of digits}. The extraction involves binary-to-decimal conversion through cumulative modular sums, with the nth digit obtained as (accumulator / f) mod 10, followed by carry propagation to handle overflows. This approach ensures reliable computation by bounding the summation terms and using exact fractions.[10] A key challenge in spigot algorithms for logarithms, including ln(2), arises from the non-power-of-ten base in the series denominators (e.g., involving factorials or linear n), requiring careful handling of divisions and scalings to maintain the spigot property of independent digit computation; unlike π or e, where powers align naturally with modular bases, logarithms demand decomposition into integer parts and fractional adjustments, such as expressing ln(Q) = k · ln(2) + ln(1 + p/q) for rational Q to isolate contributions. Alternating signs, as in slower-converging series like ∑ (-1)^{k+1} /(k · 2^k), further complicate modular summation by necessitating signed accumulators, though the non-alternating form mitigates this for efficiency. These extensions preserve the streaming nature of spigots, allowing indefinite digit generation with bounded memory.Implementations and Examples
Pseudocode for π
The Rabinowitz-Wagon spigot algorithm for π uses an array to represent the partial sums in a mixed-radix system based on the series for π, allowing digit-by-digit extraction through multiplications by 10 and modular reductions with carry propagation, all in integer arithmetic. To compute n digits of π after the decimal point, initialize an arraya of length len = (10 * n) // 3 + 1 with all elements set to 2. Use variables predigit = 0 and nines = 0 to handle potential sequences of 9s in the digits.
The main loop runs for j from 1 to n:
- Set carry
q = 0. - For
ifromlen - 1down to 0:x = 10 * a[i] + q * (i + 1)a[i] = x % (2 * i + 1)q = x // (2 * i + 1)
- Set
a[0] = q % 10 q = q // 10- If
q == 9:nines += 1
- Elif
q == 10:- Output
predigit + 1 - Output
nineszeros predigit = 0nines = 0
- Output
- Else:
- If more than one digit computed, output
predigit - If second digit, output decimal point
predigit = q- If
nines > 0:- Output
ninesnines nines = 0
- Output
- If more than one digit computed, output
- After the loop, output the final
predigit.
pseudocode
function pi_spigot(n_digits):
len = (10 * n_digits) // 3 + 1
a = [array](/page/Array) of len twos # all a[i] = 2
predigit = 0
nines = 0
for j = 1 to n_digits:
q = 0
for i = len - 1 downto 0:
x = 10 * a[i] + q * (i + 1)
a[i] = x % (2 * i + 1)
q = x // (2 * i + 1)
a[0] = q % 10
q = q // 10
if q == 9:
nines += 1
elif q == 10:
if j > 1:
output predigit + 1
else:
output (predigit + 1) # adjust for first digits
for k = 1 to nines:
output 0
predigit = 0
nines = 0
else:
if j > 1:
output predigit
predigit = q
if nines > 0:
for k = 1 to nines:
output 9
nines = 0
if j == 1:
output 3 # integer part
if j == 2:
output "."
output predigit
function pi_spigot(n_digits):
len = (10 * n_digits) // 3 + 1
a = [array](/page/Array) of len twos # all a[i] = 2
predigit = 0
nines = 0
for j = 1 to n_digits:
q = 0
for i = len - 1 downto 0:
x = 10 * a[i] + q * (i + 1)
a[i] = x % (2 * i + 1)
q = x // (2 * i + 1)
a[0] = q % 10
q = q // 10
if q == 9:
nines += 1
elif q == 10:
if j > 1:
output predigit + 1
else:
output (predigit + 1) # adjust for first digits
for k = 1 to nines:
output 0
predigit = 0
nines = 0
else:
if j > 1:
output predigit
predigit = q
if nines > 0:
for k = 1 to nines:
output 9
nines = 0
if j == 1:
output 3 # integer part
if j == 2:
output "."
output predigit