Why Avoid BASIC on RPi?

[ejolson]

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.

Strange as it seems, the programmers who work on GNU GMP are people too.

One of the things I stress when teaching is that a wrong answer is often worse than no answer. Wrong answers are particularly dangerous when produced by a computer, because people tend to believe a computer without verifying the answer--sometimes because they don't know how to verify it.

One way to verify the correctness of an answer is to independently compute it using the simplest algorithm possible. Computing the n-th number in the Fibonacci sequence directly from the definition is a possible way to verify that the more efficient and complicated algorithms are coded correctly.

While benchmark problems such as computing the eigenvalues of a particular matrix, fluid flow over a backward facing step or finding the 4784969th Fibonacci number can be used to compare algorithms, it is not unreasonable to further specify the algorithm and then compare computers or compilers. For example, the Linpack benchmark not only solves systems of linear equations, but explicitly specifies that those equations should be solved using Gaussian elimination with partial pivoting--use of the Strassen algorithm is not allowed.

In the present case, it appears the expressiveness of BBC BASIC as demonstrated by the ability to efficiently code big-number arithmetic and then compute the Fibonacci sequence using the definition

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

is being compared to the expressiveness of other programming languages in doing the same. It should also be noted that if the stated problem is to compute all numbers in the Fibonacci sequence up to and including the 4784969th, then the simple algorithm is likely optimal.

[PeterO]

Time to own up !

I cannot take credit for the Algol-60 code that performs the large number additions. I took it from a much larger programme that performs a simulation of a machine that searches for solutions to equations using prime numbers. With the sample input that came with the programme it takes 2½ days to run ! I forget the name of the mathematician that invented it.

I can take credit for the code that prints the numbers out There is some non-standard Algol in there that uses the features of the 803 compiler to closely control the layout of the printed output. Bearing in mind that a lot of the scientific uses of computers in the 1960s would have been to produce tabular outputs of calculation results, it's not surprising that Elliotts included extra functions (like "LEADZERO" and "DIGITS" ) that gave better control over printed layout.

PeterO

[PeterO]

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.

Actually it's without leading zero suppression for all but the first non-zero element in the array.

PeterO

[ejolson]

Time to own up !

I cannot take credit for the Algol-60 code that performs the large number additions. I took it from a much larger programme that performs a simulation of a machine that searches for solutions to equations using prime numbers. With the sample input that came with the programme it takes 2½ days to run ! I forget the name of the mathematician that invented it.

I can take credit for the code that prints the numbers out There is some non-standard Algol in there that uses the features of the 803 compiler to closely control the layout of the printed output. Bearing in mind that a lot of the scientific uses of computers in the 1960s would have been to produce tabular outputs of calculation results, it's not surprising that Elliotts included extra functions (like "LEADZERO" and "DIGITS" ) that gave better control over printed layout.

PeterO

Could the name be Robert Morris? The same idea for arbitrary precision arithmetic was used in the Unix calculator bc and its predecessor dc which apparently predates the C programming language (but perhaps not Algol).

[Heater]

The same idea for "big integer" arithmetic was used by me in the late 70's when wanting to work with numbers bigger than our 8 bit micro-processors could deal with natively. That's without a high level language or even an assembler. We had to assemble on paper and get the program into the machine in hex.

Which makes me think the general idea is obvious enough it dates back to the dawn of computers.

Multiply was a challenge!

[hippy]

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!

Using base 1000, dividing a big number into a sequence of 000-999 numbers, is very convenient for 16-bit systems and especially for time (s,ms,us,ns), voltage (V,mV,uV,nV), and other SI unit values where one can easily scale the value just by adding "000" or dropping a set of digits and judicious placing of the decimal point.

Eg 123.456789V =

000 . 000 123 456 789 MV
000 . 123 456 789 kV
123 . 456 789 V
123 456 . 789 mV
123 456 789 . 000 uV
123 456 789 000 . 000 nV

One would of course usually tidy that up by removing spaces and extraneous leading and trailing zeroes, limiting the number of digits after the decimal point

[jahboater]

Could the name be Robert Morris? The same idea for arbitrary precision arithmetic was used in the Unix calculator bc and its predecessor dc which apparently predates the C programming language (but perhaps not Algol).

May have been rewritten at some point, but bc (which seems to include dc) is written in C (as is "calc" - also based on dc).
With a bit of yacc!
https://ftp.gnu.org/gnu/bc/

[Heater]

ejolson,

Strange as it seems, the programmers who work on GNU GMP are people too.

I'm not sure what you mean by that. I did say "people" in my comment, that you quoted.

Do you mean "people make mistakes"?

