Fibonacci numbers: the nature's numbers...

[felipe]

Nice siekmanski  :icon14:. But i find the name of the instruction a little misleading since what it supposed to do is:

Temporary = Source + Destination;
Source = Destination;
Destination = Temporary;

So maybe a good name for the instruction will be: "add and exchange".  :idea:

If we exchange and then we add we have eax=1 forever...

Code Select Expand


temporary=destination;
destination=source;
source=temporary;
destination=source+destination;


Should we report this to intel?  :P

What do you think? 

[Siekmanski]

I think, the operation goes like this:

Temp = Source
Source = Destination    ; Exchange
Destination = Destination + Temp ; Add

[daydreamer]

This fibonnaci numbers, task seems to be used often in programming classes,so this thread would be a gem for students felipe  :t
Curious why you got the idea to start program fibonnaci?, earlier experience from school,or just randomly picked project?
Wonder if it's possible to use two or more calculations, first calculate starts from the very beginning in one part of xmm register second one in second part of xmm reg starts with big fibonnaci number about in the middle of 32bit integer range?

[felipe]

Siekmanski of course, you are a genius!  If you can improve algorithms then you can improve code surely.  :t

Magnus i was inspired from a  video on youtube about mathematics (I think the name of the documentary is "the mystery of mathematics")  :idea:.
I had before saw the fibonacci algorithm in some book, some 2 years before (approximately)  like an interesting exercise. It was no more than the operation with the add and exchange (well, exchange and add  ), but using 16 bits registers. I think the name of the book is something like "assembly programming for the ibm pc" or similar  :P.
I was thinking also (in the moment of writing this) in write something using a file  :idea:.
I still don't learn almost anything about sse instruction sets  :redface:.

[zedd151]

math is fun.

But how many primes are in the fibonacci sequence?   :P

Nice little exercise felipe!
I only tried the 32 bit version as I am anti-64 bit (anti change) lol.

Just for kicks, I fired up Windows 10-64 and ran the 64 bit version.

Have you made changes to ensure better accuracy? Siekmanski has some really good ideas.

[felipe]

Infinities of them...

Zedd maybe you should try to make a mix of the raymond algorithm (used in part by jimg too) and mine (or jimg if you want to put the results in the console and not in a file)  :idea:. How about that math challenge?  :icon14:
What i really like of raymond suggested algorithm is that you can reach long size numbers, which looks funny  :icon14:.
As you can see with what i wrote the numbers in some point (not to far from the start) overflow the registers, so the next numbers in the sequence are not correct  :idea:.

[zedd151]

I'll leave that to the math/algebra experts felipe.  Maybe Magnus can come up with something. He's always popping up with suggestions but not posting any code. Come on Magnus, show us what you got.   

[FORTRANS]

Hi,

   Back in February of 2010, I posted a Fibonacci number program
in the 16-bit subforum.  It used the BCD opcodes to generate
numbers up to 72 digits.  More of a learning excursion than
anything else.  Had to make the BCD instructions work as intended.

Cheers,

Steve N.

[jimg]

Not sure what you are asking for.
Here is where I quit playing around, writes to console.
Absolutely accurate.  Just set max size to whatever you want.

[zedd151]

Thats pretty good, Jim.

I printed it to text using ec.exe > fibo.txt
its right aligned so you have to scroll to the right. Open with qeditor works well.

ends with F954 and length of that string is 200 characters.
Nice clear, concise code. Heres a disassembly of the code using olly...

Code Select Expand


