No. That is not an approximation. It is exact. There are a few ways to compute huge fibonacci numbers. I go into some detail in my FEX submission on the topic. There I show how you can use some Fibonacci & Lucas number identities, then, based on a binary representation of the index N, you can easily step up. It has been a while since I was actively playing with them, but I recall I used some identiites between the Fibonacci and Lucas numbers. For example, given the nth Fibonacci and lucas numbers (Fn and Ln respectively), we have this pair of simple identities:
L2n = (5 *Fn*Fn + Ln*Ln)/2
F2n = Fn*Ln
So, supose you wanted to efficiently compute the Fibonacci number F(1048576)? That is just a wee bit beyond the millionth Fibonacci number. Start with the fact that the Fibonacci sequence starts out as [1 1], and the Lucas sequence as [1 3].
tic,
Ln = sym(1);
Fn = sym(1);
for i = 1:20
[Fn,Ln] = deal(Fn*Ln,(5*Fn*Fn + Ln*Ln)/2);
end
toc
Elapsed time is 0.093193 seconds.
Fn
Fn =
11868006063550661146017510449861600696082418050237429825997806662753794407904503546551015054996721473373966464927119422123857923412396535294768655766766271766381998148563840327384189412167936342692468833189168014168737767794438318535949903348551779616240961517376897002242352287039523639934469192738584765558503478712523022774994811852556256524219575234331801118729946096995204933768632573944891747450255635095214530041025409514953074197882674444630289734546651234698426641861939374594373772220850738568203301004147261187874995055648667165064367435741881379732817836395026281343601042689805892944314403954689951604398740201689770719966353808245081842747540132679607317307087566560502109797062920932863828670602033670797451981204175285900795517091312281191491883255164102391531983251990987491461041476196167608588824368986797713863365269148856354320515690614058852236905399689348823432963835863733733841704318635735769442619467967066593948376173330754537255081368769215757531564704941342538536837072272106878130297393603289820811651987250384958900239458182816023179984250644639218044380888573967124953932040278901030436407105868158710915374788682148084264832170669130966872834937163776179142484035975772528388843497362690067098067249790039825414189089112414904091759319484564965577288634489122699682736511788061808123355045810996440480051703666442134379842319338498336075545623851816138714023029471269881584360936307062579669007338275973137685460933986798707707138417641785111994303901783075681641648865143308288804315052701560637491765526837009762482168137929534073747473685463971191758215781143164100656588337399652728217179281524799750552590758011601226502666178667715557640976070528562329269453109470860331789104967144232624923812761582528002424972202966133682708876802903024599296622869907767781422389514476515627515729810097277757718150827141470707338030188309192626664897727544706259076052796226081263477915145557389933898086197222935193560948687888501699157659749289569461498255015180483807284325650227276289129538597954950581448383342301050785586674942960705774911818769738611495989849851822470031904539213898643530439901999530718325889856610570875232105656803358377361686544032636032719317547503537644560795638900857064554332988769491365929710592849664259861971182320525465353448732180589477565522995273459329490472059304192402337846763732096506466054172621689536517215899496677282815027499812460164181661569374877344269583301444259617728112184631770193136261278034905902585485796632129496410953489345772578091302999821926591726499385463400467541157555318715434141551436306663886634557979620946746585822173833603348026384402378010789797684410977223660749106284037404316332954133072403824008454650373589103845905805026593320808306318951055230518149943508333735975573142396275875005614857574829179895552935236088357409953037700772628228443671835062387175667284865014275936139931920305320854743116135186138740383582330085103528209956748204323238500675888230435416296902715547436055778504983910830496843127265814130064290440472893512847740038351753274171441102351469400235375254354298862085666609806753193428061179809747402310052050434407753470096340984350155077832032736178342450618882209645662871663234106500253168401695092055799994568731646824202767227868487708620831578063867541723309228147854417124316002183642651204104642402870526215666206102931985045609468419862183108781525229945007024195037254340460518519187088710075398277594924705701872199228932723394600401085840269174970872144342668756141134450863269439511054555829861104684506800861743830652929356546877652036594512124115651791390994848515409728099270772211635991749288374917372223495974848046142573870524642790137105973909711113922068146897499065099377723176254303803522117140463340767116491117059366284055167091239255201238712479242079983172355162675335720683894532967432851019244759850409738443421322369929055249241806465996770017365378501551923166456470264161566845682019361090979603410295227750921425784937589423281027576655440533857540765578110711200735564930818841470415237474418582770872478265709662049516280461656668714427372449241779659966517703076299791454722890316833321967345704325820359904910504895209991998917682559449934896478444579000599040478865528636480382117805529712335455416300480175624150801297820984116057178629916004821261391523191630032493431531029861948635999530165880451478739523321520875261271121002732371422141003527094656793041763714595348450158706932562648933578226645790253112873953279054282600113239274151110603088966927671092768954664529130746344659066993279545266810280573321424410285333868294189754446291973368304833510899855777071681704383358075438865772775549333937780474368808774557906843481128638307006867364020347446417905435305441638758088427220584932003909463264608389452319297952258247134391162216497930246756025692345552613677014148912927516535469086387281269100817386585705173782324688693714194276061589802999023631037954822223676951257082557908499781561840344109688853245886537487211913586985930215594779116871061306385539498296323547264465907848765976945565144461556770750582693404199376179531602123014176461832929193277351367193329355292181360697743858931344612403619316322064929336672783080666105358119386483934181337106055970478070939510919267063703043219064055038156054954204091138684527215069163443739499070886660622306058826239736786636329323111346027224331476868627266784277129998989563454612745641571324037640147900330995354094218593288616101910206805889445828143030466974021730145171482644925255917015359623007328856099847126332075388630317222311781915185168120206633941603284931690306589693414789640233548911554911871903039263937056504204472254481850393554318180454458767750650402244923312228160300274085509470598117252455128761549770012945096044575832341634630211089644688116021843317423107073030259149529290396691216488589450959287616633306749369087147094966096837496150784171199081712977611535622957183332277689269125648700480964465386812343799057515412911570572062417646049003101920897840211953107849165291888199493459279294489279719233192012128989564460139273995834704751919303721520502101767332136413000117064161448216106250744729645446529120077259341144790560934476606539472870301679335706772984576871559953158545583415572058371963228096975477471687005226635084214985025146764774007489221537454301820442206982649733030962020350051103466953047089926135207218112248680911026401153373084837003136047137133454209838512776671865883077793900716276835772404186848568195690006857419486286241968679538187614152257957817631986933457030892884027782132474688847357445819073108562628627823290376958607041909027723698529515140284291556607914381379410538775537228023405718609318160185242385613351187629819344828250906216230532848789493280027216985956546549289007449524840432261330370892601615040584368187032263710111204642408032267237901076097842820865921267920650465477167012223919302313100139128012878266720939551294043079549795297066944839924084317880687990222527592105557012071255409569676533314545977281134824561945484690525275529868408637743575688583662449012325185250211741041272434458026364073173698310182860805171619679782143586774753615227627537564626703869101056410223208009982918049244518201203989799384260063691244653808929023385237854580040458390639626274767476826631271006500426881127154730258889472356205503068362801559779638886235379990581189515789997726269808421516767156636215704521714271640868539543700085310112395525788637380643610982351849096478898222782571249068875508814352857897245906573260131089921528705609371819891486089193636169645017366876737847997193104274586144324274907606138449299455232214512922410635606953023868747587590628720986885246908966632364205016659764361627375216182777304236497588720210183701672247063719709959685324382326297176914848979528014014901476009135172620350558451964147440192176809062585427933313301120583598498367044815559699429210477639946372637775906095254668825313436279250189249098472099306429966624366277979770775059039595789034802199387945867303951192300543898436005288626319035233017058914422056056017777045724546877684260469658215212796372400656800038948718951878496529950548955425703177888201153419099528163911759253620700886550724338249725321763907158724920872260007951016825002757358611078940984238717679496063411314562423138064160196547707919059205502719930292762211820924271262602309837621045460227734160490276765220138378213890208916609792382606273178782294545884292120889592470728076381461967191171546665903859953674373693530229927552608049511475202516007599744001358006271094710509384783096463339891840740731593808304024641486192362188958463969297419390063440857097757151035416307796352974198551390770560446694577360828785886710333346553778632277421828118581328749612335946114443405407147617011568736145717513616003589899511116444816266104639996953712310854551744431806540088611900723536196293085846325369512744847711750347303284441858401582353430866726673185683310490592493480181761720437847642078844119146849417191097167080714066137712510406917459051457008916115731771502847960394407056230634298538674422110162864485955586455038250316085356865452975831135422299593915965185207510322664991825277578576470555686462089249415906497935429337365046730569284645508025532376719348565659001859186492288666637499658458627419813404496401735879011925123732334855458563880715920004035795726851462772025373427602485748721054031201124435456632097952233763349802351799013747592710683697818946341223986681722193459332763815044082401996426629831606927183779723122366709656715783838580878050830321465413392839088471610420162540124903551194122767885727058126822320333318074206336763080909627688300232339367312179037842062992452935075436426291969847766818654922032900959488871772464991197670534463161208240910204354798011443840299264394390063760273670269738229591766584358368720811288186275228488286294278473545847238863509183037310730136486723153548011909288667248240729701914147927362121885913217631898915012250474641498150389189555637987515164256459549030412460843632119555001020329862899659349514078792671009945835662431080946146985268604801597297288354883949179518915564206497374966983946236465376039801317393685700119704595318871999052943144637807750871614744992111162851183560039366763546006676662154301562213050171387466702468460385489799024577652999074980431597772495245394278371999420449515869613194689288477216864295566012909332636678868626445952878653984945033868198351071635553382169315247660920441908379201002292693805721447526213380383916435722314251970176640681509218236709893122037586909987753072127895259947755645835507081985852841124419644104730396188816083831414040782635843580931103378679459934133340008188940141558077505370500054227927157457787453048208271443040519834710656081873811636429072921687697804884236377884963474864071498881035702669674147819283132678128190500026939370347231181302705503908196745431235135157520014144936329427473898282499371273776909274810626920177198095965379310213940370945512665898797284384994224434479686464773451613525089176084141252798803747742544358976461950335073405235553661471556033703623021312741912447296482174192912200704543588351637161348866093635409148759100052637446927483592118600250240875926635817785837485441956333791767584981019796047685016678957400029898250176083143488348309327690609316333186447683424785776762561929341912229137967496570895997292229074419356428154817436611973609679066649460252149640244100602123100574227891344156956791440891340898998465870959221348191535922758312184962326583311343834333540812017257417275765800481021829707751038749579763938049885114158994596086668459724937683933297966878128292383190917623060517082881977420010538556020042614396159185856883843410846541724297912749104250733353092091294797437285511533716852204727650494624859247723465112846837746199837171819367955587690565779781485616096161498826270823237258311856563302799562382996055502208772847167333988902760685117247889318853025218733620412100126807404542310797669931090086029598869264794685599074991131460747388148383465562815786884507642064382241366402318080591194028713772004634617995815191834840838929644420768444398283644448792536781095759337275092947019997440349213930305975250232481837201485879271331754867398628861626275214674561674089353352910117146015628446729460587033266124429220687121252730487221880080245002108081299477075954987486879678844319289996559880406095405268835080464219603356754996394613487665724811175964389605523014119619398516830754047452936418481529814575383450609324178104111606258628727613105306489489961104399603490662136299910324727017365069550537930754862445988617483919753370015304700066146741120060357909366254428547292543351824086746564585410969373997852157385191172308968389014321164720223876240167069384036925991769131773047802497975001218631655517325482536753174578836786912208883255572971978965997093321936650625623231311694649737520296484717458125245116203608121255528843788109038219739007938008408099232881109231143024408284042167631676430046317698056479528466075214800005566964289354592582469630519372458339364896448464573675666783752526844907775253610784810880399511844602292091456253943167637113445654388128143423268781801634770783337979064239297768249374881145382194936745134369144645852468184462080240672229206043464036834984199430725995717423534557783482402916547421962390983469778580906736566315750385091640443342960333780631108506219878040724904217162719429183205767046013546658320996555242641432426853774481525707032541862222541339815228785928236443433201984549059232595170378138803790829470951618356962530553172420211752987550193479860618503661839809149704907494661184401102302207212027926864819073001455859093371160834732890082020958829764043277092597961234674670095672090731411035735470734609080405158396344451481773504796461970569713699377666777279970175461153746640621047450088957519821119341444728792611973134432299460108734692901475015723007086204530708529745912220481842531280725756535810678786993469406032766456975494410729068875801264435010195252816694013495803330636528516838866105006289528212006000611421931914765168998918054051060289227975058505582889840499132503999130480254005511406264279672845053211858452108043815275715504688191252998778220775865382022488854204871150194494965712290464992827891528894284534538810424371199964807318046673400664317382334367467327094365880329031439990749556673913114920731035206522351969062493713109274517877635369350239290793319510782952506350719621669002773578073478945785729369543907136284810642488500567576702933488902084902164266561335743003678251346160366499463792707982304275214442915343548913316761176512862573402634843991108251159208834980903707008141174227088277370186177736114957129491855725132451121399671220481770277717734846834814998028467589521581753921854339871660262081330613901689900765120802550077772731347690355738546113783610876622796411877066775865888482868163620407410855822436195443413709734731637524180729718292717134506663780169538753235464220204361926340041217163761061796220909218077830703872507634256132284345127165279694154384502801500023238250783860485316399843121983563636193050233244404882467572190031835770441142452368288543832911387429385608301114281279038414722232003301023476485736901439683204502852974767428261890645642355733931552110864012178276744498168629944362335813121445797494941625738517123055050591498727536301464804649593713740773765533019136908903286743116291845532007297912590206862609998856247962268154110504258882900525288158569698647485037854442349899356771344158857778377317152444261900880482872158774999390520119526639437380411216676342713790655122521111106677145138039866538830450048425381379094095115107052879116448819523603187434441987528226408186482637483083258413350753269218951725269648409683330759077881692364766234249622136595950091646846921102053239911497785598063501210036468945048040225005309883624678922581661455894388785900136061087454500119655017988225248897819071682869663659951860629656998719153740236690635426307339848037954766094323915979394214531255858835466310095414530555538629054344196873468488970554390039359478803580885028845939400809283082737151259018914097863991624669365270657781992290267012440442888864555667022657200374945776357951496920347321953318580096418530808987257899799407668864405092330646529692272022326116612223101224342297592194248155554294116210947974831343115451883207861539134568532727656790392500055167145224207572361795229646661502820170592922483738180720764236045582287337829403554535705746277171275926382395290573106935361335925330233983523685407315212855162046889509923208003453062884380137647101204224051541584921546135624440182494073645228960749371325568489484200783939863282568658366864935279740616477585356701059982279141233485913890456505179965523025809916532473730819476924827752186320877089866099285122004354157506683148562314808420578843119601090937072219615068095841239478898211470283535117291379626484964290186455139590351756453883260341509418966930014895609382769604900670657123779954504869988130322784370627015195784657019421753024952381446757771759727521977368050591251527873219640438629969603866690651270259517202834402126876663609226604315210708726137565968584224745535712840357844319798981746741769452289263794452807567734123395488265375262796135026985928007638303358957913423899716447115070060131853016176835247279211116520767861671577649600282485119617509826749715582024864851948519424424641347350146907950931554714230913565024860113080858352708619167992372480448671881693667423059461698153532532227985234403872799501873808690377108140209199973194757781999154019206175325350929954115627836608868637865265165990912353347133203804688457759322233655189004980208921083290866512665962273878937244174397323351605167209310308281491996412801602103867634315114145987814859404399773210656662164520516407215882117821688407978534233726496291373288543184521381991820936209393997762821793256473332752380300318678454929212622847310641771624103888450748861437915888773415015123981309577785409402003850953409627277027539649295741888698103102164667848289192142809171518951131426089538507914160686248137041772383006419312424246086772558237757615472384036157336606914925540522368129237273890525522335428437892884999119300461731204846390439029050601821193813502093959607943638842186564918465647826954837892169636264429036458698865774256348828692572900044076876468250924432674609275455189909315431757121214900431309095041717467210381624984747684941983340223997092104380513871550800699731091300988046701753305250544056373452194097243593907994716774645354658555353331022325203524523964420605928397733664296642451398064197212537162033545924704761959987773598076516775631701921457662823558490732836738214103570552881827433932385408536832576256660103834822457868288975140583290331366380699384896166802961567770953618227153085205423399315686541708578166170860568139934714195137734789746087844383200164024717247939899098517770399906956689833655493404138086661284509243324826274384726099359585989413642961933281195543680771762273224953877399165879459914208534402210512770759632839894909710291024129790703022666581780400487924864641348062102659450414776485889525850354163302376316082923400728691222615092477479250472886184540874448344740100189583224255236708736922511408980074734211934256005257739893925430963723048955342949695871952601699696628496810298071612729867286026868506524996909862343751519217432773270607459213162082110554747992235623359833007573068233715495416259503673782522291592523873998634171551157987919718425177366815854281124920518160456231946092790544697979495111224106925258028339214969953787616379209888581427673948222129836269495867075348147429240641367994795978208375424055877841545180625350261416320954185339863445399043844446469219610509943738213901426479953027008324972345306103610020404728924348543463622443979345923756944757642102092592888418724141808859519803194012488716709995170198014895615135338174372659853035020871131947815086904642314537503558839949248188081236715614725271007130958948898593731356967436335575068569575714974257100742507831909770731123012455848568335367500552221400640963403588633053835351429586184539627765776287762499091839778378572839520660288286043457068109955431311881872096181098598176806882759184136385415790172403478847452904444900229139532783552598604800042198198450881808977666404762297228737518379092582025799430292417928291655679238051769209423971293708769448394724020894891459544125514745299145491438328163899808714942864666202846920750607631706485883399530727012827581336406265502799933786110575451584742856807522244340027461149197441691543636748144248360138394332682248584851925542322495419718447271879863452796306900902947314503465856047240875215708649952467970492196725146367808392481119404671126195764128759298191013729442194434486089863615484692405981044689987552850337135953972245149985586620732442313373871557224412754880324932798670383629276346019626534587660001433751193980102107558851332892912786988260458364223438076712398366844824048999657151641744036022898492028464116515529498899226823318614620652922020339894451695062578512615245326342988659937100892190095977414727302463157712497741990713889682063653472968236778529766601272011215066031938605065947023425178212250771880455497402736298842724988421458065513972145775910087065970539169986805436618880961833627982255415074549556031416177475671006058548138806687508998416845296295611897692833264358621602012873761460690061176727637776772089286970315196089470673689533868131429900637397081928951672421797073371421329968683216427199572514533639116972158606133454122232224725174837351110014863688055679279904272156262158466585725668080710520637102285925742575646707822219870313479175566067432225922837287057059985492971925466512656613418751240274583516536256078263305185847842594546278520258162116622262919413611602854540469658713562274967744725203055616132413265086062027671396217035809061419312647038160763382643743552422163374474069353354052763051871176881017984526747484045128987268826913922964240856950490258287911018640848730158729982270639475185158085711436280283852467599701274057408214997305707460272166055064679485786951976077263437560808066243060242202376642691393965487296567920629220490797851272114596783293725763094473799250300743951765185678096915184793366142308000618725608644529867444743588798275902210590349580247912677825270829384165729771575116285541526898260612425475240865062498930771271574434409930736614194383129393352688853780135908881097235194271481909960016774222254214608852463688009028981059451765379083539863792749083483715933533426137000640773500830619431667616734819103924716815826603115621266442646695931239963016744614210936935096129540240241778376266916717778328928243380524440942249209655027194316688369299285205877213878794852148129285123525789283653801151213236575972869346130730013204981455020911543219215950026764252643098502121787043345560377300461998557334977393653434500924857510322450803012414930686733141337027098695475497924770967207115720484841114588573753257818236949288698418403644625349382093501157118080199679385910163830892990116465639674577083233792769165547521305070807314174806501407835153730382069773471241062292648965834217766466136466526155931087493531599435910142619634810850171546365758773399749054378892944513588267511729330674396366678344043324555936112424506273108373254293781259728280185939033208593710378356772624284239006529875697187868066342667638746030414239747049637599034896597815981917456789151974242571154057996080933502513852745616896086645642962049230214430718687929076840367512168216401671183634008290086065837321924092311404227439278766719187573274804327591877484014460024458096691535317377001826678174846866680583054812269702140016160428797304937141478377291958345396220619649732676540402198453361701456030796786897522843536258635705887477459637639644194140565063462579475063383346800367522725096452185830218240885357785036024504398226155252870010170754050394066852331365298080114019772387805988855896467718779967107309210183529139575046318115088635023356674646935169799848581888673953172132720327589753978486544565252790638215682802535484284813014431208800608446307775109238671634003786623291403663371458636032149618074997424674658997832792192564067837857247516718229621674472567268031330489471727755771154321042276373267048637222079512249671260734696481156360275640615813962240457035536712961656198008183186412004718663962358266721596472492949712301855726313459855811318215008934826652929739742010528954075255564357223116437931235337649062055453604351702447519870347131204077045105141556692494608390597809500181154330433503548826537910710612651278295972429286871496811773370667849598424607119974721323599549299968994102127304442220776097393120076770956782719858669442825166958544572536138258509762033010778830140923254560156998042693100612300124995304944724026819305097801688176993597636994261057631375693713311917412894511007476831420109419581149410517145765749469948323465653364026405664805334997145199967156927516792725660321024539671487596167100083844041380149446224136778670918187010484019136292029490603489763853192391807381613091318618084259611760032812360440501771605466652276884017666558656983551757235429307544831432863925449523906855684729621311906687774683003956128360471041170606394589592984006376659953684543276841997700600430402346352144566378889891434785536032219800705944469137957671429184651218457168616811919201026550682246005014487489301665126366189950941443448489980528607675563082793092715976408755213035891326019909729505026844669386896004526700980473257790749759819282591874564575842676370120890572855375650156197655862965852462663534863625137301218233133927182902480782810378355676099758857049232389273645640557589646170594618627168014712767649186476466888832247076895310460414036159174984240372389256940560664605289783222134157141584732959059739443769138164066603666555492081991610776193760883750552554893107366135505059793619089725969235002843573723356947194380858829328352256581482009025208538773593004463631600028895695737771841566456500041163053363906367854012838626196119945692043308202956731138611728882279008175194056350804118404459614337995000790675825318270617408468126133633422199364924598879154598047447831388413335063478673467311806296336569585888235248242521059330275437266108453363534713010699548051604078790599677134510496329619482299890874157357797640214031395364310842156229027921552365033637081560197601378470449461162145534213738971556175644091593334906278152902215407641421824022322725710962451976069299893802856719930693783042471770915518254083432360057816842534972635437512099016121329277965723549012437959865781843102768746769960423859454388983294808611702397705749614592807167468399266220690409333842600934348205540965167478482176254376003606478353463491397085786956944054204441354103520915609104181822096216760557733468209241453391016720084123816352377668026384218111316339545895999185193022664558531743621912920672541340202023495047765174313086257585518383202593396914048423481216446654229960891804658666027744884112594596576461056831797980725947933107202470564031320182085349492645930315406966230082037050412280980042800991596033028248952087519804265251440164176567915399718405625885813089648995040596671941315299982376558001124783964895835448231750320501964327252843735242532127668097878551196954604652548455602414540202483629637059049414916024264789870648500966696091591061898659402436081282331316875944103461972129744947234893378268902470734950914560854920151454844589837903265245359203464209614631964119302458649157839492819450130070919581533295903375040104437770541405523934548898484060269032325750407558183821575538514640559433853479002228510918314193648089892152958439641285515302417858733205904180553044053526842897768905931452276565235926397216308510446467776239127832757363734840478637301925295819041867183191919611272559638731140128871281800738575127509331207137116068778883824459686057835862565365678371863464362143241117249404370022511804042277396656608872896194159058748323496487379029456123517174291215196522300469843507733734165787525766603746961102530984968805108687586712678658833251378589040624510825094900556250819512066624397958337296608057999370096853149039827468914693814205460042741349115767603919224871096363727091432543784548990819496716102727646837845573077763387322413116076292404232067970132791628515226017107939167482166886065355793180214083460182046255165172617108709305219665643833792901527079415564986292538797577703896611456134671381411690630278358870192562537929886689829470241412039615195220863476010841150846621295636055368928813124416296554410232243982634765493457508786108891111040708081744626671348450003439093464506631223246671794121265902116830385954830479504741861782899335026238475020042426908145006568892322242505981055867158256021309938062892960374777378555398343688265000522579325309075652755026040638186616130911577781232083633611519974876866403824255158615068321840690188212019602277234086986030296855809109456313365400031499173990268951256353791715299142199569469782217435660666381720025748678676530902226862769891299953669413550985383348542950228015235387871880877950675151916407869283039929969173120528416473127103001955876503193493802964094758564817935388036234006502283128502477295805208374983924019806444200659140284887095586242879490899047083880563953623017469122927349694570677865732254250631537443730274926648498915074992027588319379181117526984727324287405058326019368597401873660285824618609652681738004667315338130571623818765676125609040533167719803653315892867973406024205502552058834704994675930088878724007623636301844455284503121189428760197379002129513703496212674967606524040837763769832147802310384652207828340351377162560492323497019888962241612970426350748612150784879614301953325464693963997065471228892377408010304157251826414907107680003213649688519691055572517916782179210678637808823041752821065324828599506197483862510920526956496046395009681632624732944996833555046968456660408894712228917870466296960468720285154730991727841162104968646519354627935016198434110699892617843793277344676050394654102494220163624788530221402954142460957316455446824075296362955753070968234291281274643421063694641047968913394459691547214732340372539787403221383824048423568334574104040427298483124972227726501631443133719533669676735999575018689560791630171424776981270720717985271815321269466617427887888753639778488319983086306154342590100027783607852670547127497006707297090926097879305039853630386616283565983848286729612500242358397320327298393222776112569041824821912844135668840161126799053462898880495978173661243358488769112936258888676903561630229460174951573411894830475504583789313538009042433955453893528324500991650381255156457632649702996112898308342235196481918085033170610639386899591635088281466139564812747784234431054964730755862805744780796722458785390923306909267610672524345288823189688044847207181892422999441309591319059615364734652279999755059055218007665682798154421616353243934435028704718511448699944419780833614865015454796248394822887457944409122182359637082284470184564240204916973568948977982031767875755201857430854431105176648438911604958816927723442406081443491863407427614095895172652417985193292419797308609060903999592075030276346594770314016265272313683649651307655440507325050994907853772696873612602750045078828992031374919949026532481970008977761263294342996344618858082087362779365701698002818153566373249757646950485870233972651463926321626554868989308552674167668694529380075518245379085738210943487710501036735448759410389156494402211493960872450002041916874768363316546827715729654870512676606156202032461218432603214726991762127031726463104316199107035123147679008798010635545039315142078761158338050291459856754733831213738474998282993058284965298987380766597834989595816390699484947057675563973862903353136540435598156567849230062383564682870312035620349279258337611486404330826121475163922166077467184635437132551232186400186390518902717635498037616009199265012744020326815868352666485589440653610250052998924320450997831720156396835389981705796401115695108320391324053313769757675586099306482814695572348550144867809223918420937941458985148865058891462908978829178374078058211644877583910137051040338448559681153253410236386564372689610987167271295330229825503891063659061714335029761708766225356237306550361855912096551887422893464119540896015378656203931643649935552795159558027371520958351712218223830008047338013587045585382385747173713972214924819245928428563463904535683391628085741219531287695064508837578177159511950263618496849210586487886854334446888397676752253301836998867616195656409752239182859582459737071416470691167159772172612248692767003487715594906946756366222... Output truncated. Text exceeds maximum line length for Command Window display.
Hmm. Too big to display.
vpa(log10(Fn))
ans =
219139.07437775953273144585711381
So only around 220000 decimal digits in 0.09 of a second on my old CPU.
So that was easy, for an index that is a power of 2. But still not that difficult for an index that is not a power of 2 either. The trick is to use some other related identities, combined with the binary expansion of your desired index. Again, you may want to read carefully though my Fibonacci submission on the FEX.
dec2bin(1e6)
ans =
'11110100001001000000'
So, given that binary representation, we could compute the millionth Fibonacci number easily, because it is also possible to step up or down in index, by +/- 1.