Yes indeed, especially me if it's me reinventing a complicated wheel. Which is why I said what I said, as you have quoted in your comment.

One of the things I stress when teaching is that a wrong answer is often worse than no answer.

Yes indeed. And wise to emphasize that.

One way to verify the correctness of an answer is to independently compute it using the simplest algorithm possible. Computing the n-th number in the Fibonacci sequence directly from the definition is a possible way to verify that the more efficient and complicated algorithms are coded correctly.

Yes indeed.

I started out by checking the correctness of my fastFibo against small numbers I can compute in my head. Then I checked it against huge numbers that one can get from many online Fibonacci calculators.

Now I have fiboSlow, see post: viewtopic.php?f=62&t=227343&start=125#p1395492 which computes Fibonacci the simple and slow way.

Code: Select all

$ ./fiboSlow > fiboSlow.dat
$ node fiboFast.js > fiboFast.dat
$ diff fiboFast.dat fiboSlow.dat
$

Yep, it checks out.

That is verification enough for me. Should you happen to ever want to use my code please do verify it some more.

Of course this technique is not always possible. For example: One could write a Fast Fourier Transform of a billion sample points. There is no way one could do the naive, simple, Fourier Transform to check the results against, it would take forever.

Or as another example, when the world record holder for computing the digits of PI wants to verify the result, how does he check those 10 billion digits? Certainly not against calculating 10 billion digits some simple, slow way.

I do agree that calculations used for benchmarks should use like for like algorithms. Which is exactly what I specify in my fft_bench for comparing micro-controllers and languages: "When reimplementing this benchmark in other languages please honor the intention of this benchmark by following the algorithm as closely as possible." See here: https://github.com/ZiCog/fftbench

In the present case, it appears the expressiveness of BBC BASIC as demonstrated by the ability to efficiently code big-number arithmetic and then compute the Fibonacci sequence using the definition...is being compared to the expressiveness of other programming languages in doing the same.

Yes. Well, it would be. Problem is nobody has managed to do the same in BBC BASIC yet so we have nothing to compare, neither in expressiveness or performance or size or whatever.

It should also be noted that if the stated problem is to compute all numbers in the Fibonacci sequence up to and including the 4784969th, then the simple algorithm is likely optimal.

Of course. Sometimes you just have to do the work. That was not the challenge though.

[ejolson]

Could the name be Robert Morris? The same idea for arbitrary precision arithmetic was used in the Unix calculator bc and its predecessor dc which apparently predates the C programming language (but perhaps not Algol).

May have been rewritten at some point, but bc (which seems to include dc) is written in C (as is "calc" - also based on dc).
With a bit of yacc!
https://ftp.gnu.org/gnu/bc/

As far as I know, all GNU programs that implement Unix functionality have been rewritten from scratch and include no original code from Bell Labs, AT&T or General Electric. According to Wikipedia, dc was originally written in B. I don't know where the source is, but maybe it could be found in one of the pre-R7 versions of historic Unix.

[Heater]

PeterO,

There is a bug in your ALGOL60 Fibonnaci program.

In the ADDI procedure if B(j) and J(J) have the values 99,999,999,999 and 1, in any order, and CARRY is zero then the result of SUM := B(J) + C(J) + CARRY will be 100,000,000,000.

As we are dealing with 11 digit numbers here, only 11 digits get printed, that effectively means the SUM has rolled round to zero and a carry should be propagated.

But the test for carry, IF SUM GR LIM THEN, will not detect the carry situation because LIM is 100,000,000,000.

In short, adding 1 to 99,999,999,999 produces zero instead of 100,000,000,000.

The fix for this is to change LIM to 99,999,999,999 or change the GR to GE. I prefer the former.

As it happens this situation never occurs during the calculation if Fibonacci numbers up to 500 so your program works correctly.

Amazingly I tested this in my C translation and found the error did not occur until fibo(1528930).

BUT it makes me think...

You said "...I took it from a much larger programme that performs a simulation of a machine that searches for solutions to equations using prime numbers. With the sample input that came with the programme it takes 2½ days to run ! I forget the name of the mathematician that invented it."

Does that mean I have found a bug dating back to 1960 and that the results of that mathematicians equation solver are full of errors?

That would be amazing. Especially if we could fix it and demonstrate any errors in the old results. A fix to one of the oldest know bugs in history!

Or, did you introduce this bug when borrowing the algorithm?

[PeterO]

OOoo.... Let me check....

You are correct, and I made the suggested change and running it on the emulator I also can confirm it makes no difference to the first 500 fib numbers. I had checked that the 500th one was correct. If the bug was "tickled" I think it would "self correct" since the carry would propagate in the next addition operation ?

