### Author Topic: Fibonacci series  (Read 12423 times)

#### tykkimies

• New Member
• Posts: 1
##### Fibonacci series
« on: October 17, 2012, 10:01:41 PM »
I need to create a nasm program to prompt the user for a number to calculate its fibonacci number.  It needs to be done recursively.  I so far am finding assembler to be much harder than other languages I have learned.  Would appreciate some help here.  So far i just have the data segment to prompt user the bss to get the users input, and a DoIt loop subprogram which was given to us by our teacher. I think does the recursion,  but i always have trouble with the .text segment and what goes in main
Code: [Select]
`%include "asm_io.inc"segment .data            output db "Enter number to calculate fibonacci number",0segment .bss            userInput      resd    1segment .text            global asm_mainasm_main:           DoIt:         enter 0,0         pusha         move ecx, [ebp+8]         ecx, 0         jl return         dec ecx         push ecx         call DoIt         pop ecx         mov eax, [ebp+8]         call print_int         mov eax, space         call print_stringreturn:         popa         leave         return`

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2629
• Country:
##### Re: Fibonacci series
« Reply #1 on: October 18, 2012, 04:55:18 AM »
If your teacher really gave you that "DoIt", drop the course - it won't even assemble as presented! If you screwed it up yourself, okay you're allowed to make mistakes. Nobody was born knowing this stuff.

I've been out of school so long I wasn't sure I remembered Fibonacci. I guess I do. The first two numbers in the series are 1, and after that each number is the sum of the previous two. Sounds like the "add" instruction might be useful.

Recursion is a tough assignment for beginners! (recursion error: see recursion error) It just means that a routine calls itself. Of course, this means that you have to manage the stack correctly, and you have to know when to stop!

"main()" is in "driver.c" and just calls "asm_main". You probably don't want to mess with it. "asm_main" is where your program starts. Since you've got as far as a prompt, I suppose the first thing is to display it.
Code: [Select]
`mov eax, outputcall print_int`But wait! At the end of "asm_main", you're going to want to return (the instruction is "ret", not "return"). You may want to set up a stack frame (although there are no parameters on the stack and we don't need any local variables) and save registers C expects to be preserved...
Code: [Select]
`enter 0, 0pusha; your codepopamov eax, 0 ; return zeroleaveret`I consider that overkill, and I like to be able to return a non-zero value, but that seems to be what the examples show, so that's probably the way you're "supposed" to do it.

