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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 11:44 am

PeterO,
Here's and ALGOL-60 programme for printing Fibonacci numbers.
That is just beautiful. So beautiful I had to print it out and admire it. After all, it is the mother of pretty much all languages in use today.

Shame I don't have any green stripey fan fold to print it on.
I'm just loading the compiler now.... 33 minutes to compute and print first 500 numbers...
OK. What monster machine are you running that on?

I was late to the game. My first high level language was Algol 68 run on a big, beautiful, orange, ICL 2960 in 1976.

Could I ask you a big favor?

Could you move the Fibonacci calculation into it's own procedure: FIBO(N) INTEGER N'

I'm guessing that FIBO(4784969) might be a bit of a stretch...
Memory in C++ is a leaky abstraction .

User avatar
PeterO
Posts: 5021
Joined: Sun Jul 22, 2012 4:14 pm

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 12:11 pm

Heater wrote:
Thu Nov 22, 2018 11:44 am
PeterO,
Here's and ALGOL-60 programme for printing Fibonacci numbers.
That is just beautiful. So beautiful I had to print it out and admire it. After all, it is the mother of pretty much all languages in use today.

Shame I don't have any green stripey fan fold to print it on.
I'm just loading the compiler now.... 33 minutes to compute and print first 500 numbers...
OK. What monster machine are you running that on?
Running here at home on my emulator for the Elliott 803.

https://www.youtube.com/watch?v=Wa7KVU_e8U8

Here's the Algol compiler running on the real machine https://www.youtube.com/watch?v=AIxZ1i8pvZI
Could you move the Fibonacci calculation into it's own procedure: FIBO(N) INTEGER N'
I'm guessing that FIBO(4784969) might be a bit of a stretch...
I don't think the universe is old enough to have computed that on the 803 :-)

PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 2:43 pm

Heater wrote:
Thu Nov 22, 2018 5:44 am
The md5sum of the output, as an ASCII string of hex digits, is:

9f4f03ed9084412b4e57461e8b9870d0

The sha256sum is:

ee09a5c7cd0ac5884386cefd4ac78dc377f60ad180815169ed3d01d76f934385
Thank you. Is that lower case output or uper case? Eg does it start ac7b08a or does it start AC7B08A?

I realize that some people are using %x instead of [/b]%X[/b] is the reason for my question. One limit of BASIC is that using the builtin print to print hex without any conversion in between produces uper case hex, hence the question.

Though I did find a bug in my algorithm, one that others should have caught also. I am figuring out how to correct it, as it is an odd one (I can clearly see why it is wrong, not so clear on the how to correct).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:05 pm

OK I give (for now, likely to come back to this, I like challenges). Working with extremely large numbers can be a challenge.

Later on this today when I have a few minutes I will see about reimplementing it with BCD math.

I still want to see the algorithm that succeeds at this in C if Heater or someone else is willing to show it.

@Heater:
How do you not know how to do this and yet you claim that you have done it in C? Unless you are calling C with a non-standard library C (which I would dissagree with).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:08 pm

DavidS wrote:
Thu Nov 22, 2018 2:43 pm


Thank you. Is that lower case output or uper case? Eg does it start ac7b08a or does it start AC7B08A?

I realize that some people are using %x instead of [/b]%X[/b] is the reason for my question. One limit of BASIC is that using the builtin print to print hex without any conversion in between produces uper case hex, hence the question.
I think in Heater's post he said 'x' and the output had lower case letters.

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:17 pm

DavidS wrote:
Thu Nov 22, 2018 3:05 pm
I still want to see the algorithm that succeeds at this in C if Heater or someone else is willing to show it.
C cannot do this in the language. Its not what C is about (which is producing fast code close to the hardware whilst being portable and easy to maintain). Arbitrary precision arithmetic doesn't have much relevance for most uses of C (except that the C compiler uses it for processing literals).

C is a relatively simple language that's easy to write compilers for - it relies on libraries for everything else. For example, there is no I/O in C, library routines are called for things like printf(), read() and write() etc. Similarly for extensions like big numbers. Its just the way C works.
The great run-time library support that C has, meant that million digit fibo() was easy to program.

The ease of writing compilers for it helped its success I am sure.
Last edited by jahboater on Thu Nov 22, 2018 3:22 pm, edited 2 times in total.

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:18 pm

