Mardi Gras True Fibs

[Gerson W. Barbosa]

Here is a UserRPL solution that works on the HP 49G/50g and doesn't rely on external arbitrary precision libraries:

Code:


%%HP: T(3)A(R)F(.);
DIR
  RFC
  \<< PUSH RAD -105 CF -3 CF 0 1 1 4 PICK
    START DUP 4 ROLLD DUP ROT +
    NEXT + 4 PICK ROT 2 + ROLLD LASTARG ROLLD LASTARG 2 - \->LIST REVLIST DUP 4 ROLLD DUP SIZE 4 ROLLD INV \GSLIST 4 ROLLD 1 4 PICK
    START DUP 4 ROLLD DUP ROT +
    NEXT DROP2 \->LIST REVLIST SWAP ROT TAIL SQ NEG 0 + ROT 0 + OVER SIZE 1 DUP ROT
    START GETI SWAP 1 - 4 ROLL SWAP GETI 4 ROLL / 4 ROLL ROT GETI SWAP 1 - SWAP 4 ROLL + PUTI 1 -
    NEXT DROP DUP SIZE 1 - GET INV NIP + EXPAND \->STR "/" " " SREPL DROP "'" "" SREPL DROP OBJ\-> OVER \->STR SIZE .89 ^ 1.209 * 1 - IP 
    R\->I ALOG ROT OVER * UNROT * DUP2 DUP SIZE R\->I ALOG SWAP - * SWAP IQUOT + \->STR DUP HEAD -51 FC? { "." } { "," } IFTE + SWAP TAIL + POP
  \>>
  d
  \<< DUP \v/ 1.5 * CEIL DUP 2 MOD + RFC 1 ROT 1 + SUB
  \>>
END

The following table and information might give an idea of the method.


 n  | d   |  N   |  D  |  k 
----+-----+------+-----+----
  8 |  30 |  15  |  14 |  15
 10 |  45 |  24  |  24 |  20
 12 |  64 |  36  |  35 |  28
 14 |  87 |  50  |  49 |  38
 16 | 113 |  64  |  64 |  48
 18 | 142 |  83  |  82 |  59
 20 | 174 | 100  | 100 |  73
 22 | 211 | 123  | 123 |  87
 40 | 685 | 419  | 418 | 266
 48 | 981 | 612  | 611 | 369
 50 |1064 | 664  | 663 | 400


n: number of terms of the regular term = number of terms of the continued fraction
d: number of correct digits
N: number of digits of the numerator of the simplified fraction
D: number of digits of the denominator of the simplified fraction
k: exponent of 10 used in the conversion from simplified fraction to decimal fraction

N1 = N*10^k
D1 = D*10^k

N2 = (10_complement(D1)+1)*N1) idiv (D1)
D2 = 10^(2*k)

k ~ 1.2093*N^0.88996 ( in the program, 1.209*N^0.89 - 1 )
n ~ (2.7735*d^0.51461)/2 ( in the program, ceil[1.5*sqrt(d)] )

The first program evaluates the Reciprocal Fibonacci Constant for n terms of the regular series and n terms of the continued fraction. The second program evaluates it to d decimal digits, including the integer part. The latter occasionally will fail since a better curve-fitting is still required. For instance, 1001 d will return a 977-character string rather than the 1001 digits we would expect. Using ceil[1.5*sqrt(d)] + 2 would help in this particular case, but would be worse overall.

Examples:

 2  RFC  -->    3.3  (2  digits,  1.06  s)
 8  RFC  -->    3.35988566624317755317201130  (28  digits,  2.62  s)
16  RFC  -->    3.359885666243177553172011302918927179688905133731968486495553815325130318996683​383615416216456790087297045342928  (112  digits,  13.40  s)

  50  d  -->    3.3598856662431775531720113029189271796889051337319  (6.00  s)
 100  d  -->    3.359885666243177553172011302918927179688905133731968486495553815325130318996683​383615416216456790087  (13.53  s)


1500 digits under one hour, 1000 digits under 20 minutes. Times on the HP 50g (about three times longer on the HP 49G).

Edited. N and D are the number of digits of the numerator and the denominator of the resulting irreducible fraction, not the numerator and the denominator themselves, in case some might have wondered. Sorry for the lack of attention.

—————————-

Updated version using the FXND command:

« PUSH RAD -105 CF -3 CF DUP √ 1.5 * CEIL DUP 2 MOD + 0 1 1 4 PICK
START DUP 4 ROLLD DUP ROT +
NEXT + 4 PICK ROT 2 + ROLLD LASTARG ROLLD LASTARG 2 - →LIST REVLIST DUP 4 ROLLD DUP SIZE 4 ROLLD INV ∑LIST 4 ROLLD 1 4 PICK
START DUP 4 ROLLD DUP ROT +
NEXT DROP2 →LIST REVLIST SWAP ROT TAIL SQ NEG 0 + ROT 0 + OVER SIZE 1 DUP ROT
START GETI SWAP 1 - 4 ROLL SWAP GETI 4 ROLL / 4 ROLL ROT GETI SWAP 1 - SWAP 4 ROLL + PUTI 1 -
NEXT DROP DUP SIZE 1 - GET INV NIP + EXPAND FXND OVER →STR SIZE .89 ^ 1.209 * 1 - IP R→I ALOG ROT OVER * UNROT * DUP2 DUP SIZE R→I ALOG SWAP - * SWAP IQUOT + →STR DUP HEAD -51 FC? { "." } { "," } IFTE + SWAP TAIL + 1 ROT 1 + SUB POP
»

The argument is the number of figures, as in the previous examples.