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
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
```

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.