00401000 e>/$  6A F5                                                PUSH -0B                                               ; /DevType = STD_OUTPUT_HANDLE
00401002   |.  E8 25010000                                          CALL <JMP.&kernel32.GetStdHandle>                      ; \GetStdHandle
00401007   |.  A3 70324000                                          MOV DWORD PTR DS:[403270],EAX                          ;  kernel32.BaseThreadInitThunk
0040100C   |.  6A 00                                                PUSH 0                                                 ; /pOverlapped = NULL
0040100E   |.  68 74324000                                          PUSH ec.00403274                                       ; |pBytesWritten = ec.00403274
00401013   |.  68 CB000000                                          PUSH 0CB                                               ; |nBytesToWrite = CB (203.)
00401018   |.  68 00304000                                          PUSH ec.00403000                                       ; |Buffer = ec.00403000
0040101D   |.  FF35 70324000                                        PUSH DWORD PTR DS:[403270]                             ; |hFile = NULL
00401023   |.  E8 10010000                                          CALL <JMP.&kernel32.WriteFile>                         ; \WriteFile
00401028   |.  6A 00                                                PUSH 0                                                 ; /pOverlapped = NULL
0040102A   |.  68 74324000                                          PUSH ec.00403274                                       ; |pBytesWritten = ec.00403274
0040102F   |.  68 CB000000                                          PUSH 0CB                                               ; |nBytesToWrite = CB (203.)
00401034   |.  68 CC304000                                          PUSH ec.004030CC                                       ; |Buffer = ec.004030CC
00401039   |.  FF35 70324000                                        PUSH DWORD PTR DS:[403270]                             ; |hFile = NULL
0040103F   |.  E8 F4000000                                          CALL <JMP.&kernel32.WriteFile>                         ; \WriteFile
00401044   |.  60                                                   PUSHAD
00401045   |.  8D35 00304000                                        LEA ESI,DWORD PTR DS:[403000]
0040104B   |.  8D3D CC304000                                        LEA EDI,DWORD PTR DS:[4030CC]
00401051   |.  8D2D 98314000                                        LEA EBP,DWORD PTR DS:[403198]
00401057   |.  C705 78324000 03000000                               MOV DWORD PTR DS:[403278],3
00401061   |>  B9 C8000000                                          /MOV ECX,0C8
00401066   |.  C605 7C324000 00                                     |MOV BYTE PTR DS:[40327C],0
0040106D   |>  B8 00000000                                          |/MOV EAX,0
00401072   |.  8A0431                                               ||MOV AL,BYTE PTR DS:[ECX+ESI]
00401075   |.  8A1439                                               ||MOV DL,BYTE PTR DS:[ECX+EDI]
00401078   |.  3C 20                                                ||CMP AL,20
0040107A   |.  75 02                                                ||JNZ SHORT ec.0040107E
0040107C   |.  B0 30                                                ||MOV AL,30
0040107E   |>  02C2                                                 ||ADD AL,DL
00401080   |.  0205 7C324000                                        ||ADD AL,BYTE PTR DS:[40327C]
00401086   |.  2C 30                                                ||SUB AL,30
00401088   |.  C605 7C324000 00                                     ||MOV BYTE PTR DS:[40327C],0
0040108F   |.  3C 39                                                ||CMP AL,39
00401091   |.  76 09                                                ||JBE SHORT ec.0040109C
00401093   |.  C605 7C324000 01                                     ||MOV BYTE PTR DS:[40327C],1
0040109A   |.  2C 0A                                                ||SUB AL,0A
0040109C   |>  880429                                               ||MOV BYTE PTR DS:[ECX+EBP],AL
0040109F   |.  49                                                   ||DEC ECX
004010A0   |.  74 72                                                ||JE SHORT ec.00401114
004010A2   |.  803C39 20                                            ||CMP BYTE PTR DS:[ECX+EDI],20
004010A6   |.  75 0F                                                ||JNZ SHORT ec.004010B7
004010A8   |.  803D 7C324000 00                                     ||CMP BYTE PTR DS:[40327C],0
004010AF   |.  74 04                                                ||JE SHORT ec.004010B5
004010B1   |.  C60429 31                                            ||MOV BYTE PTR DS:[ECX+EBP],31
004010B5   |>  EB 02                                                ||JMP SHORT ec.004010B9
004010B7   |>^ EB B4                                                |\JMP SHORT ec.0040106D
004010B9   |>  6A 00                                                |PUSH 0                                                ; /pOverlapped = NULL
004010BB   |.  68 74324000                                          |PUSH ec.00403274                                      ; |pBytesWritten = ec.00403274
004010C0   |.  68 C9000000                                          |PUSH 0C9                                              ; |nBytesToWrite = C9 (201.)
004010C5   |.  55                                                   |PUSH EBP                                              ; |Buffer = 0012FF94
004010C6   |.  FF35 70324000                                        |PUSH DWORD PTR DS:[403270]                            ; |hFile = NULL
004010CC   |.  E8 67000000                                          |CALL <JMP.&kernel32.WriteFile>                        ; \WriteFile
004010D1   |.  FF35 78324000                                        |PUSH DWORD PTR DS:[403278]                            ; /<%li> = 0
004010D7   |.  68 61324000                                          |PUSH ec.00403261                                      ; |Format = " %li\r\n"
004010DC   |.  68 7D324000                                          |PUSH ec.0040327D                                      ; |s = ec.0040327D
004010E1   |.  E8 58000000                                          |CALL <JMP.&user32.wsprintfA>                          ; \wsprintfA
004010E6   |.  83C4 0C                                              |ADD ESP,0C
004010E9   |.  6A 00                                                |PUSH 0                                                ; /pOverlapped = NULL
004010EB   |.  68 74324000                                          |PUSH ec.00403274                                      ; |pBytesWritten = ec.00403274
004010F0   |.  50                                                   |PUSH EAX                                              ; |nBytesToWrite = 779E3C33 (2006858803.)
004010F1   |.  68 7D324000                                          |PUSH ec.0040327D                                      ; |Buffer = ec.0040327D
004010F6   |.  FF35 70324000                                        |PUSH DWORD PTR DS:[403270]                            ; |hFile = NULL
004010FC   |.  E8 37000000                                          |CALL <JMP.&kernel32.WriteFile>                        ; \WriteFile
00401101   |.  8BC6                                                 |MOV EAX,ESI
00401103   |.  8BF7                                                 |MOV ESI,EDI
00401105   |.  8BFD                                                 |MOV EDI,EBP
00401107   |.  8BE8                                                 |MOV EBP,EAX                                           ;  kernel32.BaseThreadInitThunk
00401109   |.  FF05 78324000                                        |INC DWORD PTR DS:[403278]
0040110F   |.^ E9 4DFFFFFF                                          \JMP ec.00401061
00401114   |>  61                                                   POPAD
00401115   |.  68 A0860100                                          PUSH 186A0                                             ; /Timeout = 100000. ms
0040111A   |.  E8 13000000                                          CALL <JMP.&kernel32.Sleep>                             ; \Sleep
0040111F   |.  6A 00                                                PUSH 0                                                 ; /ExitCode = 0
00401121   \.  E8 00000000                                          CALL <JMP.&kernel32.ExitProcess>                       ; \ExitProcess


