Heater
Posts: 12744
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 10:44 pm

danjperron,

If you run the python code I just posted here it will output the one million digits of fibo(4784969). You can redirect them to a file for comparison:

Code: Select all

$ python fibo.py > fibo_4784969.dat
You may want to remove the the last line of the program that prints the run time.

I'm pretty sure this is the correct result. We have had enough people comparing results for the last half a year!
I think that you are using double value. Then you have an estimation of the Fibonacci and not the exact value.
No. I just use regular Python integers. There are no floating point numbers being used here.

User avatar
davidcoton
Posts: 3810
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 10:50 pm

danjperron wrote:
Mon Jun 03, 2019 10:29 pm

Do you have a place were you have the 1 millions digit from fibo(4784969). I want to compare yours against mine to be sure that all digits are the same!.

I think that you are using double value. Then you have an estimation of the Fibonacci and not the exact value.
This is why I'm using the Decimal module which I do have the resolution to the last digit. This is why it is very slow to calculate when you have 1millions digits to calculate,
See the original challenge in "Why Avoid BASIC on RPi" in Off-Topic. There are 93 pages of semi-relevant stuff, along with rants, opinion, and plain error! But the key parts of verifying an answer start about here., with checksums (not the full million digits) on the following page. Enough is shown to verify any algorithm.
AFAICT all the methods shown there and here produce arbitary (ie, million decimal digit) precision, or they are rejected.
Signature retired

timrowledge
Posts: 1266
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 12:38 am

danjperron wrote:
Mon Jun 03, 2019 8:21 pm
Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

timrowledge
Posts: 1266
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 12:41 am

Heater wrote:
Mon Jun 03, 2019 6:11 pm
timrowledge,
Javascript was created by Brendan Eich. He wanted to make Self for the browser but Netscape insisted he make it look more like Java. That is why JS has all those Scheme like features: first class functions, closures, etc.
And let's remember that Self came out of the Smalltalk community...
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

danjperron
Posts: 3334
Joined: Thu Dec 27, 2012 4:05 am
Location: Québec, Canada

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 12:51 am

Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?
Decimal module in python is different from normal floating point. You are able to assign N numbers of decimals. This is why it is so slow.......
For 1 millions number you will need at least 1 millions of digit + some digits to compensate for floating errors. If you look at my code I'm using the log10 to get around the correct number of digits needed and then I add some precision digits. Once I got the precision then I'm using the number of decimals needed.

This is why Heater method works faster because the integer part of Python uses unlimited bits length, (I just find out ).
Floating are not the same than Decimals!

ejolson
Posts: 3084
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 12:55 am

timrowledge wrote:
Tue Jun 04, 2019 12:38 am
danjperron wrote:
Mon Jun 03, 2019 8:21 pm
Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?
The exact formula is

F(n) = (ϕ^n − (−ϕ)^(−n))/sqrt(5)

which, in spite of the divisions and square roots, is always an integer. When n is large the term

(−ϕ)^(−n)/sqrt(5)

is very small. Therefore, it can be neglected and the resulting approximation

F(n) ≈ ϕ^n/sqrt(5)

rounded to the nearest integer to obtain the exact value. It is possible that this trick only works when n is large enough, but I haven't checked.

timrowledge
Posts: 1266
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 12:58 am

Heater wrote:
Mon Jun 03, 2019 9:07 pm
It takes 32 seconds in Squeak Smalltalk on my old PC. Over five hours in GNU Smalltalk!
As we've mentioned, the latest version (which you can get simply by updating from within the system you already have) is a bit faster and actually does the calculation in 6.6 secs (not 11) on my Pi3 or 0.9s on my i7 iMac. Printing it out adds another 10 (3 on Imac) or so. And really, I don't recommend using GNU Smalltalk for anything; it's a long way out of date, etc etc. All you're doing there is punishing yourself!
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 1:28 am

Has BIGINT been a feature of Python from the beginning? If not, my addition of GMP to ScriptBasic would be no different.

User avatar
Paeryn
Posts: 2570
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 2:03 am

ScriptBasic wrote:
Tue Jun 04, 2019 1:28 am
Has BIGINT been a feature of Python from the beginning? If not, my addition of GMP to ScriptBasic would be no different.
Yes, Python 2 has always had arbitrary precision integers, I'm sure Python 1 and even Python 0.9 had them. In Python 2 you have integer which is either 16 or 32 bit (depended mainly on the register size of the platform it is on) and for numbers outside that range there is long which is the arbitrary precision integer type.

