## Liberation through Computer Literacy

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

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

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?)

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

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

You have ScriptBasic running on your box. Can you give the script a try when you get home?

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

### Re: A Final Fibonacci Challenge

Does anyone have a fibo routine beyond schoolboy that I can try?

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

### Re: A Final Fibonacci Challenge

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
m = BI_ADD(p, q)
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.

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

### Re: A Final Fibonacci Challenge

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
m = BI_ADD(p, q)
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\$
``````

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

### Re: A Final Fibonacci Challenge

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?

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

### Re: A Final Fibonacci Challenge

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"

``````

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

### Re: A Final Fibonacci Challenge

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?

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

### Re: A Final Fibonacci Challenge

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.
Last edited by John_Spikowski on Sat Jun 15, 2019 3:33 am, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

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)
Memory in C++ is a leaky abstraction .

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

Heater,

How does this routine work for the Fibonacci 500 challenge?

In Python and JavaScript would be great.

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

### Re: A Final Fibonacci Challenge

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.
Memory in C++ is a leaky abstraction .

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

### Re: A Final Fibonacci Challenge

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\$

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

### Re: A Final Fibonacci Challenge

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
``````
Last edited by Heater on Sat Jun 15, 2019 4:41 am, edited 2 times in total.
Memory in C++ is a leaky abstraction .

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

### Re: A Final Fibonacci Challenge

ScriptBasic,

Well that's nuts then isn't it.

Your code says, first thing:

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!
Memory in C++ is a leaky abstraction .

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

### Re: A Final Fibonacci Challenge

N is passed as 10 so that is dead code.

(Schoolboy rolling on the floor laughing)

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

### Re: A Final Fibonacci Challenge

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.
Memory in C++ is a leaky abstraction .

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

### Re: A Final Fibonacci Challenge

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.
Last edited by John_Spikowski on Sat Jun 15, 2019 5:09 am, edited 6 times in total.

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

### Re: A Final Fibonacci Challenge

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

Well that's nuts then isn't it.

Your code says, first thing:

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.

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

### Re: A Final Fibonacci Challenge

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.
Last edited by Heater on Sat Jun 15, 2019 5:15 am, edited 1 time in total.
Memory in C++ is a leaky abstraction .