Calculate Fibonacci Numbers

This function calculates the Nth Fibonacci number.

The Fibonacci numbers are a well-known mathematical sequence. The first and second numbers are both 1. From then on, the Nth number is the sum of numbers (N-1) and (N-2), so the sequence begins:

1, 1, 2, 3, 5, 8, 13, 21 . . .

Because the numbers can become large, the program calculates a 64-bit result. It assumes on entry that ecx contains the number in the Fibonacci sequence to calculate. It returns the result in edx:eax, which means edx stores the high 32 bits and eax stores the low 32 bits.

If the result would overflow 64 bits, 0 is returned.

This is a code fragment, not a full procedure. It does not worry about preserving the initial values of registers.

The program uses the xchg instruction, which simply swaps the two operands. The jc conditional jumps if the carry flag is set.

The adc instruction allows multi-byte/-word/-dword additions. It adds the carry flag to the result, so you could add ebx:eax to edx:ecx (storing the result in ebx:eax) using the following:

add eax, ecx   ; adc not needed on low dword operation

adc ebx, edx   ; add carry flag from previous operation

Source Code

 1.     fibonacci:

 2.

 3.         ; ecx holds the number

 4.         mov eax, 1

 5.         mov edx, 0

 6.         cmp ecx, 2   ; if ecx is 1 or 2

 7.         jle done     ; then return 1 in edx:eax

 8.

 9.         sub ecx, 1

10.

11.         ; result will go in edx:eax

12.         mov ebx, 0    ; esi:ebx store previous value

13.         mov esi, 0

14.     top:

15.         add edx, eax

16.         adc esi, ebx  ; esi:ebx += edx:eax

17.         jc overflow   ; if carry flag set, we overflowed

18.         xchg eax, ebx

19.         xchg edx, esi ; swap esi:ebx and edx:eax

20.         loop top

21.

22.         jmp done

23.

24.     overflow:

25.         mov eax, 0

26.         mov edx, 0

27.

28.     done:

Suggestions

Hints

Walk through the program with the following values in ecx to test the first few numbers in the sequence:

Explanation of the Bug

The addition of the two 64-bit numbers on lines 15-16 is incorrect:

add edx, eax

adc esi, ebx  ; esi:ebx += edx:eax

The comment on line 16 is correct in what the code should be trying to do, but the registers are mixed up. The code should read as follows:

add ebx, eax

adc esi, edx  ; esi:ebx += edx:eax

This is a B.variable error that actually has an interesting behavior if you walk through the code. The code still works correctly for the first and second number because those are special-cased on lines 6-7. For N larger than 2, the result depends on whether N is even or odd. If it's even, the result is 0. If it's odd, edx winds up set to N-1 and eax winds up set to 1, so the result is [(N-1) * (2³²)] + 1. Maybe that's a useful sequence on its own.

The corrected program, incidentally, overflows trying to calculate the 94th Fibonacci number, which is 19,740,274,219,868,223,167. This is larger than the maximum unsigned 64-bit value of 18,446,744,073,709,551,615 (both numbers have 20 digits).