Most of the time if, say a function takes two integers and adds them, if the sum is greater than what an integer can hold then you return the answer as a long instead.

Python 3 merged the two in to a single int type, as long as the value it holds is small enough to fit in the machine's registers it is stored exactly as a word, if it is over then Python uses a custom format whereby only the absolute of a number is stored, the sign is held in the sign of the size field of the number (so size 2 means +ve value stored in 2 words, size -2 means the +ve value stored in the two words is really a negative value). It stores 30 bits of the number in each word (15 on 16-bit cpus).
Last edited by Paeryn on Tue Jun 04, 2019 2:21 am, edited 1 time in total.
She who travels light — forgot something.

User avatar
scruss
Posts: 2275
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 2:15 am

ejolson wrote:
Tue Jun 04, 2019 12:55 am
timrowledge wrote:
Tue Jun 04, 2019 12:38 am
Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?

F(n) ≈ ϕ^n/sqrt(5)

… It is possible that this trick only works when n is large enough, but I haven't checked.
It works from the get-go:

Code: Select all

10 DEF FNfib(n)=INT(0.5+((SQR(5)+1)/2)^n/SQR(5))
20 FOR i=0 TO 20
30   PRINT i,FNfib(i)
40 NEXT i
Of course, you run out of bits in floating point pretty quickly. But if you're using big floats - like PARI/GP does - it's not a problem.
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

danjperron
Posts: 3334
Joined: Thu Dec 27, 2012 4:05 am
Location: Québec, Canada

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 2:18 am

rounded to the nearest integer to obtain the exact value. It is possible that this trick only works when n is large enough, but I haven't checked.
nope it works even with small numbers
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 2
1
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 3
1.894427190999915878563669466
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 4
3.065247584249852787486421565
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 5
4.959674775249768666050091030
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 6
8.024922359499621453536512592
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 7
12.98459713474939011958660362
MacBook-Air-de-Daniel:~ daniel$
round the value and it is exact.

danjperron
Posts: 3334
Joined: Thu Dec 27, 2012 4:05 am
Location: Québec, Canada

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 5:37 am

ok I made one in C using tables of 32bits digits.

It is not finished since I need to convert the result from hex to decimal. But it is blazzing fast.

This version uses the same method than fibo.py. Since you don't want gmp, I made my own multiply and add fonction.

Code: Select all

#include <stdlib.h>
#include  <stdio.h>
#include <string.h>

typedef struct{
 int bytesize;
 unsigned int * pt;
}BigN_struct;

extern void print_BigN(BigN_struct *);

typedef struct{
  int index;
  BigN_struct number;
}Fibs_struct;


int fibs_size=100;
Fibs_struct * fibs;
int MaxFibs;

BigN_struct Big2;


Fibs_struct * fiboAdd(int n,BigN_struct * P)
{

  if((MaxFibs+1) >= fibs_size)
  {
     fibs_size+=100;
     realloc(fibs, sizeof(Fibs_struct)*fibs_size);
  }
 fibs[MaxFibs].index=n;
 fibs[MaxFibs].number= *P;
 MaxFibs++;
 return(&(fibs[MaxFibs-1]));
}


Fibs_struct * fiboFind(int n)
{
  int loop;
  for(loop = 0 ;loop < MaxFibs;loop++)
  {
     if(fibs[loop].index == n)
        return  &(fibs[loop]);
  }
  return NULL;
}



void deleteFibs()
 {
   int loop;
   for(loop=0;loop<MaxFibs;loop++)
   {
     if(fibs[loop].number.pt == NULL)
         continue;
     free(fibs[loop].number.pt);
     fibs[loop].number.pt=NULL;
   }
}


void Big_Reduce(BigN_struct *P)
{
   int loop;
   for(loop= P->bytesize-1 ; loop>0;loop--)
     if(P->pt[loop]) break;
   P->bytesize= loop+1;

}



