### Author Topic: Fibonacci numbers: the nature's numbers...  (Read 198 times)

#### felipe

• Member
• Posts: 866
• Eagles are just great!
##### Fibonacci numbers: the nature's numbers...
« on: July 06, 2018, 04:56:35 PM »
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.

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)...

Finally, i want to make clear (by the way sorry for my english again  ) 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!
Felipe.

#### AW

• Member
• Posts: 1346
• Let's Make ASM Great Again!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #1 on: July 06, 2018, 05:19:14 PM »
Quote
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

• Member
• Posts: 866
• Eagles are just great!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #2 on: July 07, 2018, 02:08:24 AM »
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).
Felipe.

#### raymond

• Member
• Posts: 199
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #3 on: July 07, 2018, 02:36:23 AM »
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.
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

#### daydreamer

• Member
• Posts: 465
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #4 on: July 07, 2018, 03:05:31 AM »
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
Quote from Flashdance
Nick  :  When you give up your dream, you die.
*wears a flameproof asbestos suit*

#### jimg

• Member
• Posts: 260
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #5 on: July 07, 2018, 03:41:16 AM »
I just did it using ascii characters, 60 char wide, easily expandable.  Thanks for the fun diversion :)

Code: [Select]
`; by JimG.nolist.586.model flat, stdcalloption casemap:none ; case sensitiveinclude windows.incuselib Macro libname:req    include    libname.inc    includelib libname.libEndmuselib kernel32uselib user32inv equ invokemaxsize=60  ; max width of answers.data?hout dd ?nout dd ?ncnt dd ?cary db ?.dataval1 db maxsize-1 dup (" "),"1",13,10,0val2 db maxsize-1 dup (" "),"1",13,10,0val3 db maxsize-1 dup (" "),"0",13,10,0.codeProgram:    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,0End Program`
very quick and dirty, can be cleaned up a lot :)

#### jack

• Regular Member
• Posts: 19
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #6 on: July 07, 2018, 04:04:17 AM »
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

• Member
• Posts: 866
• Eagles are just great!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #7 on: July 07, 2018, 04:16:20 AM »
Thanks raymond i will check that tutorial for sure. Hey jimg, that looks great, nice work.

Felipe.

#### felipe

• Member
• Posts: 866
• Eagles are just great!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #8 on: July 07, 2018, 09:49:30 AM »
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  ). This version can easily produce the first 100 fibonacci numbers in the file as can be seen here:

Code: [Select]
`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.
Felipe.

#### raymond

• Member
• Posts: 199
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #9 on: July 07, 2018, 11:40:32 AM »
If we start the series with F1= 1 and F2=1, then F3=2, etc.
F93=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 Fn is reached.

BTW, F476 is the first one to contain 100 digits.

Code: [Select]
`;           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" numberstart1:      mov   ecx,digits        ;use as counter for number of additions      xor   edx,edx           ;offset into the two numbersstart2:      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,0end start`
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

#### felipe

• Member
• Posts: 866
• Eagles are just great!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #10 on: July 07, 2018, 12:43:31 PM »
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  . Thanks for telling me that and for your help with that code. I will study the code soon as i can.

Felipe.

#### raymond

• Member
• Posts: 199
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #11 on: July 07, 2018, 01:41:03 PM »
Quote
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.
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

#### daydreamer

• Member
• Posts: 465
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #12 on: July 07, 2018, 06:47:46 PM »
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
Quote from Flashdance
Nick  :  When you give up your dream, you die.
*wears a flameproof asbestos suit*

#### felipe

• Member
• Posts: 866
• Eagles are just great!
##### Re: Fibonacci numbers: the nature's numbers...
« Reply #13 on: July 08, 2018, 06:22:56 AM »
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.

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

Felipe.