The repository contains a collection of different programming snippets to different programming languages from own developments as well as other projects
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 261 lines 8.4 KiB Raw Permalink Blame History

 ```; fibo.asm ``` ```; assemble using nasm: ``` ```; nasm -o fibo.com -f bin fibo.asm ``` ```; ``` ```;**************************************************************************** ``` ```; Alterable Constant ``` ```;**************************************************************************** ``` ```; You can adjust this upward but the upper limit is around 150000 terms. ``` ```; the limitation is due to the fact that we can only address 64K of memory ``` ```; in a DOS com file, and the program is about 211 bytes long and the ``` ```; address space starts at 100h. So that leaves roughly 65000 bytes to ``` ```; be shared by the two terms (num1 and num2 at the end of this file). Since ``` ```; they're of equal size, that's about 32500 bytes each, and the 150000th ``` ```; term of the Fibonacci sequence is 31349 digits long. ``` ```; ``` ``` maxTerms equ 15000 ; number of terms of the series to calculate ``` ``` ``` ```;**************************************************************************** ``` ```; Number digits to use. This is based on a little bit of tricky math. ``` ```; One way to calculate F(n) (i.e. the nth term of the Fibonacci seeries) ``` ```; is to use the equation int(phi^n/sqrt(5)) where ^ means exponentiation ``` ```; and phi = (1 + sqrt(5))/2, the "golden number" which is a constant about ``` ```; equal to 1.618. To get the number of decimal digits, we just take the ``` ```; base ten log of this number. We can very easily see how to get the ``` ```; base phi log of F(n) -- it's just n*lp(phi)+lp(sqrt(5)), where lp means ``` ```; a base phi log. To get the base ten log of this we just divide by the ``` ```; base ten log of phi. If we work through all that math, we get: ``` ```; ``` ```; digits = terms * log(phi) + log(sqrt(5))/log(phi) ``` ```; ``` ```; the constants below are slightly high to assure that we always have ``` ```; enough room. As mentioned above the 150000th term has 31349 digits, ``` ```; but this formula gives 31351. Not too much waste there, but I'd be ``` ```; a little concerned about the stack! ``` ```; ``` ``` digits equ (maxTerms*209+1673)/1000 ``` ``` ``` ```; this is just the number of digits for the term counter ``` ``` cntDigits equ 6 ; number of digits for counter ``` ``` ``` ``` org 100h ; this is a DOS com file ``` ```;**************************************************************************** ``` ```;**************************************************************************** ``` ```main: ``` ```; initializes the two numbers and the counter. Note that this assumes ``` ```; that the counter and num1 and num2 areas are contiguous! ``` ```; ``` ``` mov ax,'00' ; initialize to all ASCII zeroes ``` ``` mov di,counter ; including the counter ``` ``` mov cx,digits+cntDigits/2 ; two bytes at a time ``` ``` cld ; initialize from low to high memory ``` ``` rep stosw ; write the data ``` ``` inc ax ; make sure ASCII zero is in al ``` ``` mov [num1 + digits - 1],al ; last digit is one ``` ``` mov [num2 + digits - 1],al ; ``` ``` mov [counter + cntDigits - 1],al ``` ``` ``` ``` jmp .bottom ; done with initialization, so begin ``` ``` ``` ```.top ``` ``` ; add num1 to num2 ``` ``` mov di,num1+digits-1 ``` ``` mov si,num2+digits-1 ``` ``` mov cx,digits ; ``` ``` call AddNumbers ; num2 += num1 ``` ``` mov bp,num2 ; ``` ``` call PrintLine ; ``` ``` dec dword [term] ; decrement loop counter ``` ``` jz .done ; ``` ``` ``` ``` ; add num2 to num1 ``` ``` mov di,num2+digits-1 ``` ``` mov si,num1+digits-1 ``` ``` mov cx,digits ; ``` ``` call AddNumbers ; num1 += num2 ``` ```.bottom ``` ``` mov bp,num1 ; ``` ``` call PrintLine ; ``` ``` dec dword [term] ; decrement loop counter ``` ``` jnz .top ; ``` ```.done ``` ``` call CRLF ; finish off with CRLF ``` ``` mov ax,4c00h ; terminate ``` ``` int 21h ; ``` ``` ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; PrintLine ``` ```; prints a single line of output containing one term of the ``` ```; Fibonacci sequence. The first few lines look like this: ``` ```; ``` ```; Fibonacci(1): 1 ``` ```; Fibonacci(2): 1 ``` ```; Fibonacci(3): 2 ``` ```; Fibonacci(4): 3 ``` ```; ``` ```; INPUT: ds:bp ==> number string, cx = max string length ``` ```; OUTPUT: CF set on error, AX = error code if carry set ``` ```; DESTROYED: ax, bx, cx, dx, di ``` ```; ``` ```;**************************************************************************** ``` ```PrintLine: ``` ``` mov dx,eol ; print combined CRLF and msg1 ``` ``` mov cx,msg1len+eollen ; ``` ``` call PrintString ; ``` ``` ``` ``` mov di,counter ; print counter ``` ``` mov cx,cntDigits ; ``` ``` call PrintNumericString ``` ``` ``` ``` call IncrementCount ; also increment the counter ``` ``` ``` ``` mov dx,msg2 ; print msg2 ``` ``` mov cx,msg2len ; ``` ``` call PrintString ; ``` ``` ``` ``` mov di,bp ; recall address of number ``` ``` mov cx,digits ; ``` ``` ; deliberately fall through to PrintNumericString ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; PrintNumericString ``` ```; prints the numeric string at DS:DI, suppressing leading zeroes ``` ```; max length is CX ``` ```; ``` ```; INPUT: ds:di ==> number string, cx = max string length ``` ```; OUTPUT: CF set on error, AX = error code if carry set ``` ```; DESTROYED: ax, bx, cx, dx, di ``` ```; ``` ```;**************************************************************************** ``` ```PrintNumericString: ``` ``` ; first scan for the first non-zero byte ``` ``` mov al,'0' ; look for ASCII zero ``` ``` cld ; scan from MSD to LSD ``` ``` repe scasb ; ``` ``` mov dx,di ; points to one byte after ``` ``` dec dx ; back up one character ``` ``` inc cx ; ``` ``` ; deliberately fall through to PrintString ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; PrintString ``` ```; prints the string at DS:DX with length CX to stdout ``` ```; ``` ```; INPUT: ds:dx ==> string, cx = string length ``` ```; OUTPUT: CF set on error, AX = error code if carry set ``` ```; DESTROYED: ax, bx ``` ```; ``` ```;**************************************************************************** ``` ```PrintString: ``` ``` mov bx, 1 ; write to stdout ``` ``` mov ah, 040h ; write to file handle ``` ``` int 21h ; ignore return value ``` ``` ret ; ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; AddNumbers ``` ```; add number 2 at ds:si to number 1 at es:di of width cx ``` ```; ``` ```; ``` ```; INPUT: es:di ==> number1, ds:si ==> number2, cx= max width ``` ```; OUTPUT: CF set on overflow ``` ```; DESTROYED: ax, si, di ``` ```; ``` ```;**************************************************************************** ``` ```AddNumbers: ``` ``` std ; go from LSB to MSB ``` ``` clc ; ``` ``` pushf ; save carry flag ``` ```.top ``` ``` mov ax,0f0fh ; convert from ASCII BCD to BCD ``` ``` and al,[si] ; get next digit of number2 in al ``` ``` and ah,[di] ; get next digit of number1 in ah ``` ``` popf ; recall carry flag ``` ``` adc al,ah ; add these digits ``` ``` aaa ; convert to BCD ``` ``` pushf ; ``` ``` add al,'0' ; convert back to ASCII BCD digit ``` ``` stosb ; save it and increment both counters ``` ``` dec si ; ``` ``` loop .top ; keep going until we've got them all ``` ``` popf ; recall carry flag ``` ``` ret ; ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; IncrementCount ``` ```; increments a multidigit term counter by one ``` ```; ``` ```; INPUT: none ``` ```; OUTPUT: CF set on overflow ``` ```; DESTROYED: ax, cx, di ``` ```; ``` ```;**************************************************************************** ``` ```IncrementCount: ``` ``` mov cx,cntDigits ; ``` ``` mov di,counter+cntDigits-1 ``` ``` std ; go from LSB to MSB ``` ``` stc ; this is our increment ``` ``` pushf ; save carry flag ``` ```.top ``` ``` mov ax,000fh ; convert from ASCII BCD to BCD ``` ``` and al,[di] ; get next digit of counter in al ``` ``` popf ; recall carry flag ``` ``` adc al,ah ; add these digits ``` ``` aaa ; convert to BCD ``` ``` pushf ; ``` ``` add al,'0' ; convert back to ASCII BCD digit ``` ``` stosb ; save and increment counter ``` ``` loop .top ; ``` ``` popf ; recall carry flag ``` ``` ret ; ``` ``` ``` ```;**************************************************************************** ``` ```; ``` ```; CRLF ``` ```; prints carriage return, line feed pair to stdout ``` ```; ``` ```; INPUT: none ``` ```; OUTPUT: CF set on error, AX = error code if carry set ``` ```; DESTROYED: ax, bx, cx, dx ``` ```; ``` ```;**************************************************************************** ``` ```CRLF: mov dx,eol ; ``` ``` mov cx,eollen ; ``` ``` jmp PrintString ; ``` ``` ``` ```;**************************************************************************** ``` ```; static data ``` ```;**************************************************************************** ``` ```eol db 13,10 ; DOS-style end of line ``` ```eollen equ \$ - eol ``` ``` ``` ```msg1 db 'Fibonacci(' ; ``` ```msg1len equ \$ - msg1 ``` ``` ``` ```msg2 db '): ' ; ``` ```msg2len equ \$ - msg2 ``` ```;**************************************************************************** ``` ```; initialized data ``` ```;**************************************************************************** ``` ```term dd maxTerms ; ``` ```;**************************************************************************** ``` ```; unallocated data ``` ```; ``` ```; A better way to do this would be to actually ask for a memory ``` ```; allocation and use that memory space, but this is a DOS COM file ``` ```; and so we are given the entire 64K of space. Technically, this ``` ```; could fail since we *might* be running on a machine which doesn't ``` ```; have 64K free. If you're running on such a memory poor machine, ``` ```; my advice would be to not run this program. ``` ```; ``` ```;**************************************************************************** ``` ```; static data ``` ```counter: ; ``` ```num1 equ counter+cntDigits ; ``` `num2 equ num1+digits ;`