flat assembler
Message board for the users of flat assembler.

 Index > Heap > Euler challenge 2 - Even Fibonacci numbers
Author
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
;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
;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
mov esp,ebp
pop ebp
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".
22 Feb 2014, 07:14
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
@@:
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:
...    ```
22 Feb 2014, 08:37
watdapho

Joined: 17 Jan 2014
Posts: 5
watdapho
@tthsqe
Yeap 4613732 was my answer. Thanks for the input! very nice tips
22 Feb 2014, 09:06
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.
22 Feb 2014, 11:41
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.
25 Feb 2014, 16:52
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....
25 Feb 2014, 21:10
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.
25 Feb 2014, 22:41
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum