jalih
Posts: 124
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 6:39 pm

timrowledge wrote:
Sat Jun 01, 2019 5:43 pm
That's a pretty damn good PacMan. It was written by the Oliver brothers (purportedly in a single night of drink-programming, which sounds ridiculous until you remember that for a while they were pretty much theUK games industry) and very tightly replicates the original.
The only true way to code! :D when starting game programming, you don't need maximum speed or graphical effects for your first game. First you want to draw something, then you want to make it move and respond to input. Next you add enemies and learn about state tables to give some interesting behaviour for them. Collision detection probably comes next. Finally you learn about game timing and game states. Soon you realize you have created your first game.

Attached is a picture from my simple game example written in 8th programming language running on ROCK64 board. Now, where did I put that beer... ;)
Attachments
työtila 1_003.png
työtila 1_003.png (196.29 KiB) Viewed 1778 times

jalih
Posts: 124
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 7:22 pm

ejolson wrote:
Sat Jun 01, 2019 6:23 pm
If anyone wants to try this, I would suggest using the Visual Basic code visual.bas as a starting point.
I think I will try doing PL/I conversion tomorrow, If I have some free time.

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 7:58 pm

ejolson wrote:
Sat Jun 01, 2019 5:18 am
… it doesn't take strong powers of observation for a child to notice it is impossible to create anything resembling even the simplest commercially-produced video game using Scratch. This implies Scratch does not satisfy item 4 in Kurtz and Kemeny's list of requirements, paraphrased here as follows: A good beginners language should be general purpose and enable a person to code any kind of program the machine is capable of executing.
Then again, K&K's list was written when a computer could do far less. The user interface was by teletype. Some BASIC systems were clever enough to track the response time for input. Early versions of Oregon Trail linked your hunting prowess to how quickly you could type WHAM or BANG into the teletype … Those were simpler days …
If what could be accomplished using interpreted Basic was much less than what the 8-bit computers of the golden age could do, what was the motivation to learn Basic?
It was there, and on most systems, it came with a decent enough manual to be able to get something out. Even the Commodore 64, famous for its dire and feature-free BASIC, came with a manual that showed the intrepid reader how to get as far as coding sprites and multi-channel sound.
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?
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.
Pronouns: he/him

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 8:02 pm

jalih wrote:
Sat Jun 01, 2019 6:39 pm
timrowledge wrote:
Sat Jun 01, 2019 5:43 pm
That's a pretty damn good PacMan. It was written by the Oliver brothers (purportedly in a single night of drink-programming, which sounds ridiculous until you remember that for a while they were pretty much theUK games industry) and very tightly replicates the original.
when starting game programming, you don't need maximum speed or graphical effects for your first game.
This is definitely true and also why flashing an LED is so satisfying the first time around. At the same time, if those who aspire to more cannot because the first programming language they mastered is not sufficiently general, then the current learning-to-code fashion may again get the reputation of being a bit useless.

The difficulty, as I see it, is that people designing educational materials don't understand the degree to which people get stuck using the first language they learn. As a result they promote languages for teaching which do not wear well as the student becomes more experienced.

The Fibonacci challenge is a measure of how expressive a programming language is for coding complicated algorithms. In my opinion, an equally valid metric would be how expressive a language is for coding video games. Again, because people tend to get stuck using the first language they master, a good language for beginners should be general purpose enough to do many things well. This is why I suggested a graphical networked version of the classic multiplayer game Star Trader as a follow-up challenge.

Except for the missing cameo by IronPython, our dramatic comedy includes performances from the full Monty of Python interpreters. Therefore, I'm now looking for the lost sheep of the fold: Decimal Basic, Go, Haskell, NodeJS, Java and Julia.

What programmer, having an hundred Fibonacci programs, if he or she lose one of them, doth not write the ninety and nine on the backup tape, and search the Why Avoid Basic thread on the Raspberry Pi forum for that which is lost, until he or she finds it? And when it hath been found, the programmer copies it to the GitHub, rejoicing. And when cometh home, calleth together all friends and neighbours, saying unto them, Rejoice with me; for I have found my code which was lost.
Last edited by ejolson on Sat Jun 01, 2019 10:09 pm, edited 2 times in total.

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 8:41 pm

