NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: tykkimies 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
%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
-
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.
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...
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...
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:
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:
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
-
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...
; 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.
-
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:
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
-
Here's a relatively simple version that minimizes stack usage, based on http://www.asmcommunity.net/board/index.php?topic=14206.msg110054#msg110054 (http://www.asmcommunity.net/board/index.php?topic=14206.msg110054#msg110054)
;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.
-
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
-
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