O(log(n)) Fibonacci in bc(1)

README

$ make
bc fibo.bc <test.bc
0       0
1       1
2       1
3       2
4       3
5       5
6       8
7       13
8       21
9       34
10      55
echo 'fibo(123456)' | time -p bc fibo.bc >output.txt
real 1.31
user 1.24
sys 0.02
cmp output.txt expected.txt
echo 'fibo(123456)' | time -p bc naive.bc >output.txt
real 10.78
user 10.28
sys 0.05
cmp output.txt expected.txt
rm -f output.txt
$ 

expected.txt

26830557650282090486383163536458057815231640657255408238347681532550\
70315009218329685198430631667429548801953783586796725030958749787702\
35997192296829947699315900184358007864172966752231291515275893550316\
69440740142317318454564878287435775361525249344104379207659257481448\
17002746151001777756388428574582132628693329691465619434658191867838\
59633056542866179785312648315945079332977361617640083510069383325506\
09053503587593448099055624433781071144756741473976158257410346818983\
30289537723467185748341168464652265447663941506045431125008082289011\
12417740723886804949179256909951858933135313066627450470675721819932\
58354381863274548261759080386059513987036247603194434509517694752789\
39804670840735292691831240982913613317463643856885080299107487167772\
45956634402847346358489347878861765103905235475824165921600275926831\
65028411202720565785587670317762990737216225122970462137774405181306\
22357730889559428499697612012164562131035009370703103451540345001548\
97239016735114345726419540973696692541413816499519462708328092522442\
65027227808925321951827666786793471860799251558424648927310840426180\
89441023043961374557649864027129023881409539242146726499101849450423\
65655405195410149464104449979195218764590161509100517562068174878153\
44331979798197838834873835244896337302533589111180737538638500274187\
24309436936421890899066076316629469181983960428958334498393289308700\
77346191310098317661879957072286683003377167661515201555616620887185\
82709566773862203167171972775468779045681817050965664887979441716508\
15456712304459249998526133068362030539248697749216476862143772755773\
13002946361412588771957066935970871650804130896822809161388513586800\
02132584290765585155719743439958256582438429664410048928052443792834\
54318768855819747166137638677836541064149734861642664697645278641836\
18613056148632078028757408916648948178751346783516217565199142665656\
03528089551847984213999503588522379947520017557493375500547598811735\
13597188033232107395270612188555759113601881647475969664477813518313\
04252557082153999921284468905382094754767319881421608115516196532528\
16940159408177395680669710589808968321271627032176939525939233122906\
72476349675345485073319690980902516101890101456940479328563951058003\
47492687443487689752428435739383104235718202725051764657362470670684\
02326684324625631414437827201365286409128965377873127120360919531436\
53504540804161493868714853790839407136356705083550175196137101539167\
26382703856689782312137196393354026351149062388531945998473053768519\
78559137503313944575766618377364924169774846729461600895399024127843\
53556767910655261651120198907913449519244033103181985300598337516995\
86498463719288202137105136596090972211955921400788674062265717409307\
50650735292481613636192667633950188350881902343692071872403535076133\
15819916354726169533204292773635351956307738347779025152706183388356\
78016859682962939398011868992141187259571834730454774260819508037217\
28233647042610724956642986309801338314403742701800548144914368024523\
52010294099237066941427815744189538775241717230401929672013666919941\
68214510198623736743256785019221816909075756122250614397816846319292\
04140941269591699409397510620918557738657276422106151702363974259089\
57274270883842698644897512945858923716235717441773196805607087714196\
90513486243039830656816505632431793762216120312469756222623088101248\
32911500492001629152448761286385452936719485903405393503574208238300\
41985370572253353623320413787446591519811455918150627288457085606986\
92225367414273028767958479709176400370051897223736279578028731695727\
96062390104770190253372886892199559850123199593455546170645907879730\
89752621261731369411132146034206456355998466488544748213503375037714\
97879017923911203636280439067766452609061538020313730021006365006962\
87944607985241937094313771977777938071487412801128083130062778823119\
80757980618127663692197439992429472736904668329039637569109086388899\
13284724942508739987670897926982240494709563217623008669496394629484\
54365346367581874746183014101472487367801850762468664719897502791364\
04892468454335870706007462338298722505672574343403574914073813065372\
57011068735581391359440215505619066551616286493784883841916306812443\
38988392016130828326659285558615539211450287535935004927253814779621\
04959137196027249892932485450975877944470965148445977111647356258900\
57661563908454863578623096224583691435512995732804218829439689547155\
12625704392859996957208032897759554014449328626473650700796872721612\
11500869895153928836242830606986387681549607834539051700403850207017\
40219172870163020867225029126742533660784235935783096063137750824763\
60171398316787528162273297784283593393893035325516577749953908979265\
57794315649290203631336391737216590066889934963090094404657642593633\
37089737802784728306479136588134866632801563153464111422139021884042\
58401567629731492185239505777336890062037478253975379214502880531409\
97481296770836431023108723958911668434785185537534988666224907678982\
74698752212150217112053506990494607569899851226900998558093610298717\
48757031973580701584119989366159534514999656420643464322402344221066\
22774681959568291641621243685622197691819965497883789993431653532485\
88428761873871290374182599957610455259290740380195675898708905772384\
32874984002176002608956046350102231531314016638692340932760243797984\
67491553779214674851710853048079610238370658983902502155106272277017\
93040461852645948367210585736498496985997553114414695949391669660732\
21133031572858014848490976655448320472469715523106850873637315223425\
20087680199447953935575513355465302498762738800663198541763196161060\
26675428232138890382756602500538504057107449764875722024662703821588\
13347098930330245707550262844483569266873081450977144928593675469095\
50033708019449536934079892085839994397516287376374448061916573785169\
86535771387606178599594175876144330991759761512526148945476469106792\
81801015953846852404405952424301249750413440120724489215959422961651\
92801962221307848045068401665549271006457513656604972018571666030667\
51003342944475171444797185478446562253123472903455021133523664740135\
82555083170969510022090572206038499605849196904092066074156308306783\
11483889511514990282435524794956302285138072677923168863932047054385\
87710324806120643309022778587404892866378181303543780646795881087039\
24724641124547749017808274037274900000310869324536388337663536969944\
46455155674276919299798249182515212992678095889595608807758425799923\
85249388754723274059916624300921744564155515271081010329030741923159\
03520047911665740129754408518994910203637039038288826420825038273395\
02109272726048802242315299021307063852810468297943769745201840983460\
70759664298951484399032333816363991091954597723300714127507823036365\
47006617254526239812074987623214606312235920406570258160151343702690\
53755421495428906851422135952284147712052626636744812935874440116091\
67112318638864887678799263720051800004274600708389863652687154835297\
41661060224325436798577907415797835523396876943290756747928647832568\
30956632304745372008796864548916484999818963392328786497611428669286\
36739978070291849943773464199703038268338525373808208824691866404677\
78702575208888477920571313755474563788063990085028649639479577256385\
99529066759869842242212770384469128849551342462360859105107642585464\
73154636453481506172023472785058906153791823800404815242081418674222\
01832383711020329739149066571765771447785378435199770494798038047387\
52102397475073890856953042544022822460603056219247686948359654770831\
87350510942279877154982087605974811341116665744202234890105557092427\
38507211580104940049815803266270379443677700202319956055040891178034\
86206105288441855337475181609042811229936487064056063786708606343803\
61756310135498945456194137220709221143767770047649250820625665255103\
83988100210483856490058775692132652093049996012418342890707097329087\
93781328393038048458307782448832099506707256897491291573561620728080\
33154689943281327151107816760794202073130566180581196734508079149416\
36813114386695141243274138230627708979233291009774353808133347736751\
02369404133096502481455828699899914071282361452016204898941051194394\
97477632646608061849745756824997810424825992783320214970843794545333\
83025145812139599304039661526587680619082536498919089646385820897135\
79846947632588785281542259839339182844135498695369741871563765428065\
27676796707128738320768987023058353752007319817392164120205125001208\
16908157375450102914263137658251622227210510112202538789284480936892\
91148624956497359691528268485127822033134239658908339037339034463794\
34673959088702428979850565978581794266719383272966845507151799266855\
67496404184436856709080112232384561019222536166503537185260763816761\
65070720717821164110129669951759932510855149342143861573393708371280\
17347952579692894888895620668452937079250663837363859714060984958486\
31165109102928206545531659805283472733051967859342005722937603468782\
87492758060772007835645153473586269657990182836528475683777528737184\
68116298062171302913085670675098445344943228314685413746976478989381\
25643594937105560670675287817902430776012436457545489940304773986439\
27416647826994102051825749146645458852056688192515550824422320662480\
25449550722445005113547139037623774921469746650189834031189418508083\
62462982358367116318625378237541270559769546892729823588402949312734\
66012893975090240136373158288945476922010684006105760444818350894436\
67384741008398976647867457355715463388723048076151976027968499819931\
44364883003482453853272916535215224736018911545666239459538883147413\
09199055728085206283798672789392358616503013140474842299042430718342\
89635005867374599709221732547525936743875067819391157497579061758619\
64019989222268598756706795039932308537051554153212012803797728287739\
72388457513850116735203330078996480527436567611783158246810669614669\
33027594795903697371603992010020736246950444870756568848726890991544\
11148081394425998056682726812641184782346991047474699002487641065188\
08531241356881633892235346593027398570901407332029096173870282280409\
11113195729432699914259307899773491062298278866395571192367908076655\
04983348860976054269061848373332004747872476097392845165071862037566\
97305298670154850560930375531884819165499628559159292022987633439034\
71819135768216616060790807038213838866370917449702587041093961591967\
29556464588366167429818452175239143823783895173382863228917211557716\
70649630750242624725943179375635871059302729634229589387657131732862\
56235374555291640150823408336001603714536640642814180234869271408781\
64045989972668592464251166759571136603317476756428484723324193472802\
73452949823926922000560103648522704922059904819300552703107171744675\
78177330794831239988313779566474963909025742613134626148561734925693\
79216923031979455143162792349868674372137026556312614063100071520443\
80391188343623457467312238422219845572793200995427601785018660025695\
69329444072575996361347949339705531496146171610299768141322133715226\
59755965781483952420642357971209340005335563760349250218673709454488\
33545500836833368449236727329807817106112066307849841973439240691732\
61539745232948865478840539619329516788705103181929734241303346908983\
94898364986209124630411543319558606927784161592915258249618983450254\
00984120104926010034737606702385834152064099439895283858143535010210\
65162540135054306140062326465329354199103706029569300179981916096855\
89579466236965649145824103668083567328413264797485865770858933606552\
47780324952688381476387599424366072492694580834367348795792383151701\
62161812527662671124287144561018452812743020261455435355283948756061\
82365085997437779545849388648400502779966181531550989586437573220759\
54871336868496100787971729739221168416312745720252885778015527776496\
26235756226594570401193310680243840228795900792471770106263239390746\
35404346321611785922420292467348300964326588698625438390408652867772\
71902945379788164203543433223074306443379389683180401624530658985396\
07344365959271200719987350211940339759988206205839052851235915426061\
34757991820546757602487911432301179036638878264435995599029311825365\
93735372607752567637270378221568048608009069956200667923580101564063\
00995720265339447304516867762451595509822338470356192616402520742918\
15517437255379270573181815263024166595510835906818614987483278340218\
87665303004685054871842512550252058653478645926171292203114869475878\
33804688938521701985124822718190933208622481745577031302425823760548\
86302498250093557763048993263135733022157364239956730451936892891406\
98705007803378266146906634295862142851293522724908597119820853469824\
04010252306022012126371848625563208485320987973240416004155318145738\
92674468765904590721167489758483558386563477021172928592081301647180\
95746541212456115863087506149322830438096874318740590920920589361747\
33673645557547474303375265447112956129006692618161268135115805683941\
73621366329712046137963582967840132742102184388683736672714067678710\
43754263876198899891997327275678478552349104840357019621177361812150\
28429419496943746085178149813750260385259970088485637393388268039610\
56380179793297252926912055814756110532429946547219037905867118301300\
10818030734315636418936100030666577943836038812660197932244678979566\
01330352447206464439082174292884357921915447265656605453663336999853\
78600622186402399917608349125283211975101909088304649813169641353600\
08121440817584433601526840737004456261206701506140392460149194348794\
57028260403394567919851516006091561693653555236082142365618954281656\
39815577415844189865893911832947297641689088478773414099765637100464\
30631248145126461911565920618113085082314829156332759344505812386724\
95014529502374859297696929256586686339629606468818778230598028708550\
04240077821643758136856244283231491693091649486905871444542836450045\
21522517364642487280020829416117580396553742670999058016184843038321\
87516010120002127156968065100001763856329277433493690297778046660019\
86486350208862166812106842098430526438653164778084681111268327442492\
74313538088651643395523351073525587275535510880170230275739178123127\
13863242583521392265251516309060604662235510100598346950926962648239\
45844765915505500552703186563820342862822215106093755273207306454403\
73060605530466551001326876346174380626488205227056368697129922265641\
61860950041447565546128707728724375632148754225524751506100525060247\
04006963744991796489739427137603508705698839952504692062522999858503\
19009605367340396579420594029579642098860889387367885203440652257735\
51186706483587376963886602116574295800763495682369592078174996278460\
84514923676381717236654514998566800485586633015497865454989280823373\
42455032313355607587506741561754510997858442430078567525234264662658\
78522656752486665101176083613810400297499216323001537211943804100861\
49967920259291307644869441922628539869061022194265364714977174890766\
06917342122646480171143816793496441746511873342853439820505874953059\
72374174373175787616069804833730665515225665302383048172332152422558\
61625759595515138526422034238812836882266149839916256808485019600671\
35425190544182909048968008171198926387708287997488088838252374477199\
92293341603790353907471166331526160489744698991752625441134263303525\
72596047391941266648234312803255845843169137533138450139906610153061\
42837945963465605631920598918668702028713630594365152799494591096553\
18044563364042010643244578505158779502491109406078261165973925279300\
57022490991811576620367064212650081276681264274991703053723512764196\
46738399800626618907171430440728197372277084660972289015689606119877\
15758910146420350417917962506416683850702641002402549916451480958448\
28747993787885024020469088330689837915420544905528004921434102005656\
78728647061017446268121672080001772501636962432405391183905876899216\
74015688789588429947276467287900486016964826788163166592596287455716\
38579546501044288894175479495247182260989378223702821763185065640971\
17892492472273745598155505617883622391665616890576017499240972415192\
21132211651732801622613245549212302870252404892249721899066140181141\
33462436191757405992091040091377881931733000528012724149071693865305\
07764537307246031330796476810009760974628572579824925939896694316095\
96138671290176070161725685964497562313610163413886708634657347380364\
50387375577901787711597644178285930288517963707680249357109728291287\
64888554432116295984146392629078740364402238898867406405100265507231\
40580058408616199295015193422604997070373827061942129923258119030000\
26325128100609319414512357836865464399177595488992404254576930920256\
42902862284957899486563065097363951912106454747586291843194586201010\
62047461788017206762924413168882982929852284880043720410076283573861\
57921655726865956089201432073852440507784038638061133577848307656419\
69018268780048655442208752099508445332489378776587449466449373907825\
06211266591923554257966564852470031318216043566960769809933568867687\
81464967516857403977274360101218166016999922408604725920235127780601\
04260691618352321737694172709841818148137095357647688810690111091732\
62486233691537229019512671659974710802718831549733261095860461109320\
15930781080056723039706473454386254738022241996848405629955188260515\
52297758001464994556489648245141129541648719095798288095328932088941\
50012487756644976340573518999272654124022043223612429958175242746855\
85739771681097023913172704112371962656520784357560354459068039395438\
10513474433089997103808249313462655575924798357407608324269980774520\
36806072718173393320296845570102073624536628661639510819872291409072\
73050339828768010407888758818884840889310234049900149301782497471519\
87349735488611243887573614046869622474488499996024610742999243108128\
79656963674466464631435343370812092423775461570495870964579692582186\
45683148603468201428284874808566202869577134255346268397854699421864\
05395009423099119729399767975055176767069654649411443507556204707960\
11986370776054654827426553598143732987869266632476596715028640044952\
78066020156095499469280992055991114704962601599638984983198308524078\
60022775474843165618387783604710338787013808199775701502572305284540\
42723203879476224605107052782611089422169048266072632145334374899065\
47706585554234099649418552542697813677260648300459938027928308265593\
92919518713555152442102653322933566550644960869177216261928832238252\
48166834073870815226579406794848843490114801269418288827444257669696\
36304593138709021195648247451367193579450567486414607750395594142030\
86286916785349770187441965752978430931454754561441176699723880867288\
90150143138558944214641735778716958387680092933081563672483626916018\
03662655412927311074190973926601821459646542406095725626497175737685\
28247473060968971964793744712541104398836516448723059235513500726466\
82339203998896791398442552401628408107135502515092531458059286006545\
29214940484775200713783491926453639381245558100647535113882682415945\
73486305812769115232776779552865165916921170676844283890948973967643\
34363819293787251971610836855927135095017490932299128171032071856276\
92240640017140150808253452342150041459889656841272044559245389117829\
92286808108026291367269421252500180975578304734482511301120105909225\
58557729626732170912469833839779230435504325866167023909389512473647\
07264967272943709697209905497147817412341719992393907685247892264247\
53332235484382136006238085800906977591159073158553876373389847986001\
44565704006464898981044003333348113061340446863974735075682259919402\
64619214438561057103996155522717296344964977578812208686445621264657\
98202774758872583264171288211045357314851840247572316600340698999676\
60234161050045548140686933599323814123970597285095571042649425954496\
11683911193769795450903218227721979197479690192239187631649359594071\
41291760931218292418005365750676902095702599339420933998081473834859\
63940227059120565450223252490987151895161257906409342592707203936998\
31798305313790658569578932554283210673093930958515805731789909826361\
19242075984064965547482874366165933405518839778211408986497835289074\
85991840500328239585971656770736004195793075039315882106250654128147\
31510600871055610348681536646392262607278364756071997307506636156132\
09239917170163924000467999547982306055487148261242166231406088584237\
07643608671777500854255652851356727010693694506827336456865329883785\
30868489398079411658836873095488763481637430719676705246612619269447\
89041846640058357279352774785544675464863975079270628114579517539122\
29093062635738257544446996321067576520213086785758701162493328197307\
56613390287740153746384909202324114852478904727064168084745693932851\
05253818607745341503593792247290554617831437692906575507103895994456\
65338292988167662799639857965406587629080693038025815415708784803466\
08252824867924688895743082682757127392289807856655288176759439201907\
27943782097448439714058985407922881179647110274580556392082692145687\
38073532991750119841561049913924793191934883849537657592107017908545\
98258036656681126418167447831137717708636411864813994948962717299581\
21280732615959560130370419659565990704461054987240730011786439943741\
33055881541360603554659480057426748655742368917150499616842321952762\
05927718549065250890803825366856261105608073640482575659285382440930\
41022439381407892846628409410498170221437363659851065946876118164256\
94518940110826143871166157019736334384289313010042087438943831761900\
30447500151077118765460956313982440378482349515158246980611680407132\
82828351001050396205856929667050853985716399605232531066128694239609\
89696622392346773181993372902493835094236212176040270024534272741781\
45174411793616409487128493777044011619691099760872458649383112451225\
19037354833297102372505849608163093147132630112195584245632502915323\
14248771148398659916053392190472880371760461806212740418127068065358\
98595967611823825048147500674690303798622513760363900903262364017243\
06063663955207589611728919553745593512422640201083858744437807555187\
49660717507974971293372787275661639279051365324170916341996722839357\
88599989221197115452263150338982825879166680108961221045394730404699\
41421676200397574953995190542787763679505832525644749716947586609926\
38392676165932913304462560437622192802912028513362433347765095148802\
51182645314965379204423044209352466580746901601157686302679053845182\
90421791137528717214932242942754176700607082680080781175138961727983\
60283944053546074503532220212004897509262658117135003546747335403843\
75708618084313805740206516258744701788244295095037924975637134586363\
84861756427146470569938170139334052477126704939401380478259538183723\
52655882032991186536892751319389087060489954095680882819616820546370\
37390987400856358942660005770313696832532619387439932757398343289591\
47932666323082699914516473103812779888003696717115873820748861161705\
99202691342035099234186672232395479802334904518767009486888729508435\
96575693847319862023474361926108616163271621703226350809241773173369\
87108196785304226847387571798221694037876647323036584267338772957071\
81813529791371588657145698114211471201415064800475356838528309453328\
64447838586926064197590705479799125330839431124436066314779077776818\
59671791914795084891575626786699246777289273834774482681462398693616\
08520251120122981896817680388831568410743020300792677771778418164192\
95663920328593218126398295541784380404630116994062731282138507354583\
95291996152866613310369046150150066513156669524552077280396577659965\
96115412965218641174014310638631965948405904461995875141885768552270\
66741569795486512453557592839306525401337315004443666546855609676686\
16123889207483200721414431970136475323629027889492430348215849977650\
84668226077203641160980886977863461048436904283557905078287987932282\
62051357304850684496386275359951198681481202905631537461984721862349\
81376187746920552655033097270735978605231401708627892220294098567783\
06600411664231090202557473845905325180594706197660464242123801048213\
16494643809265283244748485597115972478594615480632978027955802516809\
21864728922349255046793256374595552455919852378491318915923180744144\
68980396463299366002218564053757168816373859328888806968018143452944\
71223122139692875429085253527924164702650763168819959719557455601645\
01903883083844213727893622963355080871059158513566910433801008022754\
19189186636352697127082728772472494179883974231204892872201304398122\
61767933011398115239220345934346228297918482706701725477604995220980\
16273348778614291929316396058171326799338213953124505056950237249258\
46279705005466149635017219570413716876404191242952134562681164862469\
05602687918479408505053401552092822543144133178018568872993951364372\
59720985582926743962666807966437240136972553708174392491590116642887\
11037088347171914403048651881916453386227852449495904243223105125675\
26130303207367978926126934706575537415103467451401321280454094210812\
86384276148361813981531364218665281045285347026248287828660386067413\
15123271979491865795109375358398107391469804244700350481151618815034\
48668480861747047446739129294966534319943317177500858645704682860457\
38983462361383410304432755798704286872194799410162076282623563493235\
79441801232320343814950081206548183120187866905922575260755650459793\
81119139067554340863035141888610167652592224247926682421409559121909\
36726150508273042588041728379698513587308498668912678561152149802522\
19660108067424882349478310073037446936890071692163446458897822874053\
22850200059161525583502268529742254580629617997793435474306184570692\
08653106539397101052652385243647332426688752844967477346177647493588\
49341479382240571609813975625566855354405552625498123095804794128272\
72603321971259257328487316004336854899260746396870473816832688605169\
07341802051135150925211021439922442776004901255240725506906635801136\
95734305044131257417274029517916808080343997442096674829515069912696\
82308827511582907882746512024153159306623926407267803014558856822481\
06753898871057518906772115380122656745615702162951240456274420022380\
31627663027189099624686567520604211312175546128830473346369845302313\
99521379321152639310621470560041359457947044158633508110288194169917\
69538405449546173730999281945686833931780202937442280383124321340832\
48839255325799448755603012188313590885811542412163020579516874061416\
25991535554481473313625226513600995255586881423416677398154584534388\
52540622247448894878714511114812426718903042072967069597357218128081\
35129288772641021099307252815659637526022768380314707617616031962176\
07798657473707476549414614859447785967520176951112609276133489345907\
66552955692744996617742550690315173221787347716453573608110418212542\
89375576652158780263441291059995851983786365443937487229350260504096\
58943890007028244712339510480915334103928190535881819062843414795818\
17904964582239396309236251392

