Liberation through Computer Literacy

[John_Spikowski]

Native hardware math = standard integers, doubles, ...

[Heater]

Then I don't understand your question: "If you have a way that would allow ScriptBasic to do Fibonacci in hardware native math,..."

Presumably ScriptBasic uses standard integers, doubles.

What am I missing here?

[Heater]

How to make a fast fibo(4784969) in Javascript....

Previously we had a fibo.js that produced the one million digit result in about a minute. It used the Javascript BigInt type to handle the huge numbers. Annoyingly most of that minute was spent printing the result, the actual calculation only taking a few seconds.
https://github.com/ZiCog/fibo_4784969/b ... pt/fibo.js

We also had a fibo_karatsuba.js that produced the result in about three and a half minutes. It used a hand coded karatsuba multiplication.
https://github.com/ZiCog/fibo_4784969/b ... ratsuba.js

Clearly something had to be done.

Today I have a new fibo.js that gets the job done in 3.8 seconds on my PC! Like so:

Code: Select all

$ cat fibo.js
const bint = require('./bint.js')

bint.onRuntimeInitialized = function() {

    let zero = new bint.Bint("0")
    let one = new bint.Bint("1")
    let two = new bint.Bint("2")

    let memo = [zero, one, one]
    
    function fibo (n) {
        if (memo[n]) {
            return memo[n]
        }
        let k = (n / 2) | 0
        let fk = fibo(k)
        let fk1 = fibo(k + 1)
        if ((n % 2) == 0) {
            return memo[n] = fk.mul((fk1.mul(two)).sub(fk))
        }
        return memo[n] = (fk.mul(fk)).add(fk1.mul(fk1))
    }

    let n = 4784969
    let f = fibo(n)
    console.log(f.toString())
}

And the result:

Code: Select all

$ time node fibo.js | head -c 32 ; time node fibo.js | tail  -c 32
10727395641800477229364813596225
real    0m3.789s
user    0m3.688s
sys     0m0.313s
4856539211500699706378405156269

real    0m3.781s
user    0m3.703s
sys     0m0.344s
$

Now that is not bad considering that some of our fastest efforts are ejolson's parallel.c at 1.2 seconds (on one core). Or my C++ effort at 0.9 seconds.

Of course the magic is behind that "const bint = require('./bint.js')" line. You may not want to know what abominations go on there. If anyone is curious I can explain after I get some sleep...

[John_Spikowski]

I'll try again.

NO BIGINT USE just platform level integers and doubles. I've done it in a 1.7 million element array but that is what I'm trying to avoid.

[ejolson]

How to make a fast fibo(4784969) in Javascript....

How to make a fast Fibonacci calculator seems a common problem.
.

karatsubacat.jpg (145.6 KiB) Viewed 795 times

[Heater]

ScriptBasic,

I'll try again.

NO BIGINT USE just platform level integers and doubles. I've done it in a 1.7 million element array but that is what I'm trying to avoid.

I still don't get it.

Given that fibo(4784969) requires a million decimal digits and platform level intergers and doubles are only 32 or 64 bits, clearly one is going to need a bunch of them to represent the result. That bunch can be an array, a linked list or whatever. That which we call a BIGINT is just some arrangement of many small numbers.

One can use strings to represent big integers. Just hold the decimal digits in strings and do the Karatsuba algorithm on them. Terrible slow mind.

I don't see what you are getting at.

[gkreidl]

Nobody has mentioned or tested the Python fibo challenge algorithms with pypy so far, which is a bit unfair when comparing it to JS, for example, as most modern JS engines include a JIT compiler.

fiboch.py is my script using the Python algorithm from github. At the end I have added:

Code: Select all

t = time.time()
res = fibo(4784969)
print(time.time()-t)
t = time.time()
restr = str(res)
print(time.time()-t)

to measure the time needed to calculate fibo(4784969) and also the time needed to convert the result to a string (for printing).

The pypy version on Stretch only works for Python 2.7 and the timing results should be compared to Python 2, as it uses the Python 2 libraries. All tests were run on a RPi 3B+ @1400 MHz.

Code: Select all

pi@raspberrypi4:~ $ python3 fiboch.py
10.617712497711182
305.86755871772766
pi@raspberrypi4:~ $ python fiboch.py
13.2166340351
306.506959915
@raspberrypi4:~ $ pypy fiboch.py
6.28427696228
76.403824091

