flat assembler
Message board for the users of flat assembler.

Index > Windows > fibonachi numbers, need help

Author
Thread Post new topic Reply to topic
jacko221



Joined: 12 Nov 2005
Posts: 22
jacko221 12 Feb 2006, 09:39
Hi everyone. Basically i want to learn assembler to make small applications and dll files to implement with other languages. And i thought a good way to learn and program in it is to try and complete a programming challenge. So i decided to attempt this Fibonachi challenge which i have done successfully in C. I've been trying for 3 hours to get it done in Flat assembler (which i have been learning for 2 days roughly) but no luck. So here is my source of the working version in C:

Code:
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int j = 0;
  int k = 1;
  int i = 0;
  int userInputInteger;

start: //main application loop
  printf("please enter a number: \n"); //prompts for user input 
  scanf("%d", &userInputInteger); //adds input to integer
  
  while(1 == 1) // infinite loop
  {
          //the Fibonachi 
          j = i; 
          i = k;
          k = j + i;
                 
          if(k == userInputInteger) //is it a Fibonachi number?
          {
              printf("yes it is\n");
              break;
          }    
  
            else if(k > userInputInteger) //no it isn't
          {
              printf("No it isn't\n");
              break;
          }  
          
  }     
  
  //clear variables to original state
  j = 0;
  k = 1;
  i = 0;
  
  goto start;   //goto start (which is beginning of loop
  return 0;
}
    


yes it could have been done better but it works. The following is my attempt in Flat assembler:

Code:
include 'F:\FASM\INCLUDE\win32ax.inc'


section '.data' data readable writeable

import user32,\
        MessageBox,'MessageBoxA'

 import kernel32,\
        ExitProcess,'ExitProcess'


section '.code' code readable writeable

regInt:
mov eax, 0 ;i
mov ebx, 0 ;j
mov ecx, 1 ;k


notmate:
mov ebx, eax ; j = i
mov eax, ecx ; i = k
push ebx ; put j onto stack
add ebx, eax ; add j with i
mov ecx, ebx ; copy j to k
xor bx, bx ; clear j
pop bx      ; give j back its original value
cmp ecx, 5 ; using five instead because i dont know how to get user input
je start
loop notmate

start:
        invoke  MessageBox,HWND_DESKTOP,"Hi! I'm the example program!","Win32 Assembly",MB_OK
        invoke  ExitProcess,0
    


im wondering if anybody could tell me what i have done wrong and explain or give me any tips on making it better.

Thanks heaps, Jack
Post 12 Feb 2006, 09:39
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 12 Feb 2006, 10:40
Check the comments:
Code:
include 'win32ax.inc'
entry start ;This tells FASM where to put the  entrypoint
;Otherwise the program will crash and say something like:
;"Module "fib" has entry point outside the code (as specified in the PE header)...."

section '.idata' import readable ; This section must be IMPORT and
;can only be readable, because you don't need to write to it.

library user32,'user32.dll',kernel32,'kernel32.dll' ;You need to tell what the
;user- and kernel- 32s represent.

import user32,\
        MessageBox,'MessageBoxA'

 import kernel32,\
        ExitProcess,'ExitProcess'

section '.code' code readable executable ; Code should not be writable
;and it MUST be executable. It can be readable.

start:
        invoke  MessageBox,HWND_DESKTOP,"Hi! I'm the example program!","Win32 Assembly",MB_OK
        invoke  ExitProcess,0

regInt:
mov eax, 0 ;i
mov ebx, 0 ;j
mov ecx, 1 ;k


notmate:
mov ebx, eax ; j = i
mov eax, ecx ; i = k
push ebx ; put j onto stack
add ebx, eax ; add j with i
mov ecx, ebx ; copy j to k
xor bx, bx ; clear j
pop bx      ; give j back its original value
cmp ecx, 5 ; using five instead because i dont know how to get user input
je start
loop notmate
    

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 12 Feb 2006, 10:40
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
polygon7



Joined: 14 Aug 2003
Posts: 62
Location: Poznan, Poland
polygon7 12 Feb 2006, 10:57
jacko221 wrote:

Code:
include 'F:\FASM\INCLUDE\win32ax.inc'
section '.data' data readable writeable

import user32,\
        MessageBox,'MessageBoxA'

 import kernel32,\
        ExitProcess,'ExitProcess'


section '.code' code readable writeable

regInt:
mov eax, 0 ;i
mov ebx, 0 ;j
mov ecx, 1 ;k


notmate:
mov ebx, eax ; j = i
mov eax, ecx ; i = k
push ebx ; put j onto stack
add ebx, eax ; add j with i
mov ecx, ebx ; copy j to k
xor bx, bx ; clear j
pop bx      ; give j back its original value
cmp ecx, 5 ; using five instead because i dont know how to get user input
je start
loop notmate

start:
        invoke  MessageBox,HWND_DESKTOP,"Hi! I'm the example program!","Win32 Assembly",MB_OK
        invoke  ExitProcess,0
    


im wondering if anybody could tell me what i have done wrong and explain or give me any tips on making it better.

