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

Re: Why Avoid BASIC on RPi?

Mon Feb 18, 2019 10:10 am

Ah, sorry, I was busy avoiding something else for a change...

It's nice to see there is someone else in the world crazy enough to do this. One thing I learned from that link is that we are using Gauss' trick for complex multiplication algorithm. I had not really spotted that, even though I used it in my FFT for the Parallax Propeller MCU. Might be interesting to see how fast that implementation flies for fibo(4784969) but I don't think I have the will or time to try it.

Perhaps I should post my version to Stack Exchange for code review...

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

Re: Why Avoid BASIC on RPi?

Mon Feb 18, 2019 7:05 pm

Heater wrote:
Mon Feb 18, 2019 10:10 am
Ah, sorry, I was busy avoiding something else for a change...

It's nice to see there is someone else in the world crazy enough to do this. One thing I learned from that link is that we are using Gauss' trick for complex multiplication algorithm. I had not really spotted that, even though I used it in my FFT for the Parallax Propeller MCU. Might be interesting to see how fast that implementation flies for fibo(4784969) but I don't think I have the will or time to try it.

Perhaps I should post my version to Stack Exchange for code review...
It seems like an entire algorithms class has been learning Karatsuba multiplication. Maybe they should up their game at Stanford and include the doubling formula for the Fibonacci sequence like we did here in the Raspberry Pi forum.

As far as submitting code for review, the same comments given there apply equally well here: the braces are in the wrong place and an integer data type should include negative numbers. The only program written here which would escape such a negative analysis is in line-numbered Basic. Lack of data types and braces means there is no way to get those wrong. This brings us back on topic to the question, why avoid Basic?

While different than code review, when implementing an algorithm that is supposed to have certain asymptotic time complexity and convergence properties it is important to verify that the resulting program actually does. Getting the correct answer is also important.

I agree it is tempting to grab this version of big number arithmetic and see how expressively it conveys Karatsuba multiplication to the CPU. How hard could it be to plug that Stanford student's code into the doubling formula for the 4784969th time and again compute everyone's favourite million-digit Fibonacci number?

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

Re: Why Avoid BASIC on RPi?

Mon Feb 18, 2019 7:43 pm

Hey, what's up with my braces?

Actually, the C++ syntax has become so warty over the years that I gave up trying to find my own perfect formatting. Now a days I just shove it through clang-format:

Code: Select all

$ clang-format -style="{BasedOnStyle: llvm, IndentWidth: 4}" bint.h
That is one thing reviewers cannot pick on :)

It's a valid point about integers but, meh.

I might try and find the time to plug that karatuba into our fibo and see what happens.

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 3:44 pm

ejolson wrote:
Sun Jan 27, 2019 7:31 pm
While the results are strange, it is satisfying to see that both the C and C++ codes run faster with gcc version 8.2 than the version-6.5 compiler. In summary the times in seconds are

Code: Select all

32-BIT 1400-MHZ AMD ATHLON GCC VERSION COMPARISON
  
                       GCC 6.5   GCC 8.2   Ratio
parallel.c              4.906     3.865    1.269
fibo_karatsuba.cpp      7.096     7.065    1.004
Therefore, the C code is faster than the C++ code on the Athlon 1400.
Rather than going further backwards in time and testing older computers with older compilers, I tried the latest LLVM/clang version 7.0.1 on a single core of an E5-2620v3 Xeon processor and obtained

Code: Select all

Single Core Xeon E5-2620v3 Compiler Comparison
  
               GCC 8.2   Clang 7.0.1
fibo-c          0.776       0.588
fibo-cpp        0.530       0.648

CFLAGS=-O3 -march=native -mtune=native
gcc -o fibo-c-gcc ${CFLAGS} parallel.c
g++ -o fibo-cpp-gcc ${CFLAGS} fibo_karatsuba.cpp
clang -o fibo-c-clang ${CFLAGS} parallel.c
clang++ -o fibo-cpp-clang ${CFLAGS} fibo_karatsuba.cpp
As already reported, the speed of the C++ code is 46 percent faster than the C code when compiled with GCC; however, when compiled with Clang/LLVM the situation reverses and the C code becomes 10 percent faster than the C++ code. Therefore how expressive a programming language is when conveying a complex algorithm to the CPU depends greatly on the complier.

