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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 12:27 am

timrowledge wrote:
Mon Jun 03, 2019 12:05 am
Smalltalk is relatively slow at accessing arrays because every access is bounds-checked. This makes some of the favoured trivial benchmarks seem very slow - but it does mean we suffer rather fewer issues with junk getting poked into memory in places where it isn't good. Which is more important? Depends on what you're doing.
Its nice to be able to switch bounds checking on and off.
Have it on all the time during development and testing of an important product of course, and off for the trivial benchmarks.
I use bounds checking a lot in C and it doesn't seem to noticeably slow things down at all, though I have not benchmarked it.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 12:53 am

ScriptBasic doesn't use bounds checking because there isn't any. (only available memory)

a[1000000] = "One Million"

The LBOUND and UBOUND are both 1000000 until another element is defined then everything inbetween becomes undef elements.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 5:21 am

scruss wrote:
Sat Jun 01, 2019 7:58 pm
ejolson wrote:
Sat Jun 01, 2019 5:18 am
Of course it could be worse. The public library across town holds an ongoing event called Learn to Code with Mr Toad …
I've heard HTML described as "coding". But weren't we always taught that the best coding was done by planning far away from the keyboard?
Except for computing Fibonacci numbers using well-known algorithms, I suspect most other meaningful applications require a bit of planning and analysis to be performed ahead of time. However, before embarking on the kind of projects that require such analysis, it would be expedient for a beginner to become familiar with the computer and how it works. When this is done by choosing a good first programming language and writing some simple programs, that's what I would consider a hands-on approach. In particular, I find it paradoxical for the description of Mr Toad's event to read, "This activity is very hands-on and computers will seldom be used."

So far this and the Why Avoid Basic threads have focused on the following when choosing a beginner's first programming language:
  • Theoretical and practical considerations related to the language itself such as those given by Kemeny and Kurtz.
  • Employment opportunities for someone who knows that language as inferred from the TIOBE index and a survey of job descriptions.
There is another property a programming language could have that may also be important when choosing a first language: Is a student allowed to use that language when participating in one of the many national and international programming competitions?

Here is a quick list put together by consulting Wikipedia.
  • International Olympiad in Informatics: C, C++, Java or Pascal.
  • International Collegiate Programming Contest: C, C++, Java, Kotlin or Python.
  • Central European Olympiad in Informatics: C, C++, Java or Python.
  • United States of America Computing Olympiad: C, C++, Java, Pascal or Python.
  • Canadian Computing Competition: C, C++, Java or Pascal.
While focusing on these competitions is admittedly inward facing from a teaching perspective, being able to successfully compete in such a competition could be extremely liberating, especially for a student who grew up in a technologically or economically backwards community. If this is the case, then the possible choices for a first programming language are narrowed down quite dramatically by the observation that C, C++ and Java are the only languages allowed in all competitions.

On the other hand, if the goal is not liberation, empowerment or freedom, but instead fulfilling curricular requirements in the easiest possible way, the optimal choice of programming language might be much different. And, of course, this whole line of reasoning could be completely wrong.

User avatar
bensimmo
Posts: 4128
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 6:52 am

It could be as you may be targeting different types of people
There may well be some that would like C as their beginner language, envoy it, find it interesting and not get frustrated or bored quickly.
There may well be some that would like Scratch, empower them, let them get quick results and explore their creativeness and get thing moving. Keeping them engaged so they don't give up.

I may well be biased in the way I typed that.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 7:26 am

Bah, humbug, writing HTML is not "coding", as in writing programs for computers.

One can not do any planning of any software project until one has some idea of what a computer is, what a program is, what you can do with programs, and how to write programs.

Think of it like designing and building a house. It's probably better to know what materials are available, what tools you can employ, and so on, before you start.

Of course it is possible to plan software without ever having seen or used a computer, Ada Lovelace and Alan Turing did. I don't think most of us are up to that.

Personally I don't think we should be thinking of career opportunities and specific employment when teaching young kids to program. No more so than we do when teaching them to read, write or count. As such following whatever languages they use in today's software mines, factories and sweat shops is not so important.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 8:38 am

bensimmo wrote:
Mon Jun 03, 2019 6:52 am
There may well be some that would like Scratch, empower them, let them get quick results and explore their creativeness and get thing moving. Keeping them engaged so they don't give up.
I'm not sure how a language that doesn't allow read or write access to the filesystem can empower anyone. How would you even save a high score?

