Boost.Multiprecision と Boost.Flyweight でフィボナッチ数列

まぁ Boost.Flyweight でメモ化されているフィボナッチ数列のコードを Boost.Multiprecision で置き換えただけなんですが。

[ソース]

#include <iostream>
#include <boost/multiprecision/number.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/flyweight.hpp>
#include <boost/flyweight/key_value.hpp>
#include <boost/flyweight/no_tracking.hpp>

namespace fw = boost::flyweights;


struct compute_fibonacci;

typedef fw::flyweight<
    fw::key_value<long long int, compute_fibonacci>,
    fw::no_tracking
> fibonacci;

struct compute_fibonacci{
    typedef boost::multiprecision::cpp_int value_type;

    compute_fibonacci(long long int const& n)
    : value(  n == 0 ? value_type(0)
            : n == 1 ? value_type(1)
            : fibonacci(n-1).get().get() + fibonacci(n-2).get().get()
     ){}
    value_type const&
    get() const{
        return value;
    }
    operator value_type() const{
        return value;
    }
private:
    value_type value;
};

int
main(){
    std::cout << fibonacci(1000).get().get() << std::endl;
    std::cout << fibonacci(2000).get().get() << std::endl;
    std::cout << fibonacci(4000).get().get() << std::endl;
    std::cout << fibonacci(6000).get().get() << std::endl;
    std::cout << fibonacci(8000).get().get() << std::endl;
    std::cout << fibonacci(10000).get().get() << std::endl;

    return 0;
}

[出力]

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
39909473435004422792081248094960912600792570982820257852628876326523051818641373433549136769424132442293969306537520118273879628025443235370362250955435654171592897966790864814458223141914272590897468472180370639695334449662650312874735560926298246249404168309064214351044459077749425236777660809226095151852052781352975449482565838369809183771787439660825140502824343131911711296392457138867486593923544177893735428602238212249156564631452507658603400012003685322984838488962351492632577755354452904049241294565662519417235020049873873878602731379207893212335423484873469083054556329894167262818692599815209582517277965059068235543139459375028276851221435815957374273143824422909416395375178739268544368126894240979135322176080374780998010657710775625856041594078495411724236560242597759185543824798332467919613598667003025993715274875
377013149387799945333900224880775791236117337930100445535490043525045843539648818562578569150145472631258140598040875416901451349878686710189798735122954887088454924500028574003068434783807870575430696066439101846750599745829545721693784957073273631818673420751972327938538799801845560513422262958882244516053880771140410978978788942838058153862334417256446852231577242261307228498349256708182071208335817888584565766108075330781175405119280446072770439376209526520001751104214901240319492664624851096737783185573483303395157215338535471110527043630771804782569715147171393026481175856948947183228899948494260568208750719855268516476269647878714108168277444438804007613683373880351707165423524328506540659186023484368510133227968867699680214790847184799670735773757954844122828271297646621289176554762574427786113873868257758061282170336001273324376526581229870956568892731479303850890073064863486442100376745831539591175879381143478831554126208085279063513741706269326525112915577755575469466383184602256762543155745636219359236200272816189871334546629683994275939790168821520825923115371290776425534079797676308190573421064864056358117445863611087717811034416870861710009856863627270553744159738699063771087537466728943484891875282416138475233419592000
3561533204460626739768914905427460387141369539110154082973500638991885819498711815304829246223963373749873423083216889782034228521693267175594214186111978816819236959743284321273097535654614718808050244321699002512466203835566030351092652496815708455980825654877181538741827129421689128991879649533246136168998590044965735035810856774605383628378979290580539135791985063484992877932473487054068899476937399295193905527420792975902913836012199062687063537510151753758100626402591751183925883151617648375005313453493271681248233059858496951790113255897429539560654496639601132039360167542277472498901884679404509894269174519328918160745655327632006736189766801968534195725815421784083495026969542066047758885029695257263330719223956309043195653930347983496830801755572982419821881275569179922973415736010289561700699477021488635509784509168019589640190234350021673802856836365767446249424907273016689053388000785637444921523414602360860001530139933615215383220927084750528293779491002813557093860863839463287251443115581618266959802005566973874793475256663122039030056061200186123236430592279484254766158650545069933528061680141046574115103014532101595841822474764213889385114174543352137856680694687244097968099924183815689652779302937329729253678579649215884078334428338037327451220722810587680172255878795449524781554973097109174140632623167659027450550461045055883872225659796812847075286475208205923875668405160707778568995306926178023176315799965539425437791083258303238592641010878264249883586034912756021070468742995902773902487497010335873840408520900059054071283266816325489230566003110549946685475230821114509971542662742044237174282248020953398789607528748909125
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

[boost]

  • ver 1.53.0