C
CII
Hi everybody. I've been reading posts a year old about the fibonacci
series right on this newsgroup, and while it's not directly games
related, I'll share my own notes as well.
On another newsgroup there is an ongoing discussion about the famous
fibonacci sequences, and a fine program written by a poster got my
attention so just for fun I wrote one myself and put it on the web just
about two days ago. It can be found on the site
http://www.geocities.com/yssmlp
What I like about my program is that it's both small and fast, and it
makes a point: It's 207 bytes large, it handles nearly 300,000 terms
and it is very fast- it yields the first thousand or so terms in a
couple of seconds, I haven't measured it.
It is not (and it wasn't) my intention to compete trying to make the
best fibonacci program yet -incidentally I find the original poster's
attempt much better (much more elegant) than mine. What I wanted
instead was rather simply to have some fun analyzing a different
perspective from where to look at the famous sequence.
Oh yeah, and it's written in masm, for dos, in 2005, in 16 bit code
unoptimized
(just joking)
Cheers.
[I'm posting on several groups because I'm sure some people in them may
be interested in this topic, so please bear with me, Thank you.]
Here's the code for the fast and the curious:
..MODEL TINY
;----------
;PLAYING WITH FIBONACCI NUMBERS BY YSS (MAY 2005)
;
;F(N+2)=F(N+1)+F(N)
; F(0)=0, F(1)=1
;
;MAX TERMS = (60000 - LOG(SQR(5))/(LOG(1+SQR(5)/2))) / (LOG(1+SQR(5)/2))
; = 287090 APPROX.
;
;WHERE '60000' IS THE TOTAL NUMBER OF POSSIBLE DIGITS.
;
;THIS PROGRAM CALCS AND OUTPUTS THE 'FIBONACCI' SERIES TO STDOUT UP TO
;ABOUT 287000+ TERMS. IT'S NOT VERY FAST DUE TO:
;
; - NO OR LITTLE OPTIMIZATION (THIS CODE WAS WRITTEN 'ON THE FLY')
; - THE COMPRESSION OF THE DIGITS:
; EACH BYTE HOLDS TWO DECIMAL DIGITS IN LO-HI ORDER,
; THAT TAKES A LITTLE EXTRA TIME.
; - EACH DIGIT IS OUTPUT TO STDOUT ONE AT A TIME.
; A SPEED INCREASE OF OVER 32% CAN BE GAINED IF A FULL STRING
; IS OUTPUT INSTEAD.
;
;
;TWO ACCUMULATORS ARE USED, X1 AND X2, EACH CAPABLE OF HANDLING UP TO
60000
;DIGITS (30000 BYTES LONG EACH).
;
;USE:
;SET TL = MAX # OF TERMS -> ASSEMBLE -> F7 TO SEE RESULTS TO STDOUT
;TERMS ARE OUTPUT ONE LINE AT A TIME (ENDED WITH 0D 0A)
;
;
CSEG SEGMENT PARA PUBLIC 'CODE'
ORG 100H
ASSUME CS:CSEG,DS:CSEG
START:
X1 EQU 0
X2 EQU X1 + 30000
TL EQU 287000 ;TOTAL TERMS TO CALC
MOV DI,OFFSET A+X1
MOV CX,60000/2
REP STOSW ;CLR ALL
INC AX
MOV X1T,AX
MOV [A+X1],AX ;
MOV BP,TL ;TOTAL # TERMS [ F(X) ] CALC'D
S00:
MOV DI,OFFSET A+X2
MOV SI,OFFSET A+X1
TEST BL,1
JNE S001
XCHG DI,SI
S001:
CALL LOUT
ADD12:
PUSH DI
PUSH SI
PUSH BP
XOR BP,BP
MOV CX,X1T
CLC
ACXMRE:
MOV AL,[DI]
MOV DL,[SI]
MOV AH,DL
PUSH AX
CALL AAB1
MOV DH,AL
POP AX
PUSHF
SHR AX,1
SHR AX,1
SHR AX,1
SHR AX,1
POPF
CALL AAB1
PUSHF
AND DH,0FH
SHL AL,1
SHL AL,1
SHL AL,1
SHL AL,1
OR AL,DH
POPF
MOV [SI],AL
JNB ADOK
CMP CX,1
STC
JNE ADOK
INC CX
ADOK:
INC DI
INC SI
INC BP
LOOP ACXMRE
MOV X1T,BP
POP BP
POP SI
POP DI
DEC BL
DEC BP
JNE S00
RET
LOUT:
MOV DX,X1T
PUSH DI
PUSH SI
MOV AH,2
MOV SI,DI
DEC SI
ADD DI,DX
MOV CX,000FEH ;CH=0 FOR LEADING 0'S NOT OUT
LN0001:
MOV DL,[DI]
TEST CL,1
JNE LN0000
SHR DL,1
SHR DL,1
SHR DL,1
SHR DL,1
JMP SHORT LN0002
LN0000:
DEC DI
LN0002:
AND DL,0FH
OR DL,30H
CMP DL,30H
JE LN00201
OR CH,1
JMP LN0020
LN00201:
TEST CH,1
JE LN00202
LN0020:
INT 21H
LN00202:
DEC CL
CMP DI,SI
JNE LN0001
POP SI
POP DI
ODOAH:
MOV AH,9
MOV DX,OFFSET ODOAX
INT 21H
RET
ODOAX DB 13,10,36
AAB1:
PUSHF
AND AX,0F0FH
POPF
ADC AL,AH
AAA
RET
AAA
RET
AAA
RET
AAA
RET
X1T DW 0 ;#DIGITS SO FAR
A LABEL WORD
;-------------------------------
;http://www.geocities.com/yssmlp
;[email protected]
;or google around for "yssmlp" !
;-------------------------------
CSEG ENDS
END START
series right on this newsgroup, and while it's not directly games
related, I'll share my own notes as well.
On another newsgroup there is an ongoing discussion about the famous
fibonacci sequences, and a fine program written by a poster got my
attention so just for fun I wrote one myself and put it on the web just
about two days ago. It can be found on the site
http://www.geocities.com/yssmlp
What I like about my program is that it's both small and fast, and it
makes a point: It's 207 bytes large, it handles nearly 300,000 terms
and it is very fast- it yields the first thousand or so terms in a
couple of seconds, I haven't measured it.
It is not (and it wasn't) my intention to compete trying to make the
best fibonacci program yet -incidentally I find the original poster's
attempt much better (much more elegant) than mine. What I wanted
instead was rather simply to have some fun analyzing a different
perspective from where to look at the famous sequence.
Oh yeah, and it's written in masm, for dos, in 2005, in 16 bit code
unoptimized
(just joking)Cheers.
[I'm posting on several groups because I'm sure some people in them may
be interested in this topic, so please bear with me, Thank you.]
Here's the code for the fast and the curious:
..MODEL TINY
;----------
;PLAYING WITH FIBONACCI NUMBERS BY YSS (MAY 2005)
;
;F(N+2)=F(N+1)+F(N)
; F(0)=0, F(1)=1
;
;MAX TERMS = (60000 - LOG(SQR(5))/(LOG(1+SQR(5)/2))) / (LOG(1+SQR(5)/2))
; = 287090 APPROX.
;
;WHERE '60000' IS THE TOTAL NUMBER OF POSSIBLE DIGITS.
;
;THIS PROGRAM CALCS AND OUTPUTS THE 'FIBONACCI' SERIES TO STDOUT UP TO
;ABOUT 287000+ TERMS. IT'S NOT VERY FAST DUE TO:
;
; - NO OR LITTLE OPTIMIZATION (THIS CODE WAS WRITTEN 'ON THE FLY')
; - THE COMPRESSION OF THE DIGITS:
; EACH BYTE HOLDS TWO DECIMAL DIGITS IN LO-HI ORDER,
; THAT TAKES A LITTLE EXTRA TIME.
; - EACH DIGIT IS OUTPUT TO STDOUT ONE AT A TIME.
; A SPEED INCREASE OF OVER 32% CAN BE GAINED IF A FULL STRING
; IS OUTPUT INSTEAD.
;
;
;TWO ACCUMULATORS ARE USED, X1 AND X2, EACH CAPABLE OF HANDLING UP TO
60000
;DIGITS (30000 BYTES LONG EACH).
;
;USE:
;SET TL = MAX # OF TERMS -> ASSEMBLE -> F7 TO SEE RESULTS TO STDOUT
;TERMS ARE OUTPUT ONE LINE AT A TIME (ENDED WITH 0D 0A)
;
;
CSEG SEGMENT PARA PUBLIC 'CODE'
ORG 100H
ASSUME CS:CSEG,DS:CSEG
START:
X1 EQU 0
X2 EQU X1 + 30000
TL EQU 287000 ;TOTAL TERMS TO CALC
MOV DI,OFFSET A+X1
MOV CX,60000/2
REP STOSW ;CLR ALL
INC AX
MOV X1T,AX
MOV [A+X1],AX ;
MOV BP,TL ;TOTAL # TERMS [ F(X) ] CALC'D
S00:
MOV DI,OFFSET A+X2
MOV SI,OFFSET A+X1
TEST BL,1
JNE S001
XCHG DI,SI
S001:
CALL LOUT
ADD12:
PUSH DI
PUSH SI
PUSH BP
XOR BP,BP
MOV CX,X1T
CLC
ACXMRE:
MOV AL,[DI]
MOV DL,[SI]
MOV AH,DL
PUSH AX
CALL AAB1
MOV DH,AL
POP AX
PUSHF
SHR AX,1
SHR AX,1
SHR AX,1
SHR AX,1
POPF
CALL AAB1
PUSHF
AND DH,0FH
SHL AL,1
SHL AL,1
SHL AL,1
SHL AL,1
OR AL,DH
POPF
MOV [SI],AL
JNB ADOK
CMP CX,1
STC
JNE ADOK
INC CX
ADOK:
INC DI
INC SI
INC BP
LOOP ACXMRE
MOV X1T,BP
POP BP
POP SI
POP DI
DEC BL
DEC BP
JNE S00
RET
LOUT:
MOV DX,X1T
PUSH DI
PUSH SI
MOV AH,2
MOV SI,DI
DEC SI
ADD DI,DX
MOV CX,000FEH ;CH=0 FOR LEADING 0'S NOT OUT
LN0001:
MOV DL,[DI]
TEST CL,1
JNE LN0000
SHR DL,1
SHR DL,1
SHR DL,1
SHR DL,1
JMP SHORT LN0002
LN0000:
DEC DI
LN0002:
AND DL,0FH
OR DL,30H
CMP DL,30H
JE LN00201
OR CH,1
JMP LN0020
LN00201:
TEST CH,1
JE LN00202
LN0020:
INT 21H
LN00202:
DEC CL
CMP DI,SI
JNE LN0001
POP SI
POP DI
ODOAH:
MOV AH,9
MOV DX,OFFSET ODOAX
INT 21H
RET
ODOAX DB 13,10,36
AAB1:
PUSHF
AND AX,0F0FH
POPF
ADC AL,AH
AAA
RET
AAA
RET
AAA
RET
AAA
RET
X1T DW 0 ;#DIGITS SO FAR
A LABEL WORD
;-------------------------------
;http://www.geocities.com/yssmlp
;[email protected]
;or google around for "yssmlp" !
;-------------------------------
CSEG ENDS
END START