While drag and drop programming sounds interesting, Scratch does not grow well with a student's interests or abilities. This would be fine if Scratch were used for less than a week, but I've seen cases were students wrote programs for an entire year. By the end of the year they have mastered Scratch well enough that starting over with a new language is frustrating and difficult. At the same time, there are so many intrinsic limitations in the language that it neither supports further learning in computer science nor the use of computers in other subjects.

In my opinion, teaching Scratch may be worse than a waste of time. Again, the danger is that a student might practice Scratch coding enough to master it. The problem with mastering such things was made clear when
Vince Lombardi wrote:Practice does not make perfect. Only perfect practice makes perfect.
While Vince was likely objecting to the learning of habits bad for playing football, similar wisdom might profitably be applied to the dangers of learning programming languages bad for computing Fibonacci numbers.

User avatar
bensimmo
Posts: 4128
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 9:01 am

They're learning the logic, maybe they don't want high scores saved. They just want to make pictures do funny things, make a maze, plot a temperature graph, make lights turn on and off.

The logic is there, they have fun.
If interest sparks to move to something else they can and will do it. If not and they are happy, why worry.
I didn't care about speaking French or German, I learnt a bit to get by, I don't suddenly need to go of and learn Chinese to advance myself. Not my interest, why should computer programming be any different.

Once they choose to want to program in 'boring text typing', they do it and probably do it themselves and anyone with an interest will.
It's the same reason Science, Mathematics etc all have basic grounding, some do higher levels and then move on or learn themsleves, some just do enough so they can buy things in shops.


One problem is, we and most people teaching it come from when visual wasn't a thing, we are comfy with text, we read text.
Why not evolve to visual programming if it gets the job done they need. They may even peak under the hood at somepoint if the interest is there.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 2:39 pm

ejolson wrote:
Mon Jun 03, 2019 8:38 am
bensimmo wrote:
Mon Jun 03, 2019 6:52 am
There may well be some that would like Scratch, empower them, let them get quick results and explore their creativeness and get thing moving. Keeping them engaged so they don't give up.
I'm not sure how a language that doesn't allow read or write access to the filesystem can empower anyone. How would you even save a high score?
They would use a Cloud Variable.

Scratch users have persistent data they can read and write, if they wish to use that. The Scratch language caters for that.

They also have access to Scratch Extensions which provide for things which aren't part of the core language itself, just as with other programming languages.
ejolson wrote:
Mon Jun 03, 2019 8:38 am
In my opinion, teaching Scratch may be worse than a waste of time.
If it gets people interested enough to stick with computing, when they wouldn't with something else, it has to be worthwhile. Whether they continue with it, move on to something else, continue in their computing ventures or let that interest slide, are different issues.

There is a potential issue with only teaching Scratch when students have out-grown that, but that's the same for all students who are ahead of what's being taught no matter what the subject. I don't believe anyone is advocating "Scratch and only Scratch" other than where that is a mandated requirement for a curriculum.

I do agree some will stay with Scratch and keep using it long after it may be better to have moved on to something else. But it's their choice and, if that's what keeps them doing computing, it's better than their not doing computing.

I have always thought it better to provide for what a student wants to do and how they choose to do it, rather than try and coerce or force them into where we would like them to be. Or we may have lost them, abandoned them, scared them away, before they have a chance to let their talents shine through.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 4:17 pm

hippy wrote:
Mon Jun 03, 2019 2:39 pm
ejolson wrote:
Mon Jun 03, 2019 8:38 am
bensimmo wrote:
Mon Jun 03, 2019 6:52 am
There may well be some that would like Scratch, empower them, let them get quick results and explore their creativeness and get thing moving. Keeping them engaged so they don't give up.
I'm not sure how a language that doesn't allow read or write access to the filesystem can empower anyone. How would you even save a high score?
They would use a Cloud Variable.

Scratch users have persistent data they can read and write, if they wish to use that. The Scratch language caters for that.
Upon consulting this documentation I found
Scratch Wiki wrote:[The name Scratcher] can also, though, refer to specifically a user on Scratch who has received the "Scratcher" status after being helpful and active, which allows that user some more capabilities, such as using cloud variables.
Further reading led to
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. Luckily, the default Scratch on the Raspberry Pi, called nuScratch, is an update to the original version which isn't cloud-based in the same way and doesn't require a badge before using all the features.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 4:56 pm