PeterO wrote:
Thu Nov 22, 2018 12:11 pm
Heater wrote:
Thu Nov 22, 2018 11:44 am
PeterO,
Here's and ALGOL-60 programme for printing Fibonacci numbers.
That is just beautiful. So beautiful I had to print it out and admire it. After all, it is the mother of pretty much all languages in use today.

Shame I don't have any green stripey fan fold to print it on.
I'm just loading the compiler now.... 33 minutes to compute and print first 500 numbers...
OK. What monster machine are you running that on?
Running here at home on my emulator for the Elliott 803.

https://www.youtube.com/watch?v=Wa7KVU_e8U8

Here's the Algol compiler running on the real machine https://www.youtube.com/watch?v=AIxZ1i8pvZI
Could you move the Fibonacci calculation into it's own procedure: FIBO(N) INTEGER N'
I'm guessing that FIBO(4784969) might be a bit of a stretch...
I don't think the universe is old enough to have computed that on the 803 :-)

PeterO
Interesting to know. Anything not on youtube (do not really feel like typing a url of my phone, just to watch a video).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:26 pm

jahboater wrote:
Thu Nov 22, 2018 3:17 pm
DavidS wrote:
Thu Nov 22, 2018 3:05 pm
I still want to see the algorithm that succeeds at this in C if Heater or someone else is willing to show it.
C cannot do this in the language. Its not what C is about (which is producing fast code close to the hardware whilst being portable and easy to maintain). Arbitrary precision arithmetic doesn't have much relevance for most uses of C (except that the C compiler uses it for processing literals).
Same is true of BASIC, as far as not having much use for Arbitary Precision, and not being able to do it natively (without implementing an extended algorithm to deal with multiple word math). Though Heater had said he had implemented in C (unless I missunderstood), and I wanted to know the algorithm that he used to accomplish it, as it would be directly translatable to BASIC.

Just like neither langauge supports BCD math, yet people do BCD math in both all the time, when dealing with huge values and not caring about the time it takes. Every reference I have found on doing math with extremely large numbers in C shows it being done in BCD, which would be slower than multi-word native math.
C is a relatively simple language that's easy to write compilers for - it relies on libraries for everything else. For example, there is no I/O in C, library routines are called for things like printf(), read() and write() etc. Similarly for extensions like big numbers. Its just the way C works.

The ease of writing compilers for it helped its success I am sure.
That is very true. Though we generally consider the libraries defined in the C89 and C99 standards to be C, and other libraries to be not just C even when they are written in C (unless the example includes all the source for all libraries used). The exception being calls that are native to the operating environment (no one expects you to include the source for X11, it is still C without that).

And the libraries for huge numbers are not in the C89 or C99 standard so are extensions.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:46 pm

DavidS wrote:
Thu Nov 22, 2018 3:26 pm
Just like neither language supports BCD math, yet people do BCD math in both all the time, when dealing with huge values and not caring about the time it takes. Every reference I have found on doing math with extremely large numbers in C shows it being done in BCD, which would be slower than multi-word native math.
Yes it would be much slower.
I think the Intel x86 hardware dropped BCD support when it moved to 64-bit and ARM has never had it.
Python uses 16 or 32 bit words for doing big numbers, GMP (the C library) uses 32 or 64 bit words (called "limb"s).

You are right of course about GMP not being mentioned in the standard, not even C18 which is the latest. The standard does include quite a few basic library functions which means compilers can replace them with inline code as long as it does the same thing.
Last edited by jahboater on Thu Nov 22, 2018 5:20 pm, edited 1 time in total.

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 3:58 pm

DavidS,
Is that lower case output or uper case?
Lower case.
Eg does it start ac7b08a or does it start AC7B08A?
Neither.

The first 40 of the 830483 hex digits are as follows:

Code: Select all

$ node fiboFast.js | head -c 40
1d543d8cd48be3ac139b8751944afda3a607c116

$ ./fiboFast | head -c 40
1d543d8cd48be3ac139b8751944afda3a607c116

$ ./fiboFast | head -n 1 | md5sum
9f4f03ed9084412b4e57461e8b9870d0  -

$ ./fiboFast | head -n 1 | sha256sum
ee09a5c7cd0ac5884386cefd4ac78dc377f60ad180815169ed3d01d76f934385  -
One limit of BASIC is that using the builtin print to print hex without any conversion in between produces uper case hex, hence the question.
No worries. Just run the output through tr. For example:

