Why Avoid BASIC on RPi?

[DavidS]

The BASIC solution is the only fail here so far.

So you did find a problem with my implementation. What is it.

But I don't want to publish a million digits here given the current server problems

Ha!

No, the servers are struggling because I post so much

We could just present the end of the million digits, as seen above. Better would be to present the md5sum or sha hash of the result. Much smaller and unlikely to be wrong. Good luck doing that in BASIC.

Why? Many of the early implementations of md5sum were only available in BASIC.

Still simpler to just print out a partial result.

[Heater]

DavidS,

Well that might be possible, to do in a reasonable amount of time. Even in C

The C version prints all one million digits in 283ms on my PC. I don't have the possibility to try it on a Pi just now. Either way it's "reasonable".

I should have been more clear. I did not mean the program only prints a few digits. I meant a few digits should be presented here as output along with the timing information. As shown above. Or we could just run it for ourselves and get the whole million digits.

Thanks for the links to the BASIC documentation. I won't be going there. Even if I did I still don't know if your actual run time engine is correct.

So much easier to just check the out put against other solutions.

[jahboater]

The C versions we have just call a fibo function in the gmp library. I have no way to know how plausible that result is. Who knows what bugs are in there?

But we have solutions presented in Python and Javascript that do the algorithm themselves. Albeit the big integer maths is done by the languages in question. At least we can see we have the right algorithm there.

Yes. The fibo function is open source, so that slgorithm could be verified if it were crucial.
In general, gut feeling and experience leads me to trust public library functions like this (that have presumably be used by countless people over many years), rather than home written solutions used once - by the author. Especially library functions where the source is open to public scrutiny.

Long ago a team member thought the printf function was behaving incorrectly, so he wrote his own. Two sev 1 bugs later ...

[jahboater]

The SHA 256 sum is

a6fe41b901eabc0b39aaa3d9432f8b1e086d5447ab7f45da574b4466923662e9

The MD5 sum is

c926caa99ed1e30fe0d3c966da901738

[DavidS]

DavidS,

Well that might be possible, to do in a reasonable amount of time. Even in C

The C version prints all one million digits in 283ms on my PC. I don't have the possibility to try it on a Pi just now. Either way it's "reasonable".

Could I please get the algorithm you are using to convert the binary data to a decimal character string? This is one area where I have always had difficulty.

I should have been more clear. I did not mean the program only prints a few digits. I meant a few digits should be presented here as output along with the timing information. As shown above. Or we could just run it for ourselves and get the whole million digits.

Thanks for the links to the BASIC documentation. I won't be going there. Even if I did I still don't know if your actual run time engine is correct.

Only posted it because you said you were crazy enough to spend the time to do that. No problem.

So much easier to just check the out put against other solutions.

Agreed. And the output being binary data in RAM is not enough for you, so I am trying to get a good implementation of an algorithm to convert a huge number to a decimal string without having to do million place division.

[jahboater]

The Python and Javascript versions just use their inbuilt print functions I guess.

C has no in-built arbitrary precision arithmetic so the GMP library is used (Gnu Multi-Precision) and its included
"gmp_printf()" function is used.

No much help I am afraid.

Don't worry about it!

[Heater]

DavidS,

So you did find a problem with my implementation. What is it.

Only that it produces no output. So we have no way to know if it is correct.

Why? Many of the early implementations of md5sum were only available in BASIC.

References please.

Why? Because a hash is a pretty good way of verifying a big lot of data is correct whilst being manageably small. So rather than post a million digit result here, just post the hash.

I suspect that is more likely to be a an indication of a correct result that printing a partial result.

After all, if the partial result you give is only one digit, then obviously there is a good chance the result was wrong except in that last digit. Similarly for a 2 digit partial result or 3 or a hundred...

[DavidS]

The Python and Javascript versions just use their inbuilt print functions.

C has no in-built arbitrary precision arithmetic so the GMP library is used (Gnu Multi-Precision) and its included
"gmp_printf()" function is used.

No much help I am afraid.

Don't worry about it!

How is it done in C, like Heater spoke of above, he said he did it in C (not GMP+C or Python or JS)?

If I knew that it would make it a lot easier to do in BASIC.

[Heater]

DavidS,

Could I please get the algorithm you are using to convert the binary data to a decimal character string?

Sure. It's here: https://ftp.gnu.org/gnu/gmp/ The function you are looking for is gmp_printf.

My naive way would be to divide the whole thing by 10 and take the remainder. Add 0x30 and there is your first printable digit. Well, last actually, Keep dividing to get the rest.

