Page 18 of 67

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 9:37 pm
Everything is negative and the wrong result.

Old Schoolboy at least could could come up with a correct answer even if it was heavy lifting.

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:04 pm
ScriptBasic wrote:
Fri Jun 14, 2019 9:37 pm
Everything is negative and the wrong result.

Old Schoolboy at least could could come up with a correct answer even if it was heavy lifting.
Try changing

if n <= 2 THEN

to

if n < 2 THEN

and see if that fixes it.

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:06 pm
Nope.

Code: Select all

``````function hfibo(n)
if n <= 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(10)),"\n"
``````

Code: Select all

``````DECLARE SUB fibo ALIAS "fibo" LIB "gmp"

PRINT fibo(10),"\n"
``````
Output

Code: Select all

``````jrs@jrs-laptop:~/sb/GMP\$ scriba nfibo.sb
-15
jrs@jrs-laptop:~/sb/GMP\$ scriba ../examples/test/fibo.sb
55
jrs@jrs-laptop:~/sb/GMP\$
``````

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:16 pm

Code: Select all

``````function hfibo(n)
if n < 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(10)),"\n"
``````
jrs@jrs-laptop:~/sb/GMP\$ scriba nfibo.sb
Segmentation fault (core dumped)
jrs@jrs-laptop:~/sb/GMP\$

That's rare! (possible recursion overflow?)

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:24 pm
ScriptBasic wrote:
Fri Jun 14, 2019 10:16 pm

Code: Select all

``````function hfibo(n)
if n < 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(10)),"\n"
``````
jrs@jrs-laptop:~/sb/GMP\$ scriba nfibo.sb
Segmentation fault (core dumped)
jrs@jrs-laptop:~/sb/GMP\$
I guess not that then.

The base case for the recursion (first branch in the conditional) should agree with

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2

I'm not sure what the original code did. Currently I'm away from my computer, so I can't help much more. I'm certain it will eventually work.

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:27 pm
You have ScriptBasic running on your box. Can you give the script a try when you get home?

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 10:41 pm
Does anyone have a fibo routine beyond schoolboy that I can try?

### Re: A Final Fibonacci Challenge

Posted: Fri Jun 14, 2019 11:41 pm
It looks like SchoolBoy takes home the prize. All the recursive attempts were way too slow. What might be happening is ScriptBasic is not doing compares as we assume when one is a number and the other a string.

Code: Select all

``````a = 1
b = "5"

IF b > a THEN
PRINT "It Works!\n"
ELSE
PRINT "Nope.\n"
END IF

jrs@jrs-laptop:~/sb/GMP\$ scriba comptest.sb
It Works!
jrs@jrs-laptop:~/sb/GMP\$
``````

Code: Select all

``````DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"

FUNCTION sfibo (n)
IF n < 2 THEN
sfibo = 1
ELSE
m = 0
p = 1
q = 0
FOR i = 2 TO n
q = p
p = m
NEXT i
sfibo = m
END IF
END FUNCTION

PRINT sfibo(7500),"\n"
``````
Output

Code: Select all

``````jrs@jrs-laptop:~/sb/GMP\$ time scriba sbfibo
11423965231520587047220488928656904198487186633317560797959030595738263643588305263964321080516991429937628886229555340146644442744473185460778302934743807002248109695741208782411159189994651520930091202035101269350523609417276542209682261168150544790025062794209091503702088574338650460569295592498666443239807989522593072562158640947468656887645879356201301594841872491497556389555817277508349058330498007583814270123329724353233156029127910968370052734811192660492733375394472692191584489489590970254440914222778382439339334175624660291588778456250479185237898309112318829984358216337347549014336517486496643224502773380042071174360597192343056318489287038447004730922073980870072990706067508624038407888471294048912294153491398930715643640170172837379127969101176561450586945715460276780809807889664272818316865711724985646554559305334340318994612185260719042008960311269000122672589731283419608098303367260382379660402261886574952211783683104453334281684425994447306306414660032519055079504313562694958935754118796157632978970220780288168992181699708922971417067735144929461193639081445200786881549331150381216073705417531166786634690469206418611524663013854198045284806720735273715046888704916821855277543026346215355286395854263168251068150374988851620501196943905031285049077628443804052134507022504682483293396215268186620124762379744668092166035314553541731537245946256422861852573006230492322259630342294350827184840607509969289328320360093204783447860955806396350723341261564285649453007949089154165288839814442677339344794691881510389855765582716774490000

real	0m0.695s
user	0m0.253s
sys	0m0.024s
jrs@jrs-laptop:~/sb/GMP\$
``````
SchoolBoy at 78000 which is 1000 times greater than I can do without GMP support.

Code: Select all

``````jrs@jrs-laptop:~/sb/GMP\$ time scriba sbfibo > sbfibo.out

real	0m41.990s
user	0m41.086s
sys	0m0.868s
jrs@jrs-laptop:~/sb/GMP\$
``````
At this point ScriptBasic has already achieved its goal of adding BIGINT support seamlessly. Anything beyond this is icing for me.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 12:49 am
Fibonacci 500

Code: Select all

``````DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"

FUNCTION sfibo (n)
IF n < 2 THEN
sfibo = 1
PRINT "[1] - 1\n"
ELSE
m = 0
p = 1
q = 0
FOR i = 2 TO n
q = p
p = m
PRINT "[",i,"] - ", m, "\n"
NEXT i
END IF
END FUNCTION

sfibo(500)
``````
Output

Code: Select all