Code: Select all

$ ./fiboFast | head -n 1 | tr '[:upper:]' '[:lower:]'
Working with extremely large numbers can be a challenge...
Yes but, PeterO did big fibos above using 58 year old language running on a 60 year old computer architecture. It's a beautiful piece of code. Do take a look, it employs what I think is a neat trick...

The elements of PeterO's big integer arrays are in base 100,000,000,000. He does a carry when 100,000,000,000 is overflowed. That means when it comes time to print the big number he only needs to print the elements as normal decimal integers, with leading zero suppression, one after the other. No messing around with binary bases or hex conversions. It's much quicker to convert and print those elements in decimal one at a time than deal with converting the array as a whole from binary to ASCII decimal

Brilliant!

Of course PeterO can work in base 100,000,000,000 because the Eliot 803 had a 39-bit word length! We would have to use base 1,000,000,000 on 32 bit machines.

We can learn a thing or two from the old times!
How do you not know how to do this and yet you claim that you have done it in C?
Despite my awesome powers, if I were to write all this big integer maths stuff myself it would take all year, be huge, ugly, complicated and buggy. I ain't going there unless under duress.
Unless you are calling C with a non-standard library C (which I would dissagree with).
So of course I'm using a library. libgmp. It would be silly not to.
Memory in C++ is a leaky abstraction .

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 4:28 pm

Heater wrote:
Thu Nov 22, 2018 3:58 pm
DavidS,
Is that lower case output or uper case?
Lower case.
One limit of BASIC is that using the builtin print to print hex without any conversion in between produces uper case hex, hence the question.
No worries. Just run the output through tr. For example:

Code: Select all

$ ./fiboFast | head -n 1 | tr '[:upper:]' '[:lower:]'
Again this is BBC BASIC V, that is part of RISC OS, not Linux. Yes there are a few versions for Linux, and I am looking at them, though so far I am still using the RISC OS builtin version.

No tr command. I never thought to look to see if there is a command to automate that kind of thing though (not the kind of command one usually thinks about). Ok just on a quick look not finding a command for that, nor a system call (even though we have system calls to convert numbers to strings in ASCII HEX or base10).

Um if I have to convert to lower case I may as well do it in BASIC, even though though that means a one charactor at a time conversion.
Working with extremely large numbers can be a challenge...
Yes but, PeterO did big fibos above using 58 year old language running on a 60 year old computer architecture. It's a beautiful piece of code. Do take a look, it employs what I think is a neat trick...
I will look at that for sure.
The elements of PeterO's big integer arrays are in base 100,000,000,000. He does a carry when 100,000,000,000 is overflowed. That means when it comes time to print the big number he only needs to print the elements as normal decimal integers, with leading zero suppression, one after the other. No messing around with binary bases or hex conversions. It's much quicker to convert and print those elements in decimal one at a time than deal with converting the array as a whole from binary to ASCII decimal

Brilliant!

Of course PeterO can work in base 100,000,000,000 because the Eliot 803 had a 39-bit word length! We would have to use base 1,000,000,000 on 32 bit machines.

We can learn a thing or two from the old times!
Now that is a good trick. I guess that it would be a little faster than doing something like BCD to calculate, and a lot faster to convert to base10 output.
How do you not know how to do this and yet you claim that you have done it in C?
Despite my awesome powers, if I were to write all this big integer maths stuff myself it would take all year, be huge, ugly, complicated and buggy. I ain't going there unless under duress.
Unless you are calling C with a non-standard library C (which I would dissagree with).
So of course I'm using a library. libgmp. It would be silly not to.
Fair enoug. Though add is easy enough in binary for calculation purposes, so long as you know the absolute maximum size of the value (just carry over on negitive). The issues come with everything else.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 5:05 pm

For the time being this thread has had me off target to long.

I need to get back over to Linux, so that I can get RPCEmu up and runnign, see about getting RISC OS on Linux running, and make sure that the source for YANGTOS still compiles on Linux after the changes I made today.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 5:29 pm

Heater wrote:
Thu Nov 22, 2018 3:58 pm
Brilliant!

Of course PeterO can work in base 100,000,000,000 because the Eliot 803 had a 39-bit word length! We would have to use base 1,000,000,000 on 32 bit machines.