Thanks heaps, Jack


Code:
; You should define format of your program (PE = Windows executable)
format PE
; entry point of program
entry start

; code section must be executable
section '.code' code readable executable

start:
xor eax, eax ;i
mov ebx, eex ;j
mov edx, 1 ;k
mov ecx,5; How many times?

notmate:
mov ebx, eax                ; j = i
mov eax, edx                ; i = k

; don't push "bx" when you make program for Win32
push ebx                       ; put j onto stack

add ebx, eax                  ; add j with i
mov edx, ebx                ; copy j to k

;; Edit2: xor is not needed, becouse pop overwrites ebx value
;; ; xor "ebx" instead "bx"
;;  xor ebx, ebx                 ; clear j

pop ebx                         ; give j back its original value
dec ecx
jnz notmate

ret; when stack is clean ret == ExitProcess

    


//Edit: Madis731 was faster Razz

_________________
best regards
p7
Post 12 Feb 2006, 10:57
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 12 Feb 2006, 15:04
Code:
; You should define format of your program (PE = Windows executable)
format PE
; entry point of program
entry start

; code section must be executable
section '.code' code readable executable

start:
  mov  eax, 1           ; n
  mov  ebx, 1           ; n-1

  mov  ecx, 5           ; This is the user input

fibonacciIteration:
  mov  edx, ebx         ; n-2 = n-1
  mov  ebx, eax         ; n-1 = n

  lea  eax, [ebx+edx]   ; n = n-1 + n-2

; |EAX = n| |EBX = n-1| |EDX = n-2|
  cmp  eax, ecx
  jb   fibonacciIteration

  je   isFibonacciNumber ; The flags remains untoched here so I can do this without comparing again

;### Here goes the code for a non Fibonacci number

  jmp  exit

isFibonacciNumber:
; ### Here goes the code for a Fibonacci number

exit:
  ret; when stack is clean ret == ExitProcess 
    


Not sure if it's faster than the others but at least it's short and clear Razz

Edit: This chunk maybe is faster than the code above since I remove a little register dependence
Code:
start:
  mov  eax, 1           ; n
  mov  ecx, 5           ; This is the user input

  mov  ebx, eax         ; n-1
  mov  edx, eax         ; n-2

fibonacciIteration:

  lea  eax, [ebx+edx]   ; n = n-1 + n-2

  mov  edx, ebx         ; n-2 = n-1
  mov  ebx, eax         ; n-1 = n

; |EAX = n| |EBX = n| |EDX = n-1|
  cmp  eax, ecx
  jb   fibonacciIteration

  je   isFibonacciNumber ; The flags remains untoched here so I can do this without comparing again    
Post 12 Feb 2006, 15:04
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 13 Feb 2006, 09:10
...yet another clever update, thank you locodelassembly:
Code:
format PE GUI
include 'win32a.inc'
entry start

section '.code' code readable executable

    start:
        stdcall fib,2971215073
        invoke  MessageBox,HWND_DESKTOP,[answer],title,MB_OK
        invoke  ExitProcess,0

    proc fib,fibnum
        mov     eax,1
        mov     ecx,[fibnum]
        cmp     ecx,0B11924E1h; 2971215073 - Last Fibonacci number in range
        ja      .earlyexit

        mov     esi,eax
        mov     edi,eax
      .fibiter:
        lea     eax,[esi+edi]
        mov     edi,esi
        mov     esi,eax
        cmp     eax,ecx
        jc      .fibiter
        je      .isfib
      .notfib:
        mov     [answer],answerNo
      .isfib:
        ret
      .earlyexit:
        mov     [answer],answerBig
        ret
    endp
section '.idata' import data readable writable

    library\
        user32,'user32.dll',\
        kernel32,'kernel32.dll'

    import user32,\
        MessageBox,'MessageBoxA'

    import kernel32,\
        ExitProcess,'ExitProcess'

    answer     dd answerYes
    answerYes  db "Yes, it is a Fibonacci number!",0
    answerNo   db "No, it is NOT a Fibonacci number!",0
    answerBig  db "Sorry, I can't figure out - too big!",0
    title      db "Win32 Assembly"
    


Last edited by Madis731 on 13 Feb 2006, 18:08; edited 2 times in total
Post 13 Feb 2006, 09:10
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
jacko221



Joined: 12 Nov 2005
Posts: 22
jacko221 13 Feb 2006, 10:48
thanks heaps for your help
Post 13 Feb 2006, 10:48
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 13 Feb 2006, 14:41
Madis731: That's true, computers don't agree with the mathematics idea of natural numbers goes to infinite Razz. However maybe is better to check first if the number is above or equal to the known limit. And of course maybe is better to use the non iterative way of fibonacci, unfortunately I don't remember the formula

Regards,
LocoDelAssembly
Post 13 Feb 2006, 14:41
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 13 Feb 2006, 17:50
Is it possible to know if number is Fibonacci's in O(n) time Neutral. Wow - I want that link...please try to remember it...thanks!
>>Updated code above according to suggestions...
Post 13 Feb 2006, 17:50
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 13 Feb 2006, 20:48
Well, in spanish http://fractus.uson.mx/Papers/Varios/Articulo97.html