``````jrs@jrs-laptop:~/sb/GMP\$ time scriba fibo500.sb
[2] - 1
[3] - 2
[4] - 3
[5] - 5
[6] - 8
[7] - 13
[8] - 21
[9] - 34
[10] - 55
[11] - 89
[12] - 144
[13] - 233
[14] - 377
[15] - 610
[16] - 987
[17] - 1597
[18] - 2584
[19] - 4181
[20] - 6765
[21] - 10946
[22] - 17711
[23] - 28657
[24] - 46368
[25] - 75025
[26] - 121393
[27] - 196418
[28] - 317811
[29] - 514229
[30] - 832040
[31] - 1346269
[32] - 2178309
[33] - 3524578
[34] - 5702887
[35] - 9227465
[36] - 14930352
[37] - 24157817
[38] - 39088169
[39] - 63245986
[40] - 102334155
[41] - 165580141
[42] - 267914296
[43] - 433494437
[44] - 701408733
[45] - 1134903170
[46] - 1836311903
[47] - 2971215073
[48] - 4807526976
[49] - 7778742049
[50] - 12586269025
[51] - 20365011074
[52] - 32951280099
[53] - 53316291173
[54] - 86267571272
[55] - 139583862445
[56] - 225851433717
[57] - 365435296162
[58] - 591286729879
[59] - 956722026041
[60] - 1548008755920
[61] - 2504730781961
[62] - 4052739537881
[63] - 6557470319842
[64] - 10610209857723
[65] - 17167680177565
[66] - 27777890035288
[67] - 44945570212853
[68] - 72723460248141
[69] - 117669030460994
[70] - 190392490709135
[71] - 308061521170129
[72] - 498454011879264
[73] - 806515533049393
[74] - 1304969544928657
[75] - 2111485077978050
[76] - 3416454622906707
[77] - 5527939700884757
[78] - 8944394323791464
[79] - 14472334024676221
[80] - 23416728348467685
[81] - 37889062373143906
[82] - 61305790721611591
[83] - 99194853094755497
[84] - 160500643816367088
[85] - 259695496911122585
[86] - 420196140727489673
[87] - 679891637638612258
[88] - 1100087778366101931
[89] - 1779979416004714189
[90] - 2880067194370816120
[91] - 4660046610375530309
[92] - 7540113804746346429
[93] - 12200160415121876738
[94] - 19740274219868223167
[95] - 31940434634990099905
[96] - 51680708854858323072
[97] - 83621143489848422977
[98] - 135301852344706746049
[99] - 218922995834555169026
[100] - 354224848179261915075
[101] - 573147844013817084101
[102] - 927372692193078999176
[103] - 1500520536206896083277
[104] - 2427893228399975082453
[105] - 3928413764606871165730
[106] - 6356306993006846248183
[107] - 10284720757613717413913
[108] - 16641027750620563662096
[109] - 26925748508234281076009
[110] - 43566776258854844738105
[111] - 70492524767089125814114
[112] - 114059301025943970552219
[113] - 184551825793033096366333
[114] - 298611126818977066918552
[115] - 483162952612010163284885
[116] - 781774079430987230203437
[117] - 1264937032042997393488322
[118] - 2046711111473984623691759
[119] - 3311648143516982017180081
[120] - 5358359254990966640871840
[121] - 8670007398507948658051921
[122] - 14028366653498915298923761
[123] - 22698374052006863956975682
[124] - 36726740705505779255899443
[125] - 59425114757512643212875125
[126] - 96151855463018422468774568
[127] - 155576970220531065681649693
[128] - 251728825683549488150424261
[129] - 407305795904080553832073954
[130] - 659034621587630041982498215
[131] - 1066340417491710595814572169
[132] - 1725375039079340637797070384
[133] - 2791715456571051233611642553
[134] - 4517090495650391871408712937
[135] - 7308805952221443105020355490
[136] - 11825896447871834976429068427
[137] - 19134702400093278081449423917
[138] - 30960598847965113057878492344
[139] - 50095301248058391139327916261
[140] - 81055900096023504197206408605
[141] - 131151201344081895336534324866
[142] - 212207101440105399533740733471
[143] - 343358302784187294870275058337
[144] - 555565404224292694404015791808
[145] - 898923707008479989274290850145
[146] - 1454489111232772683678306641953
[147] - 2353412818241252672952597492098
[148] - 3807901929474025356630904134051
[149] - 6161314747715278029583501626149
[150] - 9969216677189303386214405760200
[151] - 16130531424904581415797907386349
[152] - 26099748102093884802012313146549
[153] - 42230279526998466217810220532898
[154] - 68330027629092351019822533679447
[155] - 110560307156090817237632754212345
[156] - 178890334785183168257455287891792
[157] - 289450641941273985495088042104137
[158] - 468340976726457153752543329995929
[159] - 757791618667731139247631372100066
[160] - 1226132595394188293000174702095995
[161] - 1983924214061919432247806074196061
[162] - 3210056809456107725247980776292056
[163] - 5193981023518027157495786850488117
[164] - 8404037832974134882743767626780173
[165] - 13598018856492162040239554477268290
[166] - 22002056689466296922983322104048463
[167] - 35600075545958458963222876581316753
[168] - 57602132235424755886206198685365216
[169] - 93202207781383214849429075266681969
[170] - 150804340016807970735635273952047185
[171] - 244006547798191185585064349218729154
[172] - 394810887814999156320699623170776339
[173] - 638817435613190341905763972389505493
[174] - 1033628323428189498226463595560281832
[175] - 1672445759041379840132227567949787325
[176] - 2706074082469569338358691163510069157
[177] - 4378519841510949178490918731459856482
[178] - 7084593923980518516849609894969925639
[179] - 11463113765491467695340528626429782121
[180] - 18547707689471986212190138521399707760
[181] - 30010821454963453907530667147829489881
[182] - 48558529144435440119720805669229197641
[183] - 78569350599398894027251472817058687522
[184] - 127127879743834334146972278486287885163
[185] - 205697230343233228174223751303346572685
[186] - 332825110087067562321196029789634457848
[187] - 538522340430300790495419781092981030533
[188] - 871347450517368352816615810882615488381
[189] - 1409869790947669143312035591975596518914
[190] - 2281217241465037496128651402858212007295
[191] - 3691087032412706639440686994833808526209
[192] - 5972304273877744135569338397692020533504
[193] - 9663391306290450775010025392525829059713
[194] - 15635695580168194910579363790217849593217
[195] - 25299086886458645685589389182743678652930
[196] - 40934782466626840596168752972961528246147
[197] - 66233869353085486281758142155705206899077
[198] - 107168651819712326877926895128666735145224
[199] - 173402521172797813159685037284371942044301
[200] - 280571172992510140037611932413038677189525
[201] - 453973694165307953197296969697410619233826
[202] - 734544867157818093234908902110449296423351
[203] - 1188518561323126046432205871807859915657177
[204] - 1923063428480944139667114773918309212080528
[205] - 3111581989804070186099320645726169127737705
[206] - 5034645418285014325766435419644478339818233
[207] - 8146227408089084511865756065370647467555938
[208] - 13180872826374098837632191485015125807374171
[209] - 21327100234463183349497947550385773274930109
[210] - 34507973060837282187130139035400899082304280
[211] - 55835073295300465536628086585786672357234389
[212] - 90343046356137747723758225621187571439538669
[213] - 146178119651438213260386312206974243796773058
[214] - 236521166007575960984144537828161815236311727
[215] - 382699285659014174244530850035136059033084785
[216] - 619220451666590135228675387863297874269396512
[217] - 1001919737325604309473206237898433933302481297
[218] - 1621140188992194444701881625761731807571877809
[219] - 2623059926317798754175087863660165740874359106
[220] - 4244200115309993198876969489421897548446236915
[221] - 6867260041627791953052057353082063289320596021
[222] - 11111460156937785151929026842503960837766832936
[223] - 17978720198565577104981084195586024127087428957
[224] - 29090180355503362256910111038089984964854261893
[225] - 47068900554068939361891195233676009091941690850
[226] - 76159080909572301618801306271765994056795952743
[227] - 123227981463641240980692501505442003148737643593
[228] - 199387062373213542599493807777207997205533596336
[229] - 322615043836854783580186309282650000354271239929
[230] - 522002106210068326179680117059857997559804836265
[231] - 844617150046923109759866426342507997914076076194
[232] - 1366619256256991435939546543402365995473880912459
[233] - 2211236406303914545699412969744873993387956988653
[234] - 3577855662560905981638959513147239988861837901112
[235] - 5789092068864820527338372482892113982249794889765
[236] - 9366947731425726508977331996039353971111632790877
[237] - 15156039800290547036315704478931467953361427680642
[238] - 24522987531716273545293036474970821924473060471519
[239] - 39679027332006820581608740953902289877834488152161
[240] - 64202014863723094126901777428873111802307548623680
[241] - 103881042195729914708510518382775401680142036775841
[242] - 168083057059453008835412295811648513482449585399521
[243] - 271964099255182923543922814194423915162591622175362
[244] - 440047156314635932379335110006072428645041207574883
[245] - 712011255569818855923257924200496343807632829750245
[246] - 1152058411884454788302593034206568772452674037325128
[247] - 1864069667454273644225850958407065116260306867075373
[248] - 3016128079338728432528443992613633888712980904400501
[249] - 4880197746793002076754294951020699004973287771475874
[250] - 7896325826131730509282738943634332893686268675876375
[251] - 12776523572924732586037033894655031898659556447352249
[252] - 20672849399056463095319772838289364792345825123228624
[253] - 33449372971981195681356806732944396691005381570580873
[254] - 54122222371037658776676579571233761483351206693809497
[255] - 87571595343018854458033386304178158174356588264390370
[256] - 141693817714056513234709965875411919657707794958199867
[257] - 229265413057075367692743352179590077832064383222590237
[258] - 370959230771131880927453318055001997489772178180790104
[259] - 600224643828207248620196670234592075321836561403380341
[260] - 971183874599339129547649988289594072811608739584170445
[261] - 1571408518427546378167846658524186148133445300987550786
[262] - 2542592393026885507715496646813780220945054040571721231
[263] - 4114000911454431885883343305337966369078499341559272017
[264] - 6656593304481317393598839952151746590023553382130993248
[265] - 10770594215935749279482183257489712959102052723690265265
[266] - 17427187520417066673081023209641459549125606105821258513
[267] - 28197781736352815952563206467131172508227658829511523778
[268] - 45624969256769882625644229676772632057353264935332782291
[269] - 73822750993122698578207436143903804565580923764844306069
[270] - 119447720249892581203851665820676436622934188700177088360
[271] - 193270471243015279782059101964580241188515112465021394429
[272] - 312718191492907860985910767785256677811449301165198482789
[273] - 505988662735923140767969869749836918999964413630219877218
[274] - 818706854228831001753880637535093596811413714795418360007
[275] - 1324695516964754142521850507284930515811378128425638237225
[276] - 2143402371193585144275731144820024112622791843221056597232
[277] - 3468097888158339286797581652104954628434169971646694834457
[278] - 5611500259351924431073312796924978741056961814867751431689
[279] - 9079598147510263717870894449029933369491131786514446266146
[280] - 14691098406862188148944207245954912110548093601382197697835
[281] - 23770696554372451866815101694984845480039225387896643963981
[282] - 38461794961234640015759308940939757590587318989278841661816
[283] - 62232491515607091882574410635924603070626544377175485625797
[284] - 100694286476841731898333719576864360661213863366454327287613
[285] - 162926777992448823780908130212788963731840407743629812913410
[286] - 263621064469290555679241849789653324393054271110084140201023
[287] - 426547842461739379460149980002442288124894678853713953114433
[288] - 690168906931029935139391829792095612517948949963798093315456
[289] - 1116716749392769314599541809794537900642843628817512046429889
[290] - 1806885656323799249738933639586633513160792578781310139745345
[291] - 2923602405716568564338475449381171413803636207598822186175234
[292] - 4730488062040367814077409088967804926964428786380132325920579
[293] - 7654090467756936378415884538348976340768064993978954512095813
[294] - 12384578529797304192493293627316781267732493780359086838016392
[295] - 20038668997554240570909178165665757608500558774338041350112205
[296] - 32423247527351544763402471792982538876233052554697128188128597
[297] - 52461916524905785334311649958648296484733611329035169538240802
[298] - 84885164052257330097714121751630835360966663883732297726369399
[299] - 137347080577163115432025771710279131845700275212767467264610201
[300] - 222232244629420445529739893461909967206666939096499764990979600
[301] - 359579325206583560961765665172189099052367214309267232255589801
[302] - 581811569836004006491505558634099066259034153405766997246569401
[303] - 941390895042587567453271223806288165311401367715034229502159202
[304] - 1523202464878591573944776782440387231570435521120801226748728603
[305] - 2464593359921179141398048006246675396881836888835835456250887805
[306] - 3987795824799770715342824788687062628452272409956636682999616408
[307] - 6452389184720949856740872794933738025334109298792472139250504213
[308] - 10440185009520720572083697583620800653786381708749108822250120621
[309] - 16892574194241670428824570378554538679120491007541580961500624834
[310] - 27332759203762391000908267962175339332906872716290689783750745455
[311] - 44225333398004061429732838340729878012027363723832270745251370289
[312] - 71558092601766452430641106302905217344934236440122960529002115744
[313] - 115783425999770513860373944643635095356961600163955231274253486033
[314] - 187341518601536966291015050946540312701895836604078191803255601777
[315] - 303124944601307480151388995590175408058857436768033423077509087810
[316] - 490466463202844446442404046536715720760753273372111614880764689587
[317] - 793591407804151926593793042126891128819610710140145037958273777397
[318] - 1284057871006996373036197088663606849580363983512256652839038466984
[319] - 2077649278811148299629990130790497978399974693652401690797312244381
[320] - 3361707149818144672666187219454104827980338677164658343636350711365
[321] - 5439356428629292972296177350244602806380313370817060034433662955746
[322] - 8801063578447437644962364569698707634360652047981718378070013667111
[323] - 14240420007076730617258541919943310440740965418798778412503676622857
[324] - 23041483585524168262220906489642018075101617466780496790573690289968
[325] - 37281903592600898879479448409585328515842582885579275203077366912825
[326] - 60323387178125067141700354899227346590944200352359771993651057202793
[327] - 97605290770725966021179803308812675106786783237939047196728424115618
[328] - 157928677948851033162880158208040021697730983590298819190379481318411
[329] - 255533968719576999184059961516852696804517766828237866387107905434029
[330] - 413462646668428032346940119724892718502248750418536685577487386752440
[331] - 668996615388005031531000081241745415306766517246774551964595292186469
[332] - 1082459262056433063877940200966638133809015267665311237542082678938909
[333] - 1751455877444438095408940282208383549115781784912085789506677971125378
[334] - 2833915139500871159286880483175021682924797052577397027048760650064287
[335] - 4585371016945309254695820765383405232040578837489482816555438621189665
[336] - 7419286156446180413982701248558426914965375890066879843604199271253952
[337] - 12004657173391489668678522013941832147005954727556362660159637892443617
[338] - 19423943329837670082661223262500259061971330617623242503763837163697569
[339] - 31428600503229159751339745276442091208977285345179605163923475056141186
[340] - 50852543833066829834000968538942350270948615962802847667687312219838755
[341] - 82281144336295989585340713815384441479925901307982452831610787275979941
[342] - 133133688169362819419341682354326791750874517270785300499298099495818696
[343] - 215414832505658809004682396169711233230800418578767753330908886771798637
[344] - 348548520675021628424024078524038024981674935849553053830206986267617333
[345] - 563963353180680437428706474693749258212475354428320807161115873039415970
[346] - 912511873855702065852730553217787283194150290277873860991322859307033303
[347] - 1476475227036382503281437027911536541406625644706194668152438732346449273
[348] - 2388987100892084569134167581129323824600775934984068529143761591653482576
[349] - 3865462327928467072415604609040860366007401579690263197296200323999931849
[350] - 6254449428820551641549772190170184190608177514674331726439961915653414425
[351] - 10119911756749018713965376799211044556615579094364594923736162239653346274
[352] - 16374361185569570355515148989381228747223756609038926650176124155306760699
[353] - 26494272942318589069480525788592273303839335703403521573912286394960106973
[354] - 42868634127888159424995674777973502051063092312442448224088410550266867672
[355] - 69362907070206748494476200566565775354902428015845969798000696945226974645
[356] - 112231541198094907919471875344539277405965520328288418022089107495493842317
[357] - 181594448268301656413948075911105052760867948344134387820089804440720816962
[358] - 293825989466396564333419951255644330166833468672422805842178911936214659279
[359] - 475420437734698220747368027166749382927701417016557193662268716376935476241
[360] - 769246427201094785080787978422393713094534885688979999504447628313150135520
[361] - 1244666864935793005828156005589143096022236302705537193166716344690085611761
[362] - 2013913292136887790908943984011536809116771188394517192671163973003235747281
[363] - 3258580157072680796737099989600679905139007491100054385837880317693321359042
[364] - 5272493449209568587646043973612216714255778679494571578509044290696557106323
[365] - 8531073606282249384383143963212896619394786170594625964346924608389878465365
[366] - 13803567055491817972029187936825113333650564850089197542855968899086435571688
[367] - 22334640661774067356412331900038009953045351020683823507202893507476314037053
[368] - 36138207717265885328441519836863123286695915870773021050058862406562749608741
[369] - 58472848379039952684853851736901133239741266891456844557261755914039063645794
[370] - 94611056096305838013295371573764256526437182762229865607320618320601813254535
[371] - 153083904475345790698149223310665389766178449653686710164582374234640876900329
[372] - 247694960571651628711444594884429646292615632415916575771902992555242690154864
[373] - 400778865046997419409593818195095036058794082069603285936485366789883567055193
[374] - 648473825618649048121038413079524682351409714485519861708388359345126257210057
[375] - 1049252690665646467530632231274619718410203796555123147644873726135009824265250
[376] - 1697726516284295515651670644354144400761613511040643009353262085480136081475307
[377] - 2746979206949941983182302875628764119171817307595766156998135811615145905740557
[378] - 4444705723234237498833973519982908519933430818636409166351397897095281987215864
[379] - 7191684930184179482016276395611672639105248126232175323349533708710427892956421
[380] - 11636390653418416980850249915594581159038678944868584489700931605805709880172285
[381] - 18828075583602596462866526311206253798143927071100759813050465314516137773128706
[382] - 30464466237021013443716776226800834957182606015969344302751396920321847653300991
[383] - 49292541820623609906583302538007088755326533087070104115801862234837985426429697
[384] - 79757008057644623350300078764807923712509139103039448418553259155159833079730688
[385] - 129049549878268233256883381302815012467835672190109552534355121389997818506160385
[386] - 208806557935912856607183460067622936180344811293149000952908380545157651585891073
[387] - 337856107814181089864066841370437948648180483483258553487263501935155470092051458
[388] - 546662665750093946471250301438060884828525294776407554440171882480313121677942531
[389] - 884518773564275036335317142808498833476705778259666107927435384415468591769993989
[390] - 1431181439314368982806567444246559718305231073036073662367607266895781713447936520
[391] - 2315700212878644019141884587055058551781936851295739770295042651311250305217930509
[392] - 3746881652193013001948452031301618270087167924331813432662649918207032018665867029
[393] - 6062581865071657021090336618356676821869104775627553202957692569518282323883797538
[394] - 9809463517264670023038788649658295091956272699959366635620342487725314342549664567
[395] - 15872045382336327044129125268014971913825377475586919838578035057243596666433462105
[396] - 25681508899600997067167913917673267005781650175546286474198377544968911008983126672
[397] - 41553554281937324111297039185688238919607027651133206312776412602212507675416588777
[398] - 67235063181538321178464953103361505925388677826679492786974790147181418684399715449
[399] - 108788617463475645289761992289049744844995705477812699099751202749393926359816304226
[400] - 176023680645013966468226945392411250770384383304492191886725992896575345044216019675
[401] - 284812298108489611757988937681460995615380088782304890986477195645969271404032323901
[402] - 460835978753503578226215883073872246385764472086797082873203188542544616448248343576
[403] - 745648276861993189984204820755333242001144560869101973859680384188513887852280667477
[404] - 1206484255615496768210420703829205488386909032955899056732883572731058504300529011053
[405] - 1952132532477489958194625524584538730388053593825001030592563956919572392152809678530
[406] - 3158616788092986726405046228413744218774962626780900087325447529650630896453338689583
[407] - 5110749320570476684599671752998282949163016220605901117918011486570203288606148368113
[408] - 8269366108663463411004717981412027167937978847386801205243459016220834185059487057696
[409] - 13380115429233940095604389734410310117100995067992702323161470502791037473665635425809
[410] - 21649481537897403506609107715822337285038973915379503528404929519011871658725122483505
[411] - 35029596967131343602213497450232647402139968983372205851566400021802909132390757909314
[412] - 56679078505028747108822605166054984687178942898751709379971329540814780791115880392819
[413] - 91708675472160090711036102616287632089318911882123915231537729562617689923506638302133
[414] - 148387753977188837819858707782342616776497854780875624611509059103432470714622518694952
[415] - 240096429449348928530894810398630248865816766662999539843046788666050160638129156997085
[416] - 388484183426537766350753518180972865642314621443875164454555847769482631352751675692037
[417] - 628580612875886694881648328579603114508131388106874704297602636435532791990880832689122
[418] - 1017064796302424461232401846760575980150446009550749868752158484205015423343632508381159
[419] - 1645645409178311156114050175340179094658577397657624573049761120640548215334513341070281
[420] - 2662710205480735617346452022100755074809023407208374441801919604845563638678145849451440
[421] - 4308355614659046773460502197440934169467600804865999014851680725486111854012659190521721
[422] - 6971065820139782390806954219541689244276624212074373456653600330331675492690805039973161
[423] - 11279421434798829164267456416982623413744225016940372471505281055817787346703464230494882
[424] - 18250487254938611555074410636524312658020849229014745928158881386149462839394269270468043
[425] - 29529908689737440719341867053506936071765074245955118399664162441967250186097733500962925
[426] - 47780395944676052274416277690031248729785923474969864327823043828116713025492002771430968
[427] - 77310304634413492993758144743538184801550997720924982727487206270083963211589736272393893
[428] - 125090700579089545268174422433569433531336921195894847055310250098200676237081739043824861
[429] - 202401005213503038261932567177107618332887918916819829782797456368284639448671475316218754
[430] - 327491705792592583530106989610677051864224840112714676838107706466485315685753214360043615
[431] - 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369
[432] - 857384416798688205322146546398461722061337599142249183459012869301255270820177904036305984
[433] - 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353
[434] - 2244661544603472032436332649584708114319787957314032873538930901437280496774780497748874337
[435] - 3631938672408255859550518752770954506578238315485816563618848933573305722729383091461442690
[436] - 5876600217011727891986851402355662620898026272799849437157779835010586219504163589210317027
[437] - 9508538889419983751537370155126617127476264588285666000776628768583891942233546680671759717
[438] - 15385139106431711643524221557482279748374290861085515437934408603594478161737710269882076744
[439] - 24893677995851695395061591712608896875850555449371181438711037372178370103971256950553836461
[440] - 40278817102283407038585813270091176624224846310456696876645445975772848265708967220435913205
[441] - 65172495098135102433647404982700073500075401759827878315356483347951218369680224170989749666
[442] - 105451312200418509472233218252791250124300248070284575192001929323724066635389191391425662871
[443] - 170623807298553611905880623235491323624375649830112453507358412671675285005069415562415412537
[444] - 276075119498972121378113841488282573748675897900397028699360341995399351640458606953841075408
[445] - 446698926797525733283994464723773897373051547730509482206718754667074636645528022516256487945
[446] - 722774046296497854662108306212056471121727445630906510906079096662473988285986629470097563353
[447] - 1169472973094023587946102770935830368494778993361415993112797851329548624931514651986354051298
[448] - 1892247019390521442608211077147886839616506438992322504018876947992022613217501281456451614651
[449] - 3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949
[450] - 4953967011875066473162524925231604047727791871346061001150551747313593851366517214899257280600
[451] - 8015687004359611503716838773315321255839077303699799498282226546635165089515533148342062946549
[452] - 12969654016234677976879363698546925303566869175045860499432778293948758940882050363241320227149
[453] - 20985341020594289480596202471862246559405946478745659997715004840583924030397583511583383173698
[454] - 33954995036828967457475566170409171862972815653791520497147783134532682971279633874824703400847
[455] - 54940336057423256938071768642271418422378762132537180494862787975116607001677217386408086574545
[456] - 88895331094252224395547334812680590285351577786328700992010571109649289972956851261232789975392
[457] - 143835667151675481333619103454952008707730339918865881486873359084765896974634068647640876549937
[458] - 232730998245927705729166438267632598993081917705194582478883930194415186947590919908873666525329
[459] - 376566665397603187062785541722584607700812257624060463965757289279181083922224988556514543075266
[460] - 609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595
[461] - 985864329041134079854737521712801814394706432953315510410398508752777354792040897021902752675861
[462] - 1595161992684664972646689501703019021088600608282570556855039728226373625661856805487290962276456
[463] - 2581026321725799052501427023415820835483307041235886067265438236979150980453897702509193714952317
[464] - 4176188314410464025148116525118839856571907649518456624120477965205524606115754507996484677228773
[465] - 6757214636136263077649543548534660692055214690754342691385916202184675586569652210505678392181090
[466] - 10933402950546727102797660073653500548627122340272799315506394167390200192685406718502163069409863
[467] - 17690617586682990180447203622188161240682337031027142006892310369574875779255058929007841461590953
[468] - 28624020537229717283244863695841661789309459371299941322398704536965075971940465647510004531000816
[469] - 46314638123912707463692067318029823029991796402327083329291014906539951751195524576517845992591769
[470] - 74938658661142424746936931013871484819301255773627024651689719443505027723135990224027850523592585
[471] - 121253296785055132210628998331901307849293052175954107980980734350044979474331514800545696516184354
[472] - 196191955446197556957565929345772792668594307949581132632670453793550007197467505024573547039776939
[473] - 317445252231252689168194927677674100517887360125535240613651188143594986671799019825119243555961293
[474] - 513637207677450246125760857023446893186481668075116373246321641937144993869266524849692790595738232
[475] - 831082459908702935293955784701120993704369028200651613859972830080739980541065544674812034151699525
[476] - 1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757
[477] - 2175802127494856116713672426425688880595219724476419600966267302098624954951397614199316858899137282
[478] - 3520521795081009298133389068150256767486070420752187588072561774116509929361729683723821683646575039
[479] - 5696323922575865414847061494575945648081290145228607189038829076215134884313127297923138542545712321
[480] - 9216845717656874712980450562726202415567360565980794777111390850331644813674856981646960226192287360
[481] - 14913169640232740127827512057302148063648650711209401966150219926546779697987984279570098768737999681
[482] - 24130015357889614840807962620028350479216011277190196743261610776878424511662841261217058994930287041
[483] - 39043184998122354968635474677330498542864661988399598709411830703425204209650825540787157763668286722
[484] - 63173200356011969809443437297358849022080673265589795452673441480303628721313666802004216758598573763
[485] - 102216385354134324778078911974689347564945335253989394162085272183728832930964492342791374522266860485
[486] - 165389585710146294587522349272048196587026008519579189614758713664032461652278159144795591280865434248
[487] - 267605971064280619365601261246737544151971343773568583776843985847761294583242651487586965803132294733
[488] - 432995556774426913953123610518785740738997352293147773391602699511793756235520810632382557083997728981
[489] - 700601527838707533318724871765523284890968696066716357168446685359555050818763462119969522887130023714
[490] - 1133597084613134447271848482284309025629966048359864130560049384871348807054284272752352079971127752695
[491] - 1834198612451841980590573354049832310520934744426580487728496070230903857873047734872321602858257776409
[492] - 2967795697064976427862421836334141336150900792786444618288545455102252664927332007624673682829385529104
[493] - 4801994309516818408452995190383973646671835537213025106017041525333156522800379742496995285687643305513
[494] - 7769790006581794836315417026718114982822736329999469724305586980435409187727711750121668968517028834617
[495] - 12571784316098613244768412217102088629494571867212494830322628505768565710528091492618664254204672140130
[496] - 20341574322680408081083829243820203612317308197211964554628215486203974898255803242740333222721700974747
[497] - 32913358638779021325852241460922292241811880064424459384950843991972540608783894735358997476926373114877
[498] - 53254932961459429406936070704742495854129188261636423939579059478176515507039697978099330699648074089624
[499] - 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501
[500] - 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