jahboater wrote:
Mon Jun 03, 2019 12:27 am
timrowledge wrote:
Mon Jun 03, 2019 12:05 am
Smalltalk is relatively slow at accessing arrays because every access is bounds-checked. This makes some of the favoured trivial benchmarks seem very slow - but it does mean we suffer rather fewer issues with junk getting poked into memory in places where it isn't good. Which is more important? Depends on what you're doing.
Its nice to be able to switch bounds checking on and off.
Have it on all the time during development and testing of an important product of course, and off for the trivial benchmarks.
I use bounds checking a lot in C and it doesn't seem to noticeably slow things down at all, though I have not benchmarked it.
I suspect the definition of 'bounds checking' may be a bit different between our two cases. It's been a while (like 28 years?) since I last had reason to try to use C compiler bounds checking flags and I bet things have changed since then, but IIRC it was a fairly primitive affair. If you have declared size arrays (which of course you don't have to have) and pointers appropriately declared and they are not sneakily aliased or cast to innocuous things, then it may be possible to bounds check them. In Smalltalk all accesses into any sort of array are bounds checked every time; after all the array may have been grown or shrunk since last time you looked at it, so you can't rely on some prior caching etc. Accesses into the private data of any object are protected too. Yes, it has a time cost, though surprisingly low. As always, horses for courses.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 5:18 pm

ejolson wrote:
Mon Jun 03, 2019 4:17 pm
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. Luckily, the default Scratch on the Raspberry Pi, called nuScratch, is an update to the original version which isn't cloud-based in the same way and doesn't require a badge before using all the features.
One has to remember that quite a lot of the work in the later versions of Scratch-from-MIT gets done by relatively junior students as a project task. And remember that Scratch 2 was written in Flash and Scratch 3 is written in... whatever fancy html nonsense is fashionable today. The original version was done largely by a couple of quite experienced Smalltalkers, including John Maloney; John worked on the original 'Self' language UI and invented the system currently known as Morphic. There's a lot of very good stuff in Morphic, as well as some parts that drive me insane. It's also worth remembering that the MIT guys swore blind that nobody could make Scratch run faster on a Pi... I think I demonstrated the falsity of that claim fairly thoroughly.

Scratch isn't a fully general language/system and it certainly has limitations. The tools are so lacking that it is almost as bad as having only a text editor. (Original) Scratch has no functions to call, only scripts. But what it does, it does quite well and can teach a lot of important concepts in computing. An interesting aspect I think gets overlooked almost all the time is that it is an Actor language (of a simple sort, certainly) and massively parallel. This isn't stuff that often gets taught to newcomers to computing.

John M did start a project to try to make a general purpose scratch/block language - see gpblocks.org - which does run on a Pi (last time I looked) but doesn't really seem to be going anywhere. One of the major problems with a visual language like this (and many prior attempts over the decades) is a very rapid rise in clutter that quickly obscures the entire screen. There are some approaches that have combatted this quite well via filtering and CAD-like UIs. The Raskin Desktop idea (http://www.raskinformac.com) is quite neat and might be the basis of a solution.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 5:49 pm

timrowledge wrote:
Mon Jun 03, 2019 4:56 pm
I suspect the definition of 'bounds checking' may be a bit different between our two cases.
I'm not sure it is different from your description.
And yes compiler technology has improved over the last 28 years! A lot.

The "sanitizers" introduced by Clang/LLVM a few years ago and later adopted by GCC do all that and much more.
(Well, I'm not sure about the private data checks as C doesn't have that, but C++ does, so I presume its covered).
That is compiler instrumentation, which is fast enough that you don't notice it.

The alternatives are separate tools that check every single memory reference for every machine instruction - which as you can imagine slows the code down quite a lot. Still useful though. Annoyingly they must understand every single instruction the CPU supports, which is a problem with Intel introducing new instructions at a prodigious rate.

I use both methods routinely, its crazy not to.
But as I said above, its great that you can turn checking off if you need that last ounce of speed.

Please, if you want to compare the technology of the C/C++ world with the equivalent for Smalltalk, its only fair to look at recent compilers and recent support tools - not 28 year old compilers! The current version of GCC is 9.1 by the way.
Last edited by jahboater on Mon Jun 03, 2019 6:07 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

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 reasons for needing to have earned some status ranking before gaining access to using Cloud Variables came about because, kids being kids, not knowing any better, not understanding the consequences of their actions, having not had them explained, or their not caring, used Cloud variables willy-nilly and were engaging in what amounted to DDoS attacks through hammering the servers with numerous requests with programs which repeatedly accessed Cloud Variables.

MIT needed some way to limit the impact of allowing persistent storage while allowing that. There have been various schemes used with tweaks over the years.

I would agree they could perhaps have found some other way and that would have been better but there's a lot one can say that about when it comes to Scratch.