Amen. :D

Have you considered a career in evangelism?

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 8:57 pm

ScriptBasic wrote:
Sat Jun 01, 2019 8:41 pm
Have you considered a career in evangelism?
While Linux and the Raspberry Pi seem clear, I still need to choose between Ada, APL, Basic, C, D, Eighth, Fortran, Go, Haskell, Matlab, NodeJS, Pascal, Python, Scheme, Scratch, Squeak, Java or Julia. Teaching used to be so much simpler when there were no computers in the classroom and the students already had a favorite programming language.
Last edited by ejolson on Sat Jun 01, 2019 9:41 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 9:21 pm

jalih wrote:
Sat Jun 01, 2019 7:22 pm
ejolson wrote:
Sat Jun 01, 2019 6:23 pm
If anyone wants to try this, I would suggest using the Visual Basic code visual.bas as a starting point.
I think I will try doing PL/I conversion tomorrow, If I have some free time.
Do you think the built-in integer data type in PL/I with precision attribute would suffice if a million digits were specified?

jalih
Posts: 124
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 9:43 pm

ejolson wrote:
Sat Jun 01, 2019 9:21 pm
Do you think the built-in integer data type in PL/I with precision attribute would suffice if a million digits were specified?
No, fixed decimal is limited at 31 decimals with compile time option, and it defaults to 15. Fixed binary is limited at 63 bits plus sign bit.

Fortunately your Visual Basic code to PL/I conversion should be quite easy.

Directly using fixed decimal (31) precision, one can calculate fibo(149):

Code: Select all

*PROCESS MARGINS(1,180) LIBS(SINGLE,STATIC);
*PROCESS OPTIMIZE(2) DFT(REORDER) LIMITS(FIXEDDEC(31));


 test: proc options(main);
   put skip list(fibo(149));


   fibo: proc(n) returns(fixed dec(31));
     dcl n fixed bin(31);

     dcl a fixed dec(31) init(0);
     dcl b fixed dec(31) init(1);
     dcl i fixed bin(31);
     do i=trunc(log2(n)) to 0 by -1;
       dcl (d, e) fixed dec(31);
       d = a*(b*2-a);
       e = a*a+b*b;
       a = d;
       b = e;
       if iand(isrl(n,i),1) ^= 0 then
         do;
           dcl c fixed dec(31);
           c = a+b;
           a = b;
           b = c;
         end;
     end;
     return(a);
   end fibo;

 end test;

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 10:29 pm

ejolson,
This is definitely true and also why flashing an LED is so satisfying the first time around. At the same time, if those who aspire to more cannot because the first programming language they mastered is not sufficiently general, then the current fashion of learning to code may again get the reputation as being a bit useless.
You mean like maths education is something most people think they have no use for.
The difficulty, as I see it, is that people designing educational materials don't understand the degree to which people get stuck using the first language they learn. As a result they promote languages for teaching which do not wear well as the student becomes more experienced.
I have been wondering about this.

Back in school, from the age of 11 upwards we had "metal work" classes. In the more senior years known as "Engineering Workshop Theory and Practice". The thing about my metal work classes was that from that tender age we built things, of increasing complexity and difficulty, in a fully equipped shop. We had two full size industrial strength lathes, a milling machine, a shaper, a furnace for melting aluminium, a forge. From the get go we used real tools, hack saws, files, drill presses etc.

You have to realize that this was in the late 1960's/early 1970's, that we could still leave school at 14 if we wished, that the expectations were that we would end up working in the local coal mines or factories. As such, all this real metal work stuff was preparing us for the real world of work.

Now, coming forward in time til today, it seems they want to teach kids to program at school. To prepare them for a life in the software mines and factories of the future. I argue then that kids should not be treated with, err, kid gloves, and given safe, plastic, child friendly programming languages like Scratch to start with. No, start them of with real, dangerous languages, teach them skills that are real and relevant.