real	0m0.017s
user	0m0.008s
sys	0m0.009s
jrs@jrs-laptop:~/sb/GMP\$
``````

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 2:10 am
ScriptBasic wrote:
Fri Jun 14, 2019 10:06 pm
Nope.

Code: Select all

``````function hfibo(n)
if n <= 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(10)),"\n"
``````

Code: Select all

``````DECLARE SUB fibo ALIAS "fibo" LIB "gmp"

PRINT fibo(10),"\n"
``````
Output

Code: Select all

``````jrs@jrs-laptop:~/sb/GMP\$ scriba nfibo.sb
-15
jrs@jrs-laptop:~/sb/GMP\$ scriba ../examples/test/fibo.sb
55
jrs@jrs-laptop:~/sb/GMP\$
``````
Further investigation seems to indicate the reason for the wrong answer is that the variables a, b, fk, fk1 and r appearing in the hfibo function have global scope in Script Basic. Adding a print statement to your code obtains

Code: Select all

``````\$ scriba double.bas
hfibo(2)=1
hfibo(1)=1
hfibo(2)=1
hfibo(3)=2
hfibo(1)=5
hfibo(2)=1
hfibo(10)=-15
-15
\$ cat double.bas
function hfibo(n)
if n <= 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
print "hfibo(",n,")=",r,"\n"
hfibo = r
end function

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(10)),"\n"``````
which nearly matches the output of the following C code:

Code: Select all

``````\$ gcc global.c
\$ ./a.out
hfibo(2)=1
hfibo(1)=1
hfibo(2)=1
hfibo(3)=2
hfibo(5)=5
hfibo(2)=1
hfibo(10)=-15
-15
\$ cat global.c
#include <stdio.h>

long a,b,fk,fk1,k,r;
long hfibo(long n){
if(n <= 2){
r = 1;
} else {
k = n / 2;
fk = hfibo(k);
fk1 = hfibo(k+1);
if(n%2 == 0){
a = fk1 + fk1;
b = a - fk;
r = fk * b;
} else {
a = fk * fk;
b = fk1 * fk1;
r = a + b;
}
}
printf("hfibo(%ld)=%ld\n",n,r);
return r;
}

int main(){
printf("%ld\n",hfibo(10));
return 0;
}``````
Note that the C code works fine if the variables are declared local as seen by

Code: Select all

``````\$ gcc local.c
\$ ./a.out
hfibo(2)=1
hfibo(1)=1
hfibo(2)=1
hfibo(3)=2
hfibo(5)=5
hfibo(1)=1
hfibo(2)=1
hfibo(3)=2
hfibo(2)=1
hfibo(1)=1
hfibo(2)=1
hfibo(3)=2
hfibo(4)=3
hfibo(6)=8
hfibo(10)=55
55
\$ cat local.c
#include <stdio.h>