But it isn't unusual within education to reward success and encourage people towards success through gaining awards, or grant them access to things only when they reach some level of proficiency. And this merely replicates that.

The main reason they don't divulge what the requirements to become a Scratcher is probably that they don't want kids gaming the system. And it also stops pesky kids moaning that they should have become Scratchers because of this that and the other, and using "you said..." arguments.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 6:11 pm

timrowledge,
...remember that Scratch 2 was written in Flash and Scratch 3 is written in... whatever fancy html nonsense is fashionable today.
Wait up a minute. That would be JavaScript.

The language behind FLASH is ActionScript. Which is basically a souped up Javascript. In fact ActionScript is now compliant with the same ECMA statnadard as JS.

Getting rid of FLASH and using JS can be seen as cleaning out a lot of closed source cruft now that the browser API's are more friendly for such applications.

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.

Rather than HTML nonsense that is fashionable, I see a continuation of old ideas going back to Self/Scheme.

Sadly Java fans have infiltrated the Javascript standards committee and started screwing it up with mis-features like "class".

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 7:18 pm

Calculating Fibo(n) could be optimize using

F(n) = phi ** n / sqrt(5)

where phi is the golden number. phi = ( 1 + sqrt(5))/2


Calculation of Fibo(2149831) needs at least 449288 digits of precision. Does your computer could handle it ?

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 7:43 pm

People have been calculating fibo(4784969) here, which is a million digits!

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 7:51 pm

jahboater wrote:
Mon Jun 03, 2019 7:43 pm
People have been calculating fibo(4784969) here, which is a million digits!
The holy grail of Fibonacci challenges. :D

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 8:21 pm

People have been calculating fibo(4784969) here, which is a million digits!
So! Are you able to do it ?
And How long it takes ?


In reality you could calculate any number you want but it will take times.

I will check how long it takes the pi to calculate fibo(4784969). Hum a week, a month?

Code: Select all

#!/usr/bin/env python
import sys

import math
from decimal import *


if len(sys.argv) != 2:
  print("usage:\n\t Fibo  Fibonacci_number")
  quit()


value = int(sys.argv[1])


if value <= 0:
   print("The value need to be > 0");
   quit()
if value <3:
  print("1")
  quit()

#let's figure out the number of digits needed

nDigits = int(round(math.log10(value))*2)


#let's calculate a approx phi

phi = (Decimal(1) + Decimal.sqrt(Decimal(5))) / Decimal(2)

Fn = (phi ** Decimal(value)) / Decimal.sqrt(Decimal(5))

precision = int(Decimal.to_integral_value(Decimal.log10(phi ** Decimal(value))) + nDigits )

print(precision)
if precision >  getcontext().prec:
    getcontext().prec = precision
    #ok let;s recalculate phi with the correct precision
    sqrt5 = Decimal.sqrt(Decimal(5))
    phi = (Decimal(1) + sqrt5) / Decimal(2)
    Fn = (phi ** Decimal(value)) / sqrt5

Fn = Decimal.to_integral_value(Fn)
print(Fn)

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 8:55 pm

danjperron
So! Are you able to do it ?
And How long it takes ?
In Python, about 18 seconds on my PC.

Code: Select all

from __future__ import print_function
import math
import timeit


fibs = {0:0, 1:1, 2:1}

def fibo(n):
    if n in fibs:
        return fibs[n]

    k = (n + 1) // 2
    fk = fibo(k)
    fk1 = fibo(k - 1)
    if n & 1:
        result = fk ** 2 + fk1 ** 2
    else:
        result = (2 * fk1 + fk) * fk
    fibs[n] = result
    return result


run_time = timeit.timeit('fibo(4784969)', setup="from __main__ import fibo", number=10)


print (fibo(4784969))
print ('Run time = {}'.format(run_time))

Code: Select all

$ time python fibo.py | head -c 100 ; time python fibo.py | tail -c 100 ;
1072739564180047722936481359622500432190722117323735062984647338302579681716358886237289956921621671
real    0m18.145s
user    0m17.656s
sys     0m0.078s
6875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.799599885941

real    0m17.684s
user    0m17.609s
sys     0m0.078s
In C / C++, less than half a second.

The trick is to use a faster algorithm than the typical highschooler would use. See here:
https://www.nayuki.io/page/fast-fibonacci-algorithms

Your equation works fine if you have the right programming language. You will find such a solution in the Fibonacci Challenge respository here: https://github.com/ZiCog/fibo_4784969/b ... gp/fibo.gp Takes about 10 seconds.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 8:55 pm

