## Liberation through Computer Literacy

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

### Re: A Final Fibonacci Challenge

danjperron wrote: And this is my new code with decimal conversion. Still need to work on the decimal conversion to print! it is the slowest part. I wonder if it is not because of memory cache.

I put Heater binary to decimal version from his code and I also add the dabble method.
It is possible I should take the blame for b2print. Between b2print, double_dabble32 and double_dabble64 which is faster?

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

### Re: A Final Fibonacci Challenge

ejolson,
I really wish you hadn't done that. I feel nauseous. And it does not say anything useful anyway.

Anyway you are right. If we print the type of what finally get's printed we see:

For fibo.py: <class 'int'>

For fibo_phi.pi: <class 'decimal.Decimal'>

Clearly the decimal class has it's own print method which is much faster.

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

### Re: A Final Fibonacci Challenge

danjperron,
Then What do I do? if the fibo ask is only 1 and the other 10000000.
One can calculate how many digits a fibo(n) result will have, without actually having to calculate the fibo(n) itself:

See here: http://www.maths.surrey.ac.uk/hosted-si ... section2.3

And hence one can preallocate the correct size arrays at start up.

Which is what ejoson does in his Classic BASIC fibo.
Your current algorithm figure out fibo using pre-calculated fibonacci number with lower values.
Strangely enough my fibo in Javascript uses memoization, all we need to do is to use the file system instead of memory for the memoized sub-fibos.

Sadly Fibonacci numbers don't compress very well. gzip only reduces fibo(4784969) by about half in size.

Paeryn
Posts: 2661
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

### Re: A Final Fibonacci Challenge

danjperron wrote:
Wed Jun 05, 2019 11:07 pm
@Paeryn

Yes that version has some bugs .

But
Code: Select all

realloc(fibs, sizeof(Fibs_struct)*fibs_size);
Do you really want to realloc fibs and throw away it's new location if it got moved?
Then What do I do? if the fibo ask is only 1 and the other 10000000.
I gave an example, realloc() returns a pointer to the start of the re-allocated block. If there was space directly after to extend the block then the pointer won't have changed. If it failed to allocate the new size then it returns NULL. If there wasn't space directly after that block to extend into then a new block of the new size will be allocated, the contents of the old block will be copied to the new block, the old block will be have free() called on it and the address of the new block is returned.
In your usage, if the re-allocated block was put somewhere else you would have been reading data from whatever happens to be allocated that memory.
You have v declared as unsigned long long, but you are multiplying two unsigned long values, that will result in an unsigned long value (just the lower half of the result) which is then promoted and stored in v, the upper half of the result is thrown away.

I don't think so! The compiler will deal with it!

Code: Select all

``````#include <stdlib.h>
#include <stdio.h>

int main(void)
{

unsigned long a,b;
unsigned long long c;

a = 0xffffffff;
b = 0x80000000;

c = a * b;

printf("%8lX * %8lX = %16llX\n",a,b,c);

return 0;
}
``````
and the result
MacBook-Air-de-Daniel:~ daniel\$ ./t1
FFFFFFFF * 80000000 = 7FFFFFFF80000000
That is on your macbook, try it on the RPi and see. C says a mathematical operator only has to return the same type as its operators, the type of variable you are assigning to has no bearing on the types used in the calculation.
She who travels light — forgot something.

gkreidl
Posts: 6093
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

### Re: A Final Fibonacci Challenge

The riddle of slow or fast printing (Python, both algorithms)

Before anything can be printed it has to be converted to a string. The conversion of the fibo(4784969) bigint takes about 301 seconds

Code: Select all

``````res = fibo(4784969)
t = time.time()
restr = str(res)
print (time.time()-t)``````
The conversion of the high precision Decimal using the Phi algorithm into a string takes almost no time (0.01 sec.).The reason is quite simple and can be found by studying the original decimal module written in Python (used up to Python version 3.4, the binary compiled C version has been added in 3.5). The internal representation of decimals is already a string.
Minimal Kiosk Browser (kweb)
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

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

