Fibonacci numbers: the nature's numbers...

[mineiro]

The Fibonacci sequence in my view was designed to tell the progression of rabbits, how many rabbits would be born. But looking better at nature, we can see paternities such as trees. The trees when they are growing have only one branch, then over the years if we imagine an imaginary horizontal line from the first branch we will have two, and so on. Fibonacci responds to some branches of trees.

[zedd151]

Small addition to my fibonacci generator. We now have the leading zeroes/spaces removed.

Code Select Expand


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;                                                                                      ;;
;;      ;-------------------------------------------------------------------------------;;
;;      ; Program to output a Fibonacci sequence of any length in the command window    ;;
;;      ;;; ----   can also print to file: "fiboz.exe > fibonacci.txt"                  ;;
;;      ;-------------------------------------------------------------------------------;;
;;      ; following the forumla "F = (F-1) + (F-2)"                                     ;;
;;      ;-----------------------------------------                                      ;;
;;      ; where F is the Fibonacci number being calculated                              ;;
;;      ; F-1 is the Fibonacci number just before that                                  ;;
;;      ; F-2 is the Fibonacci number before F-1                                        ;;
;;      ;-------------------------------------------------------------------------------;;
;;      ; credits: jimg for an excellent algo,                                          ;;
;;      ; felipe for inspiring me to finish my 'ascii adder' routine                    ;;
;;      ;-------------------------------------------------------------------------------;;
;;      ; Fair Warning! The output file can get extremely large very fast!              ;;
;;      ; example for finacci final length of 58000 the output file was                 ;;
;;      ; 7.49 GB is size! And that is with the leading zeroes/ spaces removed!         ;;
;;      ;-------------------------------------------------------------------------------;;
;;                                                                                      ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   
        include \masm32\include\masm32rt.inc
        ascii_adder proto :dword, :dword, :dword, :dword
        TrimZero proto :dword, :dword
       
    .data
       
        maxsize dd 100 ; max length of fibonacci string
       
        pval1   dd 0
        pval2   dd 0
        pval3   dd 0
        tmpbuf  dd 0
        ctrx    dd 0
       
    .code
        Program:
        pushad
        inc maxsize ; for auto zero termination
        invoke GlobalAlloc, GPTR, maxsize
        mov pval1, eax
        invoke GlobalAlloc, GPTR, maxsize
        mov pval2, eax
        invoke GlobalAlloc, GPTR, maxsize
        mov pval3, eax
       
        invoke GlobalAlloc, GPTR, maxsize ; <-- extra buffer added for the procedure
        mov tmpbuf, eax                   ; --- that removes the leading zeros.
       
        dec maxsize ; reset maxsize to original
       
        mov esi, pval1  ; previous val
        mov edi, pval2  ; previous val
        mov ebx, pval3  ; new val
       
        xor ecx, ecx
    @@:
        mov byte ptr [esi+ecx], 30h ; fill the buffers with "0"
        mov byte ptr [edi+ecx], 30h
        mov byte ptr [ebx+ecx], 30h
        inc ecx
       
    cmp ecx, maxsize                ; loop til buffers filled
    jnz @b
   
        mov byte ptr [edi+ecx-1], 31h ; insert the first digit otherwise we will be adding '0+0'   lol
       
        mov esi, pval1  ; put the buffer addresses into registers
        mov edi, pval2
        mov ebx, pval3
       
    above:
   
        invoke ascii_adder, esi, edi, ebx, maxsize ; call my little proc :)
       
        mov eax, esi  ; jimg's switcherooo register voodoo
        mov esi, edi
        mov edi, ebx
        mov ebx, eax
        cmp ctrx, 0   ; check if this counter is zero, if so we keep the ascii "0"
        jz @f         ; all other fibonacci strings wil have the leading zeros removed.
        push ebx
        invoke TrimZero, ebx, tmpbuf
        print tmpbuf, 0Dh, 0Ah
        pop ebx
        jmp ahead

        @@:
        inc ctrx
        print "0", 0Dh, 0Ah  ; for the first digit (zero) - otherwise the
                             ; proc that removes leading zeros will erase it.
        ahead:
        cmp byte ptr [ebx], "0"  ; check if we are done
        jz above
       
        invoke GlobalFree, pval1 ; free the memory
        invoke GlobalFree, pval2
        invoke GlobalFree, pval3
        invoke GlobalFree, tmpbuf
       
        popad
        invoke ExitProcess, 0   ; hasta la vista, baby
       
    ascii_adder proc src1:dword, src2:dword, dst:dword, lent:dword  ;   :D
    local carrie:dword
        push esi
        push edi
        push ebx
        mov esi, src1
        mov edi, src2
        mov ebx, dst
        mov ecx, lent
        mov carrie, 0
        top:
            mov eax,0
            mov al,byte ptr [esi+ecx-1]
            mov dl,byte ptr [edi+ecx-1]
            add al,dl
            sub al, 30h
            add eax, carrie
            mov carrie, 0
            cmp al, 39h
           
            jbe @f ; pseudo carry flag
                mov carrie, 1
                sub al, 10
            @@:
           
            mov [ebx+ecx-1], al
            dec ecx
            cmp ecx, 0
        jnz top
        pop ebx
        pop edi
        pop esi
        ret
    ascii_adder endp

    TrimZero proc src:dword, dst:dword ; added this proc to remove leading zeroes.
        push esi
        push edi
        mov esi, src
        mov edi, dst
        xor eax, eax
        xor ecx, ecx
        testlin:
        mov dl, [esi+eax]
        cmp dl, 0
        jz done
        cmp dl, 0Dh
        jz crlf
        cmp dl, 0Ah
        jz crlf
        cmp dl, 30h
        jz zero
        jmp copyall
        zero:
        inc eax
        mov dl, [esi+eax]
        cmp dl, 0
        jz done
        cmp dl, 30h
        jz zero
        cmp dl, 0Dh
        jz crlf
        cmp dl, 0Ah
        jz crlf
        jmp copyall
        crlf:
        mov dl, [esi+eax]
        mov [edi+ecx], dl
        inc eax
        inc ecx
        mov dl, [esi+eax]
        cmp dl, 0
        jz done
        cmp dl, 30h
        jz zero
        cmp dl, 0Dh
        jz crlf
        cmp dl, 0Ah
        jz crlf
        copyall:
        mov dl, [esi+eax]
        cmp dl, 0
        jz done
        cmp dl, 0Dh
        jz crlf
        cmp dl, 0Ah
        jz crlf
        mov [edi+ecx], dl
        inc eax
        inc ecx
        jmp copyall
        done:
        pop edi
        pop esi
        ret
    TrimZero endp
       
        End Program