We can learn a thing or two from the old times!
Or even from previous posts in this thread made by other forum members.
Heater wrote:
Thu Nov 22, 2018 3:58 pm
Despite my awesome powers, if I were to write all this big integer maths stuff myself it would take all year, be huge, ugly, complicated and buggy.
Anyone wanting to improve their ability to code algorithms may find it beneficial to work some of the programming contest questions at Sphere Online Judge.

Many teachers would consider scripting calls to subroutines that perform algorithms other people wrote to be a bit different than coding the algorithm oneself. People saying C can't handle big numbers may be surprised to discover the built-in big-number handing features of many programming languages use subroutine libraries written primarily in C behind the scenes.

In my experience, students who take too many short cuts eventually lack the skills needed to handle difficult problems for which algorithms and code have not already been developed. For purposes of achieving some sort of mastery, I believe it is useful to learn through a sequence of carefully graded exercises of increasing difficulty. To this end, programming big-number arithmetic not only increases understanding of how big-number arithmetic works but develops general programming skills which are essential when coding more-complicated, new and original algorithms.

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 5:39 pm

ejolson wrote:
Thu Nov 22, 2018 5:29 pm
Heater wrote:
Thu Nov 22, 2018 3:58 pm
Brilliant!

Of course PeterO can work in base 100,000,000,000 because the Eliot 803 had a 39-bit word length! We would have to use base 1,000,000,000 on 32 bit machines.

We can learn a thing or two from the old times!
Or even from previous posts in this thread made by other forum members.
Heater wrote:
Thu Nov 22, 2018 3:58 pm
Despite my awesome powers, if I were to write all this big integer maths stuff myself it would take all year, be huge, ugly, complicated and buggy.
Anyone wanting to improve their ability to code algorithms may find it beneficial to work some of the programming contest questions at Sphere Online Judge.

Many teachers would consider scripting calls to subroutines that perform algorithms other people wrote to be a bit different than coding the algorithm oneself. People saying C can't handle big numbers may be surprised to discover the built-in big-number handing features of many programming languages use subroutine libraries written primarily in C behind the scenes.

In my experience, students who take too many short cuts eventually lack the skills needed to handle difficult problems for which algorithms and code have not already been developed. For purposes of achieving some sort of mastery, I believe it is useful to learn through a sequence of carefully graded exercises of increasing difficulty. To this end, programming big-number arithmetic not only increases understanding of how big-number arithmetic works but develops general programming skills which are essential when coding more-complicated, new and original algorithms.
Thank you for reiterating my point. Just because a language does not have feature X built in does not mean you are limited from implementing a way to accomplish feature X (without using someone else libs).

Also thank you for the pointer to the contests.


Bare Metal Scene Demo coding is another way to hone skills, one that some of us have enjoyed since the early 1980's.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 6:06 pm

DavidS wrote:
Thu Nov 22, 2018 5:39 pm
Also thank you for the pointer to the contests.
You're welcome. Currently code submitted as an answer is tested for correctness and efficiency using a single Xeon E3-1220 v5 CPU core provisioned with 1.5GB RAM. Some questions also specify a maximum size for the source code, a specific programming language or other constraints to make the challenge more difficult. It looks like Visual BASIC.net is the only version of BASIC understood by the system.

I've always thought it would be fun and good publicity for the Raspberry Pi Foundation to sponsor an online programming contest where a cluster of Pi computers was used to check the submissions. If that happens, maybe BBC BASIC could also be added to the list of accepted programming languages.

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 8:43 pm

To appease those that complain that using a non C standard library to do big integer maths is cheating, and for giggles, I implemented a version of PeterO's traditional iterative fibo algorithm in C doing the big integer additions manually.

It's a bit slow. Our million digits of fibo(4784969) takes nearly 14 minutes on my PC. Compare to the 30ms of the fastFibo.

The code:

Code: Select all

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

#define N 60000

// 18 9's
#define LIM 999999999999999999

uint64_t a[N];
uint64_t b[N];
uint64_t c[N];

void puti (uint64_t *a)
{
    char leadingZero = 1;

    for (int i = N - 1; i >= 0; i--)
    {
        if (leadingZero)
        {
            if ((a[i] != 0) || (i == 0))
            {
                printf("%0" PRIu64, a[i]);
                leadingZero = 0;
            }
        }
        else
        {
            printf("%0*" PRIu64, 18, a[i]);
        }
    }    
}

