Liberation through Computer Literacy

[Heater]

I managed to build Elk from source on my Pi 64 Debian.

I got the source from the author: http://sam.zoy.org/elk/
: elk-3.99.8.tar.bz2

Configure did not detect the architecture so I updated ./auto/config.guess and ./auto/config.sub from the savannah git repo as the error message directed.

Then configure, make, make install all worked.

However, it still crashes with your code and input data, tenaciously typed in by hand...

Code: Select all

$ elk -l fibo.elk.sc
? ...
...
...
? 195
25299086886458645685589389182743678652930
? 2149831

Panic: Visit: object not in prev space at 0x7fb11894d0 ('pair') 705 707 (dumping core).
Aborted
pi@pi64-aalto:~/fibo_4784969/scheme$

[John_Spikowski]

TinyScheme seems to run the Fibo code that has been posted by Heater and ejolson. It doesn't have BIGINT or some of the advanced features other Scheme embeddables offer but good enough for my limited needs and learning process. I have ScriptBasic and C to fill any holes. TinyScheme is easily extended with C. Adding GMP shouldn't be all that difficult.

Until this fibo challenge appeared, how many times in your past have you used BIGINT for your projects? Me, never.

[ejolson]

However, it still crashes with your code and input data, tenaciously typed in by hand...

It seems Elk crashes are not that uncommon. I did a web search and found



and even an example where an elk leaped into the air and crashed into a research helicopter.

The first practical experience I had with big-number arithmetic was the public-key encryption system used to bless Netrek clients and keep the robots out of the tournaments. After the Fibonacci challenge is over, we may need a similar cryptographic integrity check for a networked version of the classic Star Trader game.

[Heater]

ScriptBasic,

Until this fibo challenge appeared, how many times in your past have you used BIGINT for your projects? Me, never.

What? You never had the urge to zoom a long way into a Mandlebrot set or other fractal? We did back in mid 1980's. Mind you, our idea of BIG back then was a pretty weeny, what with still running 16 bit machines.

If you are insinuating that this whole exercise is a pointless waste of time I think we are far ahead of you there. Being pointless does not been it's not a fun little project. Think of it like wasting time with Soduku or some such trivial pursuit. It finds bugs in implementations. It sorts the men from the boys. Sounds like sour grapes to me

On a more serious and practical note, let me turn the question around. How many times have you found bugs in systems because the integer number range was too small and overflow occurred? Me, quite many. One of the most notable being in OpenSSL.

[Heater]

Elk crashes are tragically common here in Finland too:

[ejolson]

Elk crashes are tragically common here in Finland too

Ouch. That makes the big-number Fibonacci crashes involving Elk seem quite inconsequential.

Chibi Scheme is now running through the fibench timing program. In a few hours (hopefully not days) the results will be in.

[John_Spikowski]

Like waiting for the report card to arrive as a kid.

[ejolson]

In a few hours (hopefully not days) the results will be in.

At long last after crashing through endless amounts of high-desert sage the legendary Bashkir Curly Horse was rounded up and named Chibi. That unmistakably curly mane, possibly caused by collecting garbage, gloriously garnishes the roundup of Scheme interpreters found in the wild.



All computations were performed using the Raspberry Pi Zero. Note that the black X marks the spot of the wrong answer for fibo(61403) obtained using Racket Scheme. This was a repeatable error apparently related to a software bug. Elk Scheme crashed when computing certain sequences of Fibonacci numbers again in a fully deterministic and repeatable way. The timings above reflect three identical runs in which the values of n used in fibo(n) were ordered so there were no crashes.

[ejolson]

Imagine walking into a HiFi store in the 70's and comparing the expensive equipment using a cardboard record cut from the back of a cereal box. In a completely different way we shall use a real computer that was found attached to a magazine cover to compare how state-of-the-art programming languages can be used to implement complex algorithms.

The search for Chibi the wild curly, until desert meets the hills, found many rattlesnakes near the river's silvery rills. I looked some more where the wind blows free: No pythons in that land of pine; in that lovely spot no pythons out where the sun always shines.

Apologies to Bertha Rafetto.

I've been thinking a roundup may not be such a good analogy when comparing Python interpreters and that calling the next set of timing metrics a comedy show would be more appropriate. Actually, the same might hold true for Scheme.

[timrowledge]