It also makes no difference to the answer produced by the original programme that I borrowed the code from ! So it's not surprising it's gone unnoticed.

There is a comment at the start of the original programme that contains the date "27-MAR-2003" so the bug is not quite as old as you suggest !

There was another subtle bug in that code which was caused by a missing statement separator .....

Code: Select all

      COMMENT PROGRAM START'
      PUNCH(3)'        COMMENT SET ALL OUTPUT TO ONLINE T/P
      FOR J := 1 STEP 1 UNTIL N DO
      BEGIN
         ZERO(J) := 0
      END'

There should be an apostrophe at the end of the comment line. Without it all of the code up to the "END'" becomes part of the comment. This would cause the programme to fail since the "ZERO" array was not cleared. However if the core store had been cleared before the programme was compiled the locations for the array were already zero and the programme would run as expected....

PeterO

[Heater]

PeterO,

You are right. The bug is triggered at fibo(1528930) which has a wrong result but fibo(1528931) it's correct again.

What is the probability of a wrong summation? I guess it's when any pair adds to 100,000,000,000.
1 + 99,999,999,999
2 + 99,999,999,998
...
99,999,999,998 + 2
99,999,999,999 + 1

So 1 in 99,999,999,999.

Of course there 10 pairs in each number so that's 1 in 9,999,999,999.

And that assuming all the number we are working with use all the digits, so somewhat less. But no wonder the bug was not spotted before.n

What!? Someone was writing new ALGOL 60 programs in 2003?

Was that a die hard ALGOL 60 or Eliot 803 enthusiast?

Or is that data some kind of revision date of code that was much older than that?

Enquiring minds want to know!

[Heater]

PeterO,

Speaking of ALGOL 60 enthusiasts I found this ALGOL 60 compiler a few days ago: https://github.com/JvanKatwijk/algol-60-compiler Which was created in 2003. Well, actually it translates Algol 60 to C but that's close enough to a compiler for me.

It wont' compile your FIBONACCI though. But I did hack your source around enough to get it to compile:

Removed the first "FIBONACCI NUMBERS' line.
Changed the whole file to lower case.
Changed all single quotes to semi-colons.
Changed array indexing to []
Removed anything to do with PRINT, LEADZERO, etc.

After all that it compiled without error but segfaults when I run the compiled C that it generates.

At that point a gave up.

Should we file a bug report: "Does not compile Eliot 803 ALGOL 60" ?

[PeterO]

PeterO,

It wont' compile your FIBONACCI though. But I did hack your source around enough to get it to compile:

There were many dialects of Algol-60. The language specification itself recognises three types of dialect:
The Reference Language.
Publication Languages
Hardware Representations.

The 803 compiler that I have uses 5 hole paper tape and thus has a quite limited character set :

Code: Select all

12*4$=78',+:-.%0()3?56/@9£
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Plus Carriage Return, Line Feed, Space, Figure Shift and Letter Shift. Consequently the 803's Hardware Representation has quite a lot of oddities in it.
See http://www.billp.org/ccs/A104/page05.html

The Algol 60 specification did not contain ANY input or output facillities. These were left up to the individual compiler writters so variations are to be expected in that area. As I said earlier, 803 Algol did include features to get tabular output to look exactly how you wanted it. See http://www.billp.org/ccs/A104/page16.html onwards for the details,

The programme written in 2003 had been a test for the Elliot 903 Algol compiler running on a 903 simulator (which was a totally different compiler to the 803 version.) It was "back ported" to the 803 compiler in 2003.

PeterO

[ejolson]

ejolson,

Strange as it seems, the programmers who work on GNU GMP are people too.

I'm not sure what you mean by that. I did say "people" in my comment, that you quoted.

Do you mean "people make mistakes"?

Yes. From what you just discovered with the 1528930th Fibonacci number, programmers who code in Algol are also people too.

I think there are many examples of frequently used code that has mistakes--either because it always did and nobody noticed or because a new programmer improved it without understanding exactly how it worked before. In a way this is related to this regrettably locked thread on why nothing ever works.

[Heater]

ejolson,

From what you just discovered with the 1528930th Fibonacci number, programmers who code in Algol are also people too.

Noooo... Programmers working in ALGOL at the time were Gods. Doing things that us mere mortals could not imagine.

Joking aside, I'm glad you chimed in here because the first thought that crossed my mind when I spotted that bug whilst trying to understand what the old ALGOL does was: "Does this discovery support ejolson's claims about code reuse and libraries or mine?"

On the one hand...

