Fibonacci n-th number (modulo 2^32) in x86 assembler

fibonacci.asm

; Fibonacci n-th number (modulo 2^32)
;
; input:
; 	ecx = n
; modifies:
; 	eax, ecx, edx
; ouput:
; 	eax = number
; size:
; 	15 bytes

use32

_fibonacci:
	xor    eax, eax           ; 31 c0
	jecxz  _fibonacci_end     ; e3 0a
	dec    ecx                ; 49
	inc    eax                ; 40
	jecxz  _fibonacci_end     ; e3 06
	cdq                       ; 99
_fibonacci_loop:
	xchg   eax, edx           ; 92
	add    eax, edx           ; 01 d0
	loop   _fibonacci_loop    ; e2 fb
_fibonacci_end:
	ret                       ; c3

Beautiful! Is the cdq to zero edx in a single instruction?

@paulfurber Thanks! xor edx, edx is also a single instruction, but it takes more than 1 byte, while cdq fits there. It requires additional assumption regarding eax to be used for zeroing edx (eax < 0x80000000), but the condition is already met here.

I meant single byte - sorry. Thanks for the clarification.

Hey, I got inspired by this to write a similar function using floating point and the phi formula for finding the nth Fibonacci. ecx is the number and it uses the formula round(phi^n / sqrt(5)) to do it where phi is 1+sqrt(5)/2. Not nearly as small as yours but quite quick:

sys_exit        equ     1


SECTION     .data
phi     dt    1.618033988749894848204
sqrt5   dt    2.236067977499789696409

SECTION     .bss
result  resq 1

SECTION     .text
global      _start


_start:
        mov     ecx, 5
        fld     tword [sqrt5]
        fld     tword [phi]
        fld     tword [phi]
fib:    
        fmul    st1
        loop    fib
        fdiv    st2
        fisttp  qword [result] 

Exit: 
        mov     eax, sys_exit
        xor     ebx, ebx
        int     80H

And here's a version using the same formula but runs in linear time :) :

_start:

        fld     tword [sqrt5]
        fld     tword [n]
        fld     tword [phi]

        fyl2x
        fld     st0
        frndint
        fsub    st1, st0
        fxch    st1
        f2xm1
        fld1
        fadd
        fscale
        fdiv    st2
        fistp  qword [result]
Exit: 
...

@paulfurber: Thanks for providing FP versions! They're not as short as I would like them to be, though. :>

Anyway, I'm not FP guy myself, so I won't fiddle with squeezing it as much as possible (please forgive my rude assumption that it is possible), but others are free to do so in the comments!

And sorry for late reply, but unfortunately gists lacks any notification system...