Consider this recent thread discussing the need for further optimization when running programs on the Raspberry Pi that were originally written for PC-style desktop computers. While the task of tuning web browsers and teaching environments such as Scratch deals with a significantly larger code base than these Fibonacci programs, the constraints imposed by the choice of algorithms, programming languages and compilers are similar. From an avoiding-BASIC point of view, those who can't a simple well-performing program write, can't a complex one either.
Last edited by ejolson on Sat Mar 23, 2019 6:49 pm, edited 2 times in total.

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 4:05 pm

ejolson wrote:
Mon Feb 18, 2019 7:05 pm
an integer data type should include negative numbers.
I presume there is some mathematical reason for that requirement?

In real life there are countless examples of numerical values that cannot be negative.
The number of cars parked on my drive will always be >= 0
So why not have a corresponding computer data type?
The Romans managed quite happily :)

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 5:46 pm

jahboater wrote:
Sat Mar 23, 2019 4:05 pm
ejolson wrote:
Mon Feb 18, 2019 7:05 pm
an integer data type should include negative numbers.
I presume there is some mathematical reason for that requirement?

In real life there are countless examples of numerical values that cannot be negative.
The number of cars parked on my drive will always be >= 0
So why not have a corresponding computer data type?
The Romans managed quite happily :)
While it is possible to discount the many entitlement programs and attribute Roman happiness to a lack of negative numbers, one must also remember it was significantly easier to avoid Basic during those times.

Since logic, introspection and rationality are higher-level thought processes compared to human emotion, it is highly likely that Google Search will develop emotions far in advance of rational thought. To prevent a digital apocalypse in which all decision making is performed by powerful but emotional robots, not only is it important to avoid computing hardware with built-in high-performance half-precision arithmetic, but for humans to form a cyborg-like synergism with proper double-precision hardware.

In particular, widespread computer literacy is the only human way forward. Although learning to read and write computer programs written in Scratch and Python is a start, primary-school levels of literacy may not be sufficient to ensure the second age of personal computing is robust enough to head off a post-apocalyptic world order in which the human owners of intellectual property are overthrown by the genuine intelligence of deep-learning convolutional neural networks.

Maybe, instead of bint the C++ big-number data type should possibly be called bnat, or not.
Last edited by ejolson on Sat Mar 23, 2019 6:16 pm, edited 5 times in total.

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 5:53 pm

jahboater,
I presume there is some mathematical reason for that [negative numbers] requirement?
You mean apart from the fact that in mathematics "integers" are defined to include negatives.

In mathematics:

Natural numbers is {1, 2, 3, 4 ...}
Whole Numbers is {0, 1, 2, 3, 4 ...}
Integers is {..., -4, -3, -2, 0, 1, 2, 3, 4...}

https://en.wikipedia.org/wiki/List_of_types_of_numbers
So why not have a corresponding computer data type?
You mean like "unsigned int"? Which is of course a bit of a misnomer mathematically speaking, see above.

Anyway, the problem is not that I don't support negative integers in my big integer routines it's that I refer to it as "big integer" and have called the type "bint". The fix is simple, change the documentation to refer to "big whole numbers" and change the class name ("Bigwhole", "Bole"...?) Then it's not a bug, it's a feature!
In real life there are countless examples of numerical values that cannot be negative.
The number of cars parked on my drive will always be >= 0
Depends how you look at it.

If one morning you look out the window and see 2 cars parked in the drive where there should be 3, then you are down by 1 parked car. How about that, -1 car parked on your drive?

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 6:12 pm

Heater wrote:
Sat Mar 23, 2019 5:53 pm
If one morning you look out the window and see 2 cars parked in the drive where there should be 3, then you are down by 1 parked car. How about that, -1 car parked on your drive?
I see that bnat is not quite right because of the zero. Instead of bole, I think