BigN_struct *  Big_Mul(BigN_struct *p1, BigN_struct * p2)
{
   unsigned long long v;
   int loopa,loopb;

   int bytesize= p1->bytesize + p2->bytesize;
   BigN_struct * result =  malloc(sizeof(BigN_struct));

   result->bytesize=bytesize;
   result->pt= malloc(bytesize * sizeof(int));
   for(loopa=0;loopa<bytesize;loopa++)
       result->pt[loopa]=0;
//   memset(result->pt,bytesize,0); 


  int p1s= p1->bytesize;
  int p2s= p2->bytesize;

  unsigned int * pta= p1->pt;
  unsigned int * ptb;
  unsigned int * ptr;

   for(loopa=0;loopa<p1s;loopa++)
    {
      ptr = &(result->pt[loopa]);
      ptb = p2->pt;
     for(loopb=0;loopb<p2s;loopb++)
        {
           v = (*pta)  * (*(ptb++));
           *(ptr++)+=  v & 0xffffffff;
           v >>=32;
           if(v)
            (*ptr)+= v;
        }
      pta++;
    }


  Big_Reduce(result);


  return result;

}


BigN_struct *  Big_Add(BigN_struct *p1, BigN_struct * p2)
{

   int loop;
   int bytesize;


   BigN_struct * result =  malloc(sizeof(BigN_struct));

   if(p1->bytesize > p2->bytesize)
      bytesize = p1->bytesize;
   else
      bytesize = p2->bytesize;

   result->bytesize=bytesize;
   result->pt= malloc((bytesize+1) * sizeof(int));

   unsigned long long  v=0;

   for(loop=0;loop<bytesize;loop++)
    {
       if(p1->bytesize>= loop)
          v+= p1->pt[loop];
       if(p2->bytesize>= loop)
          v+= p2->pt[loop];
       result->pt[loop]= v & 0xffffffff;
        v >>=32;
    }
    if(v)
      {
       result->bytesize++;
       result->pt[result->bytesize-1]=v;
      }
    Big_Reduce(result);
    return(result);
}


void print_BigN(BigN_struct * P)
{
  int loop;
  printf("byte size = %d\n",P->bytesize);
  for(loop=(P->bytesize -1);loop>=0;loop--)
     printf("%08X ",P->pt[loop]);
  printf("\n");
}


Fibs_struct * fibo(int n)
{
  int k;
  BigN_struct * n1,* n2,*n3;
  Fibs_struct * fk = fiboFind(n);
  Fibs_struct * fk1;

  if(fk)
   {
     return fk;
   }


  k = (n + 1) / 2;

  fk = fibo(k);

  fk1 = fibo(k-1);

  if(n&1)
   {
//        result = fk ** 2 + fk1 ** 2
     n1 = Big_Mul(&(fk->number),&(fk->number));
     n2 = Big_Mul(&(fk1->number),&(fk1->number));
     n3 = Big_Add(n1,n2);
   }
   else
   {
//        result = (2 * fk1 + fk) * fk
     n1 = Big_Mul(&(fk1->number),&Big2);
     n2 = Big_Add(n1,&(fk->number));
     n3 = Big_Mul(n2,&(fk->number));
   }
   fk =	fiboAdd(n,n3);
   free(n1);
   free(n2);
   free(n3);
   return(fk);
}



int main(int argc, char * argv[])
{
  int loop;
  int * fibs_idx;
  fibs = malloc(fibs_size * sizeof(Fibs_struct));
  MaxFibs=2;
  // create First and second Number
  fibs[0].index=1;
  fibs[0].number.bytesize=1;
  fibs[0].number.pt = malloc(4);
  fibs[0].number.pt[0] = 1;

  fibs[1].index=2;
  fibs[1].number.bytesize=1;
  fibs[1].number.pt = malloc(4);
  fibs[1].number.pt[0] = 1;

  // create number 2 in BigN
  Big2.bytesize=1;
  Big2.pt = malloc(4);
  Big2.pt[0]=2;



  int value;
  Fibs_struct * V;

 if(argc == 2)
 {

   value =  atol(argv[1]);
   printf("F(%d)=\n",value);
   V = fibo(value);
 }
 else
  V = fibo(1);

  print_BigN(&(V->number));

  deleteFibs();
  free(Big2.pt);


}

Heater
Posts: 12744
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 5:47 am

timrowledge,
Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?
Magic isn't it!

Requires you have BIG floats to program it, not puny little IEEE 754 floats. See ejolson's explanation above.
All you're doing there is punishing yourself!
Yes, I did. I stopped doing that.

