Calculating with large numbers (Fibonacci)

[Jacobus]

Hello,
I found some code by DK_PETER dating back to 2013 (here: https://www.purebasic.fr/english/viewto ... ci#p423313)
giving various calculation formulas, including one for obtaining the Fibonacci sequence. However, the formula is limited.
Although the calculations are performed with whole numbers, using PB(x86), the errors start at the 46th occurrence (0 to 45) and then give negative and inconsistent results.
As for the calculation with PB(x64), the inconsistencies start at the 92nd occurrence.
Unless I missed something, I suspect this is due to the size of the numbers (up to 19 digits with x64, and up to only 10 digits with x86).
Do you have a solution to overcome these limitations so that we can calculate much higher Fibonacci numbers?
Here's some code that illustrates the issue: (Windows 11 pro; PB 6.21b2 x86/x64)

Code: Select all

Procedure.f NombreOR()
  Nor.f = (1+Sqr(5))/2
  ProcedureReturn ValF(StrF(Nor,10))
EndProcedure 
Procedure Calcul_Fibonacci(y.l)
  
  TheNext.d = 0
  TheLast.d = 1
  For x = 0 To y        
    If TheNext<>0
      Fnor.f = Thelast/TheNext	 ; nombre d'or sur chaque nombre de la suite de Fibonacci     
    EndIf
    If Thelast<>0
      Dnor.f = TheNext/Thelast	 ; nombre d'or moins un sur chaque nombre de la suite de Fibonacci 
    EndIf     
    AddGadgetItem(4, -1, Str(x)+Chr(10)+Str(TheLast)+Chr(10)+StrF(Fnor,15)+Chr(10)+StrF(Dnor,15))   
    sum = TheNext + Thelast  ;: Debug "TheNext = " + Str(TheNext) + "     Thelast = " + Str(Thelast) + "     Somme des 2 = " + Str(sum)
    TheNext = Thelast        ;: Debug "TheNext = " + Str(TheNext) + "  =  Thelast = " + Str(Thelast)
    TheLast = sum            ;: Debug "Thelast = " + Str(Thelast) + "  =  sum = "     + Str(sum)
                             ; Debug "============================================================"
  Next x
  
EndProcedure

If OpenWindow(0, 0, 0, 800, 600, "Fibonacci sequence", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
   
  ButtonGadget  (1, 5, 5, 60, 25, "Démarrer") : GadgetToolTip(1,"Lancer le calcul/Start the calculation")
  ButtonGadget  (2, 65, 5, 60, 25, "Fermer")  : GadgetToolTip(2,"Fermer la fenêtre/Close window") 
  TextGadget    (3, 550, 10, 250, 20, "")     : SetGadgetText(3,"Nombre d'or/Golden ratio = "+NombreOR())
  ListIconGadget(4, 5, 35, 790, 560, "N°", 50, #PB_ListIcon_GridLines|#PB_ListIcon_FullRowSelect)
  AddGadgetColumn(4, 1, "Nombre (n1+n2)", 200)
  AddGadgetColumn(4, 2, "deduction of the golden ratio (n2/n1)", 200)
  AddGadgetColumn(4, 3, "golden ratio -1 (n1/n2)", 200)
  
   Repeat
     Event = WaitWindowEvent()    
     Select Event
     
       Case #PB_Event_Gadget
         Select EventGadget()
           Case 1    
             Calcul_Fibonacci(91) ; uniquement en mode 64 bit, au-delà de 91 le calcul est négatif
            ;Calcul_Fibonacci(45) ; en mode 32 bit, au-delà de 45 le calcul est négatif            
             ;exemple pour résultat négatifs (32 ou 64 bit)
             ;Calcul_Fibonacci(100)
           Case 2 
              CloseWindow(0)
              End                         
          EndSelect           
     EndSelect
   Until Event = #PB_Event_CloseWindow
 EndIf

[matalog]

To add numbers together like that (Fibonacci sequence just adds the previous 2 numbers), you just have to add the individual digits (in string format) and carry the tens, like you would add in primary school.

Using strings means that you can have any length of number you want.

This gives a method: https://www.geeksforgeeks.org/sum-two-large-numbers/

It's a simple, and enjoyable little thing to program, maybe you would want to give it a try?

[STARGÅTE]

In your code you mixed up several number types such as long, integer, float and double.
If you use integer numbers, you are limited to ~ 9.223e+18.
If you use double numbers, you lose some precision, but you can evaluate numbers until 1.798e+308.

Alternatively, you can also use this formula without iteration loop, wich has a precision of ~15 digits:

Code: Select all

#GoldenRatio           = 1.6180339887498948482 ; φ = (1+√5)/2
#InverseSquareRootFive = 0.4472135954999579393 ; 1/√5
	
Procedure.d Fibonacci(X.d)
	Protected Phi.d
	Phi.d = Pow(#GoldenRatio, X)
	ProcedureReturn ( Phi - Cos(#PI*X)/Phi ) * #InverseSquareRootFive
EndProcedure

Debug Fibonacci(100)

For arbitrary large and precise numbers, you can try my library: Lizard

[matalog]

If you don't want to code it yourself, and feel like tidying up some terrible code, I have this I wrote for ZX Spectrum, and just converted quickly.

Scroll it if you want to look, and don't if you don't .

Code: Select all

asc0= Asc ("0")
a$="1"
b$="1"
For t=0 To 10000
carry=0

la=Len (a$)
lb=Len (b$)
s$=""
str:
vala=0
If la>0 
  vala= Asc (Mid(a$,la,1))-asc0
  EndIf
valb=0
If lb>0 
  valb= Asc (Mid(b$,lb,1))-asc0
  EndIf

 som=vala+valb+carry

 carry=0
 If som>9
   carry=Int (som/10)
   EndIf
 som=som-10*carry+asc0
 s$=Chr( som)+s$

If la>0
  la=la-1
  EndIf
  If lb>0 
    lb=lb-1
    EndIf
    If la>0 Or lb>0 
      Goto str
      EndIf
      If carry=0
        Goto ed
        EndIf
 som=carry+asc0
s$=Chr(som)+s$
ed:
p$=Str(t)+": "+s$
Debug p$

a$=b$
 b$=s$
Next t

[Jacobus]

Thank you for your answers, which shed some light on the subject.

Alternatively, you can also use this formula without iteration loop, wich has a precision of ~15 digits:

Code: Select all

#GoldenRatio           = 1.6180339887498948482 ; φ = (1+√5)/2
#InverseSquareRootFive = 0.4472135954999579393 ; 1/√5
	
Procedure.d Fibonacci(X.d)
	Protected Phi.d
	Phi.d = Pow(#GoldenRatio, X)
	ProcedureReturn ( Phi - Cos(#PI*X)/Phi ) * #InverseSquareRootFive
EndProcedure

Debug Fibonacci(100)

For arbitrary large and precise numbers, you can try my library: Lizard

I'm surprised there are so many differences in the results between my simple calculation and your procedure. I'll try Lizard, which interests me.

If you don't want to code it yourself, and feel like tidying up some terrible code, I have this I wrote for ZX Spectrum, and just converted quickly.

Scroll it if you want to look, and don't if you don't .

Your code has an amusing result; if that was the goal, it's not so catastrophic. But to find the Fibonacci numbers, you'll have to get up early... lol

[matalog]

If you don't want to code it yourself, and feel like tidying up some terrible code, I have this I wrote for ZX Spectrum, and just converted quickly.

Scroll it if you want to look, and don't if you don't .

Your code has an amusing result; if that was the goal, it's not so catastrophic. But to find the Fibonacci numbers, you'll have to get up early... lol

At least it can handle more than 100 characters .

[Michael Vogel]

That's quite old code (around 20 years!) here but should work fine - I tried to reduce the code a little bit to get results more quickly...

Code: Select all

; Define

	#VNFDim=10000
	#VNFLen=18
	#VNFMod=1000000000000000000

	Structure VNF
		len.i
		num.q[#VNFDim]
	EndStructure

	Procedure.s Number(*num.VNF)

		Protected n
		Protected t.s
		Protected *t

		n=*num\len
		t=Str(*num\num[n])

		If n
			*t=Len(t)<<#PB_Compiler_Unicode
			t+Space(n*#VNFLen)
			*t+@t

			While n>0
				n-1
				PokeS(*t,RSet(Str(*num\num[n]),#VNFLen,"0"),#VNFLen,#PB_String_NoZero)
				*t+#VNFLen<<#PB_Compiler_Unicode
			Wend
		EndIf

		ProcedureReturn t

	EndProcedure

	Procedure PutNumber(*s.String,*num.VNF)

		Protected n.q,p.q
		Protected t.s

		t=PeekS(@*s\s)
		n=Len(t)-#VNFLen

		While n>0
			*num\num[p]=Val(PeekS(@t+n,#VNFLen))
			p+1
			n-#VNFLen
		Wend

		n=Val(PeekS(@t,#VNFLen+n))
		*num\num[p]=n
		*num\len=p

	EndProcedure
	Procedure VNFAdd(*a.VNF,*b.VNF,*c.VNF)

		Protected n.i
		Protected s.q

		If *a\len<*b\len
			Swap *a,*b
		EndIf

		While n<=*a\len
			s+*a\num[n]
			If n<=*b\len
				s+*b\num[n]
			EndIf
			*c\num[n]=s%#VNFMod
			s/#VNFMod
			n+1
		Wend
		If s
			*c\num[n]=s
		Else
			n-1
		EndIf

		*c\len=n

	EndProcedure

; EndDefine

x.VNF
y.VNF
z.VNF

one.String
one\s="1"

PutNumber(@one,x)
PutNumber(@one,y)

n=2
While n<100000
	n+1
	VNFAdd(x,y,z)
	x=y
	y=z

	If n=100
		Debug RSet(Str(n),6)+": "+Number(z)
		Debug "around: "+StrD((Pow(1.6180339887498948482,n)-Cos(#PI*n)/Pow(1.6180339887498948482,n) ) * 0.4472135954999579393)
		Debug RSet("",30,"-")
	ElseIf n%5000=0
		Debug RSet(Str(n),6)+": "+Number(z)
	EndIf
Wend

[Jacobus]

That's quite old code (around 20 years!) here but should work fine - I tried to reduce the code a little bit to get results more quickly...

It's really impressive to be able to get such large numbers. Thank you for this contribution. I will be able to integrate your methods into a small Fibonacci calculation program.

[SPH]

Code: Select all

max=100

Dim fibo.i(max)
fibo(0)=3
fibo(1)=1
fibo(2)=1

Repeat
  fibo(fibo(0))=fibo(fibo(0)-2)+fibo(fibo(0)-1)
  fibo(0)+1
Until fibo(0)=max

For i=1 To max-1
  Debug fibo(i)
Next

My contribution...

I'm surprised that the maximum value of a ".i" is exceeded so quickly with this famous sequence...

[Little John]

Code: Select all

max=100

Dim fibo.i(max)
fibo(0)=3
fibo(1)=1
fibo(2)=1

Repeat
  fibo(fibo(0))=fibo(fibo(0)-2)+fibo(fibo(0)-1)
  fibo(0)+1
Until fibo(0)=max

For i=1 To max-1
  Debug fibo(i)
Next

My contribution...

Don't make things (look) more complicated than necessary.
After replacing fibo(0) with index, the above code looks like this:

Code: Select all

max = 100

Dim fibo.i(max)
index = 3
fibo(1) = 1
fibo(2) = 1

Repeat
   fibo(index) = fibo(index-2) + fibo(index-1)
   index + 1
Until index = max

For i = 1 To max-1
   Debug fibo(i)
Next

Now it's obvious that this is just the definition of the Fibonacci sequence.

[Jacobus]

This is perfect, and using a double instead of an integer gives the correct results.

Code: Select all

max = 200
Dim fibo.d(max)
index = 3
fibo(1) = 1
fibo(2) = 1

Repeat
   fibo(index) = fibo(index-2) + fibo(index-1)
   index + 1
Until index = max

For i = 1 To max-1
   Debug Str(i)+" => "+ fibo(i)
Next

[PurePilish]

Jacobus -

You wrote "...and using a double instead of an integer gives the correct results."

That's not really true. The integer version of the code (2 posts ago) gives the exactly correct answer up to the 92nd Fibonacci number. The double-precision code (previous post) only gives the exactly correct answer up to the 78th Fibonacci. So in that sense the integer version is more accurate.
This is to be expected - double precision can represent integers exactly up to 15 or 16 decimal digits, whereas 64-bit integer type can represent exactly up to 19 digits.

It is true that the double version gives *approximate* answers for the higher numbers (which the integer version cannot do), but they are not exactly correct after the 78th one. Just thought I'd mention that, since one could look at the output and think that all the numbers are correct (which they aren't).

[Jacobus]

To add numbers together like that (Fibonacci sequence just adds the previous 2 numbers), you just have to add the individual digits (in string format) and carry the tens, like you would add in primary school.

Using strings means that you can have any length of number you want.

This gives a method: https://www.geeksforgeeks.org/sum-two-large-numbers/

It's a simple, and enjoyable little thing to program, maybe you would want to give it a try?

just for fun but still useful...

Code: Select all

; Manual mode calculation For long numbers.
; it's not a fish...
; Following Matalog's advice, I created a routine to do this in PB.
; The calculation is performed digit by digit.
; By Jacobus, April 1, 2025
; ------------------------------------------------------------------
; 
; 	      7 5 4 0 1 1 3 8 0 4 7 4 6 3 4 6 4 2 9
;       + 4 6 6 0 0 4 6 6 1 0 3 7 5 5 3 0 3 0 9
;         ______________________________________
; 
;     = 1 2 2 0 0 1 6 0 4 1 5 1 2 1 8 7 6 7 3 8     (calcul manuel = correct / manual calculation = correct)
; 
; ------------------------------------------------------------------
; Method used :
; ret = carry
; ret = 0 if < 10 / ret = 1 if > 10
;Addition
; 9 + 9 = 18  | 8 = 18 - 10 (ret = 1)
; 2 + 0 = 2   | 3 = 2 + ret
; 4 + 3 = 7   | 7
; 6 + 0 = 6   | 6
; 4 + 3 = 7   | 7 
; 3 + 5 = 8   | 8
; 6 + 5 = 11  | 1 = 11 - 10    (ret = 1)
; 4 + 7 = 11  | 2 = (11 + ret) (ret = 1)
; 7 + 3 = 10  | 1 = (10+ret - 10) (ret = 1)
; 4 + 0 = 4   | 5 = 4 + ret
; 0 + 1 = 1   | 1
; 8 + 6 = 14  | 4 = 14 - 10 (ret = 1)
; 3 + 6 = 9   | 0 = (9 + ret) - 10 (ret = 1)
; 1 + 4 = 5   | 6 = 5 + ret
; 1 + 0 = 1   | 1
; 0 + 0 = 0   | 0
; 4 + 6 = 10  | 0 = 10 - 10 (ret = 1)
; 5 + 6 = 11  | 2 = (11 + ret) - 10 (ret = 1)
; 7 + 4 = 11  | 12 = 11 + ret
; ------------------------------------------------------------------


Global NewList NewListDigit.l() 

;n1$ = "75401138047463464291111" ; 23 digit
n1$ = "7540113804746346429"      ; 19 digit
n2$ = "4660046610375530309"      ; 19 digit

Len1 = Len(n1$) 
Len2 = Len(n2$) 

; If one number is larger or smaller than the other, adjust the size with zeros.
; You can test with n1$
If Len1 <> Len2 
  If Len1 > Len2
    Adjust = Len1 - Len2 
    For a = 1 To Adjust
      n2$ = InsertString(n2$, "0", 1) 
    Next    
    n1$ = n1$ 
  ElseIf Len1 < Len2
    Adjust = Len2 - Len1    
    For a = 1 To Adjust
      n1$ = InsertString(n1$, "0", 1) 
    Next  
    n2$ = n2$
  EndIf  
EndIf 

; To be able to calculate from right to left, we reverse the direction of the character strings.
Revn1$ = ReverseString(n1$)
Revn2$ = ReverseString(n2$) 

LenR1 = Len(Revn1$) 
LenR2 = Len(Revn2$) 

; We add each digit of the number 1 to our list.
For x = 0 To LenR1 - 1   
  digitn1$ = Mid(Revn1$,x+1,1) ; forced to add 1 to x (list starts at 0, but number starts at first digit)
  AddElement(NewListDigit()) 
  NewListDigit() = Val(digitn1$)
Next x

; ret = the carry when the sum of 2 digits is greater than 10
ret = 0

; Now we proceed to the actual calculation
For y = 0 To LenR2-1 
  digitn2$ = Mid(Revn2$,y+1,1) 
  
  For i = 0 To ListSize(NewListDigit())-1
    If y = i      
      SelectElement(NewListDigit(), i)    
      result = NewListDigit()+Val(digitn2$)+ret
       
      If result >= 10 And i = LenR2-1 ;  allows you to keep the ten or ret for the first digit (12 in this example)
        Rdigit = result
      ElseIf result >= 10 
        Rdigit = result - 10 
        ret = 1
      ElseIf result < 10 
        Rdigit = result 
        ret = 0
      EndIf 
      
      Rdigit$ = Str(Rdigit) + Rdigit$ 
      ; Displaying each result
      Debug Rdigit$
      
    EndIf 
  Next i
  
Next y

; Displaying the final result
Debug Rdigit$

[Jacobus]

Jacobus -

You wrote "...and using a double instead of an integer gives the correct results."

That's not really true. The integer version of the code (2 posts ago) gives the exactly correct answer up to the 92nd Fibonacci number. The double-precision code (previous post) only gives the exactly correct answer up to the 78th Fibonacci. So in that sense the integer version is more accurate.
This is to be expected - double precision can represent integers exactly up to 15 or 16 decimal digits, whereas 64-bit integer type can represent exactly up to 19 digits.

It is true that the double version gives *approximate* answers for the higher numbers (which the integer version cannot do), but they are not exactly correct after the 78th one. Just thought I'd mention that, since one could look at the output and think that all the numbers are correct (which they aren't).

Thanks for your explanation. The code I just posted should allow you to ignore the length of the numbers to calculate the sum, even if it's more like a manual school calculation.