Sign in to follow this  

Big Fibonacci numbers in ASM

This topic is 3315 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to write an IA32 assembly language program which computes Fibonacci numbers up to an arbitrary length. For testing purposes, I've set ARRAYSIZE to 2, so the program should compute all the fibonacci numbers which can be expressed with 64 bits, but later I should be able to set it to anything. The Fibonacci numbers are stored in arrays of DWORDS. The first element of the array should represent the least significant 32 bits of the number, etc, and the last element should represent the most significant 32 bits. I'm using the link library from Kip Irvine's book for text output. The first problem is that the program never stops. After adding the last elements of the two arrays, I'm trying to check if there was a carry, which would mean that the result cannot be expressed with 32*ARRAYSIZE bits, and then exit the program. For some reason, that never happens. The second problem is that it just doesn't seem to work right. The result seems to be correct only as long as it fits in the first array element. Here's the code:
TITLE ASM Big Fibonacci numbers						(main.asm)

; Description:
; Computes all fibonacci numbers which can be expressed with 32 * ARRAYSIZE bits

INCLUDE Irvine32.inc
.data
myMessage BYTE "ASM Big Fibonacci Numbers",0dh,0ah,0

ARRAYSIZE = 2
a DWORD ARRAYSIZE DUP(0)		; the first operand
b DWORD ARRAYSIZE DUP(0)		; the second operand
newfib DWORD 2 DUP(0)			; the new fibonacci number
newline BYTE 0dh,0ah,0			; newline character
n DWORD 0				; number of fibonacci numbers computed so far

.code
;--------
main PROC
;--------
	call Clrscr
	mov	 edx,OFFSET myMessage
	call WriteString

	; The first two fib numbers are given, {1,1}
	mov eax, 1d
	mov [a], eax
	mov [b], eax

FIBLOOP:
	mov esi, OFFSET a
	mov edi, OFFSET b
	mov ecx, LENGTHOF b
	mov ebx, OFFSET newfib
	call AddBigNum			;computes newfib = a+b

	cmp edx, 1			;AddBigNum should set edx to 1 if a+b doesn't fit in newfib
	jz FIBEND

	; Copy b to a
	mov esi, OFFSET b
	mov ebx, OFFSET a
	mov ecx, LENGTHOF b
	call CopyArray

	; Copy newfib to b
	mov esi, OFFSET newfib
	mov ebx, OFFSET b
	mov ecx, LENGTHOF b
	call CopyArray

	; Output the new number
	mov esi, OFFSET newfib
	mov ecx, LENGTHOF b
	call WriteBigFib

	mov eax, n
	add eax, 1
	mov n, eax
	.IF (n > 95)
		add eax, 2		;add breakpoint here to test
		jmp FIBEND
	.ENDIF

	loop FIBLOOP

FIBEND:

	exit
main ENDP

;-------------
AddBigNum PROC
;-------------
;Receives: 
; esi	address of a
; edi	address of b
; ebx	address where the result should be stored
;Returns: 
; address of newfib (the result) in ebx
; EDX will be 1 if there was a carry from the last addition, 0 otherwise.

	clc
ADDLOOP:
	mov edx, 0d
	mov eax, [esi]
	adc eax, [edi]		; now eax is [esi] + [edi] + carry from last addition
	jnc NOCARRY
	mov edx, 1d
NOCARRY:
	mov [ebx], eax
	add esi, 4 ; advance all three pointers
	add edi, 4
	add ebx, 4
	loop ADDLOOP

ENDADDBIGNUM:
	ret
	AddBigNum ENDP

;-------------
CopyArray PROC
;-------------
;Receives:
; esi	address of a
; ecx   number of elements in a
; ebx   address where the resulting array should be stored
;Returns: 
; address of resulting array in ebx

COPYARRAYLOOP:
	
	mov eax, [esi]
	mov [ebx], eax
	add esi, 4
	add ebx, 4
	Loop COPYARRAYLOOP

	ret

CopyArray ENDP

;---------------
WriteBigFib PROC
;---------------
;Receives: 
; esi	address of the array
; ecx	number of elements in the array

WRITEBIGFIBLOOP:
	mov eax, [esi]
	mov ebx, TYPE DWORD
	call WriteBin	; writes a binary integer to the console window in doubleword format
DONTWRITE:
	add esi, 4
	loop WRITEBIGFIBLOOP

	mov edx, OFFSET newline
	call WriteString ; new line
	ret
	WriteBigFib ENDP

END main


Since I'm just beginning ASM coding, it could very well be just some silly mistake. But I've spent enough time thinking so I'll just ask. Can anyone help?

Share this post


Link to post
Share on other sites
Hmm, it seems to have been a stupid mistake just like I said. I forgot to save the carry flag from the number addition, and it probably got overwritten when doing the pointer arithmetic. Here's the corrected function:


;-------------
AddBigNum PROC
;-------------
;Receives:
; esi address of a
; edi address of b
; ebx address where the result should be stored
;Returns:
; address of newfib (the result) in ebx
; EDX will be 1 if there was a carry from the last addition, 0 otherwise.

clc
pushfd
ADDLOOP:
popfd
mov edx, 0d
mov eax, [esi]
adc eax, [edi] ; now eax is [esi] plus [edi] plus carry
pushfd ; save the carry
jnc NOCARRY
mov edx, 1d
NOCARRY:
mov [ebx], eax
add esi, 4
add edi, 4
add ebx, 4
loop ADDLOOP

ENDADDBIGNUM:
popfd
ret
AddBigNum ENDP



It seems to be working fine now, although it's hard to tell as the result is in binary format. I still need to figure out how to display the results in decimal correctly...

Share this post


Link to post
Share on other sites

This topic is 3315 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this