Pi digits (again) - an unbounded spigot program

[John Keith]

(05-12-2024 08:57 PM)EdS2 Wrote:  ... this on the other hand is Gibbons' unbounded spigot. Different, in some sense, except that we don't have bignums here.

We do if we are using the HP 49/50 or Prime. The spigot programs use only integer math and thus do not require arbitrary-precision floating-point software, making them a good fit for the newer HP's. Here is a straightforward RPL implementation. The program stores the digits in a string for convenience but could be easily adapted to display each digit if desired. Given an integer s on the stack, the program will return approximately 0.3*s digits. This is because only about 1 in 4 iterations actually return a new digit.

Code:


\<< 1 0 1 1 3 3 \-> s q r t k n l
  \<< ""                                   @ Empty string on stack
    WHILE k s <
    REPEAT
      IF q 4 * r + t - n t * <
      THEN n +                             @ Append n to string
        r n t * - 10 *                     @ nr
        q 3 * r + 10 * t IQUOT
        n 10 * - 'n' STO
        'q' 10 STO* 'r' STO
      ELSE q 2 * r + l *                   @ nr
        q k * 7 * r l * + 2 + t l * IQUOT  @ nn
        'q' k STO* 't' l STO*
        'l' 2 STO+ 'k' 1 STO+
        'n' STO 'r' STO
      END
    END
  \>>
\>>

If we assume that the conjecture in section 6 of Gibbons' paper is correct, we can use the last program in the paper called 'piG3' which is much more efficient. Not only does it return a new digit for every iteration, it also has features that make the program run faster. It only requires one integer divide per digit, and those are slow in RPL. Also, since there is no test clause, the control structure is simpler and we can replace the WHILE loop with a FOR loop which is faster. Here, then, is an RPL implementation of 'piG3'. It runs about 7 times faster than the previous program and is about 100 bytes smaller. Given an integer on the stack, the program will return that many digits.

Code:


\<< 1 180 60 1 1 \-> q r t u y
  \<< ""                                       @ Empty string on stack
    2 ROT 1 +                                  @ k from 2 to n+1
    FOR k k 27 * 12 - q * r 5 * + t 5 * IQUOT  @ y
      DUP 'y' STO +                            @ Append y to string
      k 3 * 1 + DUP 1 + * 3 * 'u' STO          @ u
      q k * 10 * k 2 * 1 - *                   @ Pre-compute q
      k 5 * 2 - q * r + y t * - 10 * u *       @ r
      'r' STO 'q' STO 't' u STO*               @ Update r, q, t
    NEXT
  \>>
\>>