Getting the fibo challenge to work in an Smalltalk has been the longest, hardest, most frustrating work, by a large margin, of any of the 20 odd other languages we have solutions in. Despite the sloth of GST and the fact that GST on Debian is broken, I did actually manage to get a result out it before we figured out how to get Squeak to run properly!

Credit me for not giving up!

:)

gkreidl
Posts: 5955
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 5:54 am

danjperron wrote:
Tue Jun 04, 2019 2:18 am
rounded to the nearest integer to obtain the exact value. It is possible that this trick only works when n is large enough, but I haven't checked.
nope it works even with small numbers
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 2
1
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 3
1.894427190999915878563669466
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 4
3.065247584249852787486421565
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 5
4.959674775249768666050091030
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 6
8.024922359499621453536512592
MacBook-Air-de-Daniel:~ daniel$ python fibo2.py 7
12.98459713474939011958660362
MacBook-Air-de-Daniel:~ daniel$
round the value and it is exact.
This will stop working (like any float based solution) as soon as the precision limit (number of digits) of floats is reached (system dependent). I tested a similar algorithm and it first failed at fibo(72) on a RPi.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

ejolson
Posts: 3084
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 5:59 am

hippy wrote:
Mon Jun 03, 2019 6:07 pm
ejolson wrote:
Mon Jun 03, 2019 4:17 pm
Scratch Wiki wrote:The exact requirements to become a Scratcher are unknown, as the Scratch Team does not divulge that information.
While I like the idea of graphical programming as an introduction, especially for people who lack typing skills or keyboards, the above rules do not seem like a good way to keep someone engaged to me but more like a way to make children register so their age, gender and country data can be tabulated.

Given the expertise in technology at MIT, one can't help but wonder whether the requirement to store high scores in the cloud was by design and the need to earn a Scratcher badge before doing so intentional.
Using the cloud for persistent data was intentional and by design. Scratch programs are intended to run in a browser on any supported device. There is no other globally accessible persistent storage medium other than the cloud.

But I think you are reading far, far too much into the rules for having access to Cloud Variables. I don't see any evidence that there is a desire to collate such data or that they are doing so.
The data is collated here:

https://scratch.mit.edu/statistics/

Heater
Posts: 12744
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 6:11 am

Good frikken grief. They have turned a programming language into a social media.

I guess they will know where to look when assessing future applicant's for undergrad comp. sci. courses at MIT. No need for all those annoying interviews and such.

ejolson
Posts: 3084
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 6:15 am

danjperron wrote:
Tue Jun 04, 2019 5:37 am
ok I made one in C using tables of 32bits digits.

It is not finished since I need to convert the result from hex to decimal. But it is blazzing fast.

This version uses the same method than fibo.py. Since you don't want gmp, I made my own multiply and add fonction.

Code: Select all

#include <stdlib.h>
#include  <stdio.h>
#include <string.h>

typedef struct{
 int bytesize;
 unsigned int * pt;
}BigN_struct;

extern void print_BigN(BigN_struct *);

typedef struct{
  int index;
  BigN_struct number;
}Fibs_struct;


int fibs_size=100;
Fibs_struct * fibs;
int MaxFibs;

BigN_struct Big2;


Fibs_struct * fiboAdd(int n,BigN_struct * P)
{

  if((MaxFibs+1) >= fibs_size)
  {
     fibs_size+=100;
     realloc(fibs, sizeof(Fibs_struct)*fibs_size);
  }
 fibs[MaxFibs].index=n;
 fibs[MaxFibs].number= *P;
 MaxFibs++;
 return(&(fibs[MaxFibs-1]));
}


Fibs_struct * fiboFind(int n)
{
  int loop;
  for(loop = 0 ;loop < MaxFibs;loop++)
  {
     if(fibs[loop].index == n)
        return  &(fibs[loop]);
  }
  return NULL;
}



void deleteFibs()
 {
   int loop;
   for(loop=0;loop<MaxFibs;loop++)
   {
     if(fibs[loop].number.pt == NULL)
         continue;
     free(fibs[loop].number.pt);
     fibs[loop].number.pt=NULL;
   }
}


void Big_Reduce(BigN_struct *P)
{
   int loop;
   for(loop= P->bytesize-1 ; loop>0;loop--)
     if(P->pt[loop]) break;
   P->bytesize= loop+1;

}