I don't believe that 11 years old's cannot handle C for example. In fact we know they can, many kids use Arduinos which are programmed in C++.
The Fibonacci challenge is a measure of how expressive a programming language is for coding complicated algorithms. In my opinion, an equally valid metric would be how expressive a language is for coding video games.
Sounds like you are making the same argument.
This is why I suggested a graphical networked version of the classic multiplayer game Star Trader as a follow-up challenge.
Go ahead. Make the challenge. I have no idea what Star Trader is but it sounds like a lot of work for a coding challenge. How would you specify it rigorously? Who would bother to take the time to do it?
What programmer, having an hundred Fibonacci programs, if he or she lose one of them, doth not write the ninety and nine on the backup tape, and search the Why Avoid Basic thread on the Raspberry Pi forum for that which is lost, until he or she finds it?
I'm not sure what you are getting at there. I have all Fibo Challenge entries in git repos and github. Have done for a long while now. https://github.com/ZiCog/fibo_4784969

Is there a lost Fibo sheep somewhere back along the way?
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sat Jun 01, 2019 11:32 pm

Heater wrote:
Sat Jun 01, 2019 10:29 pm
Is there a lost Fibo sheep somewhere back along the way?
Now that the Visual Basic code is there, only one is lost from among the programs I wrote. It was a C code that worked in base 2^32 rather than 10^k. It's somewhere on the avoiding Basic thread. When I find it, I'll let you know.

There is also Richard's new BBC Basic code which could be added, but I'm not sure he's posted the whole thing.

Mostly, however, that post is an introduction to the last set of timing metrics for a bunch of unrelated languages and programs that haven't yet been run through fibench.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 1:41 am

Which of the BASIC fibo submissions is the most efficient? The classic example was like a balloon test.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 3:12 am

Just for you I ran this little script over the BASIC, Python and Javascript Fibo Challenge solutions:

Code: Select all

echo "Classic line numbered BASIC:"
fbc -O 3 -lang qb -fpu sse -fpmode fast classic.bas
time ./classic | head -c 32
time ./classic | tail -c 32

echo "Modern structured Free Basic"
fbc -O 3 fibo.bas
time ./fibo | head -c32
time ./fibo | tail -c32

echo "Visula BASIC"
vbnc /optimize /removeintchecks visual.bas
time mono visual.exe | head -c 32
time mono visual.exe | tail -c 32

echo "Python 3"
time python3  ../python/fibo.py | head -c 32
time python3  ../python/fibo.py | tail -c 32

echo "Javascript (node.js)"
time  node ../javascript/fibo.js | head -c 32
time  node ../javascript/fibo.js | tail -c 32
With the following results on my Intel PC:

Code: Select all

Classic line numbered BASIC:
10727395641800477229364813596225
real    0m25.777s
user    0m6.953s
sys     0m18.828s
4856539211500699706378405156269

real    0m26.499s
user    0m6.953s
sys     0m20.313s
Modern structured Free Basic
10727395641800477229364813596225
real    0m25.639s
user    0m25.625s
sys     0m0.000s
4856539211500699706378405156269

real    0m26.958s
user    0m25.953s
sys     0m2.297s
Visula BASIC
Visual Basic.Net Compiler version 0.0.0.5943 (Mono 4.0.1 - tarball)
Copyright (C) 2004-2010 Rolf Bjarne Kvinge. All rights reserved.

Assembly 'visual, Version=0.0, Culture=neutral, PublicKeyToken=null' saved successfully to '/mnt/c/Users/michael/Documents/fibo_4784969/BASIC/visual.exe'.
Compilation successful
Compilation took 00:00:00.9075800
10727395641800477229364813596225
real    0m12.380s
user    0m11.250s
sys     0m1.109s
4856539211500699706378405156269

