Author Topic: Fibonacci series  (Read 14257 times)

Offline 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",0

segment .bss
            userInput      resd    1

segment .text
            global asm_main

asm_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_string

return:
         popa
         leave
         return





Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
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, output
call 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, 0
pusha
; your code
popa
mov eax, 0 ; return zero
leave
ret
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_int
mov [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 ecx
call DoIt
pop 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 ecx
call DoIt
add 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


Offline avcaballero

  • Full Member
  • **
  • Posts: 132
  • Country: es
    • Abre los Ojos al Ensamblador
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 »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
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


Offline Keith Kanios

  • Full Member
  • **
  • Posts: 383
  • Country: us
    • Personal Homepage
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 = result
fib:
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 »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
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


Offline Keith Kanios

  • Full Member
  • **
  • Posts: 383
  • Country: us
    • Personal Homepage
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. :P