The version using the Phi algorithm and the decimal module (only Python 3!) takes much longer for the fibo calaculation but almost no time for the string conversion.

Code: Select all

pi@raspberrypi4:~ $ python3 fibo_phi.py
863.088921546936
0.012897014617919922

BTW, the fibo algorithm runs much faster on Jessie both with Python 2 and pypy. I can only test it on a RPi 3B running at 1200 MHz.
Using pypy:
5.54095983505
62.0054118633
If I recalculate it to 1400 MHz:
4.749394144328571
53.14749588282857

In Python 2, the fibo algorithm needs 12.8203668594 seconds, which would result in 10.988885879485716 seconds for 1400 Mhz.
String conversion and Python 3 need about the same time as on Stretch.

This is in accordance with other tests I have run in the past which showed that many Python 2 programs run 20 to 30 % slower on Stretch.

[Heater]

gkreidl,

Interesting. Never heard of pypy.

On my PC at least nearly doubles the calculation speed and displaying the result is about three times faster. Using the code straight out of the github repo:

Code: Select all

$ time python2 fibo.py | tail -c 100
6875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.799810886383

real    0m17.758s
user    0m17.641s
sys     0m0.094s
$ time python3 fibo.py | tail -c 100
5379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.719452999997884

real    0m17.728s
user    0m17.641s
sys     0m0.078s
$ time pypy fibo.py | tail -c 100
6875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.412526845932

real    0m4.935s
user    0m4.703s
sys     0m0.234s

[ejolson]

gkreidl,

Interesting. Never heard of pypy.

On my PC at least nearly doubles the calculation speed and displaying the result is about three times faster. Using the code straight out of the github repo:

Code: Select all

$ time python2 fibo.py | tail -c 100
6875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.799810886383

real    0m17.758s
user    0m17.641s
sys     0m0.094s
$ time python3 fibo.py | tail -c 100
5379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.719452999997884

real    0m17.728s
user    0m17.641s
sys     0m0.078s
$ time pypy fibo.py | tail -c 100
6875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.412526845932

real    0m4.935s
user    0m4.703s
sys     0m0.234s

Some results for PyPy were included in the dramatic Fibonacci comedy here. Its big-number implementation is the fastest for much of the range, however, the asymptotically superior Jython wins in the end.

[Heater]

How to make a fast fibo(4784969) in Javascript....Part Two:

As noted above the secret of the speedy fibo in JS is it's use of a Karatsuba big integer module that I created:

Code: Select all

const bint = require('./Bint.js')

Well it's no secret. That Bint.js module is actually just my old C++ Karatsuba big integer class, bint, transpiled from C++ to Javascript using Emscripten: https://emscripten.org/

Before we can do that bint.h gets renamed to Bint.cpp and a few tweaks made to it:

1) Tell Emscripten what class and methods to export to Javascript by adding:

Code: Select all

#include <wherever/emscripten/bind.h>
...
using namespace emscripten;
...
// Binding code
EMSCRIPTEN_BINDINGS(my_class_example) {
  class_<Bint>("Bint")
    .constructor<std::string>()
    .function("add", &Bint::operator+)
    .function("sub", &Bint::operator-)
    .function("mul", &Bint::operator*)
    .function("toString", &Bint::toString)
    ;

Sadly we can't do operating overloading in JS so we need to export the operators as regular functions.

2) The constructor specified makes a big integer from a std::string so we need to fix up the original constructor that took a C string.

3) Add a method to convert the Bint to a std:string that JS can understand:

Code: Select all

     inline std::string toString() {
         std::stringstream os;
         os << *this;
         return os.str();
     }

With that in place we can compile Bint.cpp to Bint.js with emscripten:

Code: Select all

$ emcc -std=c++17 -Wall -O3 --bind -s TOTAL_MEMORY=16MB  -o Bint.js Bint.cpp

You really don't want to read the output Javascript:

var Module=typeof Module!=="undefined"?Module:{};var moduleOverrides={};var key;for(key in Module){if(Module.hasOwnProperty(key)){moduleOverrides[key]=Module[key]}}Module["arguments"]=[];Module["thisProgram"]="./this.program";Module["quit"]=function(status,toThrow){throw toThrow};Module["preRun"]=[];Module["postRun"]=[];var ENVIRONMENT_IS_WEB=false;v.....

Although compiling with -O0 does give a readable, non-compressed, output.