Python and Javascript have this built into the language.

Only posted it because you said you were crazy enough to spend the time to do that. No problem.

No, I said:

"This is not really possible unless you have a formal definition of the language I can read. And a formal proof that your interpretter does the right thing according to that definition. And I'm crazy enough to waste my life checking all that."

Notice the "unless" and the "and" there.

Sorry I broke the rules of English grammar by using "." instead of "," and starting new sentences with "And". Still, I thought it was clear enough in one paragraph.

[DavidS]

I could just calculate it in BCD, though that would be a lot slower than the current implementation. If I use the same exact algorithm it will produce the same exact result. So is that acceptable?

Problem with using a hash or md5sum or similar is that the storage format has to be the same on all implementations, which from the fact that Heater is unable to verify the algorithm I must assume is not the case (no one has actually shown how they do it in purely C [NOT C+GMP], so storage format is unknown there).

[DavidS]

I could just calculate it in BCD, though that would be a lot slower than the current implementation. If I use the same exact algorithm it will produce the same exact result. So is that acceptable?

Problem with using a hash or md5sum or similar is that the storage format has to be the same on all implementations, which from the fact that Heater is unable to verify the algorithm I must assume is not the case (no one has actually shown how they do it in purely C [NOT C+GMP], so storage format is unknown there).

AND:
You are doing a good job at making me dislike Python, JS, etc even more. How is a huge number like this represented in a machine native calculable way? I am not aware of any 3.5 million bit CPU register that can do direct calculation.

[jahboater]

How is a huge number like this represented in a machine native calculable way? I am not aware of any 3.5 million bit CPU register that can do direct calculation.

I assume they just use chains of long arithmetic (adds; adc etc). Division must be hard
They talk about "limbs" which I think is the size of the words used to do the long arithmetic. (64-bits in the case of GMP on a PC).
I am sure that Python, JavaScript, and C+GMP have three completely different ways of doing it.
Does it matter what the internal format it is?
You just have to trust the authors and the testing.

[Heater]

DavidS,

Problem with using a hash or md5sum or similar is that the storage format has to be the same on all implementations...

How is that a problem?

Your program outputs a million decimal digits.

You direct then to a file.

You take the hash of the file.

Or you just pipe the program's output into the hash program

Code: Select all

$ ./fibo | md5sum
c27e8469c65ca5d6ffdb50ce42e45df0  -
$

Please don't tell me you are using a machine that does not use ASCII and that would cause the hash to be wrong.

You are doing a good job at making me dislike Python, JS, etc even more. How is a huge number like this represented in a machine native calculable way? I am not aware of any 3.5 million bit CPU register that can do direct calculation.

True. The machine does not have the hardware to do arithmetic directly on billion digit numbers.

That does not mean to say it cannot be done in software and that software can't be built into programming languages.

A fail to see how that would cause you to not like Python or JS or anything else. Don't forget that programming languages often include many things that the machine has no concept of:

Would you dislike a language that provided 16 and 32 bit operations on an 8 bit machine?

Would you dislike a language that provided floating point maths on an an integer machine?

Would you hate a language with functions, subroutines, procedures on a machine that had no JMP, RET instructions or a stack?

Heck, BASIC is terrible. It has FOR loops. No machine has such loops built in.

And strings. WTF?

[DavidS]

Heater you know my point, not going to that again. We know that strings are close enough to raw to handle in 2 instructions, we know that there is a 1 for 1 equivalent to a for loop, etc. Besides those things are not doing direct calculations. I am not going to fall for that path this time.

At the moment I am asking a simple question that is being skirted:

What is the algorithm used to convert an extremely large number into an ASCII string? (I can not get any kind of check on a string that does not exist).

If I do the calculation in BCD (thus simplifying conversion to ASCII) then it will take many many times longer than doing it in native binary.

Do I have to do the calculations in BCD, or is there a reasonably algorithm to convert such a large binary number to ASCII without having to do 3.5 million bit division, that is all I am asking.

[davidcoton]

At the moment I am asking a simple question that is being skirted:

What is the algorithm used to convert an extremely large number into an ASCII string? (I can not get any kind of check on a string that does not exist).

If I do the calculation in BCD (thus simplifying conversion to ASCII) then it will take many many times longer than doing it in native binary.

Do I have to do the calculations in BCD, or is there a reasonably algorithm to convert such a large binary number to ASCII without having to do 3.5 million bit division, that is all I am asking.