It clearly demonstrates that cutting and pasting code from some unknown origin, into ones project can lead to problems. Especially if it was only ever intended for use in one program one time, there is no evidence it was ever reviewed or tested extensively, has never been widly used and so on.

Same can be said for random libraries, modules, plugins as we see in the worlds of Python, node.js, wordpress, etc now adays.

On the other hand...

It clearly demonstrates that writing your own code into ones project can lead to problems. After all that is exactly the case here. The original author wrote a bug that he never noticed (Unless it was introduced in the "backport from Eliot 903 to 803", yet to be determined)

On the third hand...

This is a somewhat subtle "off by one" bug. I suspect that a hundred software engineers could review that code and not spot it. Also it's a bug that only shows up one in 10 billion cases, it could slide under a lot of testing.

We see this kind of subtle bug in well known and well used libray code. Lying dormant for years until some hacker exploits it. For sure it exists in code one writes oneself.

I only spotted it because I worked for years testing avionic software where one develops the habit to check for edge cases.

Bottom line for me is:

1) All software has bugs.

2) If I write it myself it will have more bugs than some tried and tested library.

3) It's impossible to create any interesting software today without leveraging the work of others. Nobody has the time, skill or money to create everything from the ground up.

4) It's better if we all work together on perfecting what we have rather than reinventing it ourselves, over and over.

5) This case demonstrates that having open source code and more than one user gets bugs fixed!

[Heater]

PeterO,

Yeah, I was aware of the different representations of ALGOL and the lack of a standardized IO. There were so many different machine architectures to support back then.

ALGOL 60 in lower case seems very wrong to me. Do I have to write my own "Heater ALGOL 60"? It would have all keywords in uppercase whilst supporting unicode characters for anything user defined

I guess that is why ALGOL died off so quickly when C came along. C managed to run unchanged on many varied architectures. It had a standard IO library to aid portability. It came with Unix attached!

I thought I was cool in 1976 teaching myself ALGOL as a first year under grad and creating some funky graphics on the pen plotter attached to that 2960. By the time I graduated all the kool kids were using C and Unix.

The programme written in 2003 had been a test for the Elliot 903 Algol compiler running on a 903 simulator (which was a totally different compiler to the 803 version.) It was "back ported" to the 803 compiler in 2003.

The plot thickens...

Are you saying this code was written for the Eliot 903 and the back ported to the 803?

From computinghistory.org.uk I learn the 903 was an 18 bit processor. As far as I gather the 803 was 39 bits. That means the big integer maths was no doubt done a bit differently. At least with different sized arrays and values of LIM.

If that code was back ported to the 803 in 2003 then the original 903 code could still date back to 1965 or so when the 903 was launched.

Any chance of tracking that original 903 code down?

Any chance of checking if that original code has the same bug?

Software archaeologists want to know!

[PeterO]

AFAIK 903 version was not written in the 1960s. I think it was written by the guy that wrote the 903 emulator in ~2000.
There is a lot of 903 software on the CCS site at http://www.computerconservationsociety. ... /index.htm

PeterO

[davidcoton]

Do I have to write my own "Heater ALGOL 60"? It would have all keywords in uppercase whilst supporting unicode characters for anything user defined

Surely "HEATER ALGOL 60"

[DavidS]

Algol had its draw backs. Though not that bad compred to some languages, especially in the 60's, 70's and 80's.

Does anyone really remember C before the ANSI standard? While the language was set out in the first edition of The C Programming Language, there were already divergent versions of the then 6 year old language, and the book was not exactly definitive (though quite good).

If you were using one compiler you may have the ability to use different names for members of structures, while another version did not. One version may not accept case sencitive identifiers. Then there were the differences in the implementations of the libraries, as well as most of them having commonly used incompatible extensions. Some had means to provide multiple entry points to functions, there were even some that did not have the goto keyword.

Ok C was always better than the example of Algol 60, though there were many languages, and few standards. There is reason that many languages diverged greatly. If Algol had not diverged from its base we likely would have never seen BCPL, B, C, Pascal, SmallTalk, or any of the modern langauges that evolved from these.

[ejolson]

Ok C was always better than the example of Algol 60, though there were many languages, and few standards.

It is easy to turn C into Algol, just include this header file which contains the preprocessing macros

Code: Select all

/*
 *	UNIX shell
 *
 *	S. R. Bourne
 *	Bell Telephone Laboratories
 *
 */

#define LOCAL	static
#define PROC	extern
#define TYPE	typedef
#define STRUCT	TYPE struct
#define UNION	TYPE union
#define REG	register