The Fibonacci sequence in my view was designed to tell the progression of rabbits,

Or Humans! 

[daydreamer]

tested first with highlevel and I subconciusly unrolled it 2 fibonnaci/loop
I have yet to solve the printmacro

Code Select Expand

mov eax,cs:fibo1
    mov edx,0
    mov ebx,cs:fibo2
    mov ecx,0
    mov esi,0
    mov edi,0
    mov ebp,0
    mov esp,0
    loop1:
    pmac ;printmacro for 2 fibonacci numbers
    add eax,ebx ;32bit
    adc edx,ecx ;64bit
    adc esi,edi ;96bit
    adc ebp,esp ;128bit
    ;jc l2
   
    add ebx,eax ;unrolled addition
    adc ecx,edx
    adc edi,esi
    adc esp,ebp
   ; jc l2
   
    dec cs:lvar ;run thru 4giga
    jne loop1
    ;or stop when overflow of 128bit is met
    l2: ;abort when overflow has happened
   



and find right conditional jump to exit loop when overflow happens

[daydreamer]

I was also thinking about fibonnacci will be not limited by computer memory,keep 2 fibonnaci numbers stored in compressed form for each page you can display in Textarea and make them generate them Just In Time
here is my original code,dont know why I subconciusly unrolled it the first time I made it

Code Select Expand

program fibonnac
clrhome
1->C
2->D
for(B,0,1000)
Disp B,C,D
D+C->C
C+D->D
end
;end=end of forloop
1->C, is reverse way of type C=1
after 238*2
3.5205211795e99
5.696323923e99 it stopped the program because of overflow

[zedd151]

1->C, is reverse way of type C=1

Reminds me of TI-Basic.  1-->C,  yes.   8)

or 'sto' from another calc.    :P

I never did understand fully, 'for' loops, and exactly how they work.

.ifs and .whiles are easy. How would a 'for'  loop translate to asm?

[FORTRANS]

Hi,

I never did understand fully, 'for' loops, and exactly how they work.

.ifs and .whiles are easy. How would a 'for'  loop translate to asm?

   Well, for a "FOR" loop up to a few thousand, the following code
is roughly what would work.

Code Select Expand

; FOR X = 1 TO 9

;data
Xvar    DW      ?

;code

        MOV     [Xvar],1        ; Top of loop