Then we can just use the Bint module from our JS. it is necessary to wait for the module to be initialized at run time though:

Code: Select all

bint.onRuntimeInitialized = function() {
   // Do stuff with Bints
}

With a little timing code added I find:

Code: Select all

$ time node fibo.js  | tail  -c 100
76875379936330930391815964864885353407167474856539211500699706378405156269
Think:3197ms
Print:140ms

real    0m3.713s
user    0m3.656s
sys     0m0.281s

Thats 3 seconds to calculate the result compared to 13 seconds when using Javascripts built in BigInt type.
And 0.14 seconds to print the result compared to 45 seconds printing the BigInt result.
All in all 15 times faster!

Some questions for you all:

1) Can I allow myself to add this to the fibo(4784969) challenge repository?

On the one hand: It satisfies the requirements, no non-standard libraries, the source is all written my me. The fibo algorithm itself is regular Javascript. It's an interesting solution.

On the other hand: The bulk of the work is in the Bint module, not originally written in JS.

2) Can you spot the hidden secret detail in the above description that would certainly disqualify this from the challenge?

[jahboater]

Heater,

I cant see where BigInt is defined in the ECMA 262 (2018) document?
(Or am I looking at the wrong standard?)

If its not there then I guess you will have to use your own handwritten "bint" library, like C/C++ had to.

[Heater]

jahboater,

I cant see where BigInt is defined in the ECMA 262 (2018) document?

Ah but you see, I'm speaking to you from the future...

When you catch up with where I am, about 2020 in Earthling years, BigInt will be in the ECMAScript standard. For you it is still a only a proposal in the standardization process, but as it is already implemented in Chrome, FireFox, Edge, Node.js, Babel, it makes it to final approval.

I took the liberty of checking in the BigInt JS fibo version ahead of time:)

See this historical article re: BigInt standardization here: https://golb.hplar.ch/2018/09/javascript-bigint.html

If its not there then I guess you will have to use your own handwritten "bint" library, like C/C++ had to.

Actually my C++ big integers, bint, were derived from my first Karatsuba version in Javascript: https://github.com/ZiCog/fibo_4784969/b ... ratsuba.js

That is a tad slower at three and a half minutes

[jahboater]

I cant see where BigInt is defined in the ECMA 262 (2018) document?

Ah but you see, I'm speaking to you from the future...

I had better check the C2x draft

Actually I don't think it will ever be in the C standard, its not a good fit, and as usual in C its just left to run-time libraries to deal with (just like printf etc were until recently). And bigints are not in C++ which seems to want to include everything in the known computing universe.

Actually my C++ big integers, bint, were derived from my first Karatsuba version in Javascript: https://github.com/ZiCog/fibo_4784969/b ... ratsuba.js

That's great isn't it? Meets all the criteria for the challenge.
Its not supposed to be about speed, more about how elegant and expressive the code is.

[ejolson]

jahboater,

I cant see where BigInt is defined in the ECMA 262 (2018) document?

Ah but you see, I'm speaking to you from the future...

When you catch up with where I am, about 2020 in Earthling years, BigInt will be in the ECMAScript standard. For you it is still a only a proposal in the standardization process, but as it is already implemented in Chrome, FireFox, Edge, Node.js, Babel, it makes it to final approval.

I took the liberty of checking in the BigInt JS fibo version ahead of time:)

See this historical article re: BigInt standardization here: https://golb.hplar.ch/2018/09/javascript-bigint.html

If its not there then I guess you will have to use your own handwritten "bint" library, like C/C++ had to.

Actually my C++ big integers, bint, were derived from my first Karatsuba version in Javascript: https://github.com/ZiCog/fibo_4784969/b ... ratsuba.js

That is a tad slower at three and a half minutes

It appears you wrote a version of Karatsuba multiplication in JavaScript, translated it to C++ and then translated to back to JavaScript with the result that it now runs in three seconds rather than three minutes. That's 60 times faster. By my calculations if you translated it back and forth one more time, it would run in only

3 / 60 = 0.05 seconds.

Since FreeBasic has a C backend, it should be possible to take the C output corresponding to classic.bas and feed it into emcc to obtain yet another version in JavaScript. For lots of laughs the same could be done with the lcc compiler.

[Heater]

elolson,

