;
; CPASM06S.ASM
; written by Keith Fenske
; Thursday, 11 April 2002
; Copyright (c) 2002 by Keith Fenske.  All rights reserved.
;
; This is an Intel 80x86 assembly language program to compute the recursive
; Fibonacci function using subroutine calls and the stack.  The function is:
;
;   f(0) = 1
;   f(1) = 1
;   f(n) = f(n-1) + f(n-2)
;
; The first few elements of the series are 1, 1, 2, 3, 5, 8, 13, 21, etc.
;
; Calculations are done with 32-bit instructions.  The maximum value that can
; be calculated is limited by the number of subroutine calls, not the size of
; the data registers.  The number of recursive subroutine calls is a power of
; two, so the computational complexity is O(2^n).  f(40) = 165,580,141 takes
; about ten seconds of CPU time on a 500 MHz Pentium processor.
;
; The second version of this assignment uses a much faster O(n) loop to
; calculate the same result.
;
[BITS 16]               ; set 16-bit code generation
[ORG 0100H]             ; set address of first instruction in COM file

CR  equ  0Dh            ; carriage return character
LF  equ  0Ah            ; line feed character

[SECTION .text]         ; start code (instruction) section

start:
;
; Call the recursive function with a parameter in the EAX register.
;
    mov  eax,40         ; set parameter to recursive function
    call function       ; call the function
                        ; result is in the EAX register
;
; Convert the function result in EAX to ASCII one decimal digit at a time.
; We have to do this *backwards* by dividing by ten and using the remainder.
;
    mov  ebx,10         ; we will divide by ten
    mov  cx,10          ; maximum number of digits to do
    mov  di,digits+9    ; address of last digit in output string
convert:
    mov  edx,0          ; clear EDX before dividing EDX:EAX by EBX
    div  ebx            ; result: EAX has quotient, EDX has remainder
    add  dl,'0'         ; convert byte remainder to single-digit ASCII
    mov  [di],dl        ; save low-order byte as ASCII in output digits
    dec  di             ; address of previous digit in output string
    cmp  eax,0          ; quit if quotient is now zero, because ...
    je   print          ; ... we want leading spaces, not leading zeros
    loop convert        ; repeat until CX=0 (up to ten times)
;
; Write the output string.
;
print:
    mov  bx,1           ; DOS file handle 1 is standard output
    mov  cx,length      ; length of string in bytes
    mov  dx,string      ; address of first byte in string
    mov  ah,40h         ; DOS function code for write string
    int  21h            ; call DOS

    mov  ah,4Ch         ; DOS function code to exit program
    mov  al,0           ; pass this value back as ERRORLEVEL
    int  21h            ; call DOS (does not return)
;
; This is the subroutine to compute the recursive function, f(n).
;
; When called, the EAX register must have the parameter, n.
; Upon return, the EAX register has the function value, f(n).
;
; This subroutine uses the EBX and EDX registers.  The caller's values for
; those registers are saved on the stack.  The EAX register is not saved,
; because the function result is returned in EAX.
;
function:
    cmp  eax,1          ; parameters less than two have a simple result
    jg   function2      ; no, we will have to calculate the result
    mov  eax,1          ; set simple result for simple parameters
    ret                 ; return to caller
function2:
    push ebx            ; save caller's registers
    push edx
    mov  ebx,eax        ; save the caller's parameter, n
    dec  eax            ; make new parameter for n-1
    call function       ; call ourself recursively
    mov  edx,eax        ; save result for f(n-1)
    mov  eax,ebx        ; get back original parameter, n
    sub  eax,2          ; make new parameter for n-2
    call function       ; call ourself recursively
    add  eax,edx        ; add f(n-1) to f(n-2)
    pop  edx            ; restore caller's registers
    pop  ebx
    ret                 ; return to caller

[SECTION .data]         ; start data section
;
; The output string has several parts.  We only change the part that has
; the digits.
;
string   db   "Function value is "
digits   db   "          "   ; where decimal digits go
         db   ".", CR, LF    ; new line characters
length   equ  $ - string
;
; End of CPASM06S.ASM
;