Mardi Gras True Fibs

[Gerson W. Barbosa]

This thread is more than one year old, but I have decided to updated it for the sake of completeness.

Firstly, the the following revised formula is not restricted to an even number of terms anymore:

\(\psi \approx \frac{1}{F_{1}}+\frac{1}{F_{2}}+\frac{1}{F_{3}}+\cdots +\frac{1}{F_{n-1}}+\frac{1}{F_{n}}+\frac{1}{F_{n-1}+\frac{s\cdot F_{1}^{2}}{F_{n+2}\cdot F_{1}+F_{n-1}\cdot F_{2}+\frac{s\cdot F_{2}^{2}}{F_{n+2}\cdot F_{2}+F_{n-1}\cdot F_{3}+\frac{s\cdot F_{3}^{2}}{F_{n+2}\cdot F_{3}+F_{n-1}\cdot F_{4}+\frac{s\cdot F_{4}^{2}}{F_{n+2}\cdot F_{4}+F_{n-1}\cdot F_{5}+\frac{\ddots }{\ddots F_{n+2}\cdot F_{n-1}+F_{n-1}\cdot F_{n}+\frac{s\cdot F_{n}^{2}}{F_{n+2}\cdot F_{n}+F_{n-1}\cdot F_{n+1} }}}}}}}\)

where \(s = \left \{ _{ 1, \mod(n,2)=1}^{-1, \mod(n,2)=0 } \right.\)

and

\(n = \left \lceil \sqrt{d}\left ( \varphi -\frac{1}{5\sqrt[8]{d}} \right )-\frac{1}{2} \right \rceil\)

where d is the number of correct decimal digits obtained from a given n.

and \(\varphi = \frac{1+\sqrt{5}}{2}\) is the golden ratio.

The formula \(n=f(d)\) above has been obtained empirically, but the fit is so close it might as well be exact:

      n           d       sqrt(d)*(phi - 1/(5*d^(1/8))) - 1/2   relative error (%)

     12         68.987                  11.96                         0.33
     16        120.326                  16.04                         0.27
     20        182.984                  19.98                         0.12
     22        220.489                  22.01                         0.06
     26        303.895                  26.00                         0.00
     30        400.909                  30.00                         0.01
     34        511.683                  34.03                         0.08
     38        635.227                  38.03                         0.08
     40        702.522                  40.05                         0.12
     44        846.221                  44.06                         0.14
     46        922.801                  46.06                         0.14
     48       1000.700                  48.02                         0.04

Secondly, I have provided a Decimal BASIC program. The algorithm is better than the one used in the previous RPL version, also the code might be easier to convert to other programming languages.

OPTION ARITHMETIC DECIMAL_HIGH
! Reciprocal Fibonacci Constant
DEF SQRT(x) =  EXP(LOG(x)/2)                                   ! standard precision SQR as
DEF Fib(x) = INT((phi^x - (-phi)^(-x))/SQRT(5) + 0.01)         ! full precision is not re-       
INPUT  PROMPT "Number of digits: ":f                           ! quired for low values of k                      
LET t = TIME                          
LET phi = (1 + SQRT(5))/2
LET k = CEIL(SQRT(f)*(phi - 1/(5*SQRT(SQRT(SQRT(f))))) - 1/2)
LET s = 2*MOD(k,2) - 1                                         ! if k is even then s = -1 else s = 1
LET sr = 0
LET a = Fib(k) 
LET b = Fib(k + 1)
LET cf = 0
LET u = Fib(k - 1)
LET v = Fib(1)*Fib(k + 2) + Fib(2)*Fib(k - 1)                  ! this expression evaluates correct-  
LET d = v*Fib(k) + u*Fib(k - 1)                                ! ly  for k < 70 using standard pre-   
LET e = v*Fib(k + 1) + u*Fib(k)                                ! cision  SQRT,  which would suffice  
FOR i = 1 TO k                                                 ! for 2000 digits.  Anyway,  Decimal  
   LET sr = sr + 1/a                                           ! BASIC is limited to 1000 digits 
   LET w = a
   LET a = b - a
   LET b = w
   LET n = s*b*b 
   LET cf = n/(cf + d)
   LET w = d
   LET d = e - d  
   LET e = w
NEXT i
LET cf = 1/(cf + d)
LET r = TIME - t                            
LET r$ = STR$(sr + cf)
PRINT
PRINT r$(1:2);
FOR i = 3 TO f + 1
   PRINT r$(i:i);
   IF MOD((i - 2),10) = 0 THEN PRINT " ";
   IF MOD((i - 2),50) = 0 THEN 
      PRINT
      PRINT "  ";
   END IF
NEXT i
IF MOD (i - 3,50) <> 0  OR f = 0 THEN PRINT
PRINT
PRINT "Runtime: ";
PRINT  USING "0.##": r;
PRINT " seconds"
END


Number of decimal places: 1001

3.3598856662 4317755317 2011302918 9271796889 0513373196 
  8486495553 8153251303 1899668338 3615416216 4567900872 
  9704534292 8853913304 1367890171 0088367959 1351733077 
  1190785803 3355033250 7753187599 8504871797 7789700603 
  9564509215 3758927752 6567335402 4033169441 7992939346 
  1099262625 7964647651 8686594497 1021655898 4360881472 
  6932495910 7947387367 3378523326 8774997627 2775794685 
  3676918541 9814676687 4299876738 2096913901 2177220244 
  0520815109 4264934951 3745416672 7895534447 0777775847 
  8025963407 6907484741 5557910420 0675015203 4107053352 
  8512979263 5242062267 5375680557 6195566972 0848843854 
  4079833242 9285136807 0827522662 5797511886 4646409673 
  7461572387 2362955620 5361220302 4635409252 6784242243 
  4703631036 3201466298 0402490155 7872445617 6000319551 
  9879059699 4202917886 6949174808 0967465236 8265408693 
  8399069873 2117521669 5706385941 1814553647 3642687824 
  6292616665 0100098903 8048233595 1989314615 0108288726 
  3928876699 1714930405 3057745574 3215611672 9898561772 
  9731395370 7352919668 8432789802 2165047585 0280918062 
  9100244427 7017460241 0404177860 6919006503 7142835295 
  
Runtime: 0.06 seconds