long hfibo(long n){
long a,b,fk,fk1,k,r;
if(n <= 2){
r = 1;
} else {
k = n / 2;
fk = hfibo(k);
fk1 = hfibo(k+1);
if(n%2 == 0){
a = fk1 + fk1;
b = a - fk;
r = fk * b;
} else {
a = fk * fk;
b = fk1 * fk1;
r = a + b;
}
}
printf("hfibo(%ld)=%ld\n",n,r);
return r;
}

int main(){
printf("%ld\n",hfibo(10));
return 0;
}``````
Is there anyway to declare the variables a, b, fk, fk1, k and r to be local to the function hfibo in Script Basic?

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 2:21 am
here anyway to declare the variables a, b, fk, fk1, k and r to be local to the function hfibo in Script Basic?
Yes.

FUNCTION ejolson
LOCAL a, b, fk, fk1, k
.....
END FUNCTION

There is also an option you can enable that makes all variables In functions / subs LOCAL by default.

Good catch!

I'm still getting a segment fault not using GMP and a fibo(10).

Code: Select all

``````function hfibo(n)
local a, b, fk, fk1, k, r
split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1
if n < 2 then
hfibo = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

print format("%.f",hfibo(10)),"\n"

``````

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:16 am
ScriptBasic wrote:
Sat Jun 15, 2019 2:21 am
here anyway to declare the variables a, b, fk, fk1, k and r to be local to the function hfibo in Script Basic?
Yes.