BigN_struct *  Big_Mul(BigN_struct *p1, BigN_struct * p2)
{
   unsigned long long v;
   int loopa,loopb;

   int bytesize= p1->bytesize + p2->bytesize;
   BigN_struct * result =  malloc(sizeof(BigN_struct));

   result->bytesize=bytesize;
   result->pt= malloc(bytesize * sizeof(int));
   for(loopa=0;loopa<bytesize;loopa++)
       result->pt[loopa]=0;
//   memset(result->pt,bytesize,0); 


  int p1s= p1->bytesize;
  int p2s= p2->bytesize;

  unsigned int * pta= p1->pt;
  unsigned int * ptb;
  unsigned int * ptr;

   for(loopa=0;loopa<p1s;loopa++)
    {
      ptr = &(result->pt[loopa]);
      ptb = p2->pt;
     for(loopb=0;loopb<p2s;loopb++)
        {
           v = (*pta)  * (*(ptb++));
           *(ptr++)+=  v & 0xffffffff;
           v >>=32;
           if(v)
            (*ptr)+= v;
        }
      pta++;
    }


  Big_Reduce(result);


  return result;

}


BigN_struct *  Big_Add(BigN_struct *p1, BigN_struct * p2)
{

   int loop;
   int bytesize;


   BigN_struct * result =  malloc(sizeof(BigN_struct));

   if(p1->bytesize > p2->bytesize)
      bytesize = p1->bytesize;
   else
      bytesize = p2->bytesize;

   result->bytesize=bytesize;
   result->pt= malloc((bytesize+1) * sizeof(int));

   unsigned long long  v=0;

   for(loop=0;loop<bytesize;loop++)
    {
       if(p1->bytesize>= loop)
          v+= p1->pt[loop];
       if(p2->bytesize>= loop)
          v+= p2->pt[loop];
       result->pt[loop]= v & 0xffffffff;
        v >>=32;
    }
    if(v)
      {
       result->bytesize++;
       result->pt[result->bytesize-1]=v;
      }
    Big_Reduce(result);
    return(result);
}


void print_BigN(BigN_struct * P)
{
  int loop;
  printf("byte size = %d\n",P->bytesize);
  for(loop=(P->bytesize -1);loop>=0;loop--)
     printf("%08X ",P->pt[loop]);
  printf("\n");
}


Fibs_struct * fibo(int n)
{
  int k;
  BigN_struct * n1,* n2,*n3;
  Fibs_struct * fk = fiboFind(n);
  Fibs_struct * fk1;

  if(fk)
   {
     return fk;
   }


  k = (n + 1) / 2;

  fk = fibo(k);

  fk1 = fibo(k-1);

  if(n&1)
   {
//        result = fk ** 2 + fk1 ** 2
     n1 = Big_Mul(&(fk->number),&(fk->number));
     n2 = Big_Mul(&(fk1->number),&(fk1->number));
     n3 = Big_Add(n1,n2);
   }
   else
   {
//        result = (2 * fk1 + fk) * fk
     n1 = Big_Mul(&(fk1->number),&Big2);
     n2 = Big_Add(n1,&(fk->number));
     n3 = Big_Mul(n2,&(fk->number));
   }
   fk =	fiboAdd(n,n3);
   free(n1);
   free(n2);
   free(n3);
   return(fk);
}



int main(int argc, char * argv[])
{
  int loop;
  int * fibs_idx;
  fibs = malloc(fibs_size * sizeof(Fibs_struct));
  MaxFibs=2;
  // create First and second Number
  fibs[0].index=1;
  fibs[0].number.bytesize=1;
  fibs[0].number.pt = malloc(4);
  fibs[0].number.pt[0] = 1;

  fibs[1].index=2;
  fibs[1].number.bytesize=1;
  fibs[1].number.pt = malloc(4);
  fibs[1].number.pt[0] = 1;

  // create number 2 in BigN
  Big2.bytesize=1;
  Big2.pt = malloc(4);
  Big2.pt[0]=2;



  int value;
  Fibs_struct * V;

 if(argc == 2)
 {

   value =  atol(argv[1]);
   printf("F(%d)=\n",value);
   V = fibo(value);
 }
 else
  V = fibo(1);

  print_BigN(&(V->number));

  deleteFibs();
  free(Big2.pt);


}
Thanks for posting. This is a different approach than taken in any of the codes submitted so far.

Due to the difficulty of the base 2^32 to base 10 conversion needed for printing, most of the codes written so far perform the entire calculation in base 10.

