Fast fibonacci numbers

100.000th fib.txt

259740693472217241661550340212759154148804853865176965847247707039525345435112736862655567728367167447546375872230744321116383
994738750910309656973821883044930522876385313349213530267927895670105127657827163560807305053220024323311438398651613782723812
477745377833729991621463405005466986039086275099663936640921189012527196017210506030035058689402855810367511765825136837743868
493641345733883436515877542537191241050033219599133006220436303521375652542182399869084855637408017925176162939175496345855861
630076281991608110983652635299544069428420657104604490380564713634603300052085227770755444679472370903097901901486043284681985
796101595100185060826491923458731339915013391993236310230186417253647713626647508013398243123170343145296418179005118795731676
683497990168201184990775668645684506628739248560391404760519955006628882634587718941068037009187936500173301171002831047394745
625609144493282137485557386408057981302826664027035429441210491999580313187680589918651342517595991152056315533770399694103551
827527491995980225750790203779810308992298499630449625581404551700025029976432219346216536621084187674542829826139823447836658
158804081900330738293950008213200937471548513102722081730543226486694963098791471436292555425262404399961532697987680751064681
906879211829916796440917827186856170291810221267926740136265049978496884368097525470013100457418640644829948587255174474669565
187912691699324456481767332225714931496776334584662383033382023970243685947828764187578857291071013370030009422933359729277919
140921280490154597626279105705524815888405177941819290521676957660874881556786012881835435429230739781015478570132843861272862
017665395344499300198006295389369855007232866513171811358866135374726845854325489811371766051946169379168844253425947812631038
895204795659438071530191125396484711263890071336285691015514534233294412843572209962867461194209516610023097407099655319005081
586699114454426478828726428450172533204864831945789203998489382363674561822037509734856684743388724904933703163382657176072977
889179891366732519062324711803728017392157239082276922807729245666275053833750069260772105936194212689203025674435653780083183
063759333450235025697290651528532719436775601566603991640488256396769307929050295148869341379912517485666707471751493897903865
333813953468483780861267375543838211084489765383684831825883633991731045585090566384620250146313118310874290772926221594302042
915947403061018398168550669502619737615085717611994758757221298720531206079186498036159609233959410411863516885488391191851790
615115627529361584900087215019222651178531508925102752804515123860379218469212153382928713692432152733271415747882959026015719
548531644479454675028584023600023834479052034510803328201380388070898073483262012279526336067736698757833262548594490602191736
886778624112056210983698501972901771578011204045864915393511578349954610063663574544850824188827906753135995051920622297601537
652979730858816487311730823705982848940448740393205359293597645416556079547247786202996923295613897198946794221872736051233655
952113310877875822887959758032045960847902450638519417431261637751045992110248687949634170686209290889306852523480569259983337
751039010131661781230511457193270662916712544651215174680254819035835168897170757067786561880082203468363210181302623299602759
940357999777404624495211453158837035790448329315000724617341735580556783215345434117002025856080916629419863740151456957227283
692196322951118776253075340259478144820465746028848550006280693481139827601685558407954216205754355729151064153759293902288435
612079264370556006236798654438246437394697247194599655579550583803482559783968277608473153025178895171863072276110363050936007
426226171736305861329154402469543290461625869177463057850767493748799232918175016348406881346553437099758935360740517290941269
765759329515681862474712763646883655175701835341727466260730651045119576286634992284867878059108511898565355543495876166401644
758802863362970404628909706773625658430023531474946123391206863214663708784469921042754156941091224656857120471724113337848981
676409692498163342117685715031167104006817530319211541561195804257065869312727621371069747222602965552461105371555453249975084
327520019921430191050536299600704296329780510306665063878626815765877268374512897685079636637105938091122542883583919412115477
375998130192165095214013330607098731373292651816922684506344395405672981203154639232498179378046910379342216949522910079302994
923750729932506305094281390279308413447306141164335561476409310442591848136393054236937897652052645634764831827263337151211203
062923388928648794920973784786188486826080464731953920084039830800880386904955741975621929392211082576639768136104449002472094
834032679676883762139674407571388729286307982184931434387977808873795889684094614341592713175783651145782893558185990292353438
888884658745213083813777944363611976283903689459576012031650227985790154534474735270697285145459986142290273729113146378204551
622544753535677362279364854503571020864454120898423503890877022303984938021473480968743333622544915011741175157070456105089527
400020638049796796040261781866448124854726963082347337724554339051984130876978127656591676422902294818176307571025579336500815
228638363449313808997178508707086363220586901893837776606300606675773242727292924742129526500070664672273000995612419140913898
467522495579072939849560875045669421777155110734663045660394413623588844367621527392859707228793735596672392461382746870321785
845994825751474540643646099705931612059684156047323439665245723165031779283386059038836041769142873273570398680334260467007171
736357309112298130690328613712259793709660577517296452826375743407579228218074435290866960685402171859789116633386385858973620
911424843217864503947919542420819162608857106911043399480147301310086984886643072121676247311961819073782076658296828079607948
225954903632826657800699485682530053643667482253460370513450360315215429694399186623685763806235120988444874113860017117364763
212602996140856192559970756682786677873237741944446227539990929104469771647615111867232723867920813336730618194484939660712334
527185652025364362196419878275297881306008031314181706931446822118927578497828109436775154071010635055379800384221904550848223
938699329692665922111274269813306230007346562849809363669304944680162855371263341262037849191949860009720083672787665078688630
693341899522576831439083248488634031894019416103697984383334660867670943164365353843091215781554351285207772085809890209958644
960247949197068723076568710923438071950982481447315781378008063935841875665509850132188285284018498140769073850736953537771188
038852893534760093033859869160828933542114772293656190727626460372602723932099118782040706741227225812076672904007192423793033
097213236418409395610299597129179982829000953914738243780277905111203095458253288872114617013344038593965404780619933322454731
780340734090251213021727959575386315814881039295247541094388055509838262763312760671812617102201135618180077540022751673414416
921642497317562136312858828197800578883245453458152243493726813343399771051253208147834506713983503833290131394598648182027232
204334193092901190783289656922287833749735430156172282911562732946881485328192210075237362682764315268573549322302801810144964
900901552924863833888566489300225097434360120081436515362536919944670971112695196672578006189121544022248756460155463281209194
582465355743204764421265079065520820833797607146512750832048716527157747232588727576112835759213255393444628943325810502863358
366929182856689473622350825029496406579863080961434169683046759517435531322436266420719760845902426301747339222529124836631642
800655287097505199750491300985946807101360233644016440017918861085323076499171437205446782359721176046515320016308533631935158
964589068172237281231032027189791795127279965605369403211124284659099455638021546131610626752163380566439431888126819949400553
706869762185523185892110096344101293353573391845966819753983428469682288946007635203168892200202193131836975755696206111577430
582630553586201563789124603122067293399261737837962515099993540364873142320887397796890890836999629299539197721779653342124929
197838375146006205496734166283348734101109777053589806649813601139557158432830871394058253527405608101150390794168807919721293
314830307263867863141103844312821599493682434299818871976863760449634259752425688618868897898088831586507626260485646500432289
685614925506396881140440042950389424587238223354310107869151732833360477926272776568607617770561687405025774374998377583014385
613542727383858977413352694916548392972151955479357892386676250274537010466090938244962662693532130374453889247921616118888970
207791044856319951482663080287954954645358386630734442375331971227915886170728965209014984830543598320077132665340729066201677
570640969018377120130682324533347796666052532549087360196148037824156607127165038358225728921570820936951099589013285949072430
618332575520120809000717502202294974280182344541371191629844991472225419659468222146826064496183925424967090310400758148885797
167224632288701643840390846385673116430816953732679030311458368057502111963990561516915470851045970054209857179731801556474140
617233414584711126854792989244300139146828910367917921697861658248900732203359137670652767652130714398530276098847805621699465
965546137917498565973922737941672649537780199209835542786617912312669937473077773056932443016683933301155451554265686493749212
868704912175424596783113296924849246674426199903397282567487346020115044222878046612432018301610823218390865477104239822853131
655968568800522657147442882331753945654388192862443266250334538819959008510521138312449186180262443219554043398572284134125440
941177172215686708629174212405311062052284298619927362940620883475485364512812327960909721395377536002307676569420821994303464
878334854449271353945022459133437466493770165560576338469706291872574542650587941463017663976045747431108155674709165270874812
526715991379324052730461369396116989258980831190632251077792856207199945948770061180100229613230458829455844095249661115834280
490864386088079644055776369185774375402589685592725251456340438521782589059955395462745138545445291676104296926797089358005623
450191857148903041849576740081935997321871195749635709596782517109626475206889080640765144589313287076745416960710793169270428
516809341331104635350624220981036321677191042078616218421376393819462569728678141363638962012397691046541895680619732314841422
455007161721585132130203068417608721589270209887910893808104590339727654732641691684544562760075956136710358457564909443069245
253208500309106878315756151984756756919128478465469255866511155791346127242533608363513134218390517715451122846445513601601351
322894854327150476083930755610090878609666387061227869027483181933160670148495716300470526222823840626681844878837454813199438
038761383012885988526420199228618820849958864088852135250145761539648264745102590253074317295689963649961570755185583716593536
712544851508936290456773663003556245737477910098799249914696722404148160128953094401548894261378314008780431143174185807182618
514905113874483135843906722894940825828602165028892722838742643278616869038196053015589445945180873519724600822152934398082825
412612825715720935098538280073856047291094118400608448523537783350330686197772450188636407034497336647310060201812879288699186
182441845396899477725948216913713364747045317297980924584436112961899759569624097184556402051143258959184472492094293030165148
871307980210237906553652515478029805940752944051314580755153779486163587990115819201980887969496718744822415683646353432616024
263293476163445816389016380512389418452397342184149688926239848964864209340981668149477115517700956266902985010151353759980127
250124197111987152659374748477893548877781519293117143116744477388294106461502875132770947450476392287489066298984154025935083
403514203513616881924823899802770666691634213342431205450735938861668769118818577611813577133248396520988208598239129860638682
280475436240895652292141085985203733054462595326134023486468927506052689375514840329854208699122105259700562857670770256769530
097897004640892000985210698029541969980213805329579815947828993444324549156532784522384055124044520822643542065631331070294072
237155277050426348207398445488958924886139765707914541442765358457295132971909194769441191096679747426267559095383203916967349
426136003226307742868410504006135105219441377815809500571452684600981035210924904002795805073643696102124113773971716486952549
311480504012656835126882959841398322267637780450062650724173175739521979689075482519932925964980162706866565803017887740561516
715973192732047937624737550585505283966029456699252217360087408121201420907104193759857172143133801742514158249182471090508471
597724941704932025416523932323325885158889333709713631089257153141776197832603375010902628406641580137135935652927808845630595
177008144399411467429185036074885236665474486992808323051681571160291183637414795849210086052898146954775081233889694315286102
120273674704990393041703517134212692348670056662750622905863691188222890317051030540688209697087554532936943406398129769647803
182545164217834734771647105842323859458018305275621391018699760430584406866571234686967945604415574210003917975834897993588275
188152467593087892815924349219754538766830568466842077540982178124705335452319479739895332017598864028105882555769800439712053
831245942895737769600185749733524996501350936892595802186381172590650643688212715681575102171290076599275037022828396396291597
325117341858672102349731776596945428362551937155600914368032931196284254662840314244437064843239037490641081130079284895576724
348120009030988845727090775087363887329964255505047381252897596293482287891761992072513830938828829251041683762275820408191893
360365387528411678570372098971883298692192781662967584458017491180911966304818743415506779086394883148924150430047670452797128
348221152220283706285731424410782379251364508667756662280497721139714062166411632475678421661296147710901882609467737768640617
672148429389497667138012278894130902655351109611834701256519754080709538406091686393690667378662720942943426426040290215831734
500372746258899262204987712117840556334849249032600350856909938239277729749841356561483078826236332236838070982234601227424137
903647345173592521575475716093427093519290172395492142649069111527152333810912404281210289373848816735895393450893069771552298
919969890388588327540904430032198683400347027122002015969937169065033054757709539874858067002449104550489006172718916803139452
803616563394157133463722255047754746075605502410876438212168884891694037125890194849068537972224456200948381949153272450227621
858916950740579498375982100660448199651936011026157694717620257170204868491461689406840414083358756211831921083800563214456201
894150594578002531874747191160484067799776541483062217906933085387512929898300958027755414543505876898494417913653589162009872
522204905518355460370653318317671611073800978662524748869147607766447014719307447630241166033567176556487444057799053199627163
297200910944924921645603061882777294775076477744645258632891915910744425232008291820951802108370035388133098321589460868012795
422475207192413464833496391509481309754143324420929993075148107791900234612812233016179942993061880053341455063393213933964686
161641695522021644799541724317116574447136419773320489936507476784414992954807302585644294238178764150649287836176797867715851
078423570264021338801887560198923405686842321558562850864552525837701062053222424498799062526348401077432248817255860223330207
639993385415201534384772544291789513063705032044491779775237087195827797679968611362653229111862963116468515993466069346055754
595606315583003369763400027668515129384363888609082837614115773200352756515874590656702543943793110483857131329449060492658236
310894953509008267315449722639664808861804157397788847289217461897418972170077000986244965375901272701522763451087490694801221
068495206300251901165596358055242918020558690425968526104741283451846673693858002770025296535636672161988367242822693395032593
039099458316866554223465485702087550461752052185372156728267990341813552060299989536647010655790053212954133692447249221243632
452304289518846177912233806967423398069488727058750338922839509513520912310925815900696039515636773606710905056629960357187642
324792075283616080559769777875647676721052122232718482148444663126148758422609260887576433173102326376886482259469121103236773
755812213347055680595800831012748167396201958359802396741448986727684586981937678375716793672321308158619104599505897099106468
691946344803857414382962954713137217366983618455814450574867612432245151994336218291619146802609112179300186478805006135160314
435007618921344160248809174105123229035717920549792797092450247994084269615881844261616378004475947821224087320412442116919980
557264911824366192183571476289142580577187174368800032411300870481937396229501714309009847692723749887593863994253059533160789
161881086350598244457894279934651491595288486975748802582335357167786482682805114088542973278819776573696600572770016259240430
168865994686298371727059580980873090182012093100343005879655269478804980920548430546761103465474806729067439976361259243463771
999584386281239198547020241488007688081884808789239159136946329311327684932977720164664172758725912235478448081343332805008775
885526468611957696217223930869379575716582185241620434197238398993273480342926234072233815510220910126294924974242327169884202
329730326016179057567311123546589029829831311512360760677396899815381228699964201460985257979369124601634608876232128620563421
590147918863219465963748348256429161627853294823931322944023104327728876813955021334826638868745325928158785450389099156194963
247885503509028939097371898800399902613201587267863787309567810962531100805448941885798356590206368069964316503391202994432772
677086930524071841659207009613928640196672575008701221814973313369580960036975176495135004028592624920339811101495322753362184
450074433156243453248421798610834626134589759123483997075185422328167718721595682724324591082901988639036978454262256691254274
705609756798485713662367902387847816120147798293908051315025817452377352951016529693456278612224115078358775537334837276443983
808200066721474003446632277691893696761287898348894209468810230842703645285450496675969731883604449670285319063739691635798092
886571993539772349548678718041640141528148944378503629107151780528585758398771114547424015641647719411639135493546675559359260
884920054638468540302808093641725058365336809340722531082084472357022680982695142616245120404071150144874785619992281466456589
393848802864382231384985232845236066704580511367966375103924816333617327454727577563681097734453927582756059742516070546868965
779453052160231593986578097480151541498709777807870535705800847237689242218975031275852714017311762127989874495840619984391336
568029772120875193498850449971391428515803232482302134063031258607262454163776523450552205108631828535965852070817339270956644
501140405510657905503741778039335165836090454304772142228181683253961363498252521523225769092025421640965745261806605177790159
290288424059999888275369195754011695469615227040128085757976615472219292565596399182094889464265751228876633030213374636744921
744935163710472573298083281272646818775935658421838359470279201366390768974173896225257578266399080979264701140758036785059938
188718456009469583327077512618128201539104177395091824413756199993781924036246955823592417147870277944844310875190180741411029
037070605208516297579836175425104164224486757735075633801889537926318338985595595652785722792615552449473936366553390452865621
546428834316228292112329045184221253288810141588406161993919504223005989834996656946358018681671707481882321584864773438678091
156466075517538555222442852404946803369229998930078390002069012151774069642857393019691050098827852305379763794025796895329511
243616677891058555721338178908994545394791592737495860026823784448687203724348883461685629009785053249703693336194243980288236
432355380820800387574171096928972549987856625304886703309515051845212694498925159639207942145260650851605232561486193828248983
800081508535156464276170083209648311794440197178014921334533590333667237671922972206997076605548245224741692777463752213520171
623172213763244569915402239549415822741893058991174693177377651873585003231801443288391637424379585469569122177409894861151556
404660956509453811552092186371151868456254327504787053000699842314018016942110910592549359611671945763096232883127126832850176
032177168040024965767418692711321557327004993570994232441638708924242758440765121557267603792476534180898431267694111031316595
142947937767069888124964342193328740439048553822216083708890759827739018420413819781102585453708858670145062357851396010998747
605253545010043935306207243970997644514679099338144899464460978095773195360493873495002686056455569322422969181563029392248760
647087343116638420544248962876021365024699189304011251310383508562190806027086660487358584900170420092392978919393812511679842
1788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875

FastFib.hs

module FastFib where

import qualified Data.Map   as M
import           Data.Maybe (fromJust)

fastFib :: (Num a, Ord a) => M.Map a a -> a -> (M.Map a a, a)
fastFib cache 0 = (M.insert 0 0 cache, 0)
fastFib cache 1 = (M.insert 1 1 cache, 1)
fastFib cache1 n = (M.insert n result cache3, result)
    where
        (cache2, prev1) = if (n - 1) `M.member` cache1
            then (cache1, fromJust $ (n - 1) `M.lookup` cache1)
            else fastFib cache1 (n - 1)
        (cache3, prev2) = if (n - 2) `M.member` cache2
            then (cache2, fromJust $ (n - 2) `M.lookup` cache2)
            else fastFib cache2 (n - 2)
        result = prev1 + prev2

main = mapM_ putStrLn $ map (\(n, fib) -> if n == 1 then "1st fib is " ++ show fib
                                     else if n == 2 then "2nd fib is " ++ show fib
                                     else if n == 3 then "3rd fib is " ++ show fib
                                          else show n ++ "th fib is " ++ show fib) $ M.toList $ fst $ fastFib M.empty 100000