FUNCTION ejolson
LOCAL a, b, fk, fk1, k
.....
END FUNCTION

There is also an option you can enable that makes all variables In functions / subs LOCAL by default.

Good catch!

I'm still getting a segment fault not using GMP and a fibo(10).

Code: Select all

``````function hfibo(n)
local a, b, fk, fk1, k, r
split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1
if n < 2 then
hfibo = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n % 2 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

print format("%.f",hfibo(10)),"\n"

``````
Please set the if statement back to n<=2. Also, do you need to make n local as well?

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:19 am
Making that change just returns zero. Good news the seg fault went away.

All arguments are LOCAL by default.

There is also a ByVal option so if you change a global variable in a function if has no effect on the caller.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:32 am
I think I owe an apology.

I screwed up that fiboNoMemo() I posted and ended up testing the wrong version of fibo so it looked like it worked here. Shame on me.

I have now rewritten it in the style of the last ScriptBasic version I have seen here so it should be easy to convert to ScriptBasic. And tested it properly!

Code: Select all

``````\$ cat hfibo.js
function hfibo (n) {
let result
if (n <= 2 ) {
result = BigInt((n & 3) != 0)
} else {
let k = (n / 2) | 0
let fk = hfibo(k);
let fk1 = hfibo(k + 1);
if ((n & 1) == 0) {
let a = fk1 + fk1
let b = a - fk
result = fk * b
} else {
let a = fk * fk
let b = fk1 * fk1
result = a + b
}
}
return result
}