I think you have proved a fundamental issue about optimising algorithms. There is no point doing the calculation ten times faster than anyone else, if it provides a (possibly correct) answer in an unhelpful form. And if retrieving the answer slows your algorithm by a factor of ten, you have gained nothing. Assuming, of course, that the slower algorithm gives a result that is both correct and usable.

Metrics need to be chosen carefully to provide useful (comparable) results.

There is a reason for using languages with powerful libraries.Perhaps you need to benchmark using a version of Basic with an arbitrary-precision integer arithmetic library? Not easy to find? That's why Python (with all its problems, like syntactically significant white space) is more popular than Basic at present. Maybe you could write the libraries for Basic? Would thatbe of more use and significance than writing yet another micro-OS?

[davidcoton]

At the moment I am asking a simple question that is being skirted:

What is the algorithm used to convert an extremely large number into an ASCII string? (I can not get any kind of check on a string that does not exist).

If I do the calculation in BCD (thus simplifying conversion to ASCII) then it will take many many times longer than doing it in native binary.

Do I have to do the calculations in BCD, or is there a reasonably algorithm to convert such a large binary number to ASCII without having to do 3.5 million bit division, that is all I am asking.

I think you have proved a fundamental issue about optimising algorithms. There is no point doing the calculation ten times faster than anyone else, if it provides a (possibly correct) answer in an unhelpful form. And if retrieving the answer slows your algorithm by a factor of ten, you have gained nothing. Assuming, of course, that both algorithms give results that are both correct and usable.

Metrics need to be chosen carefully to provide useful (comparable and meaningful) results.

There is a reason for using languages with powerful libraries. Perhaps you need to benchmark using a version of Basic with an arbitrary-precision integer arithmetic library? Not easy to find? That's why Python (with all its problems, like syntactically significant white space) is more popular than Basic at present. Maybe you could write the libraries for Basic? Would that be of more use and significance than writing yet another micro-OS that will probably only be used by a dozen people, ever?

[scruss]

The BASIC solution is the only fail here so far.

X11Basic should be able to do it. It includes bignum support and the FIB() and HASH$() functions. Unfortunately I'm not getting it to reliably interpret FIB() as a function, so it's not much use.

[Heater]

DavidS,

We know that strings are close enough to raw to handle in 2 instructions, we know that there is a 1 for 1 equivalent to a for loop,etc.

Sometimes I don't understand you. There is no handling of string operations, strlen, strcmp, strcpy, etc in 2 instructions on any machine architecture. There is no "1 to 1" equivalents of "for" loops either. Or function calls. And yet you state there is.

What is the algorithm used to convert an extremely large number into an ASCII string?

A good question. Sadly I have no idea.

When have done this in the past it involved a lot of division my 10 and checking the remainder. But that would require a big integer division routine and take a long time.

A suspect the guys creating these big number systems have ways to optimize this a lot. However it is worth noting that all the solutions to this fibo problem have taken far, far, longer to produce a printable result that perform the calculation. This seemingly trivial output formatting is a lot of work.

I'm pretty confident none of them do the calculations in BCD.

[DavidS]

DavidS,

We know that strings are close enough to raw to handle in 2 instructions, we know that there is a 1 for 1 equivalent to a for loop,etc.

Sometimes I don't understand you. There is no handling of string operations, strlen, strcmp, strcpy, etc in 2 instructions on any machine architecture. There is no "1 to 1" equivalents of "for" loops either. Or function calls. And yet you state there is.

What is the algorithm used to convert an extremely large number into an ASCII string?

A good question. Sadly I have no idea.

When have done this in the past it involved a lot of division my 10 and checking the remainder. But that would require a big integer division routine and take a long time.

A suspect the guys creating these big number systems have ways to optimize this a lot. However it is worth noting that all the solutions to this fibo problem have taken far, far, longer to produce a printable result that perform the calculation. This seemingly trivial output formatting is a lot of work.

I'm pretty confident none of them do the calculations in BCD.

I am fairly sure that none of them use BCD as well. It would be an interesting experimint to compare the speed (including producing the final string) of a version that has the of a version with C+CMP versus a version that does it in BCD and uses the BCD values to produce the string again in C. It could be potentially be faster, or it could be as we expect slower.

As the output is needed in ASCII it may indeed end up being faster to do it in BCD just because of the speed up of the output. The entire implementation, including output may be the more telling factor here.

I am barely awake at this time, so if I remember I may see about implementing the C using BCD tomorrow (as well as a BBC BASIC V using BCD).

It will be quite interesting indeed.

[ejolson]

The BASIC solution is the only fail here so far.