ForLab:
        ; Your code?  It can use Xvar, but not change it.

        INC     [Xvar]
        CMP     WORD PTR [Xvar],9
        JB      ForLab          ; End of loop


HTH,

Steve N.

Edit
Correction JNZ => JB , it would have terminated at 8.
Added usage comment.

SRN

[zedd151]

Thanks Steve, that is pretty simple code, just the way I like it.  :t

I have seen the notation, 'for i, 1, x' or something similar but never really 'got it'  :icon_confused:

I probably write 'for' loops all the time without knowing they are 'for' loops.   8)

[Mikl__]

Binet's formula and fast exponentiation

Code Select Expand

N equ 26
.data
buffer db 50 dup(?)
format db "%u",0
caption db "Fibonacci",0
const0_5 dd 0.5
k dd ?
inverse_square_root_from_five dd 0.44721359549995793928183473374626;=1/sqrt(5)
x dd 1.6180339887498948482045868343656;=(1+sqrt(5))/2
.code
start: fninit
fld inverse_square_root_from_five ;st=0.44721359549995793928183473374626
fld x                               ;st=1.6180339887498948482045868343656
mov ecx,N+1                ;st=1.618 st(1)=0.44721
@@: test ecx,1
jz a1
fmul st(1),st             
a1: fmul st,st
shr ecx,1
jnz @b    
fstp st      
fistp k                         ;k=int(((1.62)^N)/sqrt(5))
invoke wsprintf,addr buffer,addr format,k
add esp,4*3
invoke MessageBox,0,addr buffer,addr caption,MB_OK
invoke ExitProcess,NULL
end start

[daydreamer]

Looks very fast mikl
Zedd, forloop is so BASIC loop
Assembly its seem more common with countdown to zero loops dec/sub loop counter+ jne loop

[hutch--]

Loops with fixed iteration counts vary only at which end the evaluation takes place.

Bottom evaluate

  lbl0:
    ; do something
    sub cntr, 1
    jnz lbl0                    ; <<<< fixed here.  :redface:


Top evaluate

    jmp evalhere
  lbl1:
    ; do something
  evalhere:
    sub cntr, 1
    jnz lbl1

[zedd151]

Code Select Expand


Bottom evaluate

  lbl0:
    ; do something
    sub cntr, 1
    jnz lbl1  >-------->
                        |
                        |
Top evaluate            |
                        |
    jmp evalhere        |
  lbl1: <--------------<
    ; do something
  evalhere:
    sub cntr, 1
    jnz lbl1

Must be late in the day.   :icon_mrgreen:
Apparently I write 'for' loops all the time, without knowing they are 'for' loopz.
I have been moving away  from using '.if' blocks as well, (unless a fairly complex statement) I prefer manually coding the jumps, etc.

for i, 1, 10  yuk.   ::)

[hutch--]

.if blocks come into their own when you have to have nested conditional testing, it can be done with compares, jumps and labels but it becomes very messy with multiple depth testing as you need to be very creative with the number of unique labels you need to use.

[daydreamer]

Loops with fixed iteration counts vary only at which end the evaluation takes place.

Bottom evaluate

  lbl0:
    ; do something
    sub cntr, 1
    jnz lbl0                    ; <<<< fixed here.  :redface:


Top evaluate

    jmp evalhere
  lbl1:
    ; do something
  evalhere:
    sub cntr, 1
    jnz lbl1

but whats best for innerloop counters/outerloop counters?, I have seen examples using ecx for both,with help of push/pop
and 8bits you had very few registers,so dec/inc memory location was used sometimes,especially 6502,because its way of indirect adressing
or the use of one long innerloop,with AND 1023 to get x coordinate in a 1024'768 resolution or 1024*1024 texture

zedd:forloop could as well be a while not zero etc coded in High language and compiler produces the same code in assembler

[hutch--]

Magnus,

You should know the answer to simple stuff like this. Use a register if you can, a memory operand if you can't. If you have to choose, use the register for the loop that gets hit the hardest which in your case is the inner loop but also remember that there are far more loop designs than simple nested loops, try multi cross fire loops.

[jj2007]

I have seen examples using ecx for both,with help of push/pop

Like this? Attention, if you have more than ten million iterations or so, it might be a bit slower than using a register...

Code Select Expand

include \masm32\include\masm32rt.inc

.code
start:
  loopsrequested=20
  push loopsrequested-1
  .Repeat
print "*"
dec dword ptr [esp]
  .Until Sign?
  pop edx
  inkey " - that was easy, right?"
  exit

end start