### Re: A Final Fibonacci Challenge

Thanks for the confirmation. That is pretty much what we guessed.

Time for another Python big fibo using the fast algorithm with Decimals.
Last edited by Heater on Thu Jun 06, 2019 3:16 pm, edited 1 time in total.

danjperron
Posts: 3402
Joined: Thu Dec 27, 2012 4:05 am

### Re: A Final Fibonacci Challenge

Code: Select all

``````Maybe so, but to use Python 3, your program should start
Code: Select all

#!/usr/bin/env python3
They're best thought of as two completely separate languages, united by a common fear of HTML text normalization.``````
Yes this is a mistake of my part. ;-(

I Always using the correct python interpreter on the prefix command.
I create the program using my Mac! Then I forget to change the env variable since my Mac only have python3

B.T.W. The realloc program in my C version is not a big issue. It is only to hold previous calculated value of Fibo.
The pointer in the table for the correct value is just a pointer .
Then fibo(4784969) will create a table of 59 calculated values. Since a put 100 structures increment it doesn't do a realloc at all.

Code: Select all

``````fibo( 3 )
fibo( 5 )
fibo( 4 )
fibo( 10 )
fibo( 9 )
fibo( 19 )
fibo( 8 )
fibo( 18 )
fibo( 37 )
fibo( 17 )
fibo( 36 )
fibo( 74 )
fibo( 73 )
fibo( 147 )
fibo( 35 )
fibo( 72 )
fibo( 146 )
fibo( 293 )
fibo( 145 )
fibo( 292 )
fibo( 585 )
fibo( 291 )
fibo( 584 )
fibo( 1169 )
fibo( 583 )
fibo( 1168 )
fibo( 2337 )
fibo( 1167 )
fibo( 2336 )
fibo( 4673 )
fibo( 2335 )
fibo( 4672 )
fibo( 9346 )
fibo( 9345 )
fibo( 18692 )
fibo( 18691 )
fibo( 37383 )
fibo( 4671 )
fibo( 9344 )
fibo( 18690 )
fibo( 37382 )
fibo( 74766 )
fibo( 74765 )
fibo( 149531 )
fibo( 37381 )
fibo( 74764 )
fibo( 149530 )
fibo( 299061 )
fibo( 149529 )
fibo( 299060 )
fibo( 598122 )
fibo( 598121 )
fibo( 1196243 )
fibo( 299059 )
fibo( 598120 )
fibo( 1196242 )
fibo( 2392485 )
fibo( 1196241 )
fibo( 2392484 )
fibo( 4784969 )``````

I just test the code on my rock64 with 4G Bytes of ram running a 64 bit version of Ubuntu.

The decimals version is faster! The fibo_phy is to slow at converting the binary to string..

Code: Select all

``````rock64@rockvpn:~\$ python --version
Python 3.6.5
rock64@rockvpn:~\$ cat /proc/version
Linux version 4.4.132-1075-rockchip-ayufan-ga83beded8524 (root@runner-f725ff63-project-5943294-concurrent-0) (gcc version 7.3.0 (Ubuntu/Linaro 7.3.0-16ubuntu3) ) #1 SMP Thu Jul 26 08:22:22 UTC 2018
rock64@rockvpn:~\$ uname -m
aarch64
rock64@rockvpn:~\$ time python3 ./fibo_phy.py
442948
1072739564180047722936481359622500432190722117323735062984 .....
...   0149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
Run time = 4.542796907946467

real    1m37.494s
user    1m37.408s
sys     0m0.068s

rock64@rockvpn:~\$ time python3 fibo_decimals.py 4784969
1000013
1072739564180047722936481359622500432190722117323735062984....
...    0149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269

real    1m7.719s
user    1m7.400s
sys     0m0.309s
rock64@rockvpn:~\$
``````

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

### Re: A Final Fibonacci Challenge

gkreidl wrote:
Thu Jun 06, 2019 9:27 am
The riddle of slow or fast printing (Python, both algorithms)

Before anything can be printed it has to be converted to a string. The conversion of the fibo(4784969) bigint takes about 301 seconds

Code: Select all

``````res = fibo(4784969)
t = time.time()
restr = str(res)
print (time.time()-t)``````
The conversion of the high precision Decimal using the Phi algorithm into a string takes almost no time (0.01 sec.).The reason is quite simple and can be found by studying the original decimal module written in Python (used up to Python version 3.4, the binary compiled C version has been added in 3.5). The internal representation of decimals is already a string.
The improvement in speed resulting from the C implementation of Decimal used in Python 3.5 and greater may explain why Python 2 seems so slow. Likely it still uses the native Python version of Decimal.

While fast computational speed is important, rather than rewriting the Python code for the Decimal library in C, if it remained written in Python and instead the speed of the Python language itself was improved, that would be more liberating for the beginning programmer who knows only Python.

I recently attended a talk given by a graduate student as part of their master's thesis defense. The topic was how to obtain correct statistics characterising goodness of fit when performing a linear regression in R on data which has been tabulated according to frequency. Since unpacking the data into the format needed by the standard routines required magnitudes more memory than available (on a server with 384GB RAM) the idea was to calculate directly with the tabulated data. This has a speed advantage as well. At some point during the talk the question was asked, why not simply modify the old routine to use the new formulas. The answer was that the original routine called C and Fortran subroutines and modifying those was too difficult for someone who knows only R.

People who have mastered and regularly use a language are more likely to care enough to improve it. However, if fixing bugs in Python and R requires knowing C and Fortran, then who will fix the bugs?

John_Spikowski
Posts: 1385
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Beyond who, when?

Open source can be restrictive if part of popular distribution. I enjoy the freedom to innovate by gluing stuff together.

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

### Re: A Final Fibonacci Challenge

ScriptBasic,
Open source can be restrictive if part of popular distribution
Could you please elaborate on what you mean by that? How is having any Open Source program included in a distribution in anyway restrictive?
I enjoy the freedom to innovate by gluing stuff together.
As do most Pi users and people who are into software in general.

Open Source software is an amazingly useful and plentiful source of parts for such "gluing together" projects.

Conversely there is often no freedom to innovate by gluing together parts of closed source software offerings.

I don't understand what you are trying to say there.

John_Spikowski
Posts: 1385
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

What are the chances you could get an enhancement you like into the Python / Raspian distribution?

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

### Re: A Final Fibonacci Challenge

ScriptBasic,
What are the chances you could get an enhancement you like into the Python / Raspian distribution?
Slim to none of course.

What has that got to do with being Open Source or not?

How is that different than my asking "What are the chances you could get an enhancement you like into VC++ / Windows 10?"

Nothing and none as far as I can tell.

Well, except despite being slim to none there is a lot more chance I could hack Python to do what I want than VC++, what with having the source code available.

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

### Re: A Final Fibonacci Challenge

Speaking of gluing things together. I just managed to get node.js to complete fibo(4784969) in 2.7 seconds. Twenty one times faster than fibo.js, only 3 times slower than the C++ version!
\$ time node fibo_karatsuba.js | head -c 32
10727395641800477229364813596225
real 0m2.768s
user 0m2.609s
sys 0m0.453s
Of course I cheated with the glue a bit...

John_Spikowski
Posts: 1385
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Sounds like you use GMP fibo.

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

### Re: A Final Fibonacci Challenge

Nope. All my own code.

danjperron
Posts: 3402
Joined: Thu Dec 27, 2012 4:05 am

### Re: A Final Fibonacci Challenge

MacBook-Air-de-Daniel:~ daniel\$ ./t1
FFFFFFFF * 80000000 = 7FFFFFFF80000000
That is on your macbook, try it on the RPi and see. C says a mathematical operator only has to return the same type as its operators, the type of variable you are assigning to has no bearing on the types used in the calculation.
Yes you are correct. But When I look at my history I did fix that bug when I was able to print the result!. It just slip on my mind.

I still have to work on my multiplication function which is not effective.

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

### Re: A Final Fibonacci Challenge

Heater wrote:
Fri Jun 07, 2019 6:03 am
Speaking of gluing things together. I just managed to get node.js to complete fibo(4784969) in 2.7 seconds. Twenty one times faster than fibo.js, only 3 times slower than the C++ version!
\$ time node fibo_karatsuba.js | head -c 32
10727395641800477229364813596225
real 0m2.768s
user 0m2.609s
sys 0m0.453s
Of course I cheated with the glue a bit...
From the name, it would appear you used the Karatsuba algorithm and built-in big numbers for the limbs.

In a completely different direction, there is a programming language called LOLCODE based on the LOLCAT spoken language so simple that it is understandable by any cat, not just orange ones. I stopped short of Karatsuba multiplication and even the doubling formulas with the hope that someone good with cats who frequents this thread might be able to help.

Since LOLCODE is a modern language designed for beginners that meets the same design goals Kurtz and Kemeny had for BASIC in the golden age (and Grace Hopper with COBOL before that), then anyone should be able to understand and improve the program just by reading it. The current version of the code is

Code: Select all

``````HAI 1.3

OBTW
HAIFIBO.LOL -- COMPUTE THE NTH FIBONACCI NUMBER
WRITTEN JUNE 7, 2019 BY ERIC OLSON

DIS PROGRAM DEMONSTRATEZ TEH EXPRESIVENES OV LOLCODE AS MEASURD
BY EXPLICITLY CODIN HOOJ-NUMBR ADDISHUN AN USIN TEH RECURRENCE

F(K+1) = F(K) + F(K-1)

2 COMPUTE TEH NTH FIBONACCI NUMBR.  4 SIMPLICITY DIS CODE USEZ
NEITHR KARATSUBA MULTIPLICASHUN, TEH DOUBLIN FORMULA NOR ANY OTHR
FAST CALCULATIN ALGORITHM.  TEH RUNNIN TIEM IZ O(N^2).

VERSHUN 2:  FIXD BUG IN PADZERO DAT MITE OVERFLOW IF TEH FULL
INTEGR WIDTH WUZ USD 4 DA LIMBS AN BUMPD TEH RADIX CUZ 64-BIT
INTEGERS R USD EVEN ON RASPBIAN.
TLDR

I HAS A RADIX ITZ 1000000000000000000

HOW IZ I PADZERO YR X
I HAS A Y ITZ X
YA RLY
VISIBLE X!
GTFO
OIC
VISIBLE "0"!
Y R PRODUKT OF Y AN 10
IF U SAY SO

HOW IZ I HOOJPRINT YR HOOJNUM
I HAS A J
IM IN YR PRINTIN UPPIN YR INDEX TIL ...
BOTH SAEM INDEX AN HOOJNUM'Z SRS 0
J R DIFF OF HOOJNUM'Z SRS 0 AN INDEX
BOTH SAEM J AN HOOJNUM'Z SRS 0, O RLY?
YA RLY
VISIBLE HOOJNUM'Z SRS J!
NO WAI
I IZ PADZERO YR HOOJNUM'Z SRS J MKAY
OIC
IM OUTTA YR PRINTIN
VISIBLE ""
IF U SAY SO

HOW IZ I HOOJTRIM YR HOOJNUM
I HAS A J
IM IN YR TRIMMIN UPPIN YR INDEX TIL ...
BOTH SAEM INDEX AN HOOJNUM'Z SRS 0
J R DIFF OF HOOJNUM'Z SRS 0 AN INDEX
DIFFRINT HOOJNUM'Z SRS J AN 0, O RLY?
YA RLY
HOOJNUM'Z SRS 0 R J
FOUND YR HOOJNUM
OIC
IM OUTTA YR TRIMMIN
HOOJNUM'Z SRS 0 R 1
IF U SAY SO

HOW IZ I HOOJADD YR X AN YR Y
I HAS A RETMAX ITZ SUM OF 1 AN BIGGR OF X'Z SRS 0 AN Y'Z SRS 0
I HAS A RETVAL ITZ A BUKKIT
RETVAL HAS A SRS 0 ITZ RETMAX
I HAS A J
I HAS A TEMP
I HAS A CARRY ITZ 0
IM IN YR ADDIN UPPIN YR INDEX TIL BOTH SAEM INDEX AN RETMAX
J R SUM OF INDEX AN 1
TEMP R CARRY
BOTH SAEM J AN SMALLR OF J AN X'Z SRS 0, O RLY?
YA RLY
TEMP R SUM OF TEMP AN X'Z SRS J
OIC
BOTH SAEM J AN SMALLR OF J AN Y'Z SRS 0, O RLY?
YA RLY
TEMP R SUM OF TEMP AN Y'Z SRS J
OIC
CARRY R QUOSHUNT OF TEMP AN RADIX
RETVAL HAS A SRS J ITZ MOD OF TEMP AN RADIX
FOUND YR I IZ HOOJTRIM YR RETVAL MKAY
IF U SAY SO

HOW IZ I HOOJFIBO YR N
I HAS A HOOJA ITZ A BUKKIT
HOOJA HAS A SRS 0 ITZ 1
HOOJA HAS A SRS 1 ITZ 1
DIFFRINT N AN BIGGR OF N AN 3, O RLY?
YA RLY
FOUND YR HOOJA
OIC
N R DIFF OF N AN 2
I HAS A HOOJB ITZ A BUKKIT
I HAS A HOOJC ITZ A BUKKIT
HOOJB HAS A SRS 0 ITZ 1
HOOJB HAS A SRS 1 ITZ 1
IM IN YR FIBOLOOPIN UPPIN YR INDEX TIL BOTH SAEM INDEX AN N
HOOJC R HOOJB
HOOJB R HOOJA
HOOJA R I IZ HOOJADD YR HOOJB AN YR HOOJC MKAY
IM OUTTA YR FIBOLOOPIN
FOUND YR HOOJA
IF U SAY SO

I HAS A N
I HAS A INPUT
I HAS A HOOJNUM
IM IN YR COMPUTIN
VISIBLE "? "!
GIMMEH INPUT
N R SUM OF 0 AN INPUT
BOTH SAEM N AN 0, O RLY?
YA RLY
GTFO
OIC
HOOJNUM R I IZ HOOJFIBO YR N MKAY
I IZ HOOJPRINT YR HOOJNUM MKAY
IM OUTTA YR COMPUTIN

KTHXBYE``````
It's not particularly fast, but works. Here is a test run:

Code: Select all

``````\$ lci haifibo.lol
? 1
1
? 6
8
? 100
354224848179261915075
? 200
280571172992510140037611932413038677189525
? 500
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
? 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
? 7499
7060398799376784390080431403153762407133523390537059878104950622786388718825722561078363937111808052845829043934364899297524579596771135537480100208027085369896805936602227218581761602607709602334939889484798397142942218388978326231083561149392205369863825989576207551146164545991161518248812602059748659792822539047900440615827674362997814592886203623387177745482781961764037789256204211876516867755389327862471098927207504535260828110167596703760822462988717005213704260555517262693067390672579278642451139772159098237484766060153417966500228867893493613281899397919811817985526393984078448175231602116343732669535382592866176830021901276573501388490142960269573429689010342153684955910446206097236075006861770107503447313897585687337597851533416564601034740128818628864559166341653871747561460183576425048959152474006524376867108154719826724951577811058520409795890271953207501037389580837065627491303664939319008074326639606500449899956261137209763009997639133968161102379352100526521219319009668949360509017190305822205735637047582596844361054536570105575658758958126781615314786897307911885991922151961963946513621905753392384260111071739837465056829372023129875545405507382500246527434315392215299304419577933704415638169229147761482551989210536522219106497198930639764648714287173928443999657477934962619150591299808484015221733892947047898044789624388717645430081789847014505889073245674298227489060602274996337440845903140973613284173331051297305566669585112157848209843391912656796627677634633934542271164812214908073040748492419868112329633702241675255001
? 0``````
Update: Since lci uses 64-bit integers even on Raspbian, better performance (about two times faster) was obtained by increasing the radix and modifying the padzero routine to avoid an overflow bug when using such a large radix.
Last edited by ejolson on Sat Jun 08, 2019 7:23 pm, edited 5 times in total.

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

### Re: A Final Fibonacci Challenge

ejolson,
From the name, it would appear you used the Karatsuba algorithm and built-in big numbers for the limbs.
Yes. And no.

More later when I get it running how I like.
In a completely different direction, there is a programming language called LOLCODE...
OMG. WTF?

You have out LOL'ed us all!

The 20000th HOOJFIBO comes out correct after one minute here.

I find a certain poetic charm in "HOW IZ I HOOJFIBO YR N". Don't you?

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

### Re: A Final Fibonacci Challenge

Heater wrote:
Fri Jun 07, 2019 5:22 pm
The 20000th HOOJFIBO comes out correct after one minute here.

I find a certain poetic charm in "HOW IZ I HOOJFIBO YR N". Don't you?
I just discovered that lci uses 64-bit integers even on Raspbian, so I was able to increase the size of the radix. The padzero function was also modified slightly to further increase each limb by one more decimal digit. The post above has been updated with the new version. I suspect this micro-optimization will increase the speed by about double what is was before.

What would e e cummings think if all poetry were written using only upper-case letters as in LOLCAT and LOLCODE?

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

### Re: A Final Fibonacci Challenge

ejolson wrote:
Fri Jun 07, 2019 7:18 pm
I suspect this micro-optimization will increase the speed by about double what is was before.
With further optimization a program written in LOLCODE may soon be the performance champion in the famous Fibonacci challenge.

High-performance extensions to the poetic cat-friendly meme-based programming language described in this research entitled "I CAN HAS SUPERCOMPUTER?" have resulted in an ideal way to teach parallel and distributed computing. More information is available here.

Source for an advanced optimising compiler that includeds the necessary LOLCODE parallel programming extensions along with example code is available on GitHub. Apparently the compiler has been tested on the Parallela many-core Epiphany coprocessor, Intel x86 PCs as well as a Cray XC40. Since Raspbian is surprisingly similar to the targeted Linux operating systems, it is likely lcc will also run on the Raspberry Pi 3B+.

If LOLCODE is the most expressive language developed so far for teaching parallel processing, is there any hope of avoiding a digital apocalypse?
Last edited by ejolson on Sat Jun 08, 2019 4:41 pm, edited 1 time in total.

John_Spikowski
Posts: 1385
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

If you have a way that would allow ScriptBasic to do Fibonacci in hardware native math, I would like to try it with the SBT extension module in asynchronous threads using a shared result string. That would be an interesting spin on this challenge.

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

### Re: A Final Fibonacci Challenge

ScriptBasic,

What do you mean by "hardware native math". Generally the hardware, computers we have, do arithmetic in various sizes of signed and unsigned integers and IEEE 754 standard floating point. With perhaps some help with accelerating operations on vectors of those things. Presumably ScriptBasic uses some or all of those.

I don't know if any one has ever built a hardware fibonacci calculator. But as I have an FPGA board here you start me thinking...
Last edited by Heater on Sat Jun 08, 2019 5:39 pm, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

ScriptBasic wrote:
Sat Jun 08, 2019 4:35 pm
If you have a way that would allow ScriptBasic to do Fibonacci in hardware native math, I would like to try it with the SBT extension module in asynchronous threads using a shared result string. That would be an interesting spin on this challenge.
The parallelism exhibited in the C and C++ codes is from the divide-and-conquer big-number multiplication routine. Coding this using native integer data types requires a reasonably efficient way to reference memory through an index. However, as has (or will be) demonstrated in JavaScript, it's also possible to layer Karatsuba multiplication on top of an existing implementation of big-number arithmetic (maybe).

While the JavaScript code does this to work around a bug in how fast the existing big-number printing routines are, this layering approach could also be used to create a parallel multiplication algorithm. To do this in ScriptBasic, you would need a way to use the GMP multiply, add, subtract, modulo and divide routines from within a script. After this, it would likely be possible to layer a parallel implementation of Karatsuba on top of GMP using ScriptBasic threads.
Last edited by ejolson on Sat Jun 08, 2019 5:55 pm, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

Heater wrote:I don't know if any one has ever built a hardware fibonacci calculator. But as I have an FPGA board here you start me thinking...
The double-dabble base-2 to base-10 conversion routines from the Fibonacci code in this post were apparently designed for hardware implementation. I wonder if there are big-number multiply routines that have been designed to specifically make use of the kinds of parallelism present in an FPGA.

The entries for the next roundup in the Fibonacci challenge are presently

fibo_phi.py -- A numerical approach based on taking powers of the golden ratio using floating-point numbers with greater than one-million-digit precision.

golden.pas -- An O(n^2) algebraic approach based on taking powers of the golden ratio using schoolbook multiplication.

haifibo.lol -- A simple O(n^2) dynamic-programming approach that uses repeated additions.

From what I understand new PL/I and C codes are still under preparation. Is there anything else?

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

### Re: A Final Fibonacci Challenge

ejolson,
High-performance extensions to the poetic cat-friendly meme-based programming language described in this research entitled "I CAN HAS SUPERCOMPUTER?"...
FO SHIZZLE, MA NIZZLE!

That is outstanding. And somebody said the LOLCODE thread was "nonsense".

Checking the motivation for the LOLCODE super computing project I feel that Kurtz and Kemeny and would totally approve.

Sadly I don't have a Cray XC40 lying around but strangely enough I do have a Parallela Epiphany board on my desk at this very moment. Every now and then I dig it out of the junk pile and wonder what to do with it. Now I have a plan...

Also sadly the lci LOLCODE compiler did not like my fibo code much:

a) Multi-line comments can't start on the same line as there OBTW.