Thats the disassembly from olly. Looks like it could easily be modified to write directly to file if needed.

heres the printout of the first 100 (I removed the right alignment, to save space here)

Code Select Expand


0 0
1 1
1 2
2 3
3 4
5 5
8 6
13 7
21 8
34 9
55 10
89 11
144 12
233 13
377 14
610 15
987 16
1597 17
2584 18
4181 19
6765 20
10946 21
17711 22
28657 23
46368 24
75025 25
121393 26
196418 27
317811 28
514229 29
832040 30
1346269 31
2178309 32
3524578 33
5702887 34
9227465 35
14930352 36
24157817 37
39088169 38
63245986 39
102334155 40
165580141 41
267914296 42
433494437 43
701408733 44
1134903170 45
1836311903 46
2971215073 47
4807526976 48
7778742049 49
12586269025 50
20365011074 51
32951280099 52
53316291173 53
86267571272 54
139583862445 55
225851433717 56
365435296162 57
591286729879 58
956722026041 59
1548008755920 60
2504730781961 61
4052739537881 62
6557470319842 63
10610209857723 64
17167680177565 65
27777890035288 66
44945570212853 67
72723460248141 68
117669030460994 69
190392490709135 70
308061521170129 71
498454011879264 72
806515533049393 73
1304969544928657 74
2111485077978050 75
3416454622906707 76
5527939700884757 77
8944394323791464 78
14472334024676221 79
23416728348467685 80
37889062373143906 81
61305790721611591 82
99194853094755497 83
160500643816367088 84
259695496911122585 85
420196140727489673 86
679891637638612258 87
1100087778366101931 88
1779979416004714189 89
2880067194370816120 90
4660046610375530309 91
7540113804746346429 92
12200160415121876738 93
19740274219868223167 94
31940434634990099905 95
51680708854858323072 96
83621143489848422977 97
135301852344706746049 98
218922995834555169026 99
354224848179261915075 100