A simple base 2^32 to base 10 conversion routine may be found in fibob2.c from this post which has not yet been included in the GitHub archive. That routine is not very fast, but could be used to verify you're getting the correct answer before adding a more efficient conquer-and-divide base 10 conversion algorithm.

Heater
Posts: 12744
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 6:19 am

gkreidl,
This will stop working (like any float based solution) as soon as the precision limit (number of digits) of floats is reached (system dependent). I tested a similar algorithm and it first failed at fibo(72) on a RPi.
Yes.

If you are using hardware floating point or your typical languages software impleimentation of standard IEEE 754 floats types I would expect the algorithm to fail around about fibo(72).

This is no different than using normal integer types in most languages, 64 bit integers only gets you to fibo(78) before they overflow.

But these solutions are using arbitrary precision floats. They will not fail until you run out of memory in your machine!

Code: Select all

$ python fibo2.py 20000
4188
2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125
Last edited by Heater on Tue Jun 04, 2019 6:25 am, edited 1 time in total.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 6:24 am

Can you convert that to ScriptBasic? Its array issues unjustifiably made it look like a 🐷.

Your new direction could be ScriptBasic's salvation.

I still want to try a multi-threaded fibo.

FWI: ScriptBasic can seamlessly work with numbers in any base. (binary, base 10, hex, octal...)

jahboater
Posts: 4477
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 7:43 am

Heater wrote:
Tue Jun 04, 2019 6:19 am
This is no different than using normal integer types in most languages, 64 bit integers only gets you to fibo(78) before they overflow.
Yes, but a little better.
fibo(93) with unsigned integers and fibo(92) with signed integers are the maximum before overflow for 64-bits.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define N 93

int
main( void )
{
  int term = N - 1;
  uint64_t n, a = 0, b = 1;

  do
  {
    if( __builtin_add_overflow( a, b, &n ) )
    {
      puts("Overflow");
      exit(1);
    }
    a = b;
    b = n;
  }
  while( --term );

  printf( "%" PRIu64 "\n", b );
}

Heater
Posts: 12744
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 9:16 am

Oops, sorry, yes. I was confusing regular 64 bit integers with the integers range you can get in Javascript, where all numbers are 64 bit floats.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 10:00 am

Fibonacci Pinecone.

This example was created by a brilliant mathematician that was a forum member but unfortunately no longer with us. The animation was added by the author of Oxygen Basic which the example is written it. No BIGINT required.

Image

Image

Code: Select all

  #compact
  % Title "PineCone"
 '% Animated
  % ScaleUp
 '% PlaceCentral
 '% AnchorCentral
 '% NoEscape
  % ColorCodedPick
  % MultiSamples 4

  includepath "$\inc\"
  include "ConsoleG.inc"


  function makelist() as sys
  ==========================

  type coor float x,y,z

  static coor z
  static float golden_angle = 137.508 
  static float golden       = golden_angle*Pi/180
                                     
  sub floret (sys n) 'inner procedure
  ------------------
  float r , ang , xc , yc
  r =(5.3 * Sqr(n*golden))
  ang = (n*golden)
  xc = r*Cos(ang)/100
  yc = r*Sin(ang)/100
  z.x=xc : z.y=yc
  end Sub   

  sys i
  seeds=CompileList 0
  for i=1 to 140
    floret(i)
    glPushMatrix
    glTranslatef z.x , z.y , i/100
    scale 0.11+i/900
    go sphere
    glPopMatrix   
  next 
  for i=144 To 1 step -1
    floret(i) 
    glPushMatrix
    glTranslatef -z.x , -z.y , 2.2-i/200
    Scale  0.11+i/1000
    go sphere
    glPopMatrix   
  next
  glEndList
  return seeds
  end function


 function main()
  ===============
  sys i,p
  string s
  float  a
  cls 0,0.1,0.2
  '
   shading
  '
  pushstate
  move 15,-15,-20
  static MoveableObject seeds
  static sys            seedform
  static sys            id=100
  if not seeds.id 
    seeds.snap=.5
    seeds.set id,0,0.,0.0,-0.0
    seeds.mode=0x101
    SeedForm=MakeList()
  end if
  picked=100 'always selected
  seeds.act
  scale 10
  move 0,0,-1
  SilverMaterial.act
  go SeedForm
  popstate
  '
  'F1 HELP
  '
  if key[0x70]
    flat
    pushstate
    move 20,0
    color .9,.9,.9
    scale  1.5,1.0
    printl "Active Keys:"
    printl
    scale  1/1.5,1.0
    printl "Esc"    tab "Exit"
    printl "Ctrl-P" tab "Take snapshot"
    printl "F1 This help panel"
    printl "Arrow keys PgUp PgDn to move"
    printl "Ctrl Arrow keys PgUp PgDn to rotate"
    printl "+ - keys to scale up and scale down"
    printl "Ctrl Home to reset rotation"
    printl "Shift for faster movement"
    printl
    scale 1.5,1.0
    printl "Mouse:"
    printl		
    scale 1/1.5,1.0
    printl "Point to Object, then"
    printl "Left button to move"
    printl "Middle button to scale"
    printl "Right button to rotate"
    printl "Wheel to move in Z direction"
    popstate
  end if
  picklabel 0
  lastkey=0
  lastchar=0
  end function

  EndScript