void addi (uint64_t *a, uint64_t *b, uint64_t *c)
{
    uint64_t j;
    uint64_t sum;
    int carry;

    carry = 0;

    for (j = 0; j < N; j++) {
        sum = b[j] + c[j] + carry;
        if (sum > LIM)
        {
            a[j] = sum - LIM - 1;
            carry = 1;
        }
        else{
            a[j] = sum;
            carry = 0;
        }
    }
}

int main (int argc, char* argv)
{
    for (int i = 0; i < N; i++) {
        a[i] = 0;
        b[i] = 0;
        c[i] = 0;
    }

    b[0] = 0;
    c[0] = 1;

    int n = 4784969;  // The first fibo with 1 million digits
    int count = 0;
    while (1)
    {
        addi(a, b, c);
        count++;
        if (count == n)
        {
            puti(a);
            printf("\n");
            break;
        }

        addi(c, b, a);
        count++;
        if (count == n)
        {
            puti(c);
            printf("\n");
            break;
        }

        addi(b, a, c);
        count++;
        if (count == n)
        {
            puti(b);
            printf("\n");
            break;
        }
    }

    return 0;
}
The result:

Code: Select all

$ time ./fiboSlow
...
1899441410955952199093230662515228401051114812321029531207832876870087454540927898489890806067034196931622252893057035920930130552038239931974615715617623206204585291487968755147324883784916338945806361951766313865956891695455563801462249978567353436540666740580717167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269

real    13m52.268s
user    13m50.188s
sys     0m0.063s
$
On the plus side. Because of the PeterO style decimal calculations printing the final result in decimal is indistinguishable from instant. Far quicker than the big integer printing of Python, JS or gmp.
Memory in C++ is a leaky abstraction .

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 8:55 pm

DavidS,
For the time being this thread has had me off target to long.
Yes. I think it's wise of you give up the fibo(4784969) in BASIC challenge now. Because:

1) The algorithm you are implementing (at least as presented so far) far from running in your claimed 23 seconds, will take a very long time. I see that you are implementing the naive iteration of additions until you get to the right Finonacci number. This approach will take a week to get to fibo(4784969) using interpreted BASIC and an hour or two with a compiled BASIC. It is not worth doing.

2) You could adopt the fast algorithm as presented here in Javascript and Python. But that would require you to implement enough of a big integer library to perform addition, subtraction and squaring. Personally I think your time would be better spent elsewhere.
Memory in C++ is a leaky abstraction .

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 9:00 pm

Wow.

I'm just trying using the carry bit rather than "if(sum > LIM)" to see if its any faster.
I wonder how GMP is so fast.

Code: Select all