It appears you wrote a version of Karatsuba multiplication in JavaScript, translated it to C++ and then translated to back to JavaScript with the result that it now runs in three seconds rather than three minutes. That's 60 times faster. By my calculations if you translated it back and forth one more time, it would run in only ... 3 / 60 = 0.05 seconds.

Yes indeed. That is why I'm speaking to you from the future. Too much recursion creates an excessive amount of information in too small a space and time. Information is energy, energy is mass, eventually collapsing into a black hole. Sucking in the computer and anything around and spitting it out the other end of a worm hole.

But yes, that is what happened. The JS spawned the C++. Which originally ran at about the same speed!

In other news, I just managed to get my C++ big int class to run as a JS module in a web page. Yet another online Fibonacci number calculator coming soon...

Since FreeBasic has a C backend, it should be possible to take the C output corresponding to classic.bas and feed it into emcc to obtain yet another version in JavaScript. For lots of laughs the same could be done with the lcc compiler.

Some years ago I did exactly that with a compiler written in C++ for the Spin Language. Spin is the language of the Parallax Inc Propeller micro-controller. Ended up with a full Spin IDE in the browser, syntax highlighting and all! https://github.com/ZiCog/openspin.js

[John_Spikowski]

Heater,

I don't know where your Fibonacci direction is going but you have two opposite stories going. You say the challenge is about achieving one million digits not using language features that support BIGINT yet you break your own rules with every submission. You then treat others not participating in your madness as clueless idiots.

[ejolson]

I don't know where your Fibonacci direction is going but you have two opposite stories going.

I suspect there is room for many more Fibonacci stories in this thread as well as on the GitHub.

For example, an extension to Script Basic that allows one to store big integers in strings and perform the five arithmetic operations addition, subtraction, multiplication, division and remainder on those strings using GMP would be fantastic. My suggestion is to use a base-64 encoding when the big numbers are stored as strings to avoid expensive base changes during a calculation. If Script Basic strings are 8-bit clean it would be even easier. Then convert to base 10 only upon printing the result.

If you want to use base 10 throughout, one could leverage a different big-number library behind the scenes that works in a way similar to Decimal in Python.

Another alternative is to wait until the phase of the moon and the title of this thread changes. Unless the moon gets sucked into an unexpected Fibonacci black hole, the chapter up next is the coming digital apocalypse and how to avoid it.

[Heater]

ScriptBasic,

I don't know where your Fibonacci direction is going...

Neither do I. Who would have guessed that everything that has happened here would have happened as a consequence of an off hand challenge thrown down in forum thread?

...but you have two opposite stories going...

I do? Quite possibly... let's see...

You say the challenge is about achieving one million digits not using language features that support BIGINT...

No. I have never said such a thing.

The challenge was to write a program, in the language of your choice (originally BASIC as the challenge was put to DavidS, a BASIC fanatic), that can calculate the first number of the Fibonacci sequence with one million digits. No mention of using built in big integer types or not was ever made. The requirement that no non-standard libraries be used was suggested by DavidS himself and all here agreed. It's all laid out at the start of the old "Avoiding BASIC thread".

...yet you break your own rules with every submission.

I do? How?

Admittedly it has come to light that the BigInt types I used in Javascript are not part of the JS standard yet. A genuine mistake, I did not check first. Please consider that entry as disqualified until BigInt's make it into the standard in a year or so. Anyway, I also provided a Javascript solution that only uses regular JS numbers.

My new JS solution is not in the challenge repository. I have even asked others here if they considered that as breaking the rules or not.

You then treat others not participating in your madness as clueless idiots.

Get out of here with that unfounded and insulting nonsense.

[ejolson]

I have even asked others here if they considered that as braking the rules or not.

The only official rules on this forum were stated here and say

The rules are simple. Be good to each other.

This means be kind, be civil, don't spam.

The future of the world is at stake.

We must all work together to avoid the digital apocalypse, even if that means coding yet another big-number Fibonacci program. After all, if we can't, then deep-learning convolutional artificial intelligences will soon do it for us while at the same time developing emergent behaviours that cooperate to take over the world.

[Heater]

ejolson,

Does that mean you don't have an objection to the latest JS effort as a solution to the fibo(4784969) challenge?

My contribution to the future of the world and avoiding the digital apocalypse today is putting up a web server that serves up a JS fibo(4784969) solution. The calculation is done in your browser and it displays the result. That's it, nothing more, nothing less:

http://68.183.214.85:3000/public/fibo.html