Now we need a sieve to test for prime   :icon_mrgreen:

Then we end up with a fibo-prime listing.   8)

[zedd151]

With a slight modification to jimg's code we can assemble using qeditor "console assemble and link"

Code Select Expand



include \masm32\include\windows.inc

uselib Macro libname:req
    include    \masm32\include\libname.inc
    includelib \masm32\lib\libname.lib
Endm



Helps for when you don't have WinAsm installed.

I tried it with maxsize=2000    
later :
But it only printed out up to char length=1000, F=4782   :(    <-- nevermind, I forgot to assemble & link. It works perfectly

  :t

for maxsize=10000, filesize is 456 MB  :shock:
still waiting to read file into qeditor.  8)

for maxsize=10000, F=47847 Thats a long number.
I won't post it here though.  ;)

in qeditor, the maximum line length appears to be 3071 chars (probably the limits of the rich edit control) so the results for maxsize=10000
are split into four lines. I won't check it manually for accuracy, I'll just have to trust the algo.   :P

I can see some benchmark tests over the horizon for the fastest fibonacci algo.   
I just installed (again) Windows 7 64 bit, now might be a good time to try coding with ml64.   :icon_mrgreen:

[zedd151]

Now I remember where I did something similar. It never really worked out though. ascii adder

It was supposed to read strings of ascii numbers (not hex)
Then add them together. I tried to recall yesterday, but memory fails.

[zedd151]

I should have made the program strip the leading zeros, but I have a little proggy that can do that...