real    0m10.759s
user    0m10.234s
sys     0m1.234s
Python 3
10727395641800477229364813596225
real    0m17.663s
user    0m17.578s
sys     0m0.031s
9
Run time = 0.7130409998353571

real    0m17.559s
user    0m17.500s
sys     0m0.047s
Javascript (node.js)
fibo            1072739564180047
real    0m57.086s
user    0m56.859s
sys     0m0.188s
00699706378405156269 in 12552ms

real    0m56.545s
user    0m56.266s
sys     0m0.156s
Which we can summarize as approximately:

Code: Select all

Classic line numbered BASIC     25 seconds
Modern structured Free Basic    25 seconds
Visula BASIC:                   12 seconds
Python 3:                       17 seconds
Javascript (node.js)            57 seconds
So the Classic BASIC "balloon" flies pretty speedily.

The Javascript result is really annoying. The actual calculation only takes about 12 seconds. It's the printing of the result that takes the rest of the time.
Memory in C++ is a leaky abstraction .

jalih
Posts: 124
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 3:35 am

Heater wrote:
Sun Jun 02, 2019 3:12 am
With the following results on my Intel PC:

Code: Select all

Classic line numbered BASIC:
10727395641800477229364813596225
real    0m25.777s
user    0m6.953s
sys     0m18.828s
4856539211500699706378405156269

real    0m26.499s
user    0m6.953s
sys     0m20.313s
Modern structured Free Basic
10727395641800477229364813596225
real    0m25.639s
user    0m25.625s
sys     0m0.000s
4856539211500699706378405156269

real    0m26.958s
user    0m25.953s
sys     0m2.297s
Visula BASIC
Visual Basic.Net Compiler version 0.0.0.5943 (Mono 4.0.1 - tarball)
Copyright (C) 2004-2010 Rolf Bjarne Kvinge. All rights reserved.

Assembly 'visual, Version=0.0, Culture=neutral, PublicKeyToken=null' saved successfully to '/mnt/c/Users/michael/Documents/fibo_4784969/BASIC/visual.exe'.
Compilation successful
Compilation took 00:00:00.9075800
10727395641800477229364813596225
real    0m12.380s
user    0m11.250s
sys     0m1.109s
4856539211500699706378405156269

real    0m10.759s
user    0m10.234s
sys     0m1.234s
Python 3
10727395641800477229364813596225
real    0m17.663s
user    0m17.578s
sys     0m0.031s
9
Run time = 0.7130409998353571

real    0m17.559s
user    0m17.500s
sys     0m0.047s
Javascript (node.js)
fibo            1072739564180047
real    0m57.086s
user    0m56.859s
sys     0m0.188s
00699706378405156269 in 12552ms

real    0m56.545s
user    0m56.266s
sys     0m0.156s
The Javascript result is really annoying. The actual calculation only takes about 12 seconds. It's the printing of the result that takes the rest of the time.
How come outputting the result can be so slow? I timed my little updated 8th code running on a ROCK64 board:

Code: Select all

root@DietPi:~/Downloads# time /opt/8th/bin/rpi64/8th fibo.8th | head -c 32
10727395641800477229364813596225
real	0m0,973s
user	0m0,940s
sys	0m0,012s
root@DietPi:~/Downloads# time /opt/8th/bin/rpi64/8th fibo.8th | tail -c 32
4856539211500699706378405156269

real	0m0,964s
user	0m0,908s
sys	0m0,040s
Calculating and outputting the full million digit number into console takes less than 2.8 seconds. On my PC, it would take just a few hundred millisecs.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 3:51 am

It's a mystery,

The C version of the Fibo Challenge solution that cheats by using the fibo function from the GMP library can calculate and output the whole thing in 250ms on my PC.

Even my C++ version with my home made big integer calculations can do it less than a second.

Node.js is not the only offender here. Python and some others I forget spend a lot of time just printing the result.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 4:57 am