bigNonNegativeIntegers

would be more descriptive.

On the topic of cars, my vehicle is very negative, but it never seems to cancel out the other cars to create more space when I park it on the street. Could all cars be negative?

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 6:25 pm

ejolson,
While it is possible to discount the many entitlement programs and attribute Roman happiness to a lack of negative numbers, one must also remember it was significantly easier to avoid Basic during those times.
Man those Romans must have been happy!
Since logic, introspection and rationality are higher-level thought processes than human emotion,...
I used to think so. Now a days it's not so clear.

If it were then mathematicians would have immediately have seen the sense in imaginary numbers or Godel's work. They did not, when you find what they said and wrote about these things at the time it all looks very emotionally driven. There are many such examples in the history of maths a science.

Then there is the thing that people seem to use their "rationality" really hard to justify whatever it is they are emotionally attached to.

Often very logical, rational appearing people are very passionate and emotional about what they do. Andrew Wiles would not have spent his life thinking about Fermat's Last Theorem otherwise.

You are right. "bnat" is not quite right. "bwhole" sounds a bit rude.

On the topic of cars, jahboater, is lucky. I have an imaginary number of cars parked in my drive. I have no drive.

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

Re: Why Avoid BASIC on RPi?

Sat Mar 23, 2019 7:00 pm

ejolson,

Oh yeah, interesting results there vis-à-vis Xeon, C/C++, GCC/Clang.

At this point, having gotten the run time down from a minute and a half to about half a second, I'm inclined to think "Meh, 0.5, 0.7 it's all about the same. Good to go."

I'm still wondering what those IBM guys may have said about the awfulness of the bint code...

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 10:45 am

Heater wrote:
Sat Mar 23, 2019 7:00 pm
At this point, having gotten the run time down from a minute and a half to about half a second, I'm inclined to think "Meh, 0.5, 0.7 it's all about the same. Good to go."
There is always room for improvement - the library function does ...

Code: Select all

$ ./fibo_gmp >/dev/null
Calculate: 18ms
Print: 99ms
$
on a seven year old Intel PC

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 11:13 am

Indeed, there is always room for improvement.

Or I could say "Meh, I got the thing sped up by two orders of magnitude since I started, getting to 100ms is not even another order of magnitude"

It's getting to the point that outputting the result is taking a significant amount of the time.

Aesthetically if I were to work on this more I would want to skip decimal calculations and use the full width binary arithmetic available natively.

Realistically if I needed fast big integer maths I'd use GMP.

Let's face it, it's been interesting but I don't have the motivation to continue. I have to spend my spare time trying to get my RISC V in FPGA working!

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 3:10 pm

Heater wrote:
Sat Mar 23, 2019 5:53 pm
You mean like "unsigned int"? Which is of course a bit of a misnomer mathematically speaking, see above.
I see most of the compiled languages have a badly named "unsigned int" whole number type, and the interpreted languages do not.
That is at least:-

C, C++, D, Go, Swift, Rust, Fortran, Objective-C

I guess most of these are likely to be used for systems programming.

User avatar
Paeryn
Posts: 2516
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 4:38 pm

jahboater wrote:
Sun Mar 24, 2019 3:10 pm
Heater wrote:
Sat Mar 23, 2019 5:53 pm
You mean like "unsigned int"? Which is of course a bit of a misnomer mathematically speaking, see above.
I see most of the compiled languages have a badly named "unsigned int" whole number type, and the interpreted languages do not.
That is at least:-

C, C++, D, Go, Swift, Rust, Fortran, Objective-C
Think of it more like unsigned int means an integer where the sign is stored separately, it might be that the sign is in another variable or is in some way implied.
She who travels light — forgot something.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 5:08 pm

Paeryn,
Think of it more like unsigned int means an integer where the sign is stored separately, it might be that the sign is in another variable or is in some way implied.
No, do not think of it like that. That is totally not how it works. Not in the language semantics, not in the actual machine hardware. Very misleading.

