Fibonacci numbers: the nature's numbers...

[felipe]

So...is this the soapbox?  Just kidding.

I have written this simple program that will calculate and write an arbitrary amount of the fibonacci numbers serie into a file. Please note that the source code and an .exe file are in the .zip file. What i try to say with this is that just 1 possible error (from a large spectrum of errors i guess, but maybe they are not so many actually) is notified in this version of the program: if the buffer for the actual directory of the user is too small. There are no checking errors for "write to the file" problems, like dealing with permissions and possibly others. So please feel free to modify this code to whatever you need, including all those error checkings if you want.  :idea:

I have done this program (the loaded to the forum version) to write just 100 fibonacci numbers to a .txt file. But i have tried with 1000 numbers too and it seemed that worked good to me. By the way there are no error checking, for numbers supplied in the source code that can be really big (i mean if you supply to the program to calculate a really big number of fibonacci numbers). I suposse that this situation will need basically a bigger buffer to store each number. The one is used in this version is of approximately 256 bytes for each fibonacci number transformed to ascii, but the binary fibonacci number limit size used is that of a 32 bit register (you know that size)... :idea:

Finally, i want to make clear (by the way sorry for my english again  :redface:) that all this introduction of what is supplied here, from me to all of you, doesn't mean i don't want to receive critics or similars. Please note that this program was done like that mainly for clarity. So all your comments are welcome!  :icon14:

[aw27]

I have done this program (the loaded to the forum version) to write just 100 fibonacci numbers to a .txt file

It appears that you are not concerned with the 32-bit overflow 
which will happen on and after the 48th Fibonacci number.

[felipe]

 :redface: Thanks for telling me that! Well i guess i understimated how this numbers can grow. I was thinking of doing a 64 bit version after this 32 bit version. But maybe i will repair this version first to support properly at least 100 fibonacci numbers. Thanks again, i was actually wishing someone could tell me if the numbers were all correct or not (something that i supossed was difficult to do manually).  :icon14:

[raymond]

If this is simply an exercise in curiosity, and you are not concerned with an ultrafast algo, you may want to try using binary coded decimals http://www.ray.masmcode.com/BCDtut.html.

You could then go as far as you want, the memory require being only approx. three times the number of digits required for the largest one, a third of that being for the ascii converted number. Each new converted number could then be added to the end of an open file without worrying about memory required for the entire file.

[daydreamer]

Felipe if you make this work correctly,it would be Worth much for students who usually get fibonacci as task,C#,c++,java etc
the question I asked myself was if it somehow was possible to make a SIMD solution?
and the question is does there exist something similar algo for fibonacci,that exist an alternative x! algo for approximation of high numbers

[jimg]

 I just did it using ascii characters, 60 char wide, easily expandable.  Thanks for the fun diversion :)

Code Select Expand

; by JimG
.nolist
.586
.model flat, stdcall
option casemap:none ; case sensitive
include windows.inc

uselib Macro libname:req
    include    libname.inc
    includelib libname.lib
Endm
uselib kernel32
uselib user32

inv equ invoke
maxsize=60  ; max width of answers
.data?
hout dd ?
nout dd ?
ncnt dd ?
cary db ?
.data
val1 db maxsize-1 dup (" "),"1",13,10,0
val2 db maxsize-1 dup (" "),"1",13,10,0
val3 db maxsize-1 dup (" "),"0",13,10,0
.code

