Fibonacci Series in Assembly x86

Question

Finally after a long session of countless errors , hope this is the final one.

No Compile or runtime errors, Just a logical error.

EDIT: (Fixed Pseudocode)

My Pseudocode:

first  = 1;
second = 1;
third  = 0;

 for i from 1 to n{

    third=first+second
    first=second
    second=third

}
return third

This would print the final result of the series.

My Assembly Code:

I have added Comments where ever possible

.386
.model flat,stdcall
option casemap:none

.data
timestell     db "Loop Ran : %d Times -----",0     ;format string
fmtd   db "%d",0
finalprint  db "Final Number is : %d ------",0     ;format string
times  dd 0Ah                                      ;times to loop
first dd 1h
second dd 1h
third dd 0h


.data?

retvalue1 dd ?             ;we will initialize it later

.code
include windows.inc
include user32.inc
includelib user32.lib
include kernel32.inc
includelib kernel32.lib
includelib MSVCRT
extrn printf:near
extrn exit:near

public main
main proc


         mov ecx, times      ;loop "times" times
         mov eax,0           ;just to store number of times loop ran
      top:                   ;body of loop
         cmp ecx, 0          ;test at top of loop
         je bottom           ;loop exit when while condition false
         add eax,1           ;Just to test number of times loop ran
         mov ebx,first       ;move first into ebx
         add ebx,second      ;add ebx, [ first+second ]
         mov third,ebx       ;Copy result i.e ebx [first+second] to third
         xor ebx,ebx         ;clear for further use
         mov ebx,first       ;move first into ebx
         mov second,ebx      ;copy ebx to second [NOW second=first]
         xor ebx,ebx         ;clear for later use
         mov ebx,third       ;move thirs into ebx
         mov second,ebx      ;copy ebx to third [NOW second=third]
         xor ebx,ebx         ;clear it
         dec ecx             ;decrement loop
         jmp top             ;Loop again

      bottom:
           mov retvalue1,eax       ;store eax into a variable
           push retvalue1          ;pass this variable to printf
           push offset timestell   ;pass Format string to printf    
           call printf             ;Print no.  of times loop ran
           push third              ;push value of third to printf
           push offset finalprint  ;push the format string
           call printf             ;Print the final number


      push 0        ;exit gracefully
      call exit     ;exit system

main endp

end main

The code runs well but the output doesn't satisfies me:

Output: Loop Ran : 10 Times -----Final Number is : 11 ------

First of all i am not really sure that Final number is in decimal or hex form.

Assuming it as decimal : Fibonacci Series doesn't have 11
Assuming it as hex : Fibonacci Series doesn't have 17 (11 hex = 17 dec)

What am i doing wrong?