I certainly learned some interesting things from fiddling with The Fibonacci Challenge(™) for Smalltalk on my Pi.
The obvious new thing was that whole field of amazing number handling algorithms I'd never had reason to look at before. I just love the thought processes behind the "oh, let's stick this in a matrix, then simply taking that to the power of n gives us the nth Fibonacci number". And the Karatsuba/Toom-Cook algorithms... fabulous stuff. So, thank you for leading me down that path.

Specifically for Smalltalk it prompted putting those algorithms into the system for the next release and a massive speed up in handling large numbers. Now we have to look and see if there are any equivalently better algorithms we've been ignoring for simplifying Fractions (least common denominator etc) because although it can be really useful to have that sort of exactness, they can be a bit slow to use.

It was also interesting to (re)try the commandline stuff in Squeak Smalltalk; I haven't had any reason to play with it in years and it was also fascinating to see how deeply attached some people are to using such a thing. I'd forgotten that we could handle commandline input that was a URL or zipped files, for example. What still isn't done right is being able to not have the GUI open up before considering the commandline parameters; this is mainly because the initial usage for that was to specify an EToys project file for the SUGAR/OLPC project, where you certainly want the GUI open.

As a slightly weird aside, I ended up playing briefly with the way unices can have a

Code: Select all

#! /usr/bin/bash

type line at the beginning of files intended to be used like scripts. It turns out that one can use

Code: Select all

 #! /usr/bin/squeak

as well, though it did require a tiny tweak to Squeak to ignore the !# line in the file. That made it possible to have the fibonacci script file be

Code: Select all

#! /usr/bin/squeak
some smalltalk code to load for a fibonacci method
some smalltalk code to run that method and write results out

Pretty cool.

But - there is something even cooler that is perhaps of much wider interest, and that is the way that unix handles these scripting header lines. I'd always assumed it was fxed as

Code: Select all

 !# /path/to/some/executable

