It is possible I should take the blame for b2print. Between b2print, double_dabble32 and double_dabble64 which is faster?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.
Re: A Final Fibonacci Challenge
Re: A Final Fibonacci Challenge
ejolson,
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.
I really wish you hadn't done that. I feel nauseous. And it does not say anything useful anyway.If you don't mind the colour pink, see also...
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.
Memory in C++ is a leaky abstraction .
Re: A Final Fibonacci Challenge
danjperron,
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.
Sadly Fibonacci numbers don't compress very well. gzip only reduces fibo(4784969) by about half in size.
One can calculate how many digits a fibo(n) result will have, without actually having to calculate the fibo(n) itself:Then What do I do? if the fibo ask is only 1 and the other 10000000.
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.
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.Your current algorithm figure out fibo using pre-calculated fibonacci number with lower values.
Sadly Fibonacci numbers don't compress very well. gzip only reduces fibo(4784969) by about half in size.
Memory in C++ is a leaky abstraction .
Re: A Final Fibonacci Challenge
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.danjperron wrote: ↑Wed Jun 05, 2019 11:07 pm@Paeryn
Yes that version has some bugs .
But
Then What do I do? if the fibo ask is only 1 and the other 10000000.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?
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!and the resultCode: 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; }
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.MacBook-Air-de-Daniel:~ daniel$ ./t1
FFFFFFFF * 80000000 = 7FFFFFFF80000000
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
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
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.
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)
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
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.
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.
Memory in C++ is a leaky abstraction .
-
- Posts: 3531
- Joined: Thu Dec 27, 2012 4:05 am
- Location: Québec, Canada
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.
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:~$
Re: A Final Fibonacci Challenge
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.gkreidl wrote: ↑Thu Jun 06, 2019 9:27 amThe 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 secondsThe 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.Code: Select all
res = fibo(4784969) t = time.time() restr = str(res) print (time.time()-t)
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: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
- Contact: Website Twitter
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.
Open source can be restrictive if part of popular distribution. I enjoy the freedom to innovate by gluing stuff together.
Re: A Final Fibonacci Challenge
ScriptBasic,
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.
Could you please elaborate on what you mean by that? How is having any Open Source program included in a distribution in anyway restrictive?Open source can be restrictive if part of popular distribution
As do most Pi users and people who are into software in general.I enjoy the freedom to innovate by gluing stuff together.
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.
Memory in C++ is a leaky abstraction .
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
- Contact: Website Twitter
Re: A Final Fibonacci Challenge
What are the chances you could get an enhancement you like into the Python / Raspian distribution?
Re: A Final Fibonacci Challenge
ScriptBasic,
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.
Slim to none of course.What are the chances you could get an enhancement you like into the Python / Raspian distribution?
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.
Memory in C++ is a leaky abstraction .
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!
Of course I cheated with the glue a bit...$ time node fibo_karatsuba.js | head -c 32
10727395641800477229364813596225
real 0m2.768s
user 0m2.609s
sys 0m0.453s
Memory in C++ is a leaky abstraction .
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
- Contact: Website Twitter
Re: A Final Fibonacci Challenge
Sounds like you use GMP fibo.
-
- Posts: 3531
- Joined: Thu Dec 27, 2012 4:05 am
- Location: Québec, Canada
Re: A Final Fibonacci Challenge
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.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.
I still have to work on my multiplication function which is not effective.
Re: A Final Fibonacci Challenge
From the name, it would appear you used the Karatsuba algorithm and built-in big numbers for the limbs.Heater wrote: ↑Fri Jun 07, 2019 6:03 amSpeaking 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!Of course I cheated with the glue a bit...$ time node fibo_karatsuba.js | head -c 32
10727395641800477229364813596225
real 0m2.768s
user 0m2.609s
sys 0m0.453s
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
I HAS A PADLIMIT ITZ QUOSHUNT OF RADIX AN 10
HOW IZ I PADZERO YR X
I HAS A Y ITZ X
IM IN YR PADDIN
BOTH SAEM PADLIMIT AN SMALLR OF PADLIMIT AN Y, O RLY?
YA RLY
VISIBLE X!
GTFO
OIC
VISIBLE "0"!
Y R PRODUKT OF Y AN 10
IM OUTTA YR PADDIN
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
IM OUTTA YR ADDIN
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
Code: Select all
$ lci haifibo.lol
? 1
1
? 6
8
? 100
354224848179261915075
? 200
280571172992510140037611932413038677189525
? 500
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
? 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
? 7499
7060398799376784390080431403153762407133523390537059878104950622786388718825722561078363937111808052845829043934364899297524579596771135537480100208027085369896805936602227218581761602607709602334939889484798397142942218388978326231083561149392205369863825989576207551146164545991161518248812602059748659792822539047900440615827674362997814592886203623387177745482781961764037789256204211876516867755389327862471098927207504535260828110167596703760822462988717005213704260555517262693067390672579278642451139772159098237484766060153417966500228867893493613281899397919811817985526393984078448175231602116343732669535382592866176830021901276573501388490142960269573429689010342153684955910446206097236075006861770107503447313897585687337597851533416564601034740128818628864559166341653871747561460183576425048959152474006524376867108154719826724951577811058520409795890271953207501037389580837065627491303664939319008074326639606500449899956261137209763009997639133968161102379352100526521219319009668949360509017190305822205735637047582596844361054536570105575658758958126781615314786897307911885991922151961963946513621905753392384260111071739837465056829372023129875545405507382500246527434315392215299304419577933704415638169229147761482551989210536522219106497198930639764648714287173928443999657477934962619150591299808484015221733892947047898044789624388717645430081789847014505889073245674298227489060602274996337440845903140973613284173331051297305566669585112157848209843391912656796627677634633934542271164812214908073040748492419868112329633702241675255001
? 0
Last edited by ejolson on Sat Jun 08, 2019 7:23 pm, edited 5 times in total.
Re: A Final Fibonacci Challenge
ejolson,

More later when I get it running how I like.
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?
Yes. And no.From the name, it would appear you used the Karatsuba algorithm and built-in big numbers for the limbs.

More later when I get it running how I like.
OMG. WTF?In a completely different direction, there is a programming language called LOLCODE...
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?
Memory in C++ is a leaky abstraction .
Re: A Final Fibonacci Challenge
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?
Re: A Final Fibonacci Challenge
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: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
- Contact: Website Twitter
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.
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...
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.
Memory in C++ is a leaky abstraction .
Re: A Final Fibonacci 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).ScriptBasic wrote: ↑Sat Jun 08, 2019 4:35 pmIf 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.
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.
Re: A Final Fibonacci Challenge
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.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 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?
Re: A Final Fibonacci Challenge
ejolson,
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:
FO SHIZZLE, MA NIZZLE!High-performance extensions to the poetic cat-friendly meme-based programming language described in this research entitled "I CAN HAS SUPERCOMPUTER?"...
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
Memory in C++ is a leaky abstraction .