No need to be unsure if the printed number is in decimal. `printf` uses the `finalprint` string as format, and if it's anything like a regular `printf`, it will use `%d` to output as decimal. — Jongware, Feb 23 '16 at 14:31
Just compare your comments to what you really wanted to do ;) `NOW second=first` yeah but you wanted `first=second` ... oops. You get a +1 for commenting, that's how we can spot your error. — Jester, Feb 23 '16 at 14:32
Note: the pseudocode returns the correct Fibonacci number, although for n=10 it returns `144`, technically the *12th* fib num (or `89`, depending on how `n` gets initialized, but it's still one too far). — Jongware, Feb 23 '16 at 14:35
@RadLexus So, my pseudocode has some error, thanks, i'll check it out — Idkwhoami, Feb 23 '16 at 14:44
If you're unrolling, use `a+=b; b+=a` to compute the Fibonacci sequence. Or use `LEA` as a non-destructive add, to put the result into a 3rd register. Your code is pretty clunky: you waste an instruction zeroing a register before moving into it. (mov has no dependency on the previous contents). You store and reload to memory instead of just keeping your variables live in three registers (introducing about 5 cycles of latency into the loop-carried dependency chain). See [my answer on a similar question](http://stackoverflow.com/a/32661389/224132) for an optimized Fibonacci loop. — Peter Cordes, Feb 24 '16 at 00:53
Still, +1 for well-commented code and asking a good question. Note that you could post the working version as an answer to your question, rather than editing it into the question. This is the recommended way to do things here on SO. That other Fib question I linked had some interesting discussion. For example, it's possible to compute Fib(n) in log2(n) steps. (The OP of that question wanted an array of all Fib(0..n), though.) Anyway, check it out, I think my code there makes nice examples of efficient ASM.) — Peter Cordes, Feb 24 '16 at 00:56
@PeterCordes Thanks for the suggestion, this is my second Assembly program after "hello world", so i focused mainly on simplicity rather than efficiency, i'll surely check out the better code you linked. I have moved my edit into my answer, Sorry i am new here. Am i allowed to accept it as correct answer? — Idkwhoami, Feb 24 '16 at 01:06
Yes, you can accept your own answer. You're doing far better than most new users in terms of question quality and responding to comments, so keep it up. The edit to split your answer out into an answer improves the question readability a lot. It's kind of skim-able now, with only one big code block :) And yeah, everyone writes awkward code while learning; that's expected. I'm pointing out the flaws so you'll know what they are, not because you shouldn't have made them in the first place. :P — Peter Cordes, Feb 24 '16 at 01:10

score 5 · Accepted Answer · answered Feb 24 '16 at 01:03

5

The problem was that my Actual code was not matching with my Pseudocode which resulted in the Logical error.

This Part

     mov ebx,first       ;move first into ebx
     mov second,ebx      ;copy ebx to second [NOW second=first]

This gives first value of second, but my PseudoCode says "first=second", which means give value of second to first.

     mov ebx,second      ;move second into ebx
     mov first,ebx       ;copy ebx to second [NOW first=second]

Final Working Code for x86 Intel Processor:

For any further referrers , i am posting a working code for x86 intel

.386
.model flat,stdcall
option casemap:none

.data
timestell   db   "Loop Ran : %d Times -----",0          ;format string
finalprint  db   "%d th Fibonacci number is %d",0       ;format string
times       dd   14h                                    ;times to loop
first dd 1h
second dd 1h
third dd 0h



.code
include windows.inc
include user32.inc
includelib user32.lib
include kernel32.inc
includelib kernel32.lib
includelib MSVCRT
extrn printf:near
extrn exit:near

public main
main proc


         mov ecx, times       ;set loop counter to "times" time
         sub ecx,2            ;loop times-2 times

      top:
         cmp ecx, 0          ; test at top of loop
         je bottom           ; loop exit when while condition false
         xor ebx,ebx         ;Clear ebx
         mov ebx,first       ;move first into ebx
         add ebx,second      ;add ebx, [ first+second ]
         mov third,ebx       ;Copy result i.e ebx [first+second] to third
         xor ebx,ebx         ;clear for further use
         mov ebx,second      ;move second into ebx
         mov first,ebx       ;copy ebx to second [NOW first=second]
         xor ebx,ebx         ;clear for later use
         mov ebx,third       ;move thirs into ebx
         mov second,ebx      ;copy ebx to third [NOW second=third]
         xor ebx,ebx         ;clear it
         dec ecx             ;decrement loop
         jmp top             ;Loop again

      bottom:
        push third
              push times                ;push value of third to printf
              push offset finalprint    ;push the format string
              call printf               ;Print the final number
      push 0        ;exit gracefully
         call exit      ;exit system

    main endp

end main

answered Feb 24 '16 at 01:03

Idkwhoami

145
1
10