If anyone has a Pi to visit that from I'd love to know if it works at all. I only have headless Pi here.

If you open the console in the browser dev tools and reload it will show how long the calculation and displaying took.

If you poke around in the dev tools you might find out why you might object to this as a fibo(4784969) challenge solution.

Luckily all this effort is not wasted, even if it does not save the world or prevent the digital apocalypse, turns out I have a work related reason for being able to do all this. So it has been a good way to figure out how it all works.

[ejolson]

The calculation is done in your browser and it displays the result.

The good news is that I was able to reach your website. The bad news is that the digital apocalypse has not yet been avoided.

On my mobile phone (Android 7.1.1 with the default Chrome browser) I obtain the text

The 4784969th Fibonacci Number is: Calculator:Preparing... (0/1)

Sometimes nothing further happens; sometimes the big number appears after a few minutes. If I try to scroll to see the number, it disappears leaving me with a completely black screen. I couldn't find the performance metrics. Fortunately closing the webpage returns me safely to the Raspberry Pi forum.

Maybe the performance metrics should be displayed first along with a button called "show number."

I see no problem adding the new JavaScript code to the GitHub repository in addition to those solutions which use ScriptBasic extensions.

To keep things organized, what do you think about creating a subdirectory named extraordinary to hold the multi-language and hybrid codes that represent important programming techniques which transcend a single language solution?

[Paeryn]

On my mobile phone (Android 7.1.1 with the default Chrome browser) I obtain the text

The 4784969th Fibonacci Number is: Calculator:Preparing... (0/1)

Sometimes nothing further happens; sometimes the big number appears after a few minutes. If I try to scroll to see the number, it disappears leaving me with a completely black screen. I couldn't find the performance metrics. Fortunately closing the webpage returns me safely to the Raspberry Pi forum.

I've just loaded the page on my phone (Android 9, Exynos 9810 SoC, default Chrome), there wasn't any preparing message at the start, just a blank page until suddenly the result was displayed (after about 19 seconds). Although reloading the page (I didn't time it the first time) did show the preparing message. The result page shows my hatred for one thing in Android, 99% of the time the scroll bar is a purely visual indicator and can't be used to select the area you want to go to.

[Heater]

ejolson,

Ah, never thought to try it on my phone. It's such a cheap old Samsung whatever. I had much the same results.

Then I connected the phone to my WIFI box and updated Chrome. Since then I have been able to get the million digits up a few times. It takes a while. Amazingly when it's really done I can swipie/scrollie to the last digit pretty fluidly. But even that wears out my swipie/scrollie finger.

The performance figures do not appear in the page. You need to get into the browser developer tools to see that. I have no idea if that is even possible on Android Chrome.

I'll tweak around with the interface tomorrow.

I see no problem adding the new JavaScript code to the GitHub repository...

OK. It's time for me to 'fess up. There is a reason why what I present now is not a valid big fibo challenge solution...

The last time I used Emscripten it transpiled C++ to Javascript. Now I find that by default it compiles C++ to WASM. Now WASM is a new fangled kind of byte code that is being rolled out into browsers. It's back to the bad old days of Java applets, except built into the browser standards rather than being a plugin. Potentially any language that can be compiled can be compiled to WASM bytecodes and run in a browser. Ironically that excludes Javascript as it is too much of a dynamic language!

Emscripten now produces WASM byte codes and a Javascript wrapper around it to load and run it from node.js or whatever browser.

There is an Emscripten switch to stop it generating WASM and just emit JS. Which is what I would need to make a valid big fibo challenge solution. Sadly when I use that I get no result out of it! No idea why yet.

I'll have a think about that challenge repo organization after business today...

[John_Spikowski]

For example, an extension to Script Basic that allows one to store big integers in strings and perform the five arithmetic operations addition, subtraction, multiplication, division and remainder on those strings using GMP would be fantastic.

I have already started a GMP extension module which only has one function which is fibo. If you have time maybe you can add the missing functions.

My focus is device / sensor interfaces at the moment. Getting folks to use ScriptBasic for analysis is a stretch.

[hippy]

...yet you break your own rules with every submission.

I do? How?

I would guess that has something to do with ...

2) Can you spot the hidden secret detail in the above description that would certainly disqualify this from the challenge?

You appear to acknowledge that entry is disqualified from the challenge but appear to be suggesting it should be included if others cannot see why it should be disqualified.

Why avoid sophistry when we have meta-sophistry ?