Recent Posts

Pages: 1 ... 8 9 [10]
91
Example Code / Re: Fibonacci, with bigger numbers
« Last post by fredericopissarra on November 28, 2023, 05:30:49 PM »
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.
92
Example Code / Re: Fibonacci, with bigger numbers
« Last post by fredericopissarra on November 28, 2023, 12:27:51 PM »
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...
93
Example Code / Re: Fibonacci, with bigger numbers
« Last post by andyz74 on November 27, 2023, 08:11:07 PM »
Quote from: fredericopissarra on November 27, 2023, 12:44:45 PM
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).
94
Example Code / Re: Fibonacci, with bigger numbers
« Last post by debs3759 on November 27, 2023, 05:47:26 PM »
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 :)
95
Example Code / Re: Fibonacci, with bigger numbers
« Last post by debs3759 on November 27, 2023, 05:43:52 PM »
Quote from: fredericopissarra on November 27, 2023, 02:37:57 PM
Quote from: debs3759 on November 27, 2023, 02:21:31 PM
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.
96
Example Code / Re: Fibonacci, with bigger numbers
« Last post by fredericopissarra on November 27, 2023, 02:37:57 PM »
Quote from: debs3759 on November 27, 2023, 02:21:31 PM
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!
97
Example Code / Re: Fibonacci, with bigger numbers
« Last post by debs3759 on November 27, 2023, 02:21:31 PM »
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 :)
98
Example Code / Re: Fibonacci, with bigger numbers
« Last post by fredericopissarra on November 27, 2023, 12:44:45 PM »
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.
99
Example Code / Re: Fibonacci, with bigger numbers
« Last post by alCoPaUL on November 26, 2023, 09:29:17 PM »
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

100
Example Code / Re: Fibonacci, with bigger numbers
« Last post by fredericopissarra on November 22, 2023, 10:01:28 AM »
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))
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
Pages: 1 ... 8 9 [10]