NASM Forum > Example Code

Fibonacci, with bigger numbers

(1/3) > >>

andyz74:
This is a mess of a code, I have to admire, but it works, as I see.
In this version, it is hardcoded for a maximum until fib(399), which has 63 numbers (or ciphers? sorry, don't know it correct in english...)
and a hardcoded maximum until 80 numbers (or ciphers? sorry, don't know it correct in english...)

This is Linux 64bit.


--- Code: ---; fibogr.asm
;
; errechnet Fibonacci's und gibt jene aus.
; nasm -f elf64 fibogr.asm
; ld -s -o fibogr fibogr.o      "warum -s ? -s "strippt" die Debug-Infos weg. Wenn man debuggen will, lieber ohne -s"

[bits 64]

SECTION .data

_overflow_msg db '*** Series overflown.',0ah
len_overflow_msg equ $-_overflow_msg
_one db '1 '
_endl db 10
_leerz db 32
ziffer db 0

SECTION .bss
 f1array  :  resb 80
 f2array  :  resb 80
 f3array  :  resb 80



global _start ; global entry point export for ld

SECTION .text

_start:
start:


mov rax, 0
.nochmal1:
mov byte [f1array+rax],0
mov byte [f2array+rax],0
mov byte [f3array+rax],0

inc rax
cmp rax, 81
jne .nochmal1
mov byte [f1array],1
mov byte [f2array],1

mov r15, 300 ; HARDCODED : 300 fib-Zahlen machen.
; soviele fib() sollen errechnet werden...
cmp eax, 0
jz .done

dec r15
jz .done ; wenn fertig, ganz runter, Ende



call .ausgabe_f2
call .crlf

.calc_fibo:
call .kill_f3

mov r14, 0 ; r14 ist Index, wo im Array wir sind.
mov cl, 0
.alle_ziffern:
mov rax, 0
mov rbx, 0
mov r13, 0
mov al, byte [f1array+r14]
add [f3array+r14], al
mov bl, byte [f2array+r14]
add [f3array+r14], bl
mov bl, byte [f3array+r14]
jo .overflow ; Ergebnis zu groß für Datentyp?
nop
nop

inc r14
cmp r14, 80
jne .alle_ziffern

; *****  hier fertig mit rechnen *******



call .adjust_f3

call .shift_arrays

call .ausgabe_f3
call .crlf



 .done:
; call .crlf

dec r15
jnz .calc_fibo ; alle Fibos berechnet ?

mov eax, 1 ; Programmende
mov ebx, 0
int 80h

.overflow:
mov eax, 4
mov ebx, 1
mov ecx, _overflow_msg
mov edx, len_overflow_msg
int 80h

mov eax, 1
mov ebx, 1
int 80h

; *******************************************************************
; *********************** ab hier proceduren ************************
; *******************************************************************


.shift_arrays:
push rax
push rbx
push rcx
push rdx
mov rax, 0
.nochmal3:
mov ch, byte [f2array+rax]
mov byte [f1array+rax], ch

mov ch, byte [f3array+rax]
mov byte [f2array+rax], ch
inc rax
cmp rax, 80
jne .nochmal3
pop rdx
pop rcx
pop rbx
pop rax
ret


.crlf:
push rax
push rbx
push rcx
push rdx
mov eax, 4 ; schreiben
mov ebx, 1
mov ecx, _endl
mov edx, 1
int 80h
pop rdx
pop rcx
pop rbx
pop rax
ret

.leer:
push rax
push rbx
push rcx
push rdx
mov eax, 4 ; schreiben
mov ebx, 1
mov ecx, _leerz
mov edx, 1
int 80h
pop rdx
pop rcx
pop rbx
pop rax
ret


.ausgabe_f1:
push rax
push rbx
push rcx
push rdx
mov r12, 80 ; Zur Ausgabe des Arrays r12 als Index
.noch_ein_array_teil:
dec r12
mov rcx, 0
mov cl, byte [f1array+r12]
add ecx, "0"
mov byte[ziffer], cl
mov eax, 4 ; fertige "Zahl" ausgeben
mov ebx, 1
mov edx, 1 ; Länge, hier bei uns immer 1
mov ecx, ziffer
int 80h
cmp r12, 0
jne .noch_ein_array_teil
pop rdx
pop rcx
pop rbx
pop rax
ret

.ausgabe_f2:
push rax
push rbx
push rcx
push rdx
mov r12, 80 ; Zur Ausgabe des Arrays r12 als Index
.noch_ein_array_teil2:
dec r12
mov rcx, 0
mov cl, byte [f2array+r12]
add ecx, "0"
mov byte[ziffer], cl
mov eax, 4 ; fertige "Zahl" ausgeben
mov ebx, 1
mov edx, 1 ; Länge, hier bei uns immer 1
mov ecx, ziffer
int 80h
cmp r12, 0
jne .noch_ein_array_teil2
pop rdx
pop rcx
pop rbx
pop rax
ret

.ausgabe_f3:
push rax
push rbx
push rcx
push rdx
mov r13, 0  ; solange führende Nullen, später dann 1
mov r12, 80 ; Zur Ausgabe des Arrays r12 als Index
.noch_ein_array_teil3:
dec r12
mov rcx, 0
mov cl, byte [f3array+r12]
cmp r13, 0
jne .write_it ; wenn schon richtige Ziffern waren, dann hüpfen

cmp cl, 0
jne .write_it_vor ; wenn ab jetzt richtige Zahlen kommen, dann hüpfen

mov byte[ziffer], 32 ; führende Null soll Leerzeichen werden
jmp .ausgabe_leerz
.write_it_vor:
mov r13,1
.write_it:
add cl, "0"
mov byte[ziffer], cl
.ausgabe_leerz:
mov eax, 4 ; fertige "Zahl" ausgeben
mov ebx, 1
mov edx, 1 ; Länge, hier bei uns immer 1
mov ecx, ziffer
int 80h
cmp r12, 0
jne .noch_ein_array_teil3
pop rdx
pop rcx
pop rbx
pop rax
ret

.kill_f3:
push rax
mov rax, 0
.nochmal2:
mov byte [f3array+rax],0
inc rax
cmp rax, 81
jne .nochmal2
pop rax
ret


.adjust_f3:
push rax
push rbx ; Indexzähler
push rcx ; einzelner Wert
push rdx
mov rcx, 0
.nochmal4:
mov bx, 0
mov bl, byte [f3array+rcx]
cmp bl, 10 ; größer als 9  ?
jl .good
xor ax, ax
mov ax, bx
add byte [f3array+rcx+1], 1
xor rdx, rdx
mov bx, 10
div bx
; Zehner in eax, Einer in rdx
mov byte [f3array+rcx], dl
.good:
inc rcx
cmp rcx, 79
jne .nochmal4
pop rdx
pop rcx
pop rbx
pop rax
ret


--- End code ---

debs3759:
Another way to find the nth number (an) in the sequence is

an = [Phi^n – (phi)^n] / Sqrt[5].
where Phi = (1 + Sqrt[5]) / 2
and phi = (1 – Sqrt[5]) / 2 (or (-1 / Phi))

andyz74:
Thank you debs, I will test this too.

But in my program, the major aspect was, how to handle the big numbers. :-)

fredericopissarra:

--- Quote from: debs3759 on November 21, 2023, 09:58:04 PM ---Another way to find the nth number (an) in the sequence is

an = [Phi^n – (phi)^n] / Sqrt[5].
where Phi = (1 + Sqrt[5]) / 2
and phi = (1 – Sqrt[5]) / 2 (or (-1 / Phi))

--- End quote ---
The problem with these approaches is lack of "precision" for big n.
To make this work you have to deal with "multi precision arithmetic".

[]s
Fred

alCoPaUL:
the algorithm for any math functions should preserve the integer size of the initial result and just spit out the desired result as

[2]
[4]2
[6]42
[..]...642

and do compression on the output big number, say compress([..]...642)

and you save time, extra loops and space

Navigation

[0] Message Index

[#] Next page