Program:
    inv GetStdHandle,STD_OUTPUT_HANDLE
    mov hout,eax
    inv WriteFile,hout,addr val1,maxsize+2,addr nout,0
    inv WriteFile,hout,addr val2,maxsize+2,addr nout,0
    pusha
    lea esi,val1  ; previous val
    lea edi,val2  ; previous val
    lea ebx,val3  ; new val
    mov ncnt,2
    .repeat
        mov ecx,maxsize-1  ; 0 to max
        mov cary,0
        .repeat
            mov eax,0
            mov al,byte ptr [esi+ecx]
            mov dl,byte ptr [edi+ecx]
            .if al==" "
                mov al,'0'
            .endif
            .if dl==" "
                mov dl,'0'
            .endif
            sub al,'0'  ; convert to binary
            sub dl,'0'
            add al,dl
            add al,cary
            mov cary,0
            .if al>9
                mov cary,1
                sub al,10
            .endif
            add al,'0'  ; convert to ascii
            mov [ebx+ecx],al
            dec ecx
            jz maxdone
            .if byte ptr [edi+ecx]==" "  ; are we done?
                .if cary
                    mov byte ptr [ebx+ecx],'1'
                .endif
                .break
            .endif
        .until 0
        inv WriteFile,hout,ebx,maxsize+2,addr nout,0
        mov eax,esi  ; where next answer will go
        mov esi,edi
        mov edi,ebx
        mov ebx,eax
        inc ncnt
    .until 0
     
maxdone: inv Sleep,100000
    popa   
    inv ExitProcess,0
End Program


very quick and dirty, can be cleaned up a lot :)

[jack]

the question is does there exist something similar algo for fibonacci,that exist an alternative x! algo for approximation of high numbers

there's a closed form formula for Fibonacci numbers, F(n) = (((1+sqrt(5))*(1/2))^n-((1-sqrt(5))*(1/2))^n)/sqrt(5) https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

[felipe]

Thanks raymond i will check that tutorial for sure. Hey jimg, that looks great, nice work. 

:icon14:

[felipe]

Hello, here it's a 64 bit version of the same program i wrote (which by the way also had a wrong date, indicating the creation of the program in the future  :P). This version can easily produce the first 100 fibonacci numbers in the file as can be seen here:

Code Select Expand


2-3-5-8-13-21-34-55-89-144-233-377-610-987-1597-2584-4181-6765-10946-17711-28657-46368-75025-121393-196418-317811-514229-832040-1346269-2178309-3524578-5702887-9227465-14930352-24157817-39088169-63245986-102334155-165580141-267914296-433494437-701408733-1134903170-1836311903-2971215073-4807526976-7778742049-12586269025-20365011074-32951280099-53316291173-86267571272-139583862445-225851433717-365435296162-591286729879-956722026041-1548008755920-2504730781961-4052739537881-6557470319842-10610209857723-17167680177565-27777890035288-44945570212853-72723460248141-117669030460994-190392490709135-308061521170129-498454011879264-806515533049393-1304969544928657-2111485077978050-3416454622906707-5527939700884757-8944394323791464-14472334024676221-23416728348467685-37889062373143906-61305790721611591-99194853094755497-160500643816367088-259695496911122585-420196140727489673-679891637638612258-1100087778366101931-1779979416004714189-2880067194370816120-4660046610375530309-7540113804746346429-12200160415121876738-1293530146158671551-13493690561280548289-14787220707439219840-9834167195010216513-6174643828739884737-16008811023750101250-3736710778780434371-1298777728820984005-5035488507601418376


The source code and the .exe are attached.  :icon14:

[raymond]

If we start the series with F₁= 1 and F₂=1, then F₃=2, etc.
F₉₃=12200160415121876738 which is the last one in your list which is correct.

You can easily see that your following listed number(s) cannot be the sum of the two previous ones.

Here's a short program using BCDs to compute Fibonacci numbers which you can adapt as needed. As is, it terminates when a given number of digits is reached. Instead, it could be terminated when a given F_n is reached.

BTW, F₄₇₆ is the first one to contain 100 digits.

Code Select Expand

;           Fibonacci numbers

; For computing the first Fibonacii having a specified number of  decimal digits

; #########################################################################

      .686                   ; minimum processor needed for 32 bit
      .model flat, stdcall   ; FLAT memory model & STDCALL calling
      option casemap :none   ; set code to case sensitive