Code Select Expand


    include \masm32\include\masm32rt.inc
    OpenFilex proto :dword
    SaveFilex proto :dword
    LoadFilex proto :dword
    WriteFilex proto :dword, :dword, :dword
   
    zStrLen proto :dword
   
    .data
    str1 dd 0
    str2 dd 0
    hWnd dd 0
    hInstance dd 0
    infile db 128 dup (0)
    outfile db 128 dup (0)
   
    inbuf dd 0
    insize dd 0
   
    .code
    start:
    invoke OpenFilex, addr infile
    invoke LoadFilex, eax
   
    mov inbuf, esi
    mov insize, ecx
    xor eax, eax
    xor edx, edx
   
    top1:
    mov cl, byte ptr [esi+edx]
   
    cmp cl, 0
    jz done1
   
    cmp cl, "0"
    jnz writeit
   
    iszero:
   
    cmp byte ptr [esi+edx], "0"
    jnz writeit
   
    inc edx
    jmp iszero
    writeit:
    mov cl, byte ptr [esi+edx]
    cmp cl, 0Dh
    jz crlf1
    mov byte ptr [esi+eax], cl
    inc eax
    inc edx
    cmp edx, insize
    jge done1
    jmp writeit
   
   
    crlf1: ; special case, write two bytes
    mov byte ptr [esi+eax], cl
    inc eax
    inc edx
    cmp edx, insize
    jge done1
    mov cl, byte ptr [esi+edx]
    mov byte ptr [esi+eax], cl
    inc eax
    inc edx
    cmp edx, insize
    jge done1
    jmp top1
    done1:
   
    mov byte ptr [esi+eax], 0
    invoke zStrLen, esi
   
    push eax
    push esi
    invoke SaveFilex, addr outfile
    pop esi
    pop eax
    invoke WriteFilex, addr outfile, esi, eax
    invoke GlobalFree, inbuf
    invoke ExitProcess, 0
   
    OpenFilex proc FileBuffer:DWORD
    LOCAL ofn:OPENFILENAME
        .data
        lpOpen db "Open File", 0
        lpSave db "Save File", 0
        lpFilter db "All Files", 0, "*.*", 0, 0
        .code
        mov eax, FileBuffer
        mov BYTE PTR [eax], 0
        push edi
        mov ecx, sizeof OPENFILENAME
        mov al, 0
        lea edi, ofn
        rep stosb
        pop edi
        mov ofn.lStructSize,    sizeof OPENFILENAME
        m2m ofn.hWndOwner,      hWnd
        m2m ofn.hInstance,      hInstance
        m2m ofn.lpstrFilter,    offset lpFilter
        m2m ofn.lpstrFile,      FileBuffer
        mov ofn.nMaxFile,       240h
        m2m ofn.lpstrTitle,     offset lpOpen
        mov ofn.Flags,          OFN_EXPLORER or OFN_FILEMUSTEXIST or OFN_LONGNAMES
        invoke GetOpenFileName,ADDR ofn
        mov eax, FileBuffer
        ret
    OpenFilex endp
   
    SaveFilex proc FileBuffer:DWORD
    LOCAL ofn:OPENFILENAME
        mov eax, FileBuffer
        mov BYTE PTR [eax], 0
        push edi
        mov ecx, sizeof OPENFILENAME
        mov al, 0
        lea edi, ofn
        rep stosb
        pop edi
        mov ofn.lStructSize,    sizeof OPENFILENAME
        m2m ofn.hWndOwner,      hWnd
        m2m ofn.hInstance,      hInstance
        m2m ofn.lpstrFilter,    offset lpFilter
        m2m ofn.lpstrFile,      FileBuffer
        mov ofn.nMaxFile,       240h
        m2m ofn.lpstrTitle,     offset lpSave
        mov ofn.Flags,          OFN_EXPLORER or OFN_LONGNAMES or OFN_HIDEREADONLY or OFN_OVERWRITEPROMPT
        invoke GetSaveFileName,ADDR ofn
        mov eax, FileBuffer
        ret
    SaveFilex endp
    LoadFilex proc lpName:DWORD
    LOCAL hFile:DWORD, fl:DWORD, bRead:DWORD, hMem$:DWORD
        invoke CreateFile,lpName,080000000h,1,NULL,3,NULL,NULL
        cmp eax, -1
        jne @F
        fn MessageBox,NULL,lpName,"Couldn't read File!",MB_OK
        xor eax, eax
        ret
        @@:
        mov hFile, eax
        invoke GetFileSize,hFile,NULL
        mov fl, eax
        invoke GlobalAlloc, GPTR, fl
        mov hMem$, eax      ; source file memory
        invoke ReadFile,hFile,hMem$,fl,ADDR bRead,NULL
        invoke CloseHandle,hFile
        mov eax, 1
        mov esi, hMem$
        mov ecx, fl
        ret
    LoadFilex endp
   
    WriteFilex proc lpName:DWORD,lpData:DWORD,fl:DWORD
    LOCAL hOutput:DWORD
    LOCAL bw     :DWORD
        invoke CreateFile,lpName,GENERIC_WRITE, FILE_SHARE_WRITE, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL
        cmp eax, -1
        jne @F
        fn MessageBox,NULL,lpName,"Couldn't Write File!",MB_OK
        xor eax, eax
        ret
        @@:
        mov hOutput, eax
        invoke WriteFile,hOutput,lpData,fl,ADDR bw,NULL
        invoke FlushFileBuffers,hOutput
        invoke CloseHandle,hOutput
        mov eax, 1
        ret
    WriteFilex endp
    zStrLen proc src:dword
        push esi
        push ecx
        mov esi, src
        xor eax, eax
    @@:
        mov cl, [esi]
        cmp cl, 0
        jz @f
        inc eax
        inc esi
        jmp @b
    @@:
        pop ecx
        pop esi
        ret
    zStrLen endp
end start


The only caveat with this program, it strips the very first zero, which is in fact supposed to be part of the Fibonacci sequence.   :(
I'll look at that when time permits.

[jack]

here's something you may not have known about the Fibonacci sequence https://www.futilitycloset.com/2015/06/28/made-to-order-4/
see also http://www.flyingcoloursmaths.co.uk/ask-uncle-colin-is-the-fibonacci-series-witchcraft/

[zedd151]

here's something you may not have known about the Fibonacci sequence...

Wow! That is so cool, Jack. Who would have thunk?
Thanks for the links.  :t

I think I'm going to need a better calculator to check the results.   :lol:

here's another Fibonacci Related Link
I don't believe everything I read on the internet, but it has entertainment value.