X11Basic should be able to do it. It includes bignum support and the FIB() and HASH$() functions. Unfortunately I'm not getting it to reliably interpret FIB() as a function, so it's not much use.

Here is a simple algorithm for converting binary strings to decimal. It thankfully doesn't involve division. However, it looks like an O(N^2) algorithm to me and I suspect the asymptotic runtime of the correct algorithm is much less. For the present case it makes sense, in my opinion, to print the integers in hex and avoid those expensive 10-fingered conversions. I'm pretty sure the GNU GMP library can print integers in different bases for comparison.

When discussing the relative merits of programming languages, I think it is important to distinguish the productivity of a language from its expressiveness. From my point of view, a programming language is not very expressive if most complex algorithms have to be coded using a different language in order to run well. It is expressivity that Kernighan, Ritchie and the other scientists at Bell Labs refer to which allowed them to rewrite most of the Unix operating system in C. At the same time it is interesting many of the subroutines for deep learning, statistics, graphing and big numbers that make Python programmers productive are not written in Python. A language can be productive without being very expressive.

From a social justice point of view, it is liberating to know and use a programming language which is expressive enough that it can be used to efficiently code any algorithm the computer is capable of running. If, in the name of making it easier for people to finish their work only less expressive languages are taught, then an important force has been lost that could have helped equalise the disparity between the digital peasants and the digital landlords who own the intellectual property, or maybe not. I wonder where BASIC fits in.

[ejolson]

I am fairly sure that none of them use BCD as well.

On a 64-bit architecture like ARMv8 that doesn't implement BCD in hardware, using base 1e19 which fits in a 64-bit integer with less than a bit wasted makes more sense than BCD. On 32-bit you may be better off with base 1e9, which wastes a little more than 2 bits per 32-bit integer. In either case, one needs to balance the amount of time doing the arithmetic with the time printing. For the Fibonacci sequence

F(n+1) = F(n) + F(n-1)

the arithmetic is easier than the resulting binary to decimal conversion.

I'm still in favour of printing the numbers in hex.

[DavidS]

I am fairly sure that none of them use BCD as well.

On a 64-bit architecture like ARMv8 that doesn't implement BCD in hardware, using base 1e19 which fits in a 64-bit integer with less than a bit wasted makes more sense than BCD. On 32-bit you may be better off with base 1e9, which wastes more than 2 bits per 32-bit integer and is much easier to work with than BCD. In either case, one needs to balance the amount of time doing the arithmetic with the time printing. In the case of the Fibonacci sequence

F(n+1) = F(n) + F(n-1)

the arithmetic is easier than the resulting binary to decimal conversion.

The balance is why I wonder if it would be faster overall to calculate in BCD. I would note that ARM does not have HW BCD at all (not in 32 bit, not in 64 bit), so BCD math has to be manually coded always on ARM. Also BBC BASIC V does not support BCD, though it is easy enough to code in any language.

I'm still in favour of printing the numbers in hex.

Printing the numbers in hex (or at least dumping to an ASCII text file) is something I can do, with little problem. Once printed as a ASCII file containing a single string of a value of a roughly 3.5 million bits (a bit under 900 thousand hex digits), how will anyone verify the result, as everyone else is printing there results in base10.

And what kind of check would be best to verify. Could do a CRC32, md5sum, rolling sum, or any number of other options on the output file.

[Heater]

ejolson,

For the present case it makes sense, in my opinion, to print the integers in hex and avoid those expensive 10-fingered conversions.

I think that is a good idea. After all decimal digits are for humans and nobody is going to read those million digits, we only want an output to compare with others.

So, changing the "d" to an "x" in the gmp format string I get a hex result on my PC:

Code: Select all

$ time ./fiboFast
...
ac7b08afeac68ed8bf5754a72c12118b6576646b5ca157158c4063366e10624888f2224ed5c1b898833fae0269d5bf7cdb3790e92cb5344a28e5f1c7a488b98cbfea4ec351779712da78ab4fc83e055770b703124f90fa8eaa5dc3c751eee0eeb48e52f012e296001425591bbc80797f899b8002447f9fad5af0c41e2513438599116d50e110143f3f11e10ba66931c07849b14127d984e5008f30a726795b29edd305cf119a92881e37b72529de8661d818efe0457cfebb57ee06d7c563fd47397cb6ef9d9f45c7ac554c2bdf11ca00e11ee4fd681386f276cb553c1ad7fe1d21e91f20dabf5b1b4a3ae64195f0cfb6937603bdcd47cba152def8a07b1d740a4c6d2541ada9aa8955f63e4173f0090db8413d74621c1a15ad
0.031250