console.log(hfibo(0))
console.log(hfibo(1))
console.log(hfibo(2))
console.log(hfibo(12))
console.log(hfibo(20000))
console.log(hfibo(4784969))
``````
That first part for the base cases looks a bit odd now, it just has to return 0, 1, or 1 as big integers for n = 0, 1, 2 respectively.

Results:

Code: Select all

``````\$ node  hfibo.js
0n
1n
1n
144n
253116232373236124224015500...
....
683971213093125n
107273956418004772293648135...
....
539211500699706378405156269n
``````
Takes about a minute for hfibo(4784969)

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:42 am
This still returns zero for me.

Code: Select all

``````function hfibo(n)
local a, b, fk, fk1, k, r
split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1
if n <= 2 then
hfibo = 1
else
k = n \ 2 or 0
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n and 1 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

print format("%.f",hfibo(10)),"\n"
``````

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:57 am
Heater,

How does this routine work for the Fibonacci 500 challenge?

In Python and JavaScript would be great.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 3:59 am
What does it return for:

hfibo(0)
hfibo(1)
hfibo(2)
hfibo(3)
?

You don't need the "or 0" in "k = n \ 2 or 0". That is just a Javascript thing to ensure the expression returns a 32 bit integer.

It should not make any difference but you have not fixed up the base case properly. fibo(0) will be wrong.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:07 am