Where were we? Oh yeah, after asking for a number, and providing a place to put it, I suppose the next thing is...
Code: [Select]
`call read_intmov [userInput], eax`At this point, you might be ready to start thinking about calling "DoIt". If you fix your "DoIt" so it works at all, it'll count down from the number you passed it. That's a start, but it doesn't calculate any Fibonacci numbers. There's probably a better way to do it, but the naive approach I came up with was to pass our function the last two numbers in the series (we know we want to start with 1, 1) along with the remaining count. This requires some changes to "stack management". Where your "DoIt" does:
Code: [Select]
`push ecxcall DoItpop ecx`The "pop ecx" is just to "clean up the stack" (remove the parameters you pushed). You could do "pop ecx" three times, but I prefer to do it like this:
Code: [Select]
`push (next to last number in series)push (last number in series)push ecxcall DoItadd esp, 4 * 3`The "4" is the size of the parameter in bytes, and the "3" is the number of parameters - change it if you change the number of parameters. Then we need to add "last" to "next to last" (they're at [ebp + 12] and [ebp + 16]). That becomes our "current" Fibonacci number. For the next call, our "current" number becomes "last" and our old "last" becomes "next to last", decrement the count and call ourself. Until done.

I'll show you what I came up with, but give it a shot yourself first.

Best,
Frank

#### avcaballero

• Full Member
• Posts: 132
• Country:
##### Re: Fibonacci series
« Reply #2 on: October 18, 2012, 03:26:15 PM »
I feel productive today. I'm sorry for your teacher and you, because if you don't make by yourself you won't never be able to do it. Ah, of course, only valid for 2-digits numbers...

Code: [Select]
`; abreojosensamblador.net. You can input 2 characters, do not checking errors%macro write 1  push   ax  push   cx  push   dx   mov    si, %1  mov    cl, 10  xor    ah, ah  mov    al, byte [si]   div    cl  or     ax, 3030h  mov    dx, ax  mov    ah, 2  int    21h  mov    dl, dh  int    21h  mov    dl, ' '  int    21h  pop    dx  pop    cx  pop    ax%endmacro%macro print 1  push    ax  push    dx  mov     dx, %1  mov     ah, 9  int     21h  pop     dx  pop     ax%endmacro[org 100h][section .text]  print   Text1  mov     dx, Input  mov     ah, 0Ah  int     21h  mov     si, Input+2  mov     al, byte [si]  and     al, 0Fh  jz      @Fin    cmp     byte [si-1], 1      ; Only one character?    jz      @Next      mov     ah, 10      mul     ah      mov     ah, byte [si+1]      and     ah, 0Fh      add     al, ah    @Next:    xor     ah, ah             ; Here we get the number    mov     [Number], al       ;   save it    dec     byte [Number]      ; At least one time printed    print   CRLF      write   m                ; Print first record in Fibonacci series      cmp     ax, 1      jz      @Fin        call  Fibonacci  @Fin:  ret    Fibonacci:    write   m+1                ; Print second record in Fibonacci buffer    dec     byte [Number]      ; One record less left    jz      @FFin              ; Have we finished?      mov     si, m            ; Make next record in Fibonacci series      mov     al, [si]      mov     ah, [si+1]      mov     [si], ah      add     al, ah      mov     [si+1], al      call    Fibonacci        ; Call again    @FFin:  ret[section .data]  Input      db 3, "    "  Text1      db "Number of records in the serie of Fibonacci: \$"  CRLF       db 13, 10, '\$'  m          db 1, 1[section .bss]  Number     resb 1; Result on the screen; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 0; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 1; 01; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 2; 01 01; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 3; 01 01 02; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 4; 01 01 02 03; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 5; 01 01 02 03 05; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 6; 01 01 02 03 05 08; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 7; 01 01 02 03 05 08 13; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 8; 01 01 02 03 05 08 13 21; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 9; 01 01 02 03 05 08 13 21 34; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 10; 01 01 02 03 05 08 13 21 34 55; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 11; 01 01 02 03 05 08 13 21 34 55 89; D:\Alfonso\AVCH\AOE_>fibona; Number of records in the serie of Fibonacci: 12; 01 01 02 03 05 08 13 21 34 55 89 >4`
Regards.
« Last Edit: October 18, 2012, 03:31:33 PM by avcaballero »

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2629
• Country:
##### Re: Fibonacci series
« Reply #3 on: October 20, 2012, 05:30:28 AM »
Nice, Alfonso! Thanks! I'm not sure it'll be much help to tykkimies. I ASSume he's supposed to use Dr. Carter's stuff - looks like it to me. My version contains, in the .data section, the text:
Code: [Select]
`over db "Sorry, numbers over 46 are too big for this humble program!", 10, 0`Fibbonacci 47 gives a negative number. This is because Dr. Carter's "print_int" sends a format string to printf that specifies a signed integer. We could improve this by printing an unsigned integer - but not by much. Googling around, I came across a version that uses edx:eax to store 64 bits (even though it's a 32-bit program). I might attempt something like that... if I'm feeling ambitious. What it cries out for is a "bignum" implementation. I don't think I'm that ambitious.

How's it coming, tykkimies?

Best,
Frank

#### Keith Kanios

• Full Member
• Posts: 383
• Country:
##### Re: Fibonacci series
« Reply #4 on: October 20, 2012, 06:39:28 AM »
Here's a relatively simple version that minimizes stack usage, based on http://www.asmcommunity.net/board/index.php?topic=14206.msg110054#msg110054

Code: [Select]
`;parameters: ecx = number of iterations (1-47);returns: eax = resultfib: mov edx, 1 mov eax, 0.loop: xadd eax, edx loop .loop ret`
You should be able to integrate the above with a print routine and still maintain minimal stack usage.
« Last Edit: October 20, 2012, 08:59:20 AM by Keith Kanios »

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2629
• Country:
##### Re: Fibonacci series
« Reply #5 on: October 20, 2012, 07:47:37 AM »
I learn something new every day! bitRAKE says, "Many coders forget XADD". I'm not sure I ever knew it. Been around since 486, has it? Wow! That's pretty!

Not recursive, so it won't satisfy the homework assignment... sigh...

Best,
Frank

#### Keith Kanios

• Full Member
• Posts: 383
• Country:
##### Re: Fibonacci series
« Reply #6 on: October 20, 2012, 09:43:08 AM »
Not recursive, so it won't satisfy the homework assignment... sigh...

Yes, unfortunately. However, understanding recursion is definitely important for a programmer, so I see the value in this assignment as-is.

Hopefully the takeaway with the above example is how to avoid (i.e. optimize) recursion when possible, especially since it generally reduces both data size and execution time.

To re-purpose a phrase: The ultimate aim of recursion is not having to use it.