real    0m0.125s
user    0m0.031s
sys     0m0.031s
$

Notably the total run time is now halved. Hex is much quicker.

In Javascript I just add .toString(16) to the result:

Code: Select all

$ time node fiboFast.js
...
ac7b08afeac68ed8bf5754a72c12118b6576646b5ca157158c4063366e10624888f2224ed5c1b898833fae0269d5bf7cdb3790e92cb5344a28e5f1c7a488b98cbfea4ec351779712da78ab4fc83e055770b703124f90fa8eaa5dc3c751eee0eeb48e52f012e296001425591bbc80797f899b8002447f9fad5af0c41e2513438599116d50e110143f3f11e10ba66931c07849b14127d984e5008f30a726795b29edd305cf119a92881e37b72529de8661d818efe0457cfebb57ee06d7c563fd47397cb6ef9d9f45c7ac554c2bdf11ca00e11ee4fd681386f276cb553c1ad7fe1d21e91f20dabf5b1b4a3ae64195f0cfb6937603bdcd47cba152def8a07b1d740a4c6d2541ada9aa8955f63e4173f0090db8413d74621c1a15ad
13084ms

real    0m13.362s
user    0m13.063s
sys     0m0.203s
$

In JS time to output is down from 58 seconds. Over 4 times faster.

Some Python head will have to hexadecimalize the Python version. I have no idea how.

[Heater]

The md5sum of the output, as an ASCII string of hex digits, is:

9f4f03ed9084412b4e57461e8b9870d0

The sha256sum is:

ee09a5c7cd0ac5884386cefd4ac78dc377f60ad180815169ed3d01d76f934385

[PeterO]

Since we are talking old languages....
Here's and ALGOL-60 programme for printing Fibonacci numbers.
I'm just loading the compiler now, so I'll update with compile and run times in a while ....

Enjoy.....

Code: Select all

FIBONACCI NUMBERS'

BEGIN INTEGER N,M,COUNT,LIM'
INTEGER ARRAY A, B, C(1:10)' 

PROCEDURE PUTI(A)' INTEGER ARRAY A' 
BEGIN INTEGER J' 
BOOLEAN ALLZERO'
COMMENT SKIP ZERO VALUES IN ARRAY UNTIL FIRST ONE TO PRINT'

   ALLZERO := TRUE'
   LEADZERO(£?)'
   
   PRINT £  ?' 
   FOR J := N STEP -1 UNTIL 1 DO 
   BEGIN
       IF NOT ALLZERO  THEN
             PRINT SAMELINE, SPECIAL(1), DIGITS(11), A(J)
       
       ELSE
       BEGIN
         IF A(J) GR 0 THEN
         BEGIN
           PRINT SAMELINE, SPECIAL(1), DIGITS(11), A(J)'
           LEADZERO(£0?)'
           ALLZERO := FALSE'
         END
       END 
           
   END' 
   LEADZERO(£ ?)'
END OF PUTI' 

PROCEDURE ADDI(A, B, C)' INTEGER ARRAY A, B, C' 
BEGIN INTEGER J, CARRY, SUM' 
   CARRY := 0' 
   FOR J:= 1 STEP 1 UNTIL N DO 
   BEGIN 
      SUM := B(J) + C(J) + CARRY' 
      IF SUM GR LIM THEN 
      BEGIN 
         A(J) := SUM - LIM' 
         CARRY := 1 
      END 
      ELSE 
      BEGIN 
          A(J) := SUM' 
          CARRY := 0 
      END 
     END 
END OF ADDI' 

N := 10'
LIM := 100000000000'

FOR M:= 1 STEP 1 UNTIL N DO
BEGIN
   A(M) := 0'
   B(M) := 0'
   C(M) := 0'
END'

B(1) := 1'
C(1) := 1'

PRINT DIGITS(3),1'
PUTI(B)'
PRINT DIGITS(3),2'
PUTI(C)'

COUNT := 0'
FOR COUNT := COUNT + 3 WHILE COUNT LESS 500 DO
BEGIN
    PRINT DIGITS(3),COUNT'
    ADDI(A,B,C)'
    PUTI(A)'

    PRINT DIGITS(3),COUNT+1'
    ADDI(C,B,A)'
    PUTI(C)'

    PRINT DIGITS(3),COUNT+2'
    ADDI(B,A,C)'
    PUTI(B)'

END'
END'

33 minutes to compute and print first 500 numbers
7 minutes to compute but not print first 500 numbers.

500 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

PeterO