ejolson wrote:
Sat Jun 01, 2019 11:32 pm
Heater wrote:
Sat Jun 01, 2019 10:29 pm
Is there a lost Fibo sheep somewhere back along the way?
Now that the Visual Basic code is there, only one is lost from among the programs I wrote. It was a C code that worked in base 2^32 rather than 10^k. It's somewhere on the avoiding Basic thread. When I find it, I'll let you know.
Rejoice with me; for I have found my code which was lost.

It was on page 30 of the Why Avoid Basic thread. Following is a new version that works with fibench:

Code: Select all

/*  fibob2.c -- Compute the nth Fibonacci Number
    Written December 15, 2018 by Eric Olson

    This program is provided for completeness as an example of
    explicitly using the definition

        F(k+1) = F(k) + F(k-1)

    to compute the nth Fibonacci number.

    Version 2:  Minor changes micro-optimize the upper bounds on loops
    as compilers don't do this because of possible pointer aliasing.

    Version 3:  Minor changes micro-optimize converting from base 2 to
    base 10 prior to printing.  */

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

#define K 150000

typedef unsigned int digit;
typedef unsigned long long ddigit;
static const digit halfbase=(1<<(sizeof(digit)<<2));
static int base10,zero10;

static void b10print(digit *d){
    printf("%u",d[d[0]]);
    for(int i=d[0]-1;i>=1;i--){
        printf("%0*u",zero10,d[i]);
    }
    printf("\n");
}
static inline digit digitlow(digit x){
    return x&((1<<(sizeof(digit)<<2))-1);
}
static inline digit digithigh(digit x){
    return x>>(sizeof(digit)<<2);
}
static void b10add(digit *d,digit c){
    int i,imax;
    for(i=1,imax=d[0];i<=imax;i++){
        d[i]+=c;
        c=d[i]/base10;
        d[i]%=base10;
    }
    if(c){
        do {
            d[++imax]=c;
            c=d[imax]/base10;
            d[imax]%=base10;
        } while(c);
        d[0]=imax;
    }
}
static void b10mul(digit *d,digit x){
    for(int i=1,imax=d[0];i<=imax;i++) d[i]=d[i]*x;
}
static void b2print(digit *a){
    static digit r[K*3];
    r[0]=1; r[1]=0;
    for(int i=a[0];i>=1;i--){
        b10mul(r,halfbase);
        b10add(r,digithigh(a[i]));
        b10mul(r,halfbase);
        b10add(r,digitlow(a[i]));
    }
    b10print(r);
}

static void b2add(digit *a,digit *b){
    digit *r=a;
    ddigit t=0;
    int i,imax;
    if(a[0]<b[0]) { a=b; b=r; };
    for(i=1,imax=b[0];i<=imax;i++){
        t+=(ddigit)a[i]+b[i];
        r[i]=t;
        t>>=sizeof(digit)<<3;
    }
    for(imax=a[0];i<=imax;i++){
        t+=a[i];
        r[i]=t;
        t>>=sizeof(digit)<<3;
    }
    if(!t) r[0]=a[0];
    else r[r[0]=i]=t;
}

static digit a[K],b[K];
int main(){
    if(sizeof(ddigit)!=2*sizeof(digit)){
        fprintf(stderr, "Please recompile so sizeof(ddigit)=%d"
            " is twice sizeof(digit)=%d!\n",
            (int)sizeof(ddigit),(int)sizeof(digit));
        exit(1);
    }
    for(zero10=0,base10=10;base10<halfbase;base10*=10) zero10++;
    base10/=10;
    for(;;){
        a[0]=1; a[1]=1; for(int i=2;i<K;i++) a[i]=0;
        b[0]=1; b[1]=1; for(int i=2;i<K;i++) b[i]=0;
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        int n=atoi(buf);
        if(n==0) return 0;
        digit *p1=a,*p2=b;
        for(int i=2;i<n;i++){
            b2add(p1,p2);
            digit *t=p1; p1=p2; p2=t;
        }
        b2print(p2);
    }
    return 0;
}
This program uses neither the doubling formula nor Karatsuba multiplication, but instead computes by means of dynamic programming, big numbers stored in base 2^32 and a simple base-10 conversion routine for printing.