gkreidl
Posts: 5955
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 11:49 am

Heater wrote:
Tue Jun 04, 2019 6:19 am
gkreidl,
This will stop working (like any float based solution) as soon as the precision limit (number of digits) of floats is reached (system dependent). I tested a similar algorithm and it first failed at fibo(72) on a RPi.
Yes.

If you are using hardware floating point or your typical languages software impleimentation of standard IEEE 754 floats types I would expect the algorithm to fail around about fibo(72).

This is no different than using normal integer types in most languages, 64 bit integers only gets you to fibo(78) before they overflow.

But these solutions are using arbitrary precision floats. They will not fail until you run out of memory in your machine!

Code: Select all

$ python fibo2.py 20000
4188
2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125
Can you show me (or link to) the source of this fibo2.py script? I did not find it on github.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

hippy
Posts: 5384
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 2:13 pm

ejolson wrote:
Tue Jun 04, 2019 5:59 am
But I think you are reading far, far too much into the rules for having access to Cloud Variables. I don't see any evidence that there is a desire to collate such data or that they are doing so.
The data is collated here:

https://scratch.mit.edu/statistics/
I should have perhaps phrased what I wrote differently - That I don't see the decision to limit Cloud Variables to Scratchers being driven by a desire to collate data on people.

That is, I don't believe "if we limit access we can get more people to register" was the motivating or driving force, merely it was a solution for "we need some means to reduce the load our servers are suffering under".
Heater wrote:
Tue Jun 04, 2019 6:11 am
Good frikken grief. They have turned a programming language into a social media.
You really don't want to visit the Scratch forums then.

But be fair; these are kids and kids are what they are. Scratch is a system intended for kids and therefore provides a community which kids can be happy and thrive within. Many will be quite young, quite possibly very immature, building skills, etiquette, and experience within that environment. When it serves communal needs and desires I don't have a problem with however something is.

There's a place for "no talking" libraries. But I also believe there's a place for "scream your head off and bounce from the walls" libraries if that is what people want and it helps them advance.

timrowledge
Posts: 1266
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: A Final Fibonacci Challenge

Tue Jun 04, 2019 5:52 pm

Heater wrote:
Tue Jun 04, 2019 5:47 am
timrowledge,
Wait, hang on - how does using any sort of approximation via a floating point number produce a correct answer to an integer problem? Surely that can't be right?
Magic isn't it!
Damn right. I'm not a Numerics guy by any stretch but that really make my head spin. I'll see what my mathematician niece says about it. I wonder if anyone ever got intersted in arbitrary precision (is that the right name?) floats in Smalltalk. I wonder if it would do anything more useful than arbitrary sized integers? Let's see...
Heater wrote:
Tue Jun 04, 2019 5:47 am
Credit me for not giving up!
Well yes, there's determination and there's "where's the padded armless jacket and the big strong folk that know how to dress you in it safely". BASICally (see what I did there - keeping on topic!) you made a determined attack on a specialised fastener system with a large, splintery-handled mallet, whilst an expert (that would be me) quietly advised pulling out the locking pin and using the correct powertool. Determination is certainly admirable up to a point uncertainly determinable, probably by an Admiral. What's been nice is that some of us have been learning new stuff. And you got your commandline Squeak capability, albeit for now requiring the development-trunk version rather than the stable-for-download system.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

Return to “General programming discussion”