; #########################################################################

      include \masm32\include\windows.inc

      include \masm32\include\user32.inc
      include \masm32\include\kernel32.inc

      includelib \masm32\lib\user32.lib
      includelib \masm32\lib\kernel32.lib

.data
      FibA        db    1,99 DUP(0) ;buffer for "last" number
      FibB        db    1,99 DUP(0) ;buffer for "previous" number
      digits      dd    1           ;number of digits in last number
      Fibnum      dd    2           ;F number

.code

; The two working buffers FibA and FibB will be alternating
; as the last and previous Fibonacci numbers.
; They both start at 1.
; The numbers are kept in lil-endian mode for ease of processing.

start:
      mov   esi,offset FibA   ;ESI will be always pointing to the "last" number
      mov   edi,offset FibB   ;EDI will be always pointing to the "previous" number

start1:
      mov   ecx,digits        ;use as counter for number of additions
      xor   edx,edx           ;offset into the two numbers
start2:
      mov   al,[esi+edx]      ;get digit of last number
      adc   al,[edi+edx]      ;add to it digit of previous number + carry
      aaa                     ;adjust after addition
      mov   [edi+edx],al      ;overwrite previous number with new addition result
      inc   edx               ;point to next digits
      dec   ecx               ;adjust counter
      jnz   start2            ;continue until last digits added
      .if   CARRY?            ;if addition of last digit has a carry
            mov   byte ptr [edi+edx],1
            inc   digits      ;adjust the count of digits
      .endif
      inc   Fibnum            ;Fn
      xchg  esi,edi           ;switch the pointers so ESI points to "last" number
                              ;   and edi points to "previous" number
      cmp   digits,100
      jb    start1            ;continue until target quantity of digits is reached

; prepare ascii representation of last number in buffer of previous number

      mov   ecx,100-4         ;pointing to the start of the last 4 digits
@@:
      mov   eax,[esi+ecx]     ;get 4 bytes
      add   eax,30303030h     ;convert the 4 bytes to ascii
      bswap eax
      stosd
      sub   ecx,4
      jnc   @B
      mov   byte ptr [edi],0  ;terminate with ending 0 for display

;do whatever you want with the ascii answer
;you may also want to convert to ascii and display its Fn

      invoke ExitProcess,0

end start


[felipe]

Hello raymond thank you very much. I think the last correct number from that list is 14787220707439219840 (the third number to the right from the one you mentioned ). But the others are, indeed wrong  :icon_redface:. Thanks for telling me that and for your help with that code. I will study the code soon as i can.

:icon14:

[raymond]

I think the last correct number from that list is 14787220707439219840

I may disagree.
Use paper and pencil and try them from the last one I mentioned.

[daydreamer]

the question is does there exist something similar algo for fibonacci,that exist an alternative x! algo for approximation of high numbers

there's a closed form formula for Fibonacci numbers, F(n) = (((1+sqrt(5))*(1/2))^n-((1-sqrt(5))*(1/2))^n)/sqrt(5) https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

thanks

[felipe]

Ok now i see. After you told me about the error, i just added the number 12200160415121876738 with the number 1293530146158671551. Then to the result 13493690561280548289 (which is correct) i added the previous number (1293530146158671551) and i got as a result the number 14787220707439219840 which is correct too. After that the results were wrong. But now i see you were right, because adding the number 12200160415121876738 with the previous number in the serie (7540113804746346429) is not 1293530146158671551.  :idea:

So, indeed the last one correct produced by the program i wrote was 12200160415121876738 as you mentioned. Thank you very much again.   :icon14:

[Siekmanski]

xadd is a perfect instruction to calculate Fibonacci numbers.

Code Select Expand

; Fibonacci numbers using the "xadd" instruction

    mov     ecx,12      ; term of the Fibonacci sequence
    mov     eax,0       ; first number
    mov     edx,1       ; second number
Fibonacci_LP:           ; calculate a Fibonacci number with 2 instructions
    xadd    eax,edx     ; exchange and add
    loop    Fibonacci_LP

    ; eax = 144