b) I had to pull some of the sub-expressions out of nested expressions to get it to understand.

c) Had to add types to the variables to get the generated C code to compile.

d) Had to add MKAY to the end of the fibo function declaration.

I ended up with this lci friendly fibo:

Code: Select all

``````HAI 1.2
BTW Heater's first LOLCODE for lci

OBTW
Function to calculate the n'th Fibonacci number
The recursive way.
TLDR

HOW IZ I fibo YR n MKAY
BOTH SAEM n AN 0
O RLY?
YA RLY
FOUND YR 0
OIC

BOTH SAEM n AN 1
O RLY?
YA RLY
FOUND YR 1
OIC

I HAS A d1 ITZ A NUMBR AN ITZ DIFF OF n AN 1
I HAS A d2 ITZ A NUMBR AN ITZ DIFF OF n AN 2

I HAS A f1 ITZ A NUMBR AN ITZ I IZ fibo YR d1 MKAY
I HAS A f2 ITZ A NUMBR AN ITZ I IZ fibo YR d2 MKAY

FOUND YR SUM OF f1 AN f2
IF U SAY SO

I HAS A n ITZ A NUMBR AN ITZ 20
I HAS A f ITZ A NUMBR
f R I IZ fibo YR 20 MKAY
VISIBLE "fibo("n") = "f

KTHXBYE
``````