but it actually isn't. It's just a part of something that appears to be called the binfmt handler. You can actually register a rule and an interpreter of the files that match that rule, and one of the Squeak mailing denizens demonstrated a rule that allowed for a .st file to start with "!" (" being the Smalltalk comment delimiter) and be otherwise unchanged. Now that is a seriously cool thing to be able to do. It's all centred around /proc/sys/fs/binfmt_misc/register and there is a document at https://www.kernel.org/doc/Documentatio ... t-misc.rst that describes a bit about it.

[John_Spikowski]

Can someone post the link to the BASIC fibo examples in the repo?

[Heater]

The BASIC examples for The Challenge are here:

https://github.com/ZiCog/fibo_4784969/tree/master/BASIC

[Heater]

ejolson,

I have been peeking at your results graph there for a day now in amazement.

It's amazing what has resulted from my casual throwing down of the Big Fibo Challenge.

It's amazing that Chibi is bucking all over the place for small numbers.

It's amazing that two well known and respected Scheme implementations can't get the job done correctly.

It's amazing that Guile seems to be off on a asymptotic slope shallower than all the others.

Your horse roundup analogy is fitting. If Chibi is the Bashkir I can paraphrase Wikipedia:

Chibi is known for it's calm, intelligent and friendly personality. It show an easily trainable temperament. Chibi is also known for having a tough constitution and great stamina.... Chibi is typically not flighty. It tends to do more reasoning than most Schemes. Chibi is very reliable and has a great work ethic

Perhaps if naming your next results survey after a comedy show it should be "The Fast Show": https://www.youtube.com/watch?v=pv9BKilYk9Q

[Heater]

timrowledge,

I just love the thought processes behind the "oh, let's stick this in a matrix, then simply taking that to the power of n gives us the nth Fibonacci number".

I love that as well.

Someone posted the Julia code to do that here somewhere. I can't find it now but this matrix fibo in Julia:

Code: Select all

function fibo(n)
   Fn = BigInt[1 1; 1 0] ^ n
   Fn[2, 1]
end

Is for sure the winner of the million digit Fibonacci challenge when it comes to algorithmic expressiveness and clarity.

It's about half the speed of the existing doubling formula version in Julia we have already. But that is still damn fast.

It's great to see that the Fibo challenge has inspired improvements to Squeak. A simple to use command line interface with no GUI baggage would be great.

I haven't had any reason to play with it in years and it was also fascinating to see how deeply attached some people are to using such a thing

I don't know about "attached". You make it sound like an emotional thing.

It's a practical matter. Most of the code I have ever written does not have someone watching and minding over it when it runs. Be that in embedded systems, background daemons, server side processes etc.

Emotionally, yes, I often find running things from the command line is a lot easier and quicker than dragging windows around and finding things to click on. GUI's frustrate me.

[jahboater]

It's great to see that the Fibo challenge has inspired improvements to Squeak. A simple to use command line interface with no GUI baggage would be great.

I haven't had any reason to play with it in years and it was also fascinating to see how deeply attached some people are to using such a thing

I don't know about "attached". You make it sound like an emotional thing.

It's a practical matter. Most of the code I have ever written does not have someone watching and minding over it when it runs. Be that in embedded systems, background daemons, server side processes etc.

Emotionally, yes, I often find running things from the command line is a lot easier and quicker than dragging windows around and finding things to click on. GUI's frustrate me.

Yes.
My Pi's all run headless. I access them through ssh. No GUI.

[ejolson]

Perhaps if naming your next results survey after a comedy show it should be "The Fast Show"

The Fast Show does sound like a funny name, especially for Python interpreters. I now have Python2, Python3, PyPy and Jython on the stage. IronPython for mono also looks amusing, but she's not in the Raspbian repository and since this is not a roundup she will likely not be part of the comedy, though a cameo appearance as a guest star would be welcome.

Of the Python interpreters starring in the show, only Jython appears to have a complicated personality: He takes more than a minute to get ready and insists on having a personalized ctrl-d after the entry of each n before performing his part. Jython echos the input n even when the pty device is in raw mode and further seems allergic to cats. Therefore a modified version of fibench was created and a special cat-free chauffeur found to fetch Jython to the show and back.

[ejolson]

With all the comedic drama of an over-dubbed laugh track, the plot of our show twists and turns so that

• For n between 1 and 100 Python3 is fastest.
• For n between 100 and 200 Python2 is faster.
• For n between 200 and 1000000 PyPy is faster.
• For n between 1000000 and 4784969 Jython is faster.

Although IronPython has yet to make an appearance, the present montage of Python interpreters looks like



Note that all computations were performed using a Raspberry Pi Zero computer. All versions of Python were compatible with and ran the following program:

Code: Select all

def fibo(n):
    if n<3:
        return 1
    k = (n + 1) // 2
    fk = fibo(k)
    fk1 = fibo(k - 1)
    if n & 1:
        result = fk ** 2 + fk1 ** 2
    else:
        result = (2 * fk1 + fk) * fk
    return result

while 1:
    n = int(input('? '))
    if n == 0:
        break
    print(fibo(n))

As with the Scheme roundup, the above timing metrics reflect more the performance of the built-in big-number arithmetic, rather than how efficiently the programming language itself could be used to express an algorithm similar in complexity to Karatsuba multiplication. A story line that includes Karatsuba or any other suitably complicated algorithm would likely result in different conclusions as well as being more comparable to the Basic roundup.

Recall the four requirements of a good first programming language.

1. It should be very easy to learn. This will enable people of every race, creed, gender and political persuasion the opportunity to obtain useful information from the computer without an undue investment in time.

2. It should be possible to quickly interpret or compile programs written in the language. This is a necessity when a Raspberry Pi is used as a software development environment for teaching and learning.

3. It should be a stepping-stone for students who may later wish to learn one of the standard languages, such as FORTRAN or C.

4. It should be a general purpose language; that is, every kind of machine computation should be programmable in it.

It is difficult to predict whether any of the interpreters actually satisfy all these from the current comedy of results. In particular, it is not clear if any of the Python interpreters could perform every kind of machine computation indicated in item 4 as efficiently as needed to satisfy the quickness requirement of item 2.

[bensimmo]

How do they compare to just using the built in fibo?
There is one isn't there, this is python after all?

[ejolson]

How do they compare to just using the built in fibo?

The GMP Fibonacci function has been included in all of the graphs. If there is a different fibo function built into Python, that would be interesting. If you provide a simple code example, I could run it on this super-cheap cluster of Pi Zero computers over the weekend.

In my opinion, the expressivity of the different Pythons might better be compared by coding something more complicated such as the Karatsuba algorithm or an answer to one of the competition questions on Sphere Online Judge.

[bensimmo]

I was just looking and it seems math, numpy, scipy don't have one (even if something uses it in scipy).
I guess people just don't use it.
There are however a million different ways to do it, if they can do 1million digits or not is another matter.
Probably something for stackexchange.

[John_Spikowski]

I would like to see a Fibonacci million digit in Python but not using its BIGINT support. Is that possible? Is there a version of Python that doesn't have BIGINT support?

I would like to see a classic.bas but done in Python.

[Heater]

Ha! That made me chuckle.

The fact that Python/JS etc can handle big integers out of the box is the whole reason I set the million digit fibo challenge in the first place !

The ease of expressing fast fibo using the doubling formulas was all I wanted to show.

I never expected anyone to be crazy enough to pull it off in BASIC. But then ejolson showed up

[ejolson]

Ha! That made me chuckle.

Surprisingly, the million-digit Fibonacci calculator written in classic line-numbered Basic has attracted more attention than most of the others.

My primary interest was not in calculating Fibonacci numbers, but in understanding what led to the golden age of personal computing and its collapse. A child is motivated to learn fine motor skills by the reward that food from the plate ends up in his or her mouth. The reward for learning to speak is even greater: an opportunity to tell other people what to do. More importantly, talking while stuffing food in ones mouth are state-of-the-art adult activities unsurpassed in popularity if not beauty.

Although turning an LED on and off can be motivation for learning how to code, it doesn't take strong powers of observation for a child to notice it is impossible to create anything resembling even the simplest commercially-produced video game using Scratch. This implies Scratch does not satisfy item 4 in Kurtz and Kemeny's list of requirements, paraphrased here as follows: A good beginners language should be general purpose and enable a person to code any kind of program the machine is capable of executing.

If what could be accomplished using interpreted Basic was much less than what the 8-bit computers of the golden age could do, what was the motivation to learn Basic? If what can be accomplished using Python is much less than what the 32-bit computers of the second age of personal computing can do, what is the motivation to learn anything?

In my opinion, computers are important because they can do so many different things. Coding is important because software tells the computer what to do. However, if a programming language places many restrictive limits on what kinds of programs can be written, that language does not liberate the person who learns it. Without the freedom to code all kinds of programs, from where will come the motivation necessary to make the second age of personal computing last? And will these rhetorical questions ever end?

Of course it could be worse. The public library across town holds an ongoing event called Learn to Code with Mr Toad with a description that closes with the following sentence:

This activity is very hands-on and computers will seldom be used.

[timrowledge]

Although turning an LED on and off can be motivation for learning how to code, it doesn't take strong powers of observation for a child to notice it is impossible to create anything resembling even the simplest commercially-produced video game using Scratch.

Whilst one can only agree that Scratch is not a good choice for implementing a contemporary major game (but then friends in the business will complain loudly about how pretty much no language or development system is good enough) I would point you at the PacMan included in the Demos folder of the Pi version of Scratch. That's a pretty damn good PacMan. It was written by the Oliver brothers (purportedly in a single night of drink-programming, which sounds ridiculous until you remember that for a while they were pretty much theUK games industry) and very tightly replicates the original.

[ejolson]

Although turning an LED on and off can be motivation for learning how to code, it doesn't take strong powers of observation for a child to notice it is impossible to create anything resembling even the simplest commercially-produced video game using Scratch.

I would point you at the PacMan included in the Demos folder of the Pi version of Scratch.

That's a good find; it would be interesting to look at the code. I wonder if it would be possible to program an authentic version of Joust in Scratch. That was one of my favourites from a few years later due to the possibility of cooperative or competitive game play. Of course it's better to own the machine, if playing competitively.

I've been looking at documentation and found

There are four distinct numeric types: plain integers, long integers, floating point numbers, and complex numbers.

and

There are three distinct numeric types: integers, floating point numbers, and complex numbers.

https://docs.python.org/2/library/stdtypes.html
https://docs.python.org/3/library/stdtypes.html

It appears that int in Python2 is the same as long in C and long in Python2 is instead an arbitrary-precision big integer. On the other hand, int in Python3 is always a big integer and there is no access to any of the integer data types natively supported by the processor. This probably doesn't matter, because anyway Python2 seems to promote hardware integer data types to big integers upon overflow rather than reducing the result modulo 2^k as done by the CPU. Does anyone know how the hashing, checksumming and pseudorandom number generating algorithms that rely on the hardware's modulo behaviour are coded in Python?

As there is no access to native data types, I'm at a bit of a loss how to implement my own big-number multiplication algorithms in Python. It might be possible to implement a base 10^k Karatsuba algorithm on top of the existing big integer support to avoid the apparent O(n^2) base conversion that Python performs when printing. Whether this results in faster computational speeds compared to the timing metrics reported here would be interesting. If anyone wants to try this, I would suggest using the Visual Basic code visual.bas as a starting point.