danjperron wrote:
Mon Jun 03, 2019 8:21 pm
I will check how long it takes the pi to calculate fibo(4784969). Hum a week, a month?
Evidently you hadn’t noticed that people have been posting the answer(s) o that question for a while now. As an example, it takes around 11secs in Smalltalk. A bit less than a month 😁
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 9:07 pm

danjperron,

That's great. Your solution gets me a result in about 16 seconds on my PC!

Do you mind if I add your solution to the Fibonacci Challenge hall of fame: https://github.com/ZiCog/fibo_4784969

It's great you have presented a very different solution. I'm surprised no Python head did not use that formula already.

It takes 32 seconds in Squeak Smalltalk on my old PC. Over five hours in GNU Smalltalk!


Edit: You may have notice that fibo(4784969) is the first number in the Fibonacci sequence that has one million digits. Which is why I chose it.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 9:28 pm

timrowledge wrote:
Mon Jun 03, 2019 8:55 pm
danjperron wrote:
Mon Jun 03, 2019 8:21 pm
I will check how long it takes the pi to calculate fibo(4784969). Hum a week, a month?
Evidently you hadn’t noticed that people have been posting the answer(s) o that question for a while now. As an example, it takes around 11secs in Smalltalk. A bit less than a month 😁
Here is the next roundup of Fibonacci codes.

Image

This is the fifth in a series of graphs posted to this thread comparing the run times on the Raspberry Pi Zero for various languages and Fibonacci algorithms. It should be noted the results for fibompi.c reported here were obtained by turning parallelism on only for the Karatsuba algorithm and then over provisioning the five-node super-cheap cluster with nine ranks. Runs using eighteen ranks with further parallelism in the doubling formula yielded similar results and have not been reported.

For those who are having difficulty understanding the graphs, let Tn be the time in seconds needed to compute the n-th Fibonacci number. The graphs then show Tn versus n plotted in logarithmic coordinates for a randomly chosen selection of values for n between 1 and 4784969. Note the far right of the graph represents the time to compute F(4784969); the top of the graph represents computations that took 1000 seconds.

The lower the curve the better. If the curve runs off the top first, then the program is slow and computing the million-digit Fibonacci number would take longer than 1000 seconds. If the curve runs off the right first, then the program is fast and computing the million-digit Fibonacci number took less than 1000 seconds.

Since the PL/I code didn't materialize in time, the operator-overloaded C++ program given by bint.h, fibo.cpp, fibo.h and fibo_karatsuba.cpp from the GitHub repository has been substituted and labeled karatserial on the graph. In order to run this program under fibench, the main routine was modified as

Code: Select all

#include <string.h>
#include "bint.h"
#include "fibo.h"
#include <omp.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    int n = 4784969;   // The first Fibonacci number with a million digits
    bint res;
    for(;;){
        fiboInit();
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        n=atoi(buf);
        if(n==0) return 0;
        fiboNew(n, res);
        std::cout << res << std::endl;
    }
}
The C++ code was compiled with the command

Code: Select all

$ g++ -O3 -o karatserial fibo_karatsuba.cpp fibo.cpp -lm
Last edited by ejolson on Tue Jun 04, 2019 2:19 am, edited 7 times in total.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 10:19 pm

ejplson,

Oh, oh, any chance you could add the C++ with OMP timing to that plot?

Build as:

Code: Select all

$ g++ -Wall -O3 -DUSE_OMP -fopenmp -o karatparallel fibo_karatsuba.cpp fibo.cpp
I really must clean up that repo directory and add a README.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 10:27 pm

Heater wrote:
Mon Jun 03, 2019 10:19 pm
ejplson,

Oh, oh, any chance you could add the C++ with OMP timing to that plot?

Build as:

Code: Select all

$ g++ -Wall -O3 -DUSE_OMP -fopenmp -o karatparallel fibo_karatsuba.cpp fibo.cpp
I really must clean up that repo directory and add a README.
Unfortunately the Pi Zero does not have a multi-core processor, so not a chance. That's the drawback of using a computer that came free with a magazine subscription.

I suppose someone could redo all the graphs using a Pi 3B or 3B+. I'll post the scripts I've been using shortly, to make that easier.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 10:29 pm

Do you mind if I add your solution to the Fibonacci Challenge hall of fame: https://github.com/ZiCog/fibo_4784969
not at all


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,


it's working fine! I need to figure out how the bits resolution works!
Last edited by danjperron on Mon Jun 03, 2019 10:49 pm, edited 1 time in total.

Return to “General programming discussion”