User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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.

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

Re: A Final Fibonacci Challenge

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.

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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$ 

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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

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

Re: A Final Fibonacci Challenge

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.

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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?

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 10:41 pm

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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
      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: 3580
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

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?

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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"


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

Re: A Final Fibonacci Challenge

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?

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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

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

Re: A Final Fibonacci Challenge

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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"

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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.

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

Re: A Final Fibonacci Challenge

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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$

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

Re: A Final Fibonacci Challenge

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
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: 13363
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 4:24 am

N is passed as 10 so that is dead code.

(Schoolboy rolling on the floor laughing)

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

Re: A Final Fibonacci Challenge

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

User avatar
John_Spikowski
Posts: 1394
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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

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

Re: A Final Fibonacci Challenge

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.

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: 13363
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

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

Return to “General programming discussion”