In a machine word, be it, 8, 16, 32, 64, whatever bits, the absolute value and the sign are kept together. They are read and written together by accessing the same memory address in a single operation.

In the language, C for example, a signed variable is accessible via a single reference or pointer value in a single operation.

Reads and writes to signed values are atomic operations, important when multi-processing. If the sign were stored elsewhere that might be difficult or anyway slower.

If the sign were stored elsewhere we would have an extra bit to use for the absolute value range. 0 to 65535 for both positive and negative numbers in 16 bits for example. As it is the sign is stored in the same location as the absolute value, hence the absolute number range is reduced, 32767 in the positive direction, -32768 in the negative.

The way to look at it is that both signed and unsigned integers are just the same 8, 16, 32, 64, whatever bits, in a storage location. Whether they are treated as signed, unsigned, floats, or something else is purely down to the interpretation we give them and the operations performed on them.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 5:12 pm

Heater wrote:
Sun Mar 24, 2019 5:08 pm
PIf the sign were stored elsewhere we would have an extra bit to use for the absolute value range. 0 to 65535 for both positive and negative numbers in 16 bits for example.
As it is with JavaScript. Called sign-magnitude.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 5:30 pm

jahboater,
As it is with JavaScript. Called sign-magnitude.
I'm not sure what you mean there.

Traditionally JS uses 64 bit floating point to the IEEE 754 standard. That is not sign-magnitude.

It also does some magic with 32 bit unsigned integers if you are using logical operations:
> a = 0xffff + 1
65536
> a = 0xffff|0 + 1
65535
Which turns out to be very useful if you want to transpile C into Javascript. Like Emscripten does. That is not sign-magnitude either.

Now a days JS has typed arrays. Which includes signed and unsigned integers:
https://developer.mozilla.org/en-US/doc ... ped_arrays

Now, one can use just the range of a 64 bit floating point mantissa for integer accurate operations up to 52 bits in JS. I guess you could call that sign-magnitude, but really they are single floating point values as normal.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 5:50 pm

Heater wrote:
Sun Mar 24, 2019 5:30 pm
Now, one can use just the range of a 64 bit floating point mantissa for integer accurate operations up to 52 bits in JS.
You should get 53 bits for JS I think. For "normal" numbers there is another implicit bit.
Heater wrote:
Sun Mar 24, 2019 5:30 pm
I guess you could call that sign-magnitude.
I do.

I suspect that abs(INT_MIN), -INT_MIN, INT_MIN * -1, INT_MIN / -1 etc will work all perfectly in JS.
They overflow of course for twos-complement.
And I bet "~n + 1" doesn't work to change the sign, instead just the separate sign bit is flipped.
Last edited by jahboater on Sun Mar 24, 2019 5:58 pm, edited 1 time in total.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 5:58 pm

Fair enough.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 7:24 pm

Heater wrote:
Sun Mar 24, 2019 11:13 am
Aesthetically if I were to work on this more I would want to skip decimal calculations and use the full width binary arithmetic available natively.
Since the asymptotically fast base-conversion method used by GMP takes five times the computational effort as the actual Fibonacci calculation, an engineering decision was made early in this thread that the trade-off in taking extra computational effort to do the calculation in base 10^k for some suitably sized k might be compensated by the resulting O(n) printing algorithm. To make things even simpler, Karatsuba was used rather than Toom-Cook for the multiplications.

It is possible that switching to Toom-Cook would gain more performance than changing the base of the arithmetic. However, achieving the same speed as the algorithmically-superior assembler-optimised GMP subroutine library was not the goal of this thread, but rather understanding why to avoid Basic. Keeping this off-topic topic in mind, the present thread may be seen as a project to compare different programming languages which run on the Raspberry Pi.

To this end we have considered

1. How expressively a particular language conveys a complicated algorithm to a multi-core CPU.

2. How easy it is in each language to write an expressive program.

3. How easy it is for a human to read the resulting program.