void addi (uint64_t *a, uint64_t *b, uint64_t *c)
{
    uint64_t carry = 0;

    for( uint64_t j = 0; j < N; ++j ) {
       uint64_t sum;
       carry = __builtin_add_overflow( b[j], c[j], &sum ) ||
               __builtin_add_overflow( sum, carry, &sum );
       a[j] = sum;
    }
}
11 minutes,
Its all wrong though. The result disagrees with yours, and your result disagrees with the gmp fibo function :(

I suppose its cheating to get the carry bit out with the "=@ccc" inline assembly flag output.

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 9:31 pm

jahboater,
I wonder how GMP is so fast.
The C version using GMP we are using here simply calls the gmp function: mpz_fib_ui( res, 4784969 );

No doubt that does not use the schoolboy algorithm I show above in fiboSlow. Rather they will use a fast fibo algorithm, perhaps as described here: Fast Fibonacci algorithms: https://www.nayuki.io/page/fast-fibonacci-algorithms

Which is what I implemented in JS using JS BigInts here: viewtopic.php?f=32&t=225927&start=25#p1388128

Quite often it is very wise to use a library rather than try to reinvent the wheel oneself. Where people far more knowledgeable have done the hard work to perfect an optimal solution and years of use by many users has shaken the bugs out of it.
Memory in C++ is a leaky abstraction .

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 9:37 pm

Heater wrote:
Thu Nov 22, 2018 9:31 pm
Quite often it is very wise to use a library rather than try to reinvent the wheel oneself. Where people far more knowledgeable have done the hard work to perfect an optimal solution and years of use by many users has shaken the bugs out of it.
So true!

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

Re: Why Avoid BASIC on RPi?

Thu Nov 22, 2018 9:38 pm


User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Fri Nov 23, 2018 12:45 am

Heater wrote:
Thu Nov 22, 2018 9:31 pm
jahboater,
I wonder how GMP is so fast.
The C version using GMP we are using here simply calls the gmp function: mpz_fib_ui( res, 4784969 );

No doubt that does not use the schoolboy algorithm I show above in fiboSlow. Rather they will use a fast fibo algorithm, perhaps as described here: Fast Fibonacci algorithms: https://www.nayuki.io/page/fast-fibonacci-algorithms

Which is what I implemented in JS using JS BigInts here: viewtopic.php?f=32&t=225927&start=25#p1388128

Quite often it is very wise to use a library rather than try to reinvent the wheel oneself. Where people far more knowledgeable have done the hard work to perfect an optimal solution and years of use by many users has shaken the bugs out of it.
Yes there are times to just existing libs, this is not one of them. The lack of information before on fast algorithms was causing slow implementations, and in my case one duh of a wrong implementation.

When comparing the speed of languages a common algorithm is needed, for all languages.

Thank you for finally sharing the algorithm you are using within this thread.

When one can they should take the time to figure out how to do it themselves, and working something through on a forum is one of these times. That is the only that people come up with better implementation algorithms, they may or may not be as good as the libs, though if we do not try how will we ever know.

Though this does look like a problem that when I come back to it may do well for VFP.

You did not make note of the algorithm speed I chose previously, could have saved me a lot of time in figuring out I had something wrong, based on how fast it was running alone.

Sharing is not about making things harder. And I had only ever calculated much smaller fibonacci sequence values before, usually intentionally by the worste meathod possible (recursive) and usually to show why you avoid the stack.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Fri Nov 23, 2018 12:46 am

The forum doubled my post.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Fri Nov 23, 2018 12:50 am

bensimmo wrote:
Thu Nov 22, 2018 9:38 pm
Why not add these to https://rosettacode.org/wiki/Category:Programming_Tasks as tasks ?
Yea doing all of those would be a good challenge, and a decent way to check that ones understanding of every one of them is good as well as understanding of the language of implementation.

That looks like a lot of coding for a person. Thank you for filling my evenings for a while.

As I have stated I have lost more than I wish to admit after my stroke, over a year ago. So I am still learning a lot of what I did know.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Fri Nov 23, 2018 3:15 am

DavidS,
Yes there are times to just existing libs, this is not one of them...
Actually... When I proposed the fibo(4784969) challenge there were no libs used in my Javascript solution or in the Python version. I'm not sure how we got side tracked with this libs thing.
The lack of information before on fast algorithms was causing slow implementations,...
Both the solutions, Python and JS, using a fast algorithm were shown in the original challenge post:
viewtopic.php?f=62&t=227343#p1394452 Sadly you seem to have missed that.
When comparing the speed of languages a common algorithm is needed, for all languages.
I agree. That is why the Python and JS solutions are doing step for step the same thing and look very similar. They both compute fibo using the same algorithm.
Thank you for finally sharing the algorithm you are using within this thread.
Finally? The algorithm is right there, clear as day, in JS and Python in the original challenge post here. See link above.
When one can they should take the time to figure out how to do it themselves,and working something through on a forum is one of these times.
Yep, that's what I did in this case. The actual maths that I developed those solutions from his here: https://www.nayuki.io/page/fast-fibonacci-algorithms
You did not make note of the algorithm speed I chose previously, could have saved me a lot of time in figuring out I had something wrong, based on how fast it was running alone.
Actually I did. Here: viewtopic.php?f=62&t=227343&start=50#p1394607 Where I said:

"Actually no. Your claimed execution time sounds very unlikely.

50ms to calculate fibo(4784969) is almost twice as fast as using libgmp's fibo function in C on my 3GHz PC.

Forgive me if I'm a bit suspicious about that result."
I had only ever calculated much smaller fibonacci sequence values before, usually intentionally by the worste meathod possible (recursive) and usually to show why you avoid the stack.
You should not avoid the stack, the stack is great, using the stack can be the best. In fact the fast Fibo I have presented here is recursive. It contains 5 calls to itself!

Anyway, we all learned a lot here. Thanks to PeterO I'm now writing in Algol60 again! I found this great Algol60 compiler here: https://github.com/JvanKatwijk/algol-60-compiler
Memory in C++ is a leaky abstraction .

Return to “Off topic discussion”