fibo.bc

define fibo(n)
{
	auto m[], q[], p[];

	m[0] = 1;
	m[1] = 0;
	m[2] = 0;
	m[3] = 1;

	q[0] = 1;
	q[1] = 1;
	q[2] = 1;
	q[3] = 0;

	while (n) {
		if (n % 2) {
			p[0] = m[0] * q[0] + m[1] * q[2];
			p[1] = m[0] * q[1] + m[1] * q[3];
			p[2] = m[2] * q[0] + m[3] * q[2];
			p[3] = m[2] * q[1] + m[3] * q[3];

			m[0] = p[0];
			m[1] = p[1];
			m[2] = p[2];
			m[3] = p[3];
		}

		p[0] = q[0] * q[0] + q[1] * q[2];
		p[1] = q[0] * q[1] + q[1] * q[3];
		p[2] = q[2] * q[0] + q[3] * q[2];
		p[3] = q[2] * q[1] + q[3] * q[3];

		q[0] = p[0];
		q[1] = p[1];
		q[2] = p[2];
		q[3] = p[3];

		n /= 2;
	}

	return m[1];
}

Makefile

all:
	bc fibo.bc <test.bc
	echo 'fibo(123456)' | time -p bc fibo.bc >output.txt
	cmp output.txt expected.txt
	echo 'fibo(123456)' | time -p bc naive.bc >output.txt
	cmp output.txt expected.txt
	rm -f output.txt

clean:
	-rm -f output.txt

naive.bc

define fibo(n)
{
	auto f0, f1, f2, i;

	f1 = 1;
	f2 = 0;

	for (i = 0; i < n; i++) {
		f0 = f1 + f2;
		f2 = f1;
		f1 = f0;
	}

	return f2;
}

test.bc

"0	"
fibo(0)
"1	"
fibo(1)
"2	"
fibo(2)
"3	"
fibo(3)
"4	"
fibo(4)
"5	"
fibo(5)
"6	"
fibo(6)
"7	"
fibo(7)
"8	"
fibo(8)
"9	"
fibo(9)
"10	"
fibo(10)