The fibob2.c code in C along with fibo.bas in structured Free Basic represent two simple O(n^2) algorithms that can be used to judge which programming languages are expressive enough that the asymptotically superior Karatsuba multiplication and doubling formulas lead to noticeable performance improvements for problems sized in a way that the total computational time is less than 1000 seconds. This somewhat arbitrary time limit naturally occurs as the vertical range in the graphs presented so far and is short enough the run times could be measured during a lecture-demonstration held in a computing lab.

I hope the PL/I code appears soon and runs on the Pi Zero, because I would like to include it in the next roundup of Fibonacci programs.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 9:30 am

Ah, I remember, the black sheep.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 3:04 pm

Heater wrote:
Sun Jun 02, 2019 9:30 am
Ah, I remember, the black sheep.
That little fibob2.c program is more of a lamb than a sheep.

I just found another one of my lost Fibonacci codes here on the Why Avoid Basic thread. That program is an MPI-parallel code designed to run on distributed-memory machines, though it can also run in parallel on a multiple-core system. I will again rejoice, after a way to run it under fibench is discovered.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 5:09 pm

I wonder I your fibo could run as multiple threads in ScriptBasic?

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 6:07 pm

If you want to see how to tweak the algorithm to run in multiple thread on multiple cores for a useful speed up take a look a ejolsons C solution: parallel.c : https://github.com/ZiCog/fibo_4784969/b ... parallel.c

He uses OpenMP or Cilk to manage the parallelization but use of them is hidden behind macros: spawn, sync, get_ncpu, workers. So it's easy to see how it works.

I did similar, using OpenMP only, in my C++ solution: fibo_karatsuba.cpp and bint.h : https://github.com/ZiCog/fibo_4784969/t ... er/c%2B%2B
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 6:25 pm

ScriptBasic wrote:
Sun Jun 02, 2019 5:09 pm
I wonder I your fibo could run as multiple threads in ScriptBasic?
It's possible. Rather than threads, the MPI code works with an abstraction called a rank, which is generally a separate process tied to a particular CPU core using set affinity. Since the Pi Zeros on the super-cheap cluster have single-core processors, then each rank runs on a different Pi.

You may also want to examine the multi-threaded codes (that were just mentioned above) which use OpenMP to exhibit task parallelism within the Karatsuba algorithm and the doubling formulas. These OpenMP codes may scale better than fibompi.c; however, they require shared memory on a multi-core processor and can't parallelize across multiple nodes in a cluster.

I now have fibompi running under fibench using five Pi Zero computers which have been networked together using the Ethernet gadget over USB.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 9:40 pm

I would invest time into this if array thrashing isn't part of the mix. Can't we use a 1 mil result string and fill in the holes using int/dbl math?

I could create a 1 meg string in common memory with MT (R/W lockable) and each thread do it's part updating the common string.

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 10:01 pm

What do you mean by "holes"?

I don't understand the "array thrashing" issue. Arrays are the simplest, fastest data structures we have.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sun Jun 02, 2019 11:50 pm

Not in ScriptBasic. They are basically linked lists that are dynamically allocated that have unlimited indices, can be associative or indexed based or a combo of both containing any type of data. That takes time.

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

Re: A Final Fibonacci Challenge

Mon Jun 03, 2019 12:05 am

Then you have a language using a fundamental design that makes it no so good for this particular problem. If this kind of problem is important, you'd need to change something deep in your system. If it isn't, don't worry, accept that decisions have consequences and move on to enjoy whatever benefits you consider those choices provide.
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.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

User avatar
John_Spikowski
Posts: 1614
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:19 am

I did solve the problem by using the GMP fibo.

At the time, if the language you use couldn't do the the fibo challenge native then it must be flawed.

All it proved to me is ScriptBasic arrays can take a beating and remain intact.
Last edited by John_Spikowski on Mon Jun 03, 2019 12:28 am, edited 1 time in total.

Return to “General programming discussion”