The formula: http://fractus.uson.mx/Papers/Varios/Image6.gif

However now that I saw again the formula maybe is worst than the iterative one unless you know a faster way to power a number... There is one?

Regards,
HernĂ¡n

PS: Yes, the formula gets the nth fibonacci number, it doesn't tell you if a given number is fibonacci or not but if the formula is faster you can use it in the same fashion you search in a sorted array.
Post 13 Feb 2006, 20:48
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 14 Feb 2006, 00:00
Yeah, when I remembered the phi, I got excited. This is how's it done:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html
Code:
format PE GUI
include 'win32a.inc'
entry start

section '.code' code readable executable

    start:
        stdcall fib,47
        invoke  MessageBox,HWND_DESKTOP,answer,title,MB_OK
        invoke  ExitProcess,0

    proc fib,fibnum
      locals
        two     dt 2.0
        sqfive  dt 2.2360679774997896964091736687313
        result  dd ?,?
      endl
        fld1
        fld     [sqfive]
        fdivp
        fld     [two]
        fld1
        fld     [sqfive]
        faddp
        fdivrp
        fld     [two]
        fld1
        fld     [sqfive]
        fsubp
        fdivrp
        mov     ecx,[fibnum]
        fld1
        fld1
      .power:
        fmul    st0,st2
        fincstp
        fmul    st0,st2
        fdecstp
        loop    .power
        fsubp
        fmul    st0,st3
        fistp   qword[result]
        mov     eax,[result]
;        mov     edx,[result+4]
        mov     ecx,10
        mov     edi,10
      .dc:
        xor     edx,edx
        div     edi
        add     dl,30h
        mov     [answer+ecx-1],dl
        loop    .dc
        ret
    endp
section '.idata' import data readable writable

    library\
        user32,'user32.dll',\
        kernel32,'kernel32.dll'

    import user32,\
        MessageBox,'MessageBoxA'

    import kernel32,\
        ExitProcess,'ExitProcess'

    answer     rb 21
    title      db "Win32 Assembly"
    

I'm looking at making it 64-bit...(the stress is on 32-bit machines)
EDIT: Oops! I've got 80 bits...
Code:
format PE GUI
include 'win32a.inc'
entry start

section '.code' code readable executable

    start:
        stdcall fib,87
        invoke  MessageBox,HWND_DESKTOP,answer,title,MB_OK
        invoke  ExitProcess,0

    proc fib,fibnum
      locals
        two     dt 2.0
        sqfive  dt 2.2360679774997896964091736687313
        result  dt ?
      endl
        fld1
        fld     [sqfive]
        fdivp
        fld     [two]
        fld1
        fld     [sqfive]
        faddp
        fdivrp
        fld     [two]
        fld1
        fld     [sqfive]
        fsubp
        fdivrp
        mov     ecx,[fibnum]
        fld1
        fld1
      .power:
        fmul    st0,st2
        fincstp
        fmul    st0,st2
        fdecstp
        loop    .power
        fsubp
        fmul    st0,st3
        fbstp   [result]
        mov     ecx,10
        xor     edi,edi
      .dc:
        movzx   eax,byte[result+ecx-1]
        mov     ebx,eax
        shl     eax,8
        shr     ebx,4
        or      eax,ebx
        and     eax,0F0Fh
        or      eax,3030h
        mov     word[answer+edi],ax
        add     edi,2
        loop    .dc
        ret
    endp
section '.idata' import data readable writable

    library\
        user32,'user32.dll',\
        kernel32,'kernel32.dll'

    import user32,\
        MessageBox,'MessageBoxA'

    import kernel32,\
        ExitProcess,'ExitProcess'

    answer     rb 21
    title      db "Win32 Assembly"
    


INTERESTING FACTS:
OllyDbg knows not only constants like 1.0, base-2 logarithm of e,
base-2 log of 10, base-10 log of 2, base-e log of 2, pi, zero
but also:
SQRT(2), SQRT(5), -SQRT(10), GOLDEN RATIO, ... Very Happy

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 14 Feb 2006, 00:00
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
dr_dred



Joined: 29 May 2005
Posts: 5
Location: Earth
dr_dred 14 Feb 2006, 12:54
Code:
include 'include/win32axp.inc'

.code

proc    Fibonacci, n

        ;n - number to check

        xor     ecx, ecx
        mov     eax, 1
@@:     xadd    eax, ecx
        cmp     eax, [n]
        jb      @B      ; jump to @@ back
        sete    dl
        movzx   eax, dl
        ret

endp

start:
        push    5
        call    Fibonacci
        .if     eax = TRUE
                invoke  MessageBox, 0, "yes, it is", 0, 0
        .else
                invoke  MessageBox, 0, "no it isn't", 0, 0
        .endif
        invoke  ExitProcess, 0
.end    start    
Post 14 Feb 2006, 12:54
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 14 Feb 2006, 15:04
:O thanks dr_dred for that code!!
Post 14 Feb 2006, 15:04
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.