#define IF	if(
#define THEN	){
#define ELSE	} else {
#define ELIF	} else if (
#define FI	;}

#define BEGIN	{
#define END	}
#define SWITCH	switch(
#define IN	){
#define ENDSW	}
#define FOR	for(
#define WHILE	while(
#define DO	){
#define OD	;}
#define REP	do{
#define PER	}while(
#define DONE	);
#define LOOP	for(;;){
#define POOL	}


#define SKIP	;
#define DIV	/
#define REM	%
#define NEQ	^
#define ANDF	&&
#define ORF	||

#define TRUE	(-1)
#define FALSE	0
#define LOBYTE	0377
#define STRIP	0177
#define QUOTE	0200

#define EOF	0
#define NL	'\n'
#define SP	' '
#define LQ	'`'
#define RQ	'\''
#define MINUS	'-'
#define COLON	':'

#define MAX(a,b)	((a)>(b)?(a):(b))

If you want to see how the resulting Algolification of C looks, examine the rest of the source here for the Bourne shell. I wonder if it is possible to turn C into BASIC with a different set of macros.

Any progress fixing the big number addition routines for BBC BASIC?

[Heater]

DavidS,

Algol had its draw backs. Though not that bad compred to some languages, especially in the 60's, 70's and 80's.

You make it sound like there were tons of languages back in the day and ALGOL was middle of the road.

As far as I can make out their were very few high level languages back then, famously FORTRAN, COBOL, and Lisp. A bit later we get BASIC and Simula.

To my mind that put ALGOL top of the charts. It certainly provided huge inspiration for pretty much every language in use today.

See for example a programming language "family tree" like this one:
https://camo.githubusercontent.com/8b66 ... 6d2e737667

Or even better (and very big) this one:
http://hopl.info/images/genealogies/tester-country.pdf

Certainly ALGOL had serious drawback. Significantly, as PeterO points out, the lack of an I/O specification and variances in representation as dicteated by different machines. Which made ALGOL programs a lot less portable than a high level language should enable. It was though the "C" of it's time, everybody had one.

Does anyone really remember C before the ANSI standard?

Oh yes. I learned C on the job using Micro Soft C on an early PC. Sometimes I could swear that you could present the compiler with any random string of text and it would compile it without error. Of course the resulting executable was not any kind of program that would run let alone do anything useful.

There was only one C. It was K&R and it came with Unix. Of course soon many others created "C" compilers which had all kind of variances and limitations from C. Hence the need for the ANSI standard.

My take on all this is that COBOL was built for book keepers, FORTRAN for scientists to crunch their numbers, Lisp was just, err, weird. ALGOL was very much an academic exercise in language design and specification forgetting important practical issues.

The guys who made C were very down to Earth and had a practical goal, to get stuff working. Hence creating the C language specifically to build Unix (rewritten from assembler) so that it could spread and multiply, which it did very well.

All inspired by ALGOL

[jahboater]

Long ago I thought of Fortran as the 'C' of its day.
It was very widely available and heavily optimized by manufacturers because benchmarks then were typically written in Fortran.
I remember using IBM's VS Fortran compiler, I never managed to write assembler that could beat it. An early benchmark that
did a lot of calculations but did not print a result, surprised the author because VS Fortran deleted the entire program. Of course
C compilers do that routinely, but in those days it was a clever optimization.
All sorts of stuff was written in Fortran simply because it was so widely available.

Does anyone really remember C before the ANSI standard?

Yes of course.
Importantly when ANSI C arrived, compilers happily supported both - even in the same program. The transition was gradual and painless.
There was none of this Python2/Python3 nonsense, where are separate interpreter is needed.

[jahboater]

Oh yes. I learned C on the job using Micro Soft C on an early PC. Sometimes I could swear that you could present the compiler with any random string of text and it would compile it without error. Of course the resulting executable was not any kind of program that would run let alone do anything useful.

Remember the (wise) UNIX philosophy of "each program should do one thing only and do it well"?
The point then was:-
The C compiler produced the best code it could.
The "lint" program worried about the entirely different task of static checking.

Of course things have moved on and the deep analysis that a C compiler does duplicates the effort in the static checker.
So lint fell out of use.

[Heater]

Ah yes lint.

Did Micro Soft C on the IBM PC come with a lint? If so I'm dumb enough not to have found it at the time

By the time I became aware of lint it was hardly of use anymore. Besides modern editors and IDEs do syntax checking as you type, put red squiggles under stuff they don't like and so on.

Advanced lining, static analysis, is doing better than ever: “Make Friends with the Clang Static Analysis Tools" https://www.youtube.com/watch?v=AQF6hjLKsnM