Code: Select all

``````function hfibo(n)
local a, b, fk, fk1, k, r
split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1
if n <= 2 then
hfibo = 1
else
k = n \ 2 or 0
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n and 1 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function

for x = 0 to 3
print hfibo(x),"\n"
next
``````
jrs@jrs-laptop:~/sb/GMP\$ scriba nfibo.sb
0
0
0
0
jrs@jrs-laptop:~/sb/GMP\$

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:15 am
What fibo(500) challenge?

Anyway, very well:

hfibo.js

Code: Select all

``````\$ cat hfibo.js
function hfibo (n) {
let result
if (n <= 2 ) {
result = BigInt((n & 3) != 0)
} else {
let k = (n / 2) | 0
let fk = hfibo(k);
let fk1 = hfibo(k + 1);
if ((n & 1) == 0) {
let a = fk1 + fk1
let b = a - fk
result = fk * b
} else {
let a = fk * fk
let b = fk1 * fk1
result = a + b
}
}
return result
}

//console.log(hfibo(4784969))
console.log(hfibo(500))
\$ time node hfibo.js
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125n

real    0m0.092s
user    0m0.047s
sys     0m0.016s
\$
``````
hfibo.py

Code: Select all

``````\$ cat hfibo.py
def hfibo(n):
if n == 0:
return 0
if n < 2:
return 1
k = (n + 1) // 2
fk = hfibo(k)
fk1 = hfibo(k - 1)
if n & 1:
return fk ** 2 + fk1 ** 2
return (2 * fk1 + fk) * fk

print(hfibo(500))

\$ time python3 hfibo.py
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

real    0m0.053s
user    0m0.031s
sys     0m0.000s
``````

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:20 am
ScriptBasic,

Well that's nuts then isn't it.

Code: Select all

`````` if n <= 2 then
hfibo = 1
else
...
``````
So when n is 0, 1 or 2 it has to return 1.

If it is returning 0 when n = 0, 1, 2 then you have something very broken in ScriptBasic!

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:24 am
N is passed as 10 so that is dead code.

(Schoolboy rolling on the floor laughing)

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:31 am
What do you mean "n is passed as 10"?

The code you posted says:

Code: Select all

``````for x = 0 to 3
print hfibo(x),"\n"
next
``````
So that does not look like dead code to me.

Conversely if you are passing 10 why post the results as if they are for n = 0, 1, 2, 3 and confuse everybody ?

What is schoolboy got to laugh about? He is so slow he's never going to make it out of first grade.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 4:46 am
The Fibonacci 500 challenge is printing the first 500 fibo's. Did you not read my post?

FYI: @scruss's 'schoolboy' fibo returns the fastest time not using BIGINT libraries.(fibo 78 max) I did a 1000 times that using the same routine by using the GMP add routine in16 seconds on my PoS laptop.

Recursion is a code saver but you pay the price with performance. Like creating a mini namespace.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 5:03 am
Heater wrote:
Sat Jun 15, 2019 4:20 am
ScriptBasic,

Well that's nuts then isn't it.

Code: Select all

`````` if n <= 2 then
hfibo = 1
else
...
``````
So when n is 0, 1 or 2 it has to return 1.

If it is returning 0 when n = 0, 1, 2 then you have something very broken in ScriptBasic!
Rather than

hfibo = 1

it should be

r = 1

as was pointed out about ten posts ago. Due to the impending digital apocalypse, the correction was reverted and the hfibo function is again returning 0 for everything. The old version does, of course, have the advantage of not overflowing the native integer arithmetic on the CPU.

### Re: A Final Fibonacci Challenge

Posted: Sat Jun 15, 2019 5:11 am
I just found your fibo 500 post.

That's great, your big integers work! All we need to do now is get the fibo(4784969) working.
Recursion is a code saver but you pay the price with performance.
That is not true.

Karatsuba multiplication is much faster than schoolboy multiplication for big numbers. It is recursive.
The fibo algorithms we use are much faster than schoolboy fibo for big numbers. It is recursive.
Quick sort is the fastest sorting algorithm. It is recursive.
I once wrote a recursive Fast Fourier Transform that surprised me by being faster for large data sets than the traditional iterative version I had written.
Searching a binary tree is much quicker than a iterating over a linked list. It is recursive.
Many loops can be expressed recursively, with a proper language that supports tail call optimization there is no performance penalty.

The common theme in all of these examples is the "divide and conquer" approach which enables optimization.

Currently ScriptBasic can't get to fibo(4784969) it will require recursion to do so. Unless you like to wait a long time.