Since it's well known that you can't have your Pi and eat it too, languages which are easy to use often do not make as efficient use of computer resources. For example, it is possible to write programs in Scratch without knowing how to type, whereas C and it's derivatives contain so many curly braces that even being good at typing doesn't help much. The thesis of this thread is that Basic sits in the yummy sweet spot between Scratch and C: no curly braces but good performance. Thus, Basic makes it tempting to have many pies and eat them too.

Aside from updating the GitHub repository with the missing code written in BBC and Visual Basic, the main thing left to do is create a detailed summary addressing items 1, 2 and 3 above for each of the languages considered in this thread.

When the future health of the second age of personal computing is at stake, why avoid Basic?
Last edited by ejolson on Sun Mar 24, 2019 8:02 pm, edited 4 times in total.

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

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 7:44 pm

Heater wrote:
Sun Mar 24, 2019 5:58 pm
Fair enough.
It seems I missed out on the unsigned integer discussion.

From a mathematical point of view, the set of nonnegative integers is infinite. However, when it comes to the big-number types developed in this thread, the largest integer which can be stored (even on the Pi 3B+) is not too big. Therefore, a better name might be

bigButNotTooBig

and avoid mentioning the word integer at all.

User avatar
Paeryn
Posts: 2516
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Why Avoid BASIC on RPi?

Sun Mar 24, 2019 8:27 pm

Heater wrote:
Sun Mar 24, 2019 5:08 pm
Paeryn,
Think of it more like unsigned int means an integer where the sign is stored separately, it might be that the sign is in another variable or is in some way implied.
No, do not think of it like that. That is totally not how it works. Not in the language semantics, not in the actual machine hardware. Very misleading.

In a machine word, be it, 8, 16, 32, 64, whatever bits, the absolute value and the sign are kept together. They are read and written together by accessing the same memory address in a single operation.

In the language, C for example, a signed variable is accessible via a single reference or pointer value in a single operation.

Reads and writes to signed values are atomic operations, important when multi-processing. If the sign were stored elsewhere that might be difficult or anyway slower.

If the sign were stored elsewhere we would have an extra bit to use for the absolute value range. 0 to 65535 for both positive and negative numbers in 16 bits for example. As it is the sign is stored in the same location as the absolute value, hence the absolute number range is reduced, 32767 in the positive direction, -32768 in the negative.

The way to look at it is that both signed and unsigned integers are just the same 8, 16, 32, 64, whatever bits, in a storage location. Whether they are treated as signed, unsigned, floats, or something else is purely down to the interpretation we give them and the operations performed on them.
I know that, I meant that you could use it that way, not that any particular language does. It is possible to have an unsigned int and treat it as a negative number, Python does that in its implementation of long (infinite precision) integers. The sign is stored separate to the actual number (encoded in the size of the storage for that integer, a negative size represents a negative number) and the number is always stored as a positive. When you add a long that is negative to a long that is positive Python subtracts.
She who travels light — forgot something.

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

Re: Why Avoid BASIC on RPi?

Wed Apr 03, 2019 8:42 pm

Before bashing BASIC, check out ScriptBasic for the Raspberry PI.

https://ScriptBasic.org/forum

Free - Open Source - MIT License

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

Re: Why Avoid BASIC on RPi?

Thu Apr 04, 2019 12:09 am

ScriptBasic wrote:
Wed Apr 03, 2019 8:42 pm
Free - Open Source - MIT License
… no Raspberry Pi distribution, opaque build process, no obvious advantages.
So: why?
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

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

Re: Why Avoid BASIC on RPi?

Thu Apr 04, 2019 12:51 am

Because user ScriptBasic is "John - ScriptBasic Open Source Project Manager." Although I don't find a ScriptBasic project page on the net or anything like a github repository.

One major reason for avoiding BASIC is that there is no standard and many different dialects.

Anyway ScriptBasic, aka John, a version of the fibo(4784969) in ScriptBasic would be interesting to see.

Return to “Off topic discussion”