Fast Doubling Iterative

fibonacci.py

def fast_doubling_fibonacci_iterative(n):
    """

    Args:
        n ():

    Returns:
    >>> fast_doubling_fibonacci_iterative(80)
    23416728348467685
    >>> fast_doubling_fibonacci_iterative(800)
    69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
    >>> fast_doubling_fibonacci_iterative(8000)
    3561533204460626739768914905427460387141369539110154082973500638991885819498711815304829246223963373749873423083216889782034228521693267175594214186111978816819236959743284321273097535654614718808050244321699002512466203835566030351092652496815708455980825654877181538741827129421689128991879649533246136168998590044965735035810856774605383628378979290580539135791985063484992877932473487054068899476937399295193905527420792975902913836012199062687063537510151753758100626402591751183925883151617648375005313453493271681248233059858496951790113255897429539560654496639601132039360167542277472498901884679404509894269174519328918160745655327632006736189766801968534195725815421784083495026969542066047758885029695257263330719223956309043195653930347983496830801755572982419821881275569179922973415736010289561700699477021488635509784509168019589640190234350021673802856836365767446249424907273016689053388000785637444921523414602360860001530139933615215383220927084750528293779491002813557093860863839463287251443115581618266959802005566973874793475256663122039030056061200186123236430592279484254766158650545069933528061680141046574115103014532101595841822474764213889385114174543352137856680694687244097968099924183815689652779302937329729253678579649215884078334428338037327451220722810587680172255878795449524781554973097109174140632623167659027450550461045055883872225659796812847075286475208205923875668405160707778568995306926178023176315799965539425437791083258303238592641010878264249883586034912756021070468742995902773902487497010335873840408520900059054071283266816325489230566003110549946685475230821114509971542662742044237174282248020953398789607528748909125
    >>> fast_doubling_fibonacci_iterative(80000)
    458917898454169424284040487009900919285422578647082215324012671952169440059520597175901650074832304431306891998333069486745803748702321660056035726264343242428991424083443393259745430824222689036149845638464859953642103272363957759215898400431891120792028447394382242853298818559979812598287596896099239118557125359445187060256029193677260606225812478220234099394694886753145482720900101758760382232081458878635658280916867473663619982702187421108786288511224808081924388155498116213584679609944797180671977649495679911473274148589683175671585850547302807538788111113903904553422986262662785117706013239257478690167768841192637211670061780263056238788163359723647722057766937885074024768976444397320969161375354474490280103255530562024942533396841461147990665635596391841749039406170508715165462302029867654605186617697226747330400411551044302940982217834424553297256222594294138500476579505562736508128848543761912065935838202359086253753034861658649764942921532094549532068037963189107213718137642847089411127798651845922438620346371651739794423824710911734781976344716190059433614381244737081309933006243339276403460494852258294650582864607607714918981710821932654125941900407992813300576450088330346428329846100588622878040693509474350248247007264607942938583277227326918824235128075299712752330974941571625715022868265977449529694605309684750666029800940663965074792550576723753232296948913059096296117320028145469538573818771369482204349749312252686990326849107245068711664724826027601568572672940673507638966708177904704605312462479653514193626321585746347013437157925657625130672611893987102320301251328122274152829040046721313583881538357345764033455922875999752056290903225405770979658753467551264876565545637334370702018328695350528155032170363837640602599912173812483430235153941043462729792546294868354471550179543921983666005704411324390413686747882491199068796056345172983914196943361315886153641868484583322311123826947702098452105368051890106784192774076228892427502811543167059606187572433330181253022894531389652910728812539918288125258839030424407353430488899567905960260195715770962939570454179335994864307194605301311629703164482787484140765390060219784072353831193672094477655411491631714117025438423559536836218547819584582471158135531102712036403417120814854126014345812186176490689295718983242769748288110243331886327284773720305426408195185419918221968469547470716938795769191467357723820600104618050619654055498782704185429683774376174524040514461874238665002081660551091373537569398824759862984041887868006011827706460119847258911449478971646800345420007631233867175863132092570295447956666938404235207390209877114173206216681387602251451117298623346274845195530150448229404184201651917126581504212981824141755552526604335663991488312359265313121823535787574278941059560056434401087125742158465140675328855400125169014364381324669233588775801620013859966800360076064069931216922677763017523259944198021615521733965578632517826696461834662797919878702000773828663440257604504820103700071442918092580910439221384923367886356509850910757060677850775566702709833695162455497176382840917097541097409574088538835280263414385206365831720024106957976114008622524405973024913146087245421217526908685787011126598553346263462030234882943745709133795190268357457863192217081215824680414331808405833985060956521097024018426703458629818861913310712479148028003851380956017670058535073606746883072154416678285975828425777150512997350213662010544971985691400122102366321202148175717906883735291357933404709354829308816016368668372701689735124869860185026213764168814718298263325008405109478823216678039508840751288562198556276965203581145379709160617689707864647113546169564901786098266984792515954598197940144788341076032810397104496546270366652891906357162443698817210430855701416738213432919498863828277713804374177103797121704575956011695531724783658875813843302156360146680701624890106634803031193260827788260385753686487340774422290680463534004245353041315217471449517063167864358883795979064342935628661797772414739257360660983896921676987231584112873990579836330739520585126887645362113170270345361324906180352090374610459094588322856546677139752112550611817011205309650894632352865096364586712634556207464327584493739979075903655301905053968149078207733514407251794091109575133420826836248758771544437181187268312311131846269143909734361928472422944576812367063518667674594281209916242829612983517190790725063641135743683925192377279248211666865736224202239513634658063047584354211630297453825429352084472420372672864354550659138169665958000894120242878004904940508619541792761257231404537228997612992633932024773291811571485670960190878054101887619956635376410275008619653082696561748012787862907448091762256600598514052982158443847230513245053346304082451854696507707008075470750710091451761634718018474636972326962768712478204070889546607314436851556833894987691101331920316435843696753551107042111092957417622713461483617272240224496635850798239373925059367606589960921102235043304016801560719544933301527058639119386148384851163043677617455183501853110983432846781839862537368152007224769299273828862749088630977877442715906270921103196592628995487984452089252848257457255699592252183163109765577680987775725906165379635320277724280860062689598248019495604796400902200814531821890308844228616968857557276651778453964839391398872707358451062690852172419222793939665529899152087758253959799697429805691602789335989103241676882414282431178348043893634644956268168468606131433119672931004890164335434227564776342111979843948271250902047810765529472160092796131210794311590486328720907010662115036134087919672520452882389919316640678083134116905100103847168604909036136897844888482447001576436618399201229825686805633665188385438434233049467845649410207616271999184500358635971119608927218571554319748933005112170133666941094612475330888959471963766097789082788446311850663441855608921088043555592630125147476465405331211179194568731092068018599338353596974520111664342395771201066114039115758247056620155306902310827839389471646278576631183252570617061880842152544877349486924918027519491782958828098129519043604964112924692690329790926298169791560608815321992145604288039228942577299917338016486360201304172337117593884618284041100555511686959735827575979477855830613795506091764268921299120570803079928061736569117362222348323364094720726478904904883545264003594671893277367872031516742276024041595811062015926795325589346218581656798810656304056348299056437685422305782366500808061880485312524112689351481538120813064314018275407945984975583961181885581390195376892833059904670534059961637153290952490656284144883752338762612250136050093364571026681017875346487252926774543960202826775433238988932693895847006076895239847668232694703540354436439925607891179640056620372284255332660619666600181443659802845286260983701057226463139699917256644363052401138930173945903129463643247667375578558292939456768950515409636339795277442415816567518913886645788693820459389964716279810681140676821113272675464588051648570431886966669204127714942478183648719061242184485856623216435832337642640659614432290095604462106923076245785432584650045786054730172586129620777904771469190614620837672793882627405138583935091565340878749540821671543522287315009456467068550945285916499382415474644636177657987314376675546240925746310070186424405274946631284491115848570705407886760161293420988384461479688186590279029931466151370360500060112757340798689092536854377135232108909819852880502225937557693757140563923912159116524317600152659679172900009182949325444396953506332654914773193659362236576463368191757207130770428747134689645719177649314600836428489557737520153871314336810057562418866617672593943016256388945879931104651386340294013173041023907496680492406070586717302087937298304957973200139041810861036113315079071139046292556692687200178065096760308322834867731303883736361115969427543774313658229921508569330714851069404122700555474405028164097553110187314948155238989523856240328653672947245669528844047862203563857709378395375168996992492914241877016867647133483716639537306892350739939553038529867486124856023438603144804997432599221983794843758941659925928593608632156643235169577448163321852780830596039238951564047860093759142581228045832085849471697386817699012530182403550583098947490719605038993450513593841079467279085444039877424348268678844441626639823622048892686077445989111615301242569434837255616939347873696793415189948202692237399374121555078503994273638876112656622436904689925013477134884670480768111503784999851543654078870915466909143189385407035590899638331817968120204347002361577668058049683249437996666724432317580800226561396480987566958393519139374700135351721862262774817725222985243541550479290781082491860153862468625353254247802341003892994787158939952161959053770283617328696222572365326217786665177780113201526368532580772784475556805102380225174052313877118515552444198974722677183387256239909509575180181814961112660689614300148262159110191816424019102501833529666552191163980685206818311339985114155381175869039204819436090294267353641309208762882529935309046195633205043583605630961689616521358482458896494738216533878798437418316096938763512365837999457985076132193998577606847495881990631321967448183317913172163537823637868918237025617118800217906012548843550740584335751884907181601322845124609269240151552818544664082323902705352717705547285785672794400489977956339517703408813034897206546591895357625649746270199904539450873847052111098550931977967655526430304023923760497743271247905853268939483106589791930756351774083764264608205991981683438859182958870809215121687745744722468091597773809025088806316718899127619854128245962568422154244361696426773206106390043399726828730494523918364620264050481535328537176487461147960238964673530659336338677363980276577063778475434191346645482383355036026831596633164668698874988655950367824176958708081774653104601966971592090590464276459617886867684965253835104633245512781482215142509949157493397407774148661903779190210727311243114604559430079834310581582534344900164350474722424586592563607002775751412248999395268587214631861806769453267130762582686008490784184326211325201687257725203815333243569375700628922158397220378137120461958616786000756640122103472692058329498416863140899401913170078210635008882927772511675931725042976053185211996225341900045123197684304189583918418753165583562246694866765182740225983306053995786669874700327622648172624073620144308533831947492220568888714014762185258013475236711297008086865416224563650733557842954210127400920313360541823785066880844310437411361491030790302768558918326192308552914953447315644264414906648742257973308176051805459529729509075688320148803664255189409870448469831308409650323592863031299685291247943829958763334087018458116923766818744327860264075209833654029320486257507229392839658264951758259294205385749726528481481752985488544043232478491496037643798310992743097132864230714878103162924142412406050508805839923635041214768090031879472027281291869262866905071310589556031373765926340157598279102654323190235970855879487020791100734454262740894652617945537234843966929412257810663049379156738836196512133264988555241297691357796420620498581450367803497048184470445229756472818939938703145666182344391654666558274119651574861128984270842290208843324000063383576011578456010194788133547621799514628650168341673212262146804214177399516939094035134143272822363711494605903196581364555148906196986622108277113650961350487508708978831088193079100250504721450756878475055875715498133867609848876570843146110967811742466429048987477001759368893781664935978672107141943594120255405928895856239177557732985568587578819570103158387512624739824755050852376329647363550034035971204646829083897462206481147763364604258798887654900189800649143958496805707892328090139820578302992070510358392789632443396082084464583500547011245456157938220373714071637447494939171325660786963888934523007603629979543841249372155167188941753644764930381034914769061528090272123726372341428227172822993100750985972346990406030238548751512793286216789134988578263898566899187364829061280915857068667279171874622225591305937559575663945748297462630412412111597289703474105667241410196427334933034519301168304035123563407316405399189517890015248824828272751281897203881924366592221349811399419216014288463475417899221764692778427473176262622323124939998966852238177813149193311355315804522575669274640580238526272315022092042143403071947625282895856734853048083432836328773150819665815418805442704115847433288698556066700796953958965155095202699684736222832137249995448253738114594225357081760345844850751616616567274856314230889675082144439348217015926887475594714128555161256931874516893555167845303583098610512717285491012784730479849074970904895113379859377479997738181824458765708965235866492181545996118169861974773328894650541791780686509083287345439761979030886945020526792195780113768880412111629348615114699283031537720106148010457297198207909512192219524139058833862079490846014523991135085323895411755499448770886739142886594909604321140755281371986355579421247355583320446210294774381684766370732791438998773746362499812686037943185190615485850439506954287908207121207763490281244628265629107406547155711294119328232508731432153267942947897465371215677634251265445697827850227703300751424170674515885348813446979286028786466639513984327797495038250451773063728753352250572923510637797660065959266431840590920385334011827235640217305297099986052038214674014895735776658343213237141874012968469922553309088960853365882771458131623636254768604285474421141914420015253373249601310244027992168940081101047112528146050399775697464394386649537195890142292602338228101564772174989947248644804415712390653074771331581331771218227248255881644725024175583533190755962171903182560395541845095772256365945675426584788552560491413608729444488757780764191721161036539043813600849491430655327445756085133816874978979701759310642821491606580148256315546925204387282513853840586714664872251743732534734635417349259840723548388814178700746872866244651134689166118218407898202948770012953144970698397769012769738223053267891300213324207127648667157840415283368509844271165344096753406181447870940569727164470052769539195624021996404398492530132341305706387430803189274668428740046052634807258738001045362302418985694480278218216221542334080404324774303808063719929283707275164101759824950038374375833651667309343270968433930646713335481039326118019236881877242499376255673241893507819012988999635043773758504225960952783885317244608496412064461681508279444282627743943072813682735629380672462007445097710935669855494259585792331974671384575006531648141837203988012112573802734699407670711801693427394145412231504136129174154351224791785835452984905474888229898183685037061412688506101952577606848278181212652795926431014700278657885963287458038803926069544794518516911775959279948531939482433060981596601847410409580230424488421427728629417060414702438478508326943223694690848653819029020378065483446631391917408165067192783523601455135995041707442428321853435073251127776953224203299056692850604766184943042985941401617596263374177499164451532076376734457127089166999890932027935125839737036402721249878807633933204399592495520494880005491597946060695786403529287388243724572469561386283001274137118913657045618077090824603314393692265695407669069358836795753384675459408549234268634576026067856976300208002774513105924442974992813997217040355513623623431249497676999291205986688374049264639881017062766839338154978601372769403955966091846639912250496416537718377896955275298061132564601685893003304466747815258857770469652755409463958757316608895661185800601254157142314067632116173802968635064600113503267462535098678186270424765090649007362058456204298898395573675099543752418704131942475342213850539383944341656812603747692985608693139903799258790295602897417985605819775283118831782582347619677719637487176878016068180903523739093703379477776171109577236464547177192850269474446398150731127328907601454018456045261881146474163958335659003513978190789778345730452183593421238558369644932014754827840857051370153661785746586069979864599297430943367962726292237199922576549115614054352427299392016299102570420032171267940330381146516129455008614194800484645495529279758492857261341442639565330582963188038871379600925593168510039657998604410712283774618112857854639715826030947501208791867834977829005291478829704370317807211775380247198259026226102582980086100401824521086751780250654339409464780452649723273917110011021472961175457454305321193996603536677958030554773911365171304921708039592445734537305464907803112644109424064595236950142027965241476988475353857823399382650783534013125
    """
    fibonacci = []
    while n:
        fibonacci.extend([n])
        n >>= 1

    a, b = 0, 1

    while fibonacci:
        n = fibonacci.pop()
        c = karatsuba_fast_multiply(a, ((b << 1) - a))
        d = karatsuba_fast_multiply(a, a) + karatsuba_fast_multiply(b, b)
        if n & 1:
            a, b = d, c + d
        else:
            a, b = c, d

    return a