How to Calculate Fibonacci Numbers
Sources
TLDR
Summary
Chat with GigaBrain
What Redditors are SayingCalculating Fibonacci Numbers
Recursive Formula
The simplest way to calculate Fibonacci numbers is using the recursive formula: ( F(n) = F(n-1) + F(n-2) ), with base cases ( F(0) = 0 ) and ( F(1) = 1 ). This method is straightforward but can be inefficient for large values of ( n ) due to its exponential time complexity 
[3].
Matrix Exponentiation
A more efficient method involves matrix exponentiation. The Fibonacci sequence can be represented using a matrix:
[ A = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} ]
By repeatedly squaring this matrix, you can compute Fibonacci numbers in logarithmic steps. Specifically, ( A^n \times \begin{pmatrix} 1 \ 0 \end{pmatrix} ) yields the ( (n+1) )-th and ( n )-th Fibonacci numbers [1:1][4:3].
Binet's Formula
Another approach is Binet's formula, which uses the golden ratio ((\phi)):
[ F(n) = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}} ]
This closed-form expression allows direct computation of Fibonacci numbers but requires careful handling of floating-point precision [1:7][5:1]. Despite involving square roots and irrational numbers, it results in integers due to the properties of the golden ratio [5:6].
Iterative Approach
An iterative approach can also be used, where two variables are updated in a loop to generate Fibonacci numbers sequentially. This method is efficient and avoids recursion overhead [1:6].
Memoization
To improve efficiency in recursive calculations, memoization can be employed. By storing previously computed Fibonacci numbers, redundant calculations are avoided, significantly speeding up the process [1:8].
In summary, while the recursive method is simple, matrix exponentiation and Binet's formula offer more efficient alternatives for calculating large Fibonacci numbers. Iterative and memoized approaches provide practical solutions for programming tasks.
Cut through the noise directly on Google.
The GigaBrain browser extension dives deep into billions of discussions, bringing you the most relevant and informative answers on the spot.
Source Threads
POST SUMMARY • [1]Summarize
Ever wondered what the 100,000th Fibonacci number is?
Posted by iapetus-11 · in r/math · 4 years ago
ORIGINAL POSTStarting with 1, 1, 2, 3, 5... it's
2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777453778337299916214634050054669860390862750996639366409211890125271960172105060300350586894028558103675117658251368377438684936413457338834365158775425371912410500332195991330062204363035213756525421823998690848556374080179251761629391754963458558616300762819916081109836526352995440694284206571046044903805647136346033000520852277707554446794723709030979019014860432846819857961015951001850608264919234587313399150133919932363102301864172536477136266475080133982431231703431452964181790051187957316766834979901682011849907756686456845066287392485603914047605199550066288826345877189410680370091879365001733011710028310473947456256091444932821374855573864080579813028266640270354294412104919995803131876805899186513425175959911520563155337703996941035518275274919959802257507902037798103089922984996304496255814045517000250299764322193462165366210841876745428298261398234478366581588040819003307382939500082132009374715485131027220817305432264866949630987914714362925554252624043999615326979876807510646819068792118299167964409178271868561702918102212679267401362650499784968843680975254700131004574186406448299485872551744746695651879126916993244564817673322257149314967763345846623830333820239702436859478287641875788572910710133700300094229333597292779191409212804901545976262791057055248158884051779418192905216769576608748815567860128818354354292307397810154785701328438612728620176653953444993001980062953893698550072328665131718113588661353747268458543254898113717660519461693791688442534259478126310388952047956594380715301911253964847112638900713362856910155145342332944128435722099628674611942095166100230974070996553190050815866991144544264788287264284501725332048648319457892039984893823636745618220375097348566847433887249049337031633826571760729778891798913667325190623247118037280173921572390822769228077292456662750538337500692607721059361942126892030256744356537800831830637593334502350256972906515285327194367756015666039916404882563967693079290502951488693413799125174856667074717514938979038653338139534684837808612673755438382110844897653836848318258836339917310455850905663846202501463131183108742907729262215943020429159474030610183981685506695026197376150857176119947587572212987205312060791864980361596092339594104118635168854883911918517906151156275293615849000872150192226511785315089251027528045151238603792184692121533829287136924321527332714157478829590260157195485316444794546750285840236000238344790520345108033282013803880708980734832620122795263360677366987578332625485944906021917368867786241120562109836985019729017715780112040458649153935115783499546100636635745448508241888279067531359950519206222976015376529797308588164873117308237059828489404487403932053592935976454165560795472477862029969232956138971989467942218727360512336559521133108778758228879597580320459608479024506385194174312616377510459921102486879496341706862092908893068525234805692599833377510390101316617812305114571932706629167125446512151746802548190358351688971707570677865618800822034683632101813026232996027599403579997774046244952114531588370357904483293150007246173417355805567832153454341170020258560809166294198637401514569572272836921963229511187762530753402594781448204657460288485500062806934811398276016855584079542162057543557291510641537592939022884356120792643705560062367986544382464373946972471945996555795505838034825597839682776084731530251788951718630722761103630509360074262261717363058613291544024695432904616258691774630578507674937487992329181750163484068813465534370997589353607405172909412697657593295156818624747127636468836551757018353417274662607306510451195762866349922848678780591085118985653555434958761664016447588028633629704046289097067736256584300235314749461233912068632146637087844699210427541569410912246568571204717241133378489816764096924981633421176857150311671040068175303192115415611958042570658693127276213710697472226029655524611053715554532499750843275200199214301910505362996007042963297805103066650638786268157658772683745128976850796366371059380911225428835839194121154773759981301921650952140133306070987313732926518169226845063443954056729812031546392324981793780469103793422169495229100793029949237507299325063050942813902793084134473061411643355614764093104425918481363930542369378976520526456347648318272633371512112030629233889286487949209737847861884868260804647319539200840398308008803869049557419756219293922110825766397681361044490024720948340326796768837621396744075713887292863079821849314343879778088737958896840946143415927131757836511457828935581859902923534388888846587452130838137779443636119762839036894595760120316502279857901545344747352706972851454599861422902737291131463782045516225447535356773622793648545035710208644541208984235038908770223039849380214734809687433336225449150117411751570704561050895274000206380497967960402617818664481248547269630823473377245543390519841308769781276565916764229022948181763075710255793365008152286383634493138089971785087070863632205869018938377766063006066757732427272929247421295265000706646722730009956124191409138984675224955790729398495608750456694217771551107346630456603944136235888443676215273928597072287937355966723924613827468703217858459948257514745406436460997059316120596841560473234396652457231650317792833860590388360417691428732735703986803342604670071717363573091122981306903286137122597937096605775172964528263757434075792282180744352908669606854021718597891166333863858589736209114248432178645039479195424208191626088571069110433994801473013100869848866430721216762473119618190737820766582968280796079482259549036328266578006994856825300536436674822534603705134503603152154296943991866236857638062351209884448741138600171173647632126029961408561925599707566827866778732377419444462275399909291044697716476151118672327238679208133367306181944849396607123345271856520253643621964198782752978813060080313141817069314468221189275784978281094367751540710106350553798003842219045508482239386993296926659221112742698133062300073465628498093636693049446801628553712633412620378491919498600097200836727876650786886306933418995225768314390832484886340318940194161036979843833346608676709431643653538430912157815543512852077720858098902099586449602479491970687230765687109234380719509824814473157813780080639358418756655098501321882852840184981407690738507369535377711880388528935347600930338598691608289335421147722936561907276264603726027239320991187820407067412272258120766729040071924237930330972132364184093956102995971291799828290009539147382437802779051112030954582532888721146170133440385939654047806199333224547317803407340902512130217279595753863158148810392952475410943880555098382627633127606718126171022011356181800775400227516734144169216424973175621363128588281978005788832454534581522434937268133433997710512532081478345067139835038332901313945986481820272322043341930929011907832896569222878337497354301561722829115627329468814853281922100752373626827643152685735493223028018101449649009015529248638338885664893002250974343601200814365153625369199446709711126951966725780061891215440222487564601554632812091945824653557432047644212650790655208208337976071465127508320487165271577472325887275761128357592132553934446289433258105028633583669291828566894736223508250294964065798630809614341696830467595174355313224362664207197608459024263017473392225291248366316428006552870975051997504913009859468071013602336440164400179188610853230764991714372054467823597211760465153200163085336319351589645890681722372812310320271897917951272799656053694032111242846590994556380215461316106267521633805664394318881268199494005537068697621855231858921100963441012933535733918459668197539834284696822889460076352031688922002021931318369757556962061115774305826305535862015637891246031220672933992617378379625150999935403648731423208873977968908908369996292995391977217796533421249291978383751460062054967341662833487341011097770535898066498136011395571584328308713940582535274056081011503907941688079197212933148303072638678631411038443128215994936824342998188719768637604496342597524256886188688978980888315865076262604856465004322896856149255063968811404400429503894245872382233543101078691517328333604779262727765686076177705616874050257743749983775830143856135427273838589774133526949165483929721519554793578923866762502745370104660909382449626626935321303744538892479216161188889702077910448563199514826630802879549546453583866307344423753319712279158861707289652090149848305435983200771326653407290662016775706409690183771201306823245333477966660525325490873601961480378241566071271650383582257289215708209369510995890132859490724306183325755201208090007175022022949742801823445413711916298449914722254196594682221468260644961839254249670903104007581488857971672246322887016438403908463856731164308169537326790303114583680575021119639905615169154708510459700542098571797318015564741406172334145847111268547929892443001391468289103679179216978616582489007322033591376706527676521307143985302760988478056216994659655461379174985659739227379416726495377801992098355427866179123126699374730777730569324430166839333011554515542656864937492128687049121754245967831132969248492466744261999033972825674873460201150442228780466124320183016108232183908654771042398228531316559685688005226571474428823317539456543881928624432662503345388199590085105211383124491861802624432195540433985722841341254409411771722156867086291742124053110620522842986199273629406208834754853645128123279609097213953775360023076765694208219943034648783348544492713539450224591334374664937701655605763384697062918725745426505879414630176639760457474311081556747091652708748125267159913793240527304613693961169892589808311906322510777928562071999459487700611801002296132304588294558440952496611158342804908643860880796440557763691857743754025896855927252514563404385217825890599553954627451385454452916761042969267970893580056234501918571489030418495767400819359973218711957496357095967825171096264752068890806407651445893132870767454169607107931692704285168093413311046353506242209810363216771910420786162184213763938194625697286781413636389620123976910465418956806197323148414224550071617215851321302030684176087215892702098879108938081045903397276547326416916845445627600759561367103584575649094430692452532085003091068783157561519847567569191284784654692558665111557913461272425336083635131342183905177154511228464455136016013513228948543271504760839307556100908786096663870612278690274831819331606701484957163004705262228238406266818448788374548131994380387613830128859885264201992286188208499588640888521352501457615396482647451025902530743172956899636499615707551855837165935367125448515089362904567736630035562457374779100987992499146967224041481601289530944015488942613783140087804311431741858071826185149051138744831358439067228949408258286021650288927228387426432786168690381960530155894459451808735197246008221529343980828254126128257157209350985382800738560472910941184006084485235377833503306861977724501886364070344973366473100602018128792886991861824418453968994777259482169137133647470453172979809245844361129618997595696240971845564020511432589591844724920942930301651488713079802102379065536525154780298059407529440513145807551537794861635879901158192019808879694967187448224156836463534326160242632934761634458163890163805123894184523973421841496889262398489648642093409816681494771155177009562669029850101513537599801272501241971119871526593747484778935488777815192931171431167444773882941064615028751327709474504763922874890662989841540259350834035142035136168819248238998027706666916342133424312054507359388616687691188185776118135771332483965209882085982391298606386822804754362408956522921410859852037330544625953261340234864689275060526893755148403298542086991221052597005628576707702567695300978970046408920009852106980295419699802138053295798159478289934443245491565327845223840551240445208226435420656313310702940722371552770504263482073984454889589248861397657079145414427653584572951329719091947694411910966797474262675590953832039169673494261360032263077428684105040061351052194413778158095005714526846009810352109249040027958050736436961021241137739717164869525493114805040126568351268829598413983222676377804500626507241731757395219796890754825199329259649801627068665658030178877405615167159731927320479376247375505855052839660294566992522173600874081212014209071041937598571721431338017425141582491824710905084715977249417049320254165239323233258851588893337097136310892571531417761978326033750109026284066415801371359356529278088456305951770081443994114674291850360748852366654744869928083230516815711602911836374147958492100860528981469547750812338896943152861021202736747049903930417035171342126923486700566627506229058636911882228903170510305406882096970875545329369434063981297696478031825451642178347347716471058423238594580183052756213910186997604305844068665712346869679456044155742100039179758348979935882751881524675930878928159243492197545387668305684668420775409821781247053354523194797398953320175988640281058825557698004397120538312459428957377696001857497335249965013509368925958021863811725906506436882127156815751021712900765992750370228283963962915973251173418586721023497317765969454283625519371556009143680329311962842546628403142444370648432390374906410811300792848955767243481200090309888457270907750873638873299642555050473812528975962934822878917619920725138309388288292510416837622758204081918933603653875284116785703720989718832986921927816629675844580174911809119663048187434155067790863948831489241504300476704527971283482211522202837062857314244107823792513645086677566622804977211397140621664116324756784216612961477109018826094677377686406176721484293894976671380122788941309026553511096118347012565197540807095384060916863936906673786627209429434264260402902158317345003727462588992622049877121178405563348492490326003508569099382392777297498413565614830788262363322368380709822346012274241379036473451735925215754757160934270935192901723954921426490691115271523338109124042812102893738488167358953934508930697715522989199698903885883275409044300321986834003470271220020159699371690650330547577095398748580670024491045504890061727189168031394528036165633941571334637222550477547460756055024108764382121688848916940371258901948490685379722244562009483819491532724502276218589169507405794983759821006604481996519360110261576947176202571702048684914616894068404140833587562118319210838005632144562018941505945780025318747471911604840677997765414830622179069330853875129298983009580277554145435058768984944179136535891620098725222049055183554603706533183176716110738009786625247488691476077664470147193074476302411660335671765564874440577990531996271632972009109449249216456030618827772947750764777446452586328919159107444252320082918209518021083700353881330983215894608680127954224752071924134648334963915094813097541433244209299930751481077919002346128122330161799429930618800533414550633932139339646861616416955220216447995417243171165744471364197733204899365074767844149929548073025856442942381787641506492878361767978677158510784235702640213388018875601989234056868423215585628508645525258377010620532224244987990625263484010774322488172558602233302076399933854152015343847725442917895130637050320444917797752370871958277976799686113626532291118629631164685159934660693460557545956063155830033697634000276685151293843638886090828376141157732003527565158745906567025439437931104838571313294490604926582363108949535090082673154497226396648088618041573977888472892174618974189721700770009862449653759012727015227634510874906948012210684952063002519011655963580552429180205586904259685261047412834518466736938580027700252965356366721619883672428226933950325930390994583168665542234654857020875504617520521853721567282679903418135520602999895366470106557900532129541336924472492212436324523042895188461779122338069674233980694887270587503389228395095135209123109258159006960395156367736067109050566299603571876423247920752836160805597697778756476767210521222327184821484446631261487584226092608875764331731023263768864822594691211032367737558122133470556805958008310127481673962019583598023967414489867276845869819376783757167936723213081586191045995058970991064686919463448038574143829629547131372173669836184558144505748676124322451519943362182916191468026091121793001864788050061351603144350076189213441602488091741051232290357179205497927970924502479940842696158818442616163780044759478212240873204124421169199805572649118243661921835714762891425805771871743688000324113008704819373962295017143090098476927237498875938639942530595331607891618810863505982444578942799346514915952884869757488025823353571677864826828051140885429732788197765736966005727700162592404301688659946862983717270595809808730901820120931003430058796552694788049809205484305467611034654748067290674399763612592434637719995843862812391985470202414880076880818848087892391591369463293113276849329777201646641727587259122354784480813433328050087758855264686119576962172239308693795757165821852416204341972383989932734803429262340722338155102209101262949249742423271698842023297303260161790575673111235465890298298313115123607606773968998153812286999642014609852579793691246016346088762321286205634215901479188632194659637483482564291616278532948239313229440231043277288768139550213348266388687453259281587854503890991561949632478855035090289390973718988003999026132015872678637873095678109625311008054489418857983565902063680699643165033912029944327726770869305240718416592070096139286401966725750087012218149733133695809600369751764951350040285926249203398111014953227533621844500744331562434532484217986108346261345897591234839970751854223281677187215956827243245910829019886390369784542622566912542747056097567984857136623679023878478161201477982939080513150258174523773529510165296934562786122241150783587755373348372764439838082000667214740034466322776918936967612878983488942094688102308427036452854504966759697318836044496702853190637396916357980928865719935397723495486787180416401415281489443785036291071517805285857583987711145474240156416477194116391354935466755593592608849200546384685403028080936417250583653368093407225310820844723570226809826951426162451204040711501448747856199922814664565893938488028643822313849852328452360667045805113679663751039248163336173274547275775636810977344539275827560597425160705468689657794530521602315939865780974801515414987097778078705357058008472376892422189750312758527140173117621279898744958406199843913365680297721208751934988504499713914285158032324823021340630312586072624541637765234505522051086318285359658520708173392709566445011404055106579055037417780393351658360904543047721422281816832539613634982525215232257690920254216409657452618066051777901592902884240599998882753691957540116954696152270401280857579766154722192925655963991820948894642657512288766330302133746367449217449351637104725732980832812726468187759356584218383594702792013663907689741738962252575782663990809792647011407580367850599381887184560094695833270775126181282015391041773950918244137561999937819240362469558235924171478702779448443108751901807414110290370706052085162975798361754251041642244867577350756338018895379263183389855955956527857227926155524494739363665533904528656215464288343162282921123290451842212532888101415884061619939195042230059898349966569463580186816717074818823215848647734386780911564660755175385552224428524049468033692299989300783900020690121517740696428573930196910500988278523053797637940257968953295112436166778910585557213381789089945453947915927374958600268237844486872037243488834616856290097850532497036933361942439802882364323553808208003875741710969289725499878566253048867033095150518452126944989251596392079421452606508516052325614861938282489838000815085351564642761700832096483117944401971780149213345335903336672376719229722069970766055482452247416927774637522135201716231722137632445699154022395494158227418930589911746931773776518735850032318014432883916374243795854695691221774098948611515564046609565094538115520921863711518684562543275047870530006998423140180169421109105925493596116719457630962328831271268328501760321771680400249657674186927113215573270049935709942324416387089242427584407651215572676037924765341808984312676941110313165951429479377670698881249643421933287404390485538222160837088907598277390184204138197811025854537088586701450623578513960109987476052535450100439353062072439709976445146790993381448994644609780957731953604938734950026860564555693224229691815630293922487606470873431166384205442489628760213650246991893040112513103835085621908060270866604873585849001704200923929789193938125116798421788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875I'm learning Nim and thought that this would be a cool thing to do since Nim is faster than any programming language I've learned so far. Here's the code if you're interested.
Another fun way to calculate the nth Fibonacci number is with some matrix multiplication.
Let A be the matrix
1 1
1 0Let x be the matrix
1
0It is not too hard to show that A^n x =
F_{n+1}
F_{n}Right now this looks like you're just jamming in the definition of the Fibonacci sequence into a matrix multiplication. But the key insight is, since we've framed it as repeated matrix multiplication, we can calculate A^n in fewer than n steps by repeated squaring! (For example, A^50 = (A^25)^2 = (A*A^24)^2 = (A*(A^12)^2)^2 etc.)
I've ran into a very curious hand-derived 4x4 matrix that calculates up to four terms in parallel that I am trying to generalize into higher-degree matrices(NxN), that also follows the pattern of repeated squaring to get an N-th term in less than N steps. Care to provide some insight? Been sitting on this for quite some time nowhttps://github.com/Wunkolo/qFib
There's nothing inherently special about your 4x4 matrix. Actually it's essentially a 3x3 matrix since your 4th column is zero. In general, there's the following relation:
F(n+k) = [F(k+1) - m]*F(n) + [F(k) + m]*F(n-1) + m*F(n-2),for arbitrary values of m. In your case, you did
F(n+4) = [F(5) - 1]*F(n) + [F(4) + 1]*F(n-1) + 1*F(n-2) + 0*F(n-3),
F(n+3) = [F(4) - 2]*F(n) + [F(3) + 2]*F(n-1) + 2*F(n-2) + 0*F(n-3),
F(n+2) = [F(3) - 0]*F(n) + [F(2) + 0]*F(n-1) + 0*F(n-2) + 0*F(n-3),
F(n+1) = [F(2) - 0]*F(n) + [F(1) + 0]*F(n-1) + 0*F(n-2) + 0*F(n-3),which you can write in matrix form and apply repeatedly. But you can extend this as much as you want.
There is a 2 by 2 matrix that maps the 2 element vector representing the two previous values of the Fibonacci sequence to the next pair (advances it one step, so there is overlap).
Can you figure out how to use this to efficiently calculate a number very deep in the Fibonacci sequence without computing all the intermediate values?
Hint: >!What does squaring the matrix do? What map does it now represent?!<
Hint 2: >!To find the nth Fibonacci number, consider its binary representation.!<
Just so you are aware, there is a closed formula for the Nth fibonacci number involving the golden ratio. So you could just plug in N=100,000.
But it is awesome that you are learning to code and decided to find it out this way too!
Binet's formula isn't great since it requires an unknown floating-point accuracy going in.
The matrix method mentioned in several places is objectively better than either for large powers. Exponentiation is better because you can use squaring to quickly reach high exponents; the 2^17 th fibonacci number would be found by squaring the matrix 17 times.
Assuming both addition and 2x2 matrix squaring are both constant time (definitely not true as the number of decimal places also grows), finding the nth fibonacci number would be O(n) using the iterative formula versus O(log_2(n)) with matrix multiplication. You can also naively write a simple equation
> fun F(n) = F(n-1) + F(n-2)
that is O( 𝜙^n ).
That last part is even worse. Funnily the time complexity is equal to the fibonacci value. You can count the number of functions calls:
F(n) and F(n-1) are called once. F(n-2) is called for every F(n-1) and every F(n).
In general F(n-i) is called for every F(n-(i-1)) and for every F(n-(i-2)). You can probably see where this is going. The complexity is thus somewhere in the ballpark of O(1.61^n ) which is way worse than O(n^2 ).
Keep in mind that since the Fibonacci sequence increases exponentially, the 2^100000th Fibonacci number has approximately that many digits, so you wouldn't be able to write it down. (There are ~10^80 total atoms in the entire universe)
A little more pythonic
import more_itertools
def fib():
a = 0
b = 1
while True:
yield a
a, b = b, a + b
print(more_itertools.nth(fib(), 100_000))You could try also with :
from functools import lru_cache@lru_cache(maxsize = 1000) def fibonacci(input_value): if input_value == 1: return 1 elif input_value == 2: return 1 elif input_value > 2: return fibonacci(input_value -1) + fibonacci(input_value -2)for i in range(1, 201): print("fib({}) = ".format(i), fibonacci(i))
From: https://towardsdatascience.com/memoization-in-python-57c0a738179a
Consider what happens if you multiply the given matrix by any arbitrary column vector with two elements, say [a, b]. You'll get a new column vector with entries [a+b, a]. So if you start with the vector [1, 0] and then left-multiply by A many times, you'll get a sequence like this:
- [1, 0]
- [1, 1]
- [2, 1]
- [3, 2]
- [5, 3]
- [8, 5]
- [13, 8]
So we can see that A^n * [1, 0] gives you a column vector with the n+1-st fibonacci number as its first item.
So let's say you wanted to compute the 184th fibonacci number. This means we'd need to compute A^183 * [1, 0]. The naive way to do this is to do 183 steps of matrix multiplication. But there is a faster way!
Note that by "repeated squaring" we can easily calculate A^2, A^4, A^8, etc.
​
A^2 = 1 1 * 1 1 = 2 1
1 0 1 0 1 1
A^4 = 2 1 * 2 1 = 5 3
1 1 1 1 3 2
A^8 = 5 3 * 5 3 = 34 21
3 2 3 2 21 13​
Now let's go back to computing the 184th Fibonacci number. As we said earlier, this means that we need to compute A^183. The trick now is to use the easy-to-calculate powers of A, which are all powers of 2. So in binary we have 183 = 10110111, or alternatively 183 = 128 + 32 + 16 + 4 + 2 + 1. Using this, we have
A^183 = A^(128 + 32 + 16 + 4 + 2 + 1) = A^128 * A^32 * A^16 * A^4 * A^2 * A
So instead of doing 183 matrix multiplications, we had to do 7 to calculate A^2, A^4, A^8, A^16, A^32, A^64, A^128, and then 6 more to calculate A^183 from those building blocks = 13 total matrix multiplications.
Obviously, this scales even better vs the iterative method as you try to calculate higher and higher powers. :)
Better yet, look at the powers of the matrix
- 1 1
- 1 0
and look up exponentiation by squaring. This is formally equivalent to the fastest algorithm for the nth Fibonacci number where you only care about getting the nth Fibonacci number and nothing else.
r/askmath • [2]Summarize
Some hours ago, solving another problem, I found "empirically" that for the Fibonacci numbers, for even index, they verify that
5 F(2n)^2 + 4 = p^2
the result is a perfect square.
These are the first cases
F(2n) : {1, 3, 8, 21, 55, 144, 377, 987}
5 F(2n)^2 + 4): {9, 49, 324, 2209, 15129, 103684, 710649, 4870849}
sqrt(5 F(2n)^2 + 4) = {3, 7, 18, 47, 123, 322, 843, 2207}
While for odd indexes
5 F(2n-1)^2 - 4 = q^2
gives another perfect square
F(2n-1): {1, 2, 5, 13, 34, 89, 233, 610}
5F(2n-1)^2 - 4: {1, 16, 121, 841, 5776, 39601, 271441, 1860496}
sqrt(5 F(2n-1)^2 - 4): {1, 4, 11, 29, 76, 199, 521, 1364}
Joining the two sequences we get
{1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
that are the Lucas numbers (https://oeis.org/A000204 )
so
5 F(n)^2 + 4(-1)^n = L(n)^2
Is there an easy proof of this?
Note that the Lucas numbers follow the same recursion rule as the Fibonacci numbers. You've already established enough base cases that you should be able to have this pop out by showing that, if 5 F(n-2)^2 + 4(-1)^n = L(n-2)^2 and 5 F(n-1)^2 - 4(-1)^n = L(n-1)^2, then 5 F(n)^2 + 4(-1)^n = L(n)^2.
I suspect this will pop out without too much work from using the explicit form for Fn in terms of powers of the gold and silver ratios. The leading 5 coefficient is a big hint. It's a neat property though, nice job.
This identity will probably have a relatively simple proof with strong induction, but I am not sure about the details.
https://en.wikipedia.org/wiki/Fibonacci_sequence Go to "Relation to the golden ratio" section, then to "Identification". It uses binet formula and is quite short.
You can also use https://en.wikipedia.org/wiki/Cassini_and_Catalan_identities Fn^2 +(-1)^n = F{n+1}F{n-1} Multiply it by 4 4Fn + 4 (-1)^n = 4F{n+1}F{n-1} = 4F{n}F{n-1}+ 4 F{n-1}F{n-1} Add Fn^2 to both sides 5Fn + 4 (-1)^n = Fn^2 + 4 F{n}F{n-1} 4 F{n-1}^2= (Fn + 2F{n-1})^2
r/desmos • [3]Summarize
Tutorial to compute the Fibonacci Sequence (graph not included)
Posted by Puzzleheaded_Two415 · in r/desmos · 4 months agoMake a function (preferably label it F(x)) and program it as f(x)=f(x-1)+f(x-2) and input the base cases (preferably F(0)=0 and F(1)=1). It's literally that simple.
I'll post more tutorials in the future, and it's ok if the mods remove this post.
Or you could also say f(x) = ( (1 + sqrt(5))^n - (1 - sqrt(5))^n ) / (2^n • sqrt(5))
Edit: Fixed Formatting
Don't know why you're getting downvoted lol, you're right
Formatting is a bit wrong as you have to put the denominator in parentheses (2^n sqrt(5))
Ah my bad
what about the numbers in between
This is a simple tutorial, this only works for whole numbers, sorry
Yep
r/programming • [4]Summarize
Calculating the Fibonacci numbers on GPU
Posted by ketralnis · in r/programming · 3 months agoI've been sitting on this little trick I found for a little while. While it's useful and possibly lends itself to SIMD/GPU-code, Fibonacci numbers get very large very quickly that it's almost always better to just have a look-up table when you are limited to 32 or 64 bit integers. With 32-bit integers, you only need a table of 47 elements before overflowing, with 64-bit numbers, you would need 93.
The real power of using matmul for Fibonaci numbers is that you can more efficiently compute them using Exponentiation by Squaring(2*log N matmuls instead of N matmuls, the other comment has an implementationin python) Otherwise you're better off using the normal scalar algorithm.
Given the recursive nature of the fibonacci sequence, I don't think a GPU is a good approach here.
I think this is technically not a "scan" operation. Looking at the definition of scan at the beginning, it operates on the inputs only (though can be rewritten to be a recursive form). But by taking the outputs from one step as the inputs to the next step, I think this violates the definition of the scan operation.
the definition of scan does match the code.
notice how y1=x0 * x1, and y2=x0 * x1 * x2 = y1 * x2.
it is the same as defining it using it as yn=y(n-1) * xn.
No.
The inputs to this sequence are 0,1,0,0,0,0,0,0,0,0,0...
Doing a scan (with addition) on that will yield 0,1,1,1,1,1,1.
> out: 0;1;3;
Can someone explain why applying + to (0,1,2) and (3) outputs this?
It looks like out(3) is saying that the output will be of length 3. The + is the operation that the scan is using, and what that looks like for the first example (an exclusive scan) is:
With input (1,2,3)
First output: the sum of all terms before the first. This is an empty sum, so it's 0
Second output: the sum of all terms before the second. This is just 1
Third output: the sum of all terms before the third. This is 1+2=3
A couple more terms there would probably have helped to see the pattern for those unfamiliar with the concept
$ cat fib.py
import numpy as np
n = 99999999
Mod = 9837
R = np.identity(2, dtype=int)
M = np.matrix([[1, 1], [1, 0]], dtype=int)
while n:
if n % 2:
R = (R * M) % Mod
M = (M * M) % Mod
n //= 2
print(R[0, 1])
$ time python3 fib.py
7558
real 0m0.054s
user 0m0.046s
sys 0m0.008sWhat is the mod based on?
on the article, they used the same mod
r/mathmemes • [5]Summarize
Came across the formula for n-th Fibonacci number in my old high school textbook during an induction lesson, I was intrigued to see the golden ratio appear in the formula and wondered how it still managed to produce natural numbers despite containing square roots.
Posted by 94rud4 · in r/mathmemes · 6 months ago
You can prove that it produces natural numbers through induction for all cases! It is a very fascinating formula indeed, just shows how interconnected all of math is.
East way is to use linear algebra and the eigendecompositiom
Personally I would say that using generating functions and expanding the polynomial would be better though. It may be easier, but not necessarily familiar to as many people.
Everyone knows that Fibonacci isn't real, it's all a hoax like the round earth or pirates
the square roots cancel out
Right. The expansions of both exponentials contain rational terms that cancel out due to subtraction and irrational terms that don’t but include a factor of sqrt(5). Multiplying by 1/sqrt(5) makes the whole expression rational. Proof that that rational is actually an integer is left to the reader. :)
Been trying to prove this for general Lucas sequences and it’s a nightmare. The sources I’ve seen either glaze over it or use some weird polynomial ring algebra which I don’t get
It has something to do with the golden ratio
He clearly knows what the golden ratio is, he talks about it it in the title
It has something to do with the subtraction
Whoops, I'm an idiot. Disregard me.
Basically, an = an-1 + an-2 will lead you to solving r² = r + 1, to which the golden ratio is one of the two solutions (-1/phi being the other one and is the number in the second parenthesis)
r/Python • [6]Summarize
How I Calculated the 1,000,000th Fibonacci Number with Python
Posted by 1Blademaster · in r/Python · 4 years ago
Nice post! Maybe you will want to quickly look into this site
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
in section 3:
>F(2n-1) = F(n-1)^2 + F(n)^2
>
>F(2n) = (2F(n-1) + F(n)) * F(n)
so you can actually get quite easily a O(log n) time solution!
Here's my version I wrote a while back in js with BigInt:
let cache = {0: 0n, 1: 1n, 2: 1n, 3: 2n};
// Compute the nth fibonnacci number in O(log n) time complexity
// Only works with positive numbers
const recursiveFib = (n) => {
if (cache[n] === undefined) {
// http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
// F(2n-1) = F(n-1)2 + F(n)2
// F(2n) = (2F(n-1) + F(n)) * F(n)
if (n % 2) {
let f1 = recursiveFib((n - 1) / 2);
let f2 = recursiveFib((n + 1) / 2);
cache[n] = f1 ** 2n + f2 ** 2n;
} else {
let f1 = recursiveFib(n / 2 - 1);
let f2 = recursiveFib(n / 2);
cache[n] = (2n * f1 + f2) * f2;
}
}
return cache[n];
};
recursiveFib(1_000_000);Running this code on my machine gave me similar results to yours:
node fibonacci.js 1.16s user 0.03s system 99% cpu 1.196 totalOh that's quite interesting I'll have to check it out! I think nodejs is meant to be faster than Python, makes me wonder if this method will mean it's faster overall on my machine and in Python
That's the example given in the wikipedia article for dynamic programming
There is also an example of bottom up approach which doesn't require memoization (i.e. caching repetitive subresults).
[Edit] Sorry I didn't read quite well the solution. There are additional optimization just ignore my response.
cache = {
0: 0,
1: 1,
2: 1,
3: 2,
}
def recursiveFib(n):
if cache.get(n, None) is None:
# http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
# F(2n-1) = F(n-1)^2 + F(n)^2
# F(2n) = (2F(n-1) + F(n)) * F(n)
if n % 2:
f1 = recursiveFib((n - 1) / 2)
f2 = recursiveFib((n + 1) / 2)
cache[n] = f1 ** 2 + f2 ** 2
else:
f1 = recursiveFib(n / 2 - 1)
f2 = recursiveFib(n / 2)
cache[n] = (2 * f1 + f2) * f2
return cache[n]
recursiveFib(1_000_000)The results were... unexpected:
python3 fib.py 0.03s user 0.01s system 89% cpu 0.047 totalthis is faster than any implementation so far! (note that I don't print the result to speed up the code). I printed the result, and it is effectively the same as my js implementation and your implementation
There's a codewars kata for this. "The Millionth Fibonacci Kata"
Here was my take on it:
from functools import lru_cache
@lru_cache(maxsize=None)
def fbr(n):
if n > 2: return fbr(n//2+1)*fbr(n-n//2) + fbr(n//2)*fbr(n-n//2-1)
return [0,1,1][n]It's basically a recursive version of Binet’s formula with memoization.
The 3millionth fib calculates instantly, but is too long for a reddit comment. =)
edit 1:
I noticed in your article you're using floating point math and round(), generally you'll find drift where you start to stray away from the correct answer because of floating point precession. It happens pretty early too. around fib(91) if you're not using decimal and around fib(123) if you are.
Are you verifying the correctness of the results?
Here's another method you can use for verifying results:
from numpy import matrix
def npmatrix(n):
return (matrix('0 1; 1 1',object) ** n)[0, 1]It runs about 4 times slower than the recursive binet, but it's results are accurate.
Here are the last 25 digits of the 208988 digits of the millionth fib:
...3411568996526838242546875I'll do some testing!
edit 2:
It looks like your fib(1_000_000) is correct!
So that's good. Now I'm wondering how you avoided the drift. I'm guessing that's what the decimal.getcontext().prec = 300000 does. Sweet.
Ran some time tests:
testing various fib(1000000)
208988 ...3411568996526838242546875 0.0714532000 colinbeveridge
208988 ...3411568996526838242546875 0.0865248000 fbr
208988 ...3411568996526838242546875 0.1527560000 logfibwhile
208988 ...3411568996526838242546875 0.3225976000 npmatrix
208988 ...3411568996526838242546875 7.0395497000 decifib
208988 ...3411568996526838242546875 7.6576570000 formulaFibWithDecimallogfibwhile is just binet but using a while loop, and decifib was the version of fib using decimal I had abandoned because I didn't know about decimal.getcontext().prec
def decifib(n):
decimal.getcontext().prec = 300000
r5 = decimal.Decimal(5).sqrt()
phi = (1+r5)/2
return round(phi**n / r5)edit 3:
added the impressive run time from this post by /u/colinbeveridge
You can implement the exponential squaring by hand to show how it works:
def fib(n):
return exp_squaring([[1, 1], [1, 0]], n)[0][1]
def matrix_mul(u, v):
[u00, u01], [u10, u11] = u
[v00, v01], [v10, v11] = v
return [[u00 * v00 + u01 * v10, u00 * v01 + u01 * v11],
[u10 * v00 + u11 * v10, u10 * v01 + u11 * v11]]
def exp_squaring(u, n):
if n == 0:
return [[1, 0], [0, 1]]
if n == 1:
return u
if n & 1:
return matrix_mul(u, exp_squaring(u, n - 1))
return exp_squaring(matrix_mul(u, u), n >> 1)Wow those timings are very impressive, I'll have to run them on my PC tomorrow and see what results I get as well! Thank you, your comment was really quite informative!
>However, this created another issue for me, I could not, for some strange reason, calculate the 1,553rd number in the sequence, and even after increasing the recursion limit nothing would happen, nothing would be printed out to the terminal and the program would just simply exit. This is obviously an issue and a drawback on my route to calculate the millionth Fibonacci number.
The recursion limit exists for a reason, not just to make your life harder lol. Basically what happens is that every function calls take some memory space, which remains taken for the duration of the function. Surely you can see the problem: The recursion creates tons of function calls until there is no more space and your program dies.
In a iterative method the function would be created at about the same rate that they would terminate, so this isn't an issue.
Yeah I thought more about it afterwards, I just wanted to see how far I could actually push the recursive methods, and if my computer would explode perhaps or not haha
OMG! A post about coding that shows code in a text format rather than a video. I think I must have died and gone to heaven.
And its about a topic that interests me. Have my upvote.
Haha thank you for reading, I'm glad you enjoyed it!
Really enjoyed this post
r/compsci • [7]Summarize
Can Fibonacci numbers be calculated using recursion in O(N) without memo?
Posted by Puzzled-Spend-8586 · in r/compsci · 1 year agoSo my professor told me that any loop can be converted into recursion with the same runtime complexity. He also said that Fibo can be done without using any memo in O(N). I'm confused because i can't find any solution for it in O(N) without memo
Surprised I don't see this mentioned, but there is a nifty way to do it without memoization -- in O(log N).
Matrix Exponentiation.
Basically, consider your processing step: you have two values, the previous and current numbers. You do a nice clean simple linear transformation, and end up with the current and next.
Flip it around a bit: you have an incoming 2-vector, you do a matrix multiply, giving a new 2-vector.
Doing it several times to get new numbers just stacks up a sequence of matrix multiplies, which you can re-associate to be a matrix to the Nth power times the starting vector.
More thinking. If I wanted a matrix to the 8th power, I'd not multiply it eight times. I'd square it, then square that, then square that. So O(log N) matrix multiplies (this is called Russian Peasant Exponentiation, or The Egyptian Method).
Up to some N, the O(N) method using fast steps will be faster than the O(log N) method which does Matrix Multiplies, but at some N, the O(log N) will pull ahead.
OK, trying some Bad Text Graphics ...
One FIB step, as matrix multiply:
⎡ F₂ ⎤ ⎡ 0 1 ⎤ ⎡ F₁ ⎤
⎢ ⎥ := ⎢ ⎥ × ⎢ ⎥
⎣ F₃ ⎦ ⎣ 1 1 ⎦ ⎣ F₂ ⎦ Eight FIB steps:
⎡ F₈ ⎤ ⎡ 0 1 ⎤⁸ ⎡ F₁ ⎤
⎢ ⎥ := ⎢ ⎥ × ⎢ ⎥
⎣ F₉ ⎦ ⎣ 1 1 ⎦ ⎣ F₂ ⎦ So for N steps, compute the Nth power of that matrix, which can be done in O(log N).
You can see a bunch of different "takes" on this method here:
https://rosettacode.org/wiki/Fibonacci_matrix-exponentiation
[Edit to add: looking for even faster ways to do the matrix exponentiation will lead you to looking at very cool stuff that totally does not apply to this problem. You know, just in case you are math-curious ;]
Mann i need to study linear algebra, because this is interesting. Thank you i will check it out..
Yeah it's a trick commonly used in functional programming, you indeed can convert arbitrary loops into recursive calls. Here's a solution:
def fib(n):
if n==0:
return 0
else:
return fib_aux(n, 0, 1, 0)
def fib_aux(n, ap1, ap2, i):
if i==n:
return ap2
else:
return fib_aux(n, ap2, ap1+ap2, i+1)In general, what you do is define all variables you need in the loop as parameters for the aux function, and 'continue' the loop by calling the function itself with the modified parameters for the next iteration. When the loop needs to end, to 'break' is to just return something else than a recursive call.
Edit: using this for arbitrary loops in non-functional languages is not great, because if you need n iterations, then the depth of the recursion will be n, which might exceed the size of the call stack (you can't have arbitrary deep recursions in most languages). Functional languages can avoid this usually if the recursive call is the last instruction of the function (tail recursion)
Edit2: for illustrative purposes, here is the loop that this recursion implements, with explicitly written 'break' and 'continue':
def fib(n):
if n==0:
return 0
else:
result = None
(n, ap1, ap2, i) = (n, 0, 1, 0)
while True:
if i==n:
result = ap2
break
else:
(n, ap1, ap2, i) = (n, ap2, ap1+ap2, i+1)
continue
return resultThe iterative solution always stores two variables. Thus you can model the recursive solution like this (excluding the base case): fib(n) { (a, b) = fib(n-1) return (b, a + b) }
More generally: Think about what the memoization is doing here. If you define fib like
fib(n):
fib(n-1) + fib(n-2)...then each step only needs the previous two steps.
And in particular, this is an example of the difference between memoizing (an automatic procedure that runs quicker, but might need a bunch of extra space for storing all-previously-memoized-results), and Dynamic Programming — realizing that if you "cleverly" compute things in the right order, you don't need the entire table of memoized results, but only a sliver of it. Often DP reduces memory-demands from (say) a n x n table down to 3 x n or something (i.e. just the last three columns of the original table). In the case of Fib, we're reducing an array of n elements down to just the last 2 elements of that array.
[And OP: note that memoizing can speed up recursive solution by eliminating repeated-sub-calls, at the price of extra space. Adding Dynamic Programming on top of that won't add speed, but will reduce the extra space.]
There is a doubling method which requires O(N) time and only O(log N) multiplications. There is also the matrix multiplication method with similar characteristics. I should mention that any iterative function can be implemented using recursion and vice versa.
Though implementing any recursion more complicated than tail recursion often leads to just re-implementing the call stack.
Sufficiently large Fibonacci numbers can be calculated in constant time (barring operation complexity), there's a formula:
https://github.com/dmadisetti/rules_euler/blob/master/examples/python_solution2.py
Phi was a Buddhist prodigy.
Along with Fee, Foe and Fum, Phi famously traumatized the English proletariat
r/algorithms • [8]Summarize
Can you calculate Fibonacci numbers using recursion in O(N) without memo
Posted by Puzzled-Spend-8586 · in r/algorithms · 1 year agoSo my professor told me that any loop can be converted into recursion with the same runtime complexity. He also said that Fibo can be done without using any memo in O(N). I'm confused because i can't find any solution for it in O(N) without memo
Yes, absolutely. Pass the previous values as arguments. Here's an incomplete and somewhat ungainly sketch in pseudopython. You'd need to have a wrapper function to start the recursive chain, hence _helper in the name.
def fib_helper(two_back, one_back, current_n, target_n):
zero_back = two_back + one_back
if current_n == target_n:
return ___
return fib_helper(___, ___, ___, target_n)Use the definition of fibonacci. f(n) = f(n-2) + f(n-1). If you write the linear version first you'll see where the state of the algorithm is contained. There are 2 variables a,b on the stack holding data, and 2 more i,n on the stack holding loop state.
To make a linear recursive version you can copy these data variables onto the stack by invocation. Decrementing n forces termination.
class Fib {
int linear(int n) {
if (n < 2) return n;
int a = 0, b=1;
for (int i=2; i<=n; i++) {
int ab = a+b;
a=b;
b=ab;
}
return b;
}
int recur(int n) { return recur(0, 1, n); }
int recur(int a, int b, int n) {
if (n==0) return a;
return recur(b, a+b, n-1);
}
}Summarize
How I Calculated the 1,000,000th Fibonacci Number with Python
Posted by 1Blademaster · in r/math · 4 years agoEven better, let t be an indeterminate and compute t^(1000000) mod t^(2) - t - 1 using binary powering. Implementing the polynomial multiplication / modulus by hand in pure Python I get it in 105ms.
def fib(n):
a, b, p, q = (0, 1, 1, 0)
# Invariant: (a + bt)^n * (p + qt) = fib(n-1) + fib(n) t (mod t^2 - t - 1).
while n:
if n % 2:
r = b * q
p, q = (a*p + r, a*q + b*p + r)
n -= 1
else:
r = b * b
a, b = (a*a + r, 2*a*b + r)
n //= 2
return qEdit: For fun I tried doing the ten millionth one and it took a several seconds (i.e. an order of magnitude longer), which was a bit surprising since multiplying by 10 should only add a couple iterations. Apparently Python is really slow at multiplying integers this big.
This is the same as the matrix calculation written differently. Working with t mod t^2 - t - 1 is like working with the matrix [[0, 1],[1,1]].
An interesting thing is to check Benford's Law for the leading digits of the Fibonacci sequence.
I actually thought about this, it would be cool to see if, and how the millionth, or even billionth, Fibonacci number proves the law
When n is large enough you can avoid the term (-phi)^(-n) because its contribution is negligible.
One problem with using floating point numbers is that you should be very careful estimating which precision you need. I assume you have compared the results.
You can also try the fast recursive method implemented in GNU GMP.
> When n is large enough you can avoid the term (-phi)^(-n) because its contribution is negligible.
And n is large enough when n >= 0. The contribution of the (-phi)^(-n)/sqrt(5) term is always less than 1/2, so you can just take the phi^(n)/sqrt(5) term and round it to the nearest integer.
Much slower in Scheme, using GNU Guile:
#!/usr/bin/guile -s
!#
(define (fib n)
(letrec ((fibo (lambda (n a b)
(if (= n 0)
a
(fibo (- n 1) b (+ a b))))))
(fibo n 0 1)))
(display (fib (string->number (cadr (command-line)))))Takes 18-19 seconds on my slow machine:
$ time ./fibonacci.scm 1000000 > fib1000000
real 0m18.598s
user 0m35.660s
sys 0m2.290s
$ wc -c fib1000000
208988 fib1000000Fibonacci[10^6] in mathematica takes 3-4ms on my laptop and the billionth takes about 10 seconds, so 1.151s is probably not particularly fast even with a slow language like python
Surely this is a better approach, and I was curious how much better. From this quick little python script I wrote up it seems to be about 22 thousand times faster.
import decimal
import timeit
import numpy as np
​
def formulaFibWithDecimal(n):
decimal.getcontext().prec = 10000
​
root_5 = decimal.Decimal(5).sqrt()
phi = ((1 + root_5) / 2)
​
a = ((phi ** n) - ((-phi) ** -n)) / root_5
​
return round(a)
​
dec = timeit.timeit(lambda: formulaFibWithDecimal(1000000), number=10)
​
def fibWithMatrix(n):
`F = np.array([[0,1],[1,1]])`
`powers = []`
`while n > 0:`
`if n % 2 == 1:`
`powers.append(F)`
`F = np.matmul(F, F)`
`n = n//2`
`res = np.array([[1,0],[0,1]])`
`for A in powers:`
`res = np.matmul(res, A)`
`return res[0,1]`​
mat = timeit.timeit(lambda: fibWithMatrix(1000000), number=10)
print(dec/mat)
It should be noted that Binet's formula is effectively exponentiating that matrix using the diagonalization SDS^-1 = [[0, 1], [1, 1]] with S = [[-ϕ, ϕ-1], [1, 1]] and D = [[1-ϕ, 0],[0, ϕ]].
For the uninitiated, diagonalizing a matrix into a form A = SDS^-1 with D being a diagonal matrix is useful because A^n = ( S * D * S^-1 )^n = S * D^n * S^-1 via associativity (write out the first few terms and see!), and computing the exponential of any diagonal matrix is as easy as exponentiating each of its terms independently.
As for computery implementation details, I would wager a guess that it saves a lot of time to stay in the realm of integers. High precision decimals are slow, and I'd rather binary-power a 2x2 matrix of integers than binary-power something where I have to keep track of many digits after the dot. As a bonus, I know the integer result is exact, but I can't know for sure that I have used enough precision with the irrational ϕ to round to the correct result. In fact, I struggle to see how a precision of 3000 significant digits is ever enough for a number of 200000 digits, even without worrying about error accumulation.
it's a fun exercise to give it a try, this link also has some information
r/MathArt • [10]Summarize
Made in Excel, inspired by Pascal and Collatz
Posted by T-Dex_the_T-Rex · in r/MathArt · 2 months ago
A while ago I wrote an excel formula that could generate fractal-like patterns when placed in the grid of a coordinate plane. Since then I've been experimenting with different arrangements, parameters, and coloring rules.
Here is the formula:
Adjustable starting parameters
a: Log Base
b: Constant Modulus
c: Modulus applied if n is even
d: Seed - this value is placed at the origin(s) and determines the number line sequence of the coordinate plane(s)
n[x,y] = (x-1,y)+(x,y-1)
=IFERROR(LOG(MOD(IF(ISODD(n),(n*3)+1,MOD(n,c)),b),a),0)
(the calculation of n has been broken out to aid readability, the actual formula is just cell references)In short, n is calculated based on the rules of Pascal's Triangle and then run through a modified version of the Collatz Conjecture Equation followed by a Modulo operation (b). Finally, the logarithm of this value to the given base (a) is calculated.
Here is a link to my post in r/mathematics from when I first discovered this formula and its fractal-like tendencies.
Top People to Talk to
Related
AI Answer
how to calculate Fibonacci numbers
Calculating Fibonacci Numbers: Key Methods
Recursive Method:
- The Fibonacci sequence is defined as:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
- This method is simple but inefficient for large n due to repeated calculations.
def fibonacci_recursive(n): if n <= 1: return n return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)- The Fibonacci sequence is defined as:
Iterative Method:
- A more efficient approach that uses a loop to calculate Fibonacci numbers.
- This method has a linear time complexity O(n).
def fibonacci_iterative(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return aDynamic Programming:
- Store previously calculated Fibonacci numbers in an array to avoid redundant calculations.
- This method also has a linear time complexity O(n) but uses O(n) space.
def fibonacci_dynamic(n): fib = [0] * (n + 1) fib[1] = 1 for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] return fib[n]Matrix Exponentiation:
- A more advanced method that can compute Fibonacci numbers in logarithmic time O(log n).
- This involves using matrix multiplication to derive Fibonacci numbers.
def fibonacci_matrix(n): def multiply_matrices(A, B): return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]], [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]] def matrix_power(M, p): if p == 1: return M
Still looking for a better answer?
Get more comprehensive results summarized by our most cutting edge AI model. Plus deep Youtube search.