Fibonacci, with bigger numbers

[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: [Select]

; 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



[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]

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))

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

[fredericopissarra]

The real problem is that fib(399) results in a 84 algarisms number:

108788617463475645289761992289049744844995705477812699099751202749393926359816304226

float has roughly 7 decimal algarisms of precision, double has 16 and long double, 19.
This means it is not possible to store an 84 algarisms (not 63!) integer in any standard floating point object (including __float128 with GCC, which has 34 algarisms of precision).

You have to use multiple precision arithmetic to do this.

[debs3759]

I had to google "algorism". I'm a mathematician (or was, before my memory started to fail) and had never heard the term! I thought you had mistranslated something Now I need to find an opportunity to play it in a Scrabble game

[fredericopissarra]

I had to google "algorism". I'm a mathematician (or was, before my memory started to fail) and had never heard the term! I thought you had mistranslated something Now I need to find an opportunity to play it in a Scrabble game

Not "algorism", but "algarism" (with 'a'). Word of perian origin.
I don't know if it is common in modern english. Maybe a better approximation is 'numeral' or 'digit'.
Sorry, I'm brazillian!

[debs3759]

I had to google "algorism". I'm a mathematician (or was, before my memory started to fail) and had never heard the term! I thought you had mistranslated something Now I need to find an opportunity to play it in a Scrabble game

Not "algorism", but "algarism" (with 'a'). Word of perian origin.
I don't know if it is common in modern english. Maybe a better approximation is 'numeral' or 'digit'.
Sorry, I'm brazillian!

Yeah, I mistyped. I googled algarism. It's not common to me, but might be in some mathematical or technical circles. It's not a valid Scrabble word in international English (according to Collins dictionaries), so may be archaic. Google knows it though.

[debs3759]

Just checked again, and it is actually "algorism", searching "algarism" gives results for "algorism", which mostly describe it as a digit. With an "O" it is valid in Scrabble, my reference for valid words

[andyz74]

The real problem is that fib(399) results in a 84 algarisms number:

108788617463475645289761992289049744844995705477812699099751202749393926359816304226

Therefor, I use in my code  this :

Code: [Select]

SECTION .bss
 f1array  :  resb 80
 f2array  :  resb 80
 f3array  :  resb 80
Each digit is stored in a separate byte inside this array. So I can add for example  f1array[5] + f2array[5] and store it in f3array[5] . If I do this for all array-elements, then I can afterwards calculate with DIV  and MOD that the f3array-elements are not bigger than 9, and in this way I get in f3array the new fibonacci with every digit in one byte stored.  The size of the array by now 80 bytes is hardcoded, but can easily made bigger. I tested numbers with up to 160 digits, and I am sure, there can be calculated even bigger ones.

/edit :
Just for the fun of it, I modified the arrays to 10000 and the fibonaccis to 5000 and found out, that fibonacci around 5000 is :

6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626

(I'm not sure if my indexing is totally correct.maybe it is fib(4999) or fib(5001).

[fredericopissarra]

fib(5000) is 1060 digits long.

Yep, You can calculate individual fibonacci numbers and count them until you get the nth one, but this is SLOW! The method @debs3759 shown is way faster (but imprecise for big n's using floating point).

Here's what debs shown us using 'bc':

Code: [Select]

/* mylib.bc */

define floor(x) {
  auto savescale;
  savescale = scale;
  scale = 0;
  if (x>0) {
    result = x-(x%1);
  } else result = -1*ceil(-1*x);

  scale = savescale;
  return result;
}

define ceil(x) {
  auto savescale;
  savescale = scale;
  scale = 0;
  if (x>0) {
    if (x%1>0) {
      result = x+(1-(x%1));
    } else result = x;
  } else result = -1*floor(-1*x);

  scale = savescale;
  return result;
}

// Assumes n>=1.
define fib(n) {
  auto phi, mphi;

  phi=(1+sqrt(5))/2;
  mphi=(1-sqrt(5))/2;

  return ceil((phi^n - mphi^n)/sqrt(5));
}Example:

Code: [Select]

$ bc -l ~/mylib.bc
fib(5000)
38789684543883255787369523000067185813843640028173778214077063506222\
03626861036808248455912761813059468350786484422176811658220804962450\
29069184465594582576927498373724753759527124653223656298532750056632\
01060665353651777933424438814671053850391430712735946163002282127796\
60104942391587821365405512857641059075227875609418561328142905218293\
75223351638376793068843397731129032544938237979278224184462155169779\
33412380514940819848047352373339972493973345971795548788264778422208\
30786080304051484013516612073651839454277630050248124263940786334517\
92509502669794024881601256583612837306316525432034646767889252248450\
71547922647855111740487657724282206319735894115144216122296951101007\
11629030794256019893215415437535300624534716833241942865160104177628\
09548131751704547486687263947783482447682794081805860772772003462539\
09005994915142835952622461342113322912040562545514910385588687101957\
16462440938578326400089494547058877514998175627864862046335690230149\
76205674064739162487211225072811693356299232578142392900467875891172\
4843681785226992664913336.00000000000000000000'bc' uses multi precision arithmetic.

Anyway... if you'll use add/adc approach, do it with DWORDs or QWORDs instead of bytes...

[fredericopissarra]

To be fair, using 'bc' this way isn't correct as well... Here's a simple code using 'libgmp' to illustrate:

Code: [Select]

// fib.c
//
//    cc -O2 -o fib fib.c -lgmp
//
#include <gmp.h>

// Prints all fibonacci numbers from the first to the 5000th.
int main(void)
{
  mpz_t n;
  mpz_init( n );

  for ( unsigned int i = 1; i <= 5000; i++ )
  {
    mpz_fib_ui( n, i );
    gmp_printf( "%u: %Zd\n", i, n );
  }

  mpz_clear( n );
}The 5000th number is  3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125.

[andyz74]

I am thankful for your informations and ideas! :-)

Nevertheless, due to my historic age, I teached myself ages ago Pascal and a bit of Assembler. I cannot learn new programing languages, my brain is full. ;-)
And in addition, my primary goal is teaching myself, how to handle (in Assembler and Pascal) bigger numbers as normally possible.   The above seems to be a good way for myself to understand all this.

Nevertheless, many thanks for your thoughts.