As a general comment, code that stores values in registers is always simpler, shorter and faster than similar code that puts values in memory, although need to do a little more work to comment on which variable is in which register. You could easily have done that here. Another lesson you learned its that it's usually worthwhile to actually code (not pseudocode) the algorithm in a higher level language before committing to the effort of writing the assembly code. Seeing an error in HLL is far easier than seeing the same one in assembly. – Gene Feb 24 '16 at 01:08
@Gene Sorry, i am a complete newbie for Assembly as it differs. I didn't understand what you said. Did you mean to say that i should also comment that which variable is in which register? like instead of `;move second into ebx` I should have wrote `ebx=second` ? I tested the Pseudo Code in Javascript first and i seem to have missed the error as my code gives the Correct number but two steps ahead of requested nth number, I focused on simplicity that made me miss this small error. – Idkwhoami Feb 24 '16 at 01:12
You're doing well. No I'm saying you didn't need the memory locations at all. E.g. use esi, edi, and edx for first, second and third. This still leaves 3 registers for loop counting, temporary values, etc. – Gene Feb 24 '16 at 01:13
@Gene is making the same point I did about keeping your vars live in regs, instead of storing/reloading. The answer I linked you with my Fib code does exactly that: using comments to keep track of which var is in which register, instead of using `mov` instructions to always put them back into the same register at all times. – Peter Cordes Feb 24 '16 at 01:14
1

@PeterCordes @Gene Now i understood, you mean to say i didn't even need to use `first` ,`second` and `third` variables at all, i could assume registers `eax`,`ebx`,`edx` as the corresponding variables. This would save memory and increase efficiency. Correct me if i am wrong. Thanks – Idkwhoami Feb 24 '16 at 01:18
Yep. The efficiency gain is by far the most important factor, not mem usage. `add eax, edx` only has 1 cycle of latency, but `mov [first], edx` / `add eax, [first]` has 6 cycles of latency. Since the whole computation is one long dependency chain, the total time is limited by latency (only the loop counter is a separate dependency chain that the CPU can do in parallel). So, a memory round trip between every add makes your code 6 times slower. (It's not of course a round-trip to DRAM, or even L1 cache. It's really just a round trip through store->load forwarding, which x86 does well.) – Peter Cordes Feb 24 '16 at 01:24
The useless `xor` instructions can also be done in parallel, because they don't depend on anything. (and nothing depends on their result; this is why they're useless. >.< Maybe you saw an example of 16bit code where clearing the whole register before writing bx or bl was useful to break the false dependency on the previous value of ebx?) – Peter Cordes Feb 24 '16 at 01:27
@PeterCordes So you mean i should totally eradicate them from my code? I thought of resetting them just to be on safer side. I just read it somewhere that it's necessary to clear them before each use. As always, i could be wrong. – Idkwhoami Feb 24 '16 at 01:33
You don't use one before `mov ecx, times`, and your computer didn't explode. :P Yes, you're wrong, and you should remove them all. `xor same,same` [is the best way to zero a reg, for some subtle and not-so-subtle reasons](http://stackoverflow.com/questions/33666617/which-is-best-way-to-set-a-register-to-zero-in-x86-assembly-xor-mov-or-and), but you don't need to before using it as a write-only operand (e.g. the destination of a `mov`). – Peter Cordes Feb 24 '16 at 01:51
[`popcnt` on Intel *does* have a false dep on it's write-only destination](http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance/25089720#25089720), though, so gcc does actually use `xor` to break the dependency chain when that's more convenient than `popcnt eax, eax` or something. (If eax was ready as a source operand, it's also "ready" as a dest operand and won't harm instruction-level parallelism.) This is the only sort of case where `xor`-zeroing a reg before use like that is a good idea. – Peter Cordes Feb 24 '16 at 01:52
1

Looking at optimized compiler output for very short C functions is a great way to learn some tricks. http://gcc.godbolt.org/ is great for this: I use it all the time to post asm links in my answers. Write functions that take args and return a value or store to a global, so they don't optimize away. – Peter Cordes Feb 24 '16 at 01:54

Fibonacci Series in Assembly x86

1 Answers1

Linked

Related