flat assembler
Message board for the users of flat assembler.

Index > Heap > Euler challenge 2 - Even Fibonacci numbers

Author
Thread Post new topic Reply to topic
watdapho



Joined: 17 Jan 2014
Posts: 5
watdapho
Practicing some assembly on Euler. Please review code!
Harsh criticism, optimization tips,tricks or anything else welcome!

Code:
;Even Fibonacci numbers
;Problem 2

;Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

;1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

;By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

format PE console
entry main
include 'macro/import32.inc'

section '.idata' import data readable
library msvcrt,'msvcrt.dll'
import msvcrt,\
printf,'printf',\
scanf,'scanf',\
system,'system',\
exit,'exit'

section '.data' data readable writeable
msg db "Please enter a limit: ",0xA,0xD,0
msg2 db "The total is %d",0xA,0xD,0
d dd "%d",0xA,0xD,0


section '.code' code readable executable
main:
        ;Space on stack for limit address
        sub esp,4
        ;Prologue
        push ebp
        mov ebp,esp
        sub esp,24
proc1:
        ;Asking for limit input
        mov dword[esp],msg
        call[printf]
        ;Store limit input into address [ebp+4]
        lea eax,[ebp+4]
        mov dword[esp+4],eax
        mov dword[esp],d
        call[scanf]
        ;Moving input into ecx
        mov ecx,dword[ebp+4]
        ;Initialising registers eax and edx
        mov eax,0 ;variable x
        mov edx,1 ;variable y

       ;#Note: Variable x is reserved in address [ebp-4]
       ;       Variable y is reserved in address [ebp-8]
       ;       Variable (x+y) is reservied in address [ebp-12]
       ;       The total of even (x+y) variables are reserved in address [ebp-16]
proc2:
       ;Comparing [ebp-12] (variable x+y) with limit stored in ecx
       cmp dword[ebp-12],ecx
       ;Jump if above limit to epilogue
       ja finito
       ;Add variable x and variable y
       add eax,edx
       ;Store variable (x+y) into address [ebp-12]
       mov dword[ebp-12],eax
       ;Initialising ebx to 2 for division
       mov ebx,2
       ;Extend register edx:eax for division
       CDQ
       ;Divide (x+y) by 2
       idiv ebx
       ;If edx == 0, variable (x+y) is even
       cmp edx,0
       ;Preparing variable x and y for next loop
       ;Where variable x=y
       ;      variable y=(x+y)
       mov eax,dword[ebp-12]
       mov edx,dword[ebp-8]
       mov dword[ebp-8],eax
       mov dword[ebp-4],edx
       ;The jump if variable (x+y) is odd
       jne proc2
       ;Add variable (x+y) to address [ebp-16] if even
       add dword[ebp-16],eax
       ;Continue loop
       jmp proc2


finito:
        ;Print results
        mov eax,dword[ebp-16]
        mov dword[esp+4],eax
        mov dword[esp],msg2
        call[printf]
        ;Pause system to see results
        invoke system,'pause'
        ;Epilogue
        add esp,24
        mov esp,ebp
        pop ebp
        add esp,4
        invoke exit,0

        ;End

    
Edit by revolution: To get the code tags to work you need to not tick the box "Disable BBCode in this post".
Post 22 Feb 2014, 07:14
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
Did you get 4613732 as answer?
You code does seem a little verbose. I would start with the observation that only every third term is even. Thus:
Code:
xor  ecx,ecx        ; ecx=0 will contain our total
xor  eax,eax         ; eax=0 is the 0^th fib number
lea  ebx,[eax+2]       ; ebx=2 is the third fib number 
@@:
add  ecx,ebx
push  ebx
lea  ebx,[eax+4*ebx]
pop  eax
cmp  ebx,4000000
jbe  @b
; ecx now contains answer    


Quote:
;Initialising ebx to 2 for division
mov ebx,2
;Extend register edx:eax for division
CDQ
;Divide (x+y) by 2
idiv ebx
;If edx == 0, variable (x+y) is even
cmp edx,0


a much easier way of testing if eax is even is:
Code:
test  eax,1
jz  even
odd:
 ...
even:
 ...    

or
Code:
test  eax,1
jnz  odd
even:
 ...
odd:
 ...    
Post 22 Feb 2014, 08:37
View user's profile Send private message Reply with quote
watdapho



Joined: 17 Jan 2014
Posts: 5
watdapho
@tthsqe
Yeap 4613732 was my answer. Thanks for the input! very nice tips Smile
Post 22 Feb 2014, 09:06
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
Do you have a 64 bit windows system? If so, you can try to use the 64 bit calculator that I posted in the projects and ideas section. The straightforward code is
Code:
n=0;total=0;
While[Fibonacci[n]<=4000000,
 If[And[Fibonacci[n],1]==0,
  total=total+Fibonacci[n]
 ];
 n=n+1
];
total    

This also returns with 4613732, so at least all of the relevant circuits of my calculator are free of bugs. Wink
Post 22 Feb 2014, 11:41
View user's profile Send private message Reply with quote
Xorpd!



Joined: 21 Dec 2006
Posts: 161
Xorpd!
Instead of pushing ebx and popping eax you could just

lea eax, [eax+4*ebx]
xchg eax, ebx

xchg with eax is fast and also a 1-byte instruction.
Post 25 Feb 2014, 16:52
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
you are right. However, on amd, the xchg is slower than push/pop. How about you? Why isn't your name xorps? It is the same as xorpd but 1 byte shorter....
Post 25 Feb 2014, 21:10
View user's profile Send private message Reply with quote
Xorpd!



Joined: 21 Dec 2006
Posts: 161
Xorpd!
Actually, it's a past participle passive...
Also the extra byte may be useful in aligning subsequnt instructions.
Post 25 Feb 2014, 22:41
View user's profile Send private message Visit poster's website 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 can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.