Challenge TIME!

[avansc]

I managed to get up to 20!, but then "unsigned long long" runs out of space.

Are there any C++ data types with super huge limits? Is there any way to beat the limit? Any help would be much appreciated (I don't mind being disqualified for getting help, )

here is very pertinent information to you and the task at hand.
http://www.codeproject.com/KB/cpp/largenumber.aspx

[Falco Girgis]

I managed to get up to 20!, but then "unsigned long long" runs out of space.

Are there any C++ data types with super huge limits? Is there any way to beat the limit? Any help would be much appreciated (I don't mind being disqualified for getting help, )

here is very pertinent information to you and the task at hand.
http://www.codeproject.com/KB/cpp/largenumber.aspx

Glad that you posted that. I had dreamed up some sort of convoluted idea (that I think would still work!), but it is clearly not the best way to tackle this bad boy.

[avansc]

I managed to get up to 20!, but then "unsigned long long" runs out of space.

Are there any C++ data types with super huge limits? Is there any way to beat the limit? Any help would be much appreciated (I don't mind being disqualified for getting help, )

here is very pertinent information to you and the task at hand.
http://www.codeproject.com/KB/cpp/largenumber.aspx

Glad that you posted that. I had dreamed up some sort of convoluted idea (that I think would still work!), but it is clearly not the best way to tackle this bad boy.

note that what i posted is by far not the best way to do it, but it will work.
usually in CS as in Math, simplicity is beauty, and beauty is faster than clunky complicated things.

[Falco Girgis]

Yeah, I'm looking into something much lower level than that C++ implementation, but that was still a good read.

[Chaos Clown]

Thanks for the advice, I thought there might be a much simpler solution, it's clear I'm going to have to learn some more C++ topics before I seriously tackle this. Looking forward to seeing your next challenge. Hopefully I'll be better prepared for it!

[Falco Girgis]

News'd the challenge, but I'm not quite sure why the special characters aren't showing up...

[Kleithap]

They're showing up now, don't worry 'bout it :D

[M_D_K]

OK I need speed assembly here I come

[avansc]

OK I need speed assembly here I come

this would be a very ambitious undertaking in ASM. just to let you know.
mine was dont in a high level lang.

[M_D_K]

I know but the last time i did assembly was coding quaternion operations on the PSP using the VPU(easy), so I'm going to give it a try.
/blows dust of ASM books

[avansc]

I know but the last time i did assembly was coding quaternion operations on the PSP using the VPU(easy), so I'm going to give it a try.
/blows dust of ASM books

impressive. look at challenge 2. you might like that one

[Arce]

This is a pretty interesting, and fun idea.

My question is this: will processing time be taken into account for the winner?

I think I've got a method to overcome running out of space in RAM, but it'll probably be reallly slow. ;P

[avansc]

This is a pretty interesting, and fun idea.

My question is this: will processing time be taken into account for the winner?

I think I've got a method to overcome running out of space in RAM, but it'll probably be reallly slow. ;P

dont worry about speed. its just about size

my number does not count, but just to give you an idea of what is possible.

Time : 0
Start of program.
Favtorial(100000000) = 1.617202229E+756570556 that over 756 million digits long!
End of program.
Exc Time = 318.516000

[MarauderIIC]

Have a soln I'm working on, will have to finish it tomorrow though :P

[MarauderIIC]

I have a solution that has no upper bound on result length, user input must be < max unsigned long long.
Although technically the bottleneck is result; a single digit number times the current iteration up to unsigned long long must be < max unsigned long long; so really user input bound is probably (max_unsigned_long_long / 9 + 9). I've thought of a way to get around this upper bound, though, just too lazy atm.

Used iterative method for 1) speed and 2) less function overhead
EDIT: Improved with a digit counter (this isn't present in the source I shot you, avansc).
EDIT2: Also, this does exact precision. Scientific notation would be easier :)

Had to output to file... 55KB for 15000!.

Click here to see the hidden message (It might contain spoilers)

Code: Select all

Factorial of: 15000
274659903348516826648255815026266753776699833026582418739847875253045210793122532740853073321144465098302570904958223242651688997603351488417071188234715947039096494968520278629124983763642951334817546552420880336946205213323561252923593264503848349732519698233908059735393111177667189525018722186815141889147252250088618366643924510365629085240383086414933535428101038791771944304576742714227650854262308074946692863965851300258731859511920200655441856259006342802457058491335711469938283095956838033428768211676886936383886917781049237447219374767617152191509818825747743812589699521754244065141831150099981307140455833404722069887651682584452078021855288548764791508316246302379003109653184913127744165755186825595853761634802070716339448671079976012478437416896706719083259278390158138548712249684170110111798225206271610929887835895813940105502901588288109491869141749286683674794137496316777923387036488338321958745682319156012692183199919775121143440964406279924806583181745196975127525454797883759813599884124194218770311952320221970920121012168102746626924720211855673788320549452128292181460862230159528236369434982997177338591615142134927344689457555421041254815900581050859784335009276045033648785845681912262831709408567949942628407444184430625350142366383772647192484864759658083114444347868279156261432674131999917118718065805411752844385658032313293725161743795619244541580422007819692624426537417786823931927512633428037531384676130448634012919743255733105907708293722240193268652944296681734286795219617310213887296021095147507918160925938859433893580061960921289886844699499421914853444388918196470290585721319559553188122059016480745395381145336404664717227740957157117297553566197034647103855223345866250370205646955609116294437836001420379565886726987580361115691267020097462656043072096375955514170007107150963476819574221078516008641204155403640766526734180328336840283679702855032930350529437454678966394389766412791068665744879101348059678033270850348204288861770000931589005649659679787714683105135463047970978415281370673202067343688916225404395268362200268825165988927750470954374651955290555175944010553973394608714655964448946379933613628920162919514908809300530599715109086833900795675802799289170516558898667866650080027798220595305497001609573840353078930457649151635642820486594520882379412625814423112748164484824874902360094855513426449352125528793289640367757094191912084967208526742572704933129969945959991118079499707563249314770281753867516142468531057317725790227752479853476063996200080768381290525243037593921710406264044615718310230094878911885667682092228717062132037430697624014536025431815800933965042747855342598077334095991608146441601613598542759930532977395995443080168272208587168697375846869932092685875277929850063210465336133051557672102501928368400836906516245169120107275891211221389027711369217512183895664992456089079368375692855803351213377809192752198992245544065131363689443505729219925216913173091759907425325673299767363516960997987333426141362069010904332051421600854102169625966856957065362964531968324952388549207794642301372265905734289795597080305491729726091621048149720880426011786702807941320889268136529683322865765402852743843374456517761145635255571906564638853586074903728431261289173352539625284749500928605795956592700039432985411387323102100308677377031094421091367500929009869232420636532689306708207663327522948621761044959537382002489126693383905239892962538861566336269806603898324747227145183089476180212398168659705784707107176837102795615366506567638773665851015500525906324144430311757316319305226297574645955967663228481271649514803912488007965888468222588693458536355232091552443498210536258400628260428684940809701261298739430717535977125748031654767818441679283752066193989601362953642378395220871252107153846663611157497707732013952088313623314439080776034849942489672185643455386718001128752685845858618519864509555700235338235583896388752124811022488079745458833917697865909184514283140506458064705880756911253760198867126469249591624105397639002471858816275899466450955157441678430852308526037380151946155765307096640959563156862078594159972574263989211355073453080549133159732888815304330215707201780948450586368744675606376553957854417460695680721731882286453828424011783694381166028414780888644258455522569796279733345280010710552877172128747909817500958905392948801660532528929347626863960297028187042442555562589445845067438613924011132581887499718849671219199417625967456536111755928049287533474277579680087871559940090163078624194538779604952642458639484126313079210922031312263491976746144244754477822025272793005430816305007936182184239128134770258552762701041316124117769250733464772739534770775241152907664977376176785217947399573380142521492831379180486385714871174684698245898665677579698166294587623996174319032368402916567665029840438651323188522934091871426891951704055196149250533698066812840390076706178186712578308001521337787495776699541086740027730724775303286087700040171107669209806095218059166208958731096069826298937195774934466821099508423706315892050888120452070264378056658528733156952819442906957075097956477288678930060912215770062332330692132889444891836304762189354229555729851530218991211433200761478262105273536524887348625490681263037524472420602643941832722193356646866624446161488886635271726100882844528635436170735474578231674784098167697884302556204220072364493406985810000759352820582207541225295697403028851478721626639095279527047892952831684751296107675907788960454779740030875645468930965598573173045765555601971640521948995642334127709419704935947251174782885361147921195844026254092785926340434494774334250519036134469687833353374683302723767348164279797479928624776628926741012588954262838891726369770545779028438821467277356211577845174781600075893970368070732531725233099896134856616726862232422746368953996519303009733968620717010261433379208493637105743983939433368134081862819874182827346583985549595689815103776395633056334185159234985909243511156224526097061121310096405152576711954986837994199523969628660256065603358895210361375617051496341681397238170828234541378616489860106505668053258320307149138208441500364439226148418242761754423450662665348806407105206114948547412334816401717345743979830516231010520569271464179946816050220487591671253634552244749452330518520438254615647658814520867215379087209008476698862548108619157129108449684952146916811946129302996716094417183233666425500531983600232403167386262720681584555126327441742020162486889686261697025388119461375126317793535773170013963879685316478979578452328230062908051723805690946653860029587957985308472678334836690884022101166615407360609454113988977855553817545054890955632503043008803345370012827597548024892015034862677435825613543457002200559107926035175251050453122779971143974275180831823056162382365552495824302011520891558272675339369128462873424945705409315984649824944553331651332716907683654394318736713862722069523438282970246982190840410645617274631387546089291549749737840579972481107757129983246166577005200727742408627377431811721458034669739282006255901632315078516174033894596769659099519876180227397522041847833785020832563276771048636866314984353666683268123500928058114298037136233256663468053192082870713986457867522539308275064145782328273505532851023504173618394061106544506976066249206207522337155859111671576965312059163349070860835735455770432601897773169089823326159740643523808629173632247811052271886576112685303863628860751732296039035937313028291721430531544998084922485811471273040257561459282699210404214789583120738926070115748191900275419367330486456811750292550204712566634642545932346380696464472484577142969330528989752263703038460797734511308490899270525620883694639908577506695378529488852257010688512459567461671429034035966523267166944315351017678219409176949364235739882809685769400044327564861671119453051626932859418144539664857363230502694173772613645280920667921100269431716392639505318863594584163414776900374648230774963732337260002935505349332896981762865489371260070816997483232047743453170810310821517820959052591846084151871889900025252771421090636867132456044991250184689440444063256581444829556661330506981296708539471095116293140636434818266960475491494275325631150962427598041925144921208319623366344143880271987426964671588831575926754322582541678047160200475569398774577300670822831069297446355525743685586571525443793150029565305439599077068002564806614274515099551958946135748248546487205314145425817455156430958848690601107379149228963555672153059764898008625069018359928407377230914374813892735154618169630699927636676759224277628840084072545263027796409455478576256661008842206263058569290838809335903057997402273807953317742762047827303613209575786524592787215788496895670582437971859317400008247043652443707235098484648263846328847361444630064664192972307525090231220861537241456464989112101140270021621014369386053698934844476364592166925836568863968679028999503674928184408487805763544449968015300273928367359820954507203788554130133137248745222414990693193267182250461673109708761211728512857455846227223029892505785782023037496610613167040660878612515982449960963918303249668676206796681558410130785313545337621266192667622512985164109293245811488475659845122202545462355098160257875718100295432578395159857917616749283048798730851079049730436352353552809470813923435945421643551078880255537721991504047515902787166649501772800784451815406037549203308104783909530331640487367706717796491582856851332277343010476628231223523997441093927888532670073095814552771765553934736012985121124345930678733418830127379579637756585037076726428563278812636098629727454190941032136189903055018500239670751242447121647996449132247209455963719038500201023245968775195523202915791077098374343672247122293948189301222287640081199416595888086516834465957672023576402204399624090765505280171971108752287655195751213581047369803449988662066140110347776688157401588177153198895780049974815497832729744488518929553682955509721909359677883961673926050681414029896455342916282593832297071234960395876844388877088695222767285589635155085660622073658504715449405648087778664629991913687991882163685558200892659722561806436038894851226984161531379626776785377466837767291958009851314067979924246946669349061001431497957048683008656296727194933777489686325579914071467875942716351345638682767119201742626950441569023448151400550112740930494893980713427928892147528981326853398829889606209941247816987666921271641914149141787875073630836702702483480341942856187973335342688732573891645165829932502649765097325524550450553113414748999839580760126546453301131652453807228571730455127502605947536473170133538890122600356657055796813427612236709531682612823644667074711988003633886794592073338853688537303715866751083402701039592844363319648707648827111338158357644145396595519221548148191140959756215754762158145716289797667592340578098946721534457115090394825991994423649378900237543881399177583887694867164223121956771990259380082236378503672421392011745653886166425419417388164155154129563976497984168329223758112652267480156518512403617840139970414526079289697980498990958892711211200049034494489951921552048767784656776888197312405877920845726304960953704171585151919901256558393148853132883625858078866244233228053473502482851588525634716934845810873893050426349478927265711300828447508827064096222934794830659833906239037795852229478655539827610173566845678169886512824785028733434044905694218966077323536784347174514199372240996401891950028182247197993006222836150290702510982087905427946264470502831923072669281223923586671574561088609089952782983629538061230171468444563670940356116577185044336232085594599897419641307257102024558059603166347094139774976266463030755583233027396465098756745725267097651147905278107606318620805295281951488988586392875559474737782020449917456536957721454495153578265154634356718731608859358683108868197023253474874332906647444229351883553163744161045363822823593773618545562826729636319754952274670260899768041811485044553279219477534511481432072901870870958072638609419855704881931752408492893804306911577751205991544935196474989579389149236767893910935182468604133246977315503733467145449236873176887896687969949063513037200862172602893190999709383004606381709310521291303891853731668831907901237889422894428899205975992339032996945789833118593882666748122431403556776923719373754323329352460853937255211463535593547344806590446724357209505560768112307879697488564991157526705810597263887185484094219844742001216334832779208531846695440482258455564643092009521544624074169847471141795354894259127949060278242625932281183524676756148808221111694662457937045481066906296443298351732451590348519685792074286255610038208782181012815192962616962374651551797980278098460257022675325927571420352734969341441108659303915723618440162778047158479871675644881514901033248906903825631658270991092480761099585207365519825705677713127354135217401581704726826660697859588040439846016195042721733397359473152446199708650313413409599184002550706791452177577102829704934652094201999369175637465322197249722773626809142266549666789932719510496809204732969834176039564171197909698955817056293117543024376170238906986720346317671647184090975413014888332038846543614109227031494466305525691583038174587141145932399103445878292629186346202659157908584893076556145537326949440291939563794549313696028983024859818918532256100614992514608932666471346135763026191951107452965611617983545091188225531247665848867686858811593728146218130233501160342986753484201158561262460214745591719702358330959765748762803827575249822893410125090462531981656766571399732049481564402099553715915079567618966240809251266323930726299750573574984993908140266138675274280474871256323383890736974154081956680016387504312845975391319957132480675821717908616418137235275485972231572201546791322084760960812071767828541037401126095150917383072938634578072732288702578710180661327523279653350402881832058088943751347700548657300089425228072025328969998996816727108714445588707190272419065364241196855286550525437646623334892393613704457348578889641903091952547994463833589553845896328910320831925248227351499582329027987245258433632367948824479956441459965932333083192012762223795565267889849046717250427160805919100632108716402665330449311656666535556637818645705764521105594953082206347213447214520653396723020882012365685209813784484347641884406783528696167401848442708061427423104085453688235873176794174797966409494335818020483163365092078281637297856714173825964327429056053353667157401852064627536558859609000291951391260461660902856617473204667135365967067775567621120643728685969201089340241075460015821791142456408144479185057652035531349565305595726396413552012766274332530959566333217499560147262877937427711381045756659135695876888652013647573648040250055685048277504031728460050697605232403757936112633979529381072518154896106362153435567973729041995912199633194469870994473154151933658673735910520691340416455171227227306083770797928196069333384335835872655230303049713184058607394482692212199385367208651638830595458803227942029214920165231101555173804297648807574245193515728872999690359590652731843437194451467309500050044565250949636823518508768242908075210376396299095752568450451352643666016961956538234118932428049328800065574453567681260691698441377889451938358984999589350492672358616816866405774774943728180375528476517733080250457102350865294867668890839632861247415115831476107012356335437139850556458558214120876799315121323967460272742676961576973920792779089181639087666186922743882715015749740193259240922619229265177747658587172110361591154773506794275385027573278054950005421999908089050759629294175898999599471133619319682852764570981660463267472503216582902046491058009480114131126755089188265380952898185519972432990567674099104146610551444912531769418038352095940381599722236299021711634261755315581026088992229971045171325013324135946667821515462066136103440680836829302938866901615112509626870924023719576919012298602289480554855820326168036388261802303828287733401821566694499565233532317365482222366602686142491450485220463798202616943101618802636711217190829860815756684679325110461534961601799932446473385046205338897146923525009440095590681288007700794830582698910582890458841766832189685356555063248413212693072213243493671454201470093322921883201642629293951690711352436728652924484995968210971842230560589313738532790549036628963135375279358513945409684745911975260314934479599623906833076369115209684420826083398799347715939608914107296387670936030133792337145893626468461438241228966203105671326150036891357783131698529733085349489956617675173761880981683328374126514108087256932949619987944466495594482552775116636694404085999813485628729122964462008283960201228113949932911226011233888860850952394004796548822271475935526628315275160768728959089697319509401177944990263685345461617737133334386353959139205027128369651352739614800909228988126075568071354285607790485492584572933062337727895705846506389093868378791818273780977725817418365104271961807997381137452228152266179424799933865262546756789122860380818051998568957522921821857966913575545429226476565593478870015297453970094266702292561816711703267616083809898860375141962506810800608595488510280736821939201452689963073299704960712349436395743900980902646483565176030188162939314472034109600979488036405891148867733300275906332687128115592107855628578526481369254589675330344785650244401798654148972928172374315506050135208808332026955352187553435649032651820544217371079077588779520200075094380555800037457994530106272425441500470698309031651296227557700819362760045831339590954022305233177071679788430529852436488568554952277455797674909757560531167025020146578545576638874245729536418551276991199343191636964474121549937522131820302821312891180469084378373450431060399998545702070101404883408472911106707036130629309090630749499491287235089991004879953657831113323322334102387755856522628829217729582115729473862912491695134673121422438415739468460085962435827063695286998655895654904189635510827269138812250087074669636573253602839297563420377103093942724820791195156587164239316358616578654176484106867104468054765079505071967607800155873116359341833658326056471739896334845344864405830683763473436406735146594138419265676242339138138015550020151287651353834041530907873958693549019760081781325493036344550760760412056690467634381785814374908332517859713473091155450847767343212061462713987796821437997384493076101767581426525334899299467652840669128764320143134009068567630791257176461264788432834548700680582086612210218246363757775454976836381760930847668321470942846452508537985682552935090724004188439140766937287169354118489643710084844462780581338863616651317511235927047682613961845539968354902582722613109106446321195707882763019606826931554286622287263501541463309705292590484237937060235594691930264534718519880327249556675657575038491245268403865415932969827910786111035725166821775646118504214018989266751414650277862396517916546468944478988382491952495234517471103788310739512647258658662265198455638390576518443871743840518532182528063604538883346662885215283603051557711944627563524836867464034692194733145337035131734907162623042932757642609743490289978576646681399382703250470764034391878469860449923544741547406111843042334666256392347119597691658569791136413839800793742275415021101890379382192707429293541813678106784819180496056800361086673851772186187756738332403719648872200326124253604061891493673286914661804974333187261633711057177306064607336328183514956656269803217851928994469577416750199862348451774350742959624363683460432179891117734531716274198670877890126201978468552767993735658078887808787170359871223002906392989441681898562784027882569731322643647445887399908943832069561805204184228941056111677714893148516505722085045177135199277066661733590941869091914048636800901954229213923141981659263769823243757571679557368259118764564110406655227213510313537264696058985560499487271851675178374797610758704465014998462355576544395610345454861583736618082743267829549784097681927821461171844444721074865176158633856877072026712500531752394101048416131161408772571274740280465300059598024190779260842306112716622682941144241369692194798548994821493395962571812900541121471676777222445354240463747717324519217136911983776666264207014850128674804082237150071671001538814846883818650398658254363096471552547271170376060419201591095730232456853384650535372751998453010563572116992320642807181581775481820271343014993913163629541322154841657125323354880272612871891279340753975297729945633816979157495002338430508223780867530106535851257546532201420856345059082316967473202710636711051442683097825547858771798575327664539756306221039174236463213747251392859689815074717237747237106260794074324457241800173554841563732138892831162309245059462769156595248674082959592650676302286862344177312399100953098851646518266289183187070153219104209617492840336575371735738037041286874120193540751515434513707318932708891871328617898678473458687407757591819281257776829095645070431456864574154417123312345819625845837028489834798285914690633476988272576181941911142149869090826404008045431952131963322429872996144312561261770196917270130123392410377936999771713746397182748153270143679152735880418484086300916892638692965604745665910625654423413425070651134293948616866485621659729257743489492228546585159853401245360212837147685697318142992963177598297760492046579839777231232596640876580193597298743345958252647975353167084378384255522196168625129452364591982333054714967559626436901358096562490706289038416187539668162264906454067927200180350541679572592724428094608380459939684105939007509767224908944869697168098435863268687278120021142810568345512113371237347256450824825823811940375601838285753226693966057307773313535220086314626437041588306023993946604585317774986188481575777436131154433415210001743435048285179202732362099864846550821462471714700926194957054764548421369220302454681840872547765476288333738280885253316831963490011675371109578533229274841750493069324856623570428043634519824699524345593179810044601314612745320237473011477454042975167213166988492854263816390215606055452337465658088566755086486060757819271880216690405225216396445390570583466266348010683366500202360696685274197019487245183785766663527427881225339554828115188638185456507681168484524688955468718710586943337266536666960067424871300233902576207506326942175534499509404660647723245762724094662867606373440324934584983386070354355491201061942099451391471116204075502141534775928676288082267559901038988794133563086987638757721873893724075536645810840694740988902848432295609407071028763240348982210845667042847109632339530875929456524038050249573993443832925165536750993908698973385856294421268706614467117494670863344980833499956018606745639485037176897538030426680511206957734456935396171135336479031175659280106248908416455550454494183473629759282674624210457917476435977980081868272193208016383423819539563705274061609531462153984506911525905825204040587641683038527125953207938578027147413057955917482181835845228266228645024619637358632325677948722235624798189971222149547185351959840432787557743093487214230487407899238933936969707659401742427984336784720415421774624618577565513160224379171008220183983619622895307090427279777533102661699693774286561850503173814110888500842707889113538773386292673768555701841343218205926164333478821310391307389088107801256364265334392184148352923709130410343750894378002196334020526272416503580886168668864422310287908433988014021572838239104452340068106976899332434456217371867223793106333764573970634772262111354005776800115082275498506989839548020338388548457831234513672882977251122261779976931840248123145529946014059715566278848757955571731957412061886700436578357445543240983988388652198764430035690656328868479254316785307138610345324839313518843589648461292003877934637359541869999957020832053036984804368729471184381817956858619136268574603235068443560420476020797983078359723438894084994566298550781565593933761959625958683853054797604540925298715218081065628796008708920304379858965260686188906327653614514955574598685592403819360101818562208811901636105551915358304033505799185355362373945603187387836023430319542428373801875774780071748342747350149302586559933768501714549822698953691677640681450109434884716102995806030346231553655466846455372499308909115043871432022965841040754418817234777242827804951741026434037880415104009424641110304658321571235819781015038058454504548005475429823148561906481798287953085962574232362547383584620219332738660835139525133844894600399470018135462740054298133553543434571658963461597727930077400839384013224042966056450247317755458141245007720328104621831255163531761382317423825724562944414808532663480653015669931303548188530706833149995641358316506575652243982246889240274078653786679886175937320165772401527685929054679743609273443703817579824770747448387420797564846729874970857749101578493664208621818545519466691923506309853509283964963713395717182492102608893845806110030659432433913205234312137584078831284878521104221863555263374957514864396872900116729792344084684983844762000334964852898918446145911985498789202233045423720590524472895657014182749135316947511063388435317917051823558016792457146196937336377406559157383694450656472009940812749721589778074622588475843442057263744560265668411748435663173307781060888723888271781664349843736606335926018741905322596303425565219249872513364767438094659918302074427983602189785759633365399920113397982809940850194559878697462901142880296837781149348062036608974006645376151311743912098119442840799548759116204007264114797474505203561499807312274286173314593088791132410095077105822645949495416029500558168177901995579405834008051558558153917070740826059902191808887130702350768384432367889757297984223732294578315162217988872893231359805404879407562533873205072983965077298596224567586869392078431850157597081502618847579734178543475258212227426692125718615200129647561902796479843164625810604675275540477796337248171381817019224155791586370943161182037941806462218066111132695964524404384246981531227263360312007373392572283342424461081699546307739638191665942293956562034891696279253970275826711447522286991851480859443676322797276093816812441011605664056572263821872402843033965099902679402166230527055928024354857362796143297717162906245215224855293014984229581260639931706395017369468396725116156564942347094871746108735919209888202735641163040909621211599273094469909569587354640053960702056838508854599992197055732075778727931894227973825771394289804133304769690551346587104130531420260882030420285667035645067180919823139817764182974393136482458659551985483420227148860042185040257050571213499752821078330887438852181903288760657955531131103283925680930334832054316912130271395710481235204450697437868522076651994500534907145844693397850018945822957878210900034805703086983458334113708038821590980431330575216729153649734587324349694053668726848745623404389439216133667418311981457185381725288008866462189213497006807064074479020377848918560753241039867484026802313848807078047475092452405606169040538497986394559560511233147049796412192060271592094998123363612292733111311816484720042557829137332194201304108365159434558006479766533940712342081161203647208714510040015169448866880721802309351648898150655461455641580378989888690131656089622485162367827821354542319452918938282482998327332210210507136381263766131584436026955651169406079405840216068642197867915052182979755606833206730594643326594621830506569958921649447965365469835391520748038023787997678070636178801098624460565274064647184757788024469307847996521989990835560567990793890741688999568464979679165210900332477525282567444845600816328406181510511450028515127172589446460897960447325306317004903406796059978212810026950584569170352676171858218778095834432337499682321346514606231051023117853255725480970935961449767265005366763045622880838442825629531216623070606425343111272263871030444432144451265646090847389349883169557109301624713784660458769699592124999620865832481277341032916841878469364021893785422495488866534536933659265311525598164945598646652482615658609454079575689269956568985541130276644799357060315051521241982290124322650090576149231856077663602658638719607835863581246942933558802738092981319157967995255661253665614842275671121090497945096862579665349537864019477577591930004143196163951696002436018818223989778653101564237273522840309205363355554651750253482673863113258505447062570534797120655789525545587336403152163322435890452942063452402244568273163712557457954397393508191581652354804955705381954792769091846625180524896938762949386776650613556330213094808941107912097235361130991933729321456442963248207263839115466066064673356884611021574937809676912314492507378003561217022737838408807804602284365015332445750932489612028981982061160709217218922110616808500223609291464399271451468465995984754416958271698857419808106141987586249012713332868324109684365955354907163798701050694563789152502731932346402077397178515315790861334260453229928030179588593358248772306408835553794791410681929097400124066037384359546317648898771793441843646788220362838755151281354222052677785065659767288495418678794254825517112648455120752607373945809336292175390087806045294866041854786610285771542462679997322773630496602881586797870046138373336348594373260335907723537117098588864137785487400361041773860525173849524581470922844307786671069886861740309983276122398155258312002814304071526681176076122736414832681568870764535555024716352554994074282361241409862575286205259674849630576343542861996183242854563750554024957117891794830110457236216970039345685560813785209144780682107003848151356257110963631172848625987549609124984727285890346513357447438241927358463862882140784783523441352292450003580861704084312742679313321985785159271201701400573102733237573912586688326935103717461055386016591700959766919521418093503415652661089183065348964371482147792838436154913482310853190700611109768133723419304109282870583328768343543631612822415525297237016176978757339027875669986408955668802954182179468290378428239609704368077687337550449855288755899843398971764124105159555147980515258154377420808874795209185069852183481275107714448350311096691659466893274445268595472437108908108643200506900041831797664820289596605694210159001232981379257396941451118770999680471268135421297109180473536517325918622101891280964731205588578973940085991766088103834805040140239726680681751604987112325863469605045240061821053605559803411922652061519632408427994955870250439878277035524093464989556243480519214657802996462425075162078095676580634958051019889925865591238076536571078514201000050637355916133455572628174827490032079711967124157812516989833313518500838546643621676865173656039330506904519796792820941564529607637109904763916510205314707004653150995171121434848134821350512509790791697290965932213488153990833312102010776103058139351573508622002666274424245980990558438169094012845265187573799228840950070985493694500123331630670378370541913833150215884329578838246987779489925268732993926468695113767084269204564723074004481977778141847991534052124396875313726139876517251321313880442598135921630549475649722027261931541873961527136969165114668494131619993967546213120462008430118878936328869832807016069401838368305600646357358881662882452350114768748976873279940730472617393345513855718181034733658431291208778581767195064290512477253051046241559100103219426888589648545990355228777344874383658190778652177850417597782129682929781894440142865448633718339593843452297938157979620834622198220093972101876832893096382352827193402663403295221530381622567103283425265213836473051286916577985127241110452183529763139882151590654330537714154328849230010238690102387456650718225413677126189923060710340846673283992220197944542998539751097196206299567465113170198888419139721190021923416517152793908284633409243847717217591442374055149336027510851481916302914019170393391586023033452727591780408881679436875696957262781135611406789096247368007762521605152977004456230428459645802983377159164877378577083151676733704720674448643961736890869169606474965504269932822554555839297645020670576653995888229195770604612124976431257800317560021902618226019433719213540328285111653482160127098347909620658365104761440205949945684349561548928450975322756784118025085505287583292588433633626747311728158482849618848472496504864679776003336654549513799792791000990489218212041570588695166681901114198480858887438216044545584638919317764580966269134726403477639984763247447523202652019485255996973908000961156790241646142471285334914960453876780182985664598087506834117244685522507170933184399210808207456514846649832562084014153862763937790136505088114810439858481323483086721348155935078225106342370218032873450603297356744279149892797548278786126430619624142515614339064706774727002420850534277448203002945854538579084595678236251625252136986255031014711656777246972658489487504367652671844106494787320101667318835649367109520824771866100396761613621138630338227846610574187659896700753486402260432183532553722760080963576802935997705958116738249041508715677057405730116967470564639352606411781198725249821684254759954321244804428762897076957899166528515601497117723371541164292607162654545273896867969892471960651059789680441977795667351544648379240681655489727289841127308536551287040055852160198668811119566736245944505308983404161010644998739184075205308868737052557215351728748368156828118350061622147727222310014597965498119696226798883970906928019739181432362596623712241303719337973957614758911538932526999779082833256092857390060650144285701086347077486337770989701402154539907826403699887728399379205289986836158871577223910416370021291342754814976238494439403957723936310921352858004548971490694587331681414188566130944009980816249073642912762119159862512703679899798188200060549522439142636927734885351208864007640798491475372476388733527927413056692408097651585913263098220614907921535300557243384639130606426970119190340112516169916630454419846458412848295971525679344195374384406254162521829929796130645358066732965473828615266288425986800036890893117988368743120782415516014711735613679045506671615561679713664120750230293733657805909296204550968193431914582285670264716048661173638179880288527969462729054304738732807258708616303790771092901983591291210067663072594631226589760956597046451629428309478577379532649259571088587906568169656589312508141192242402867562998576066589229748991411217351594218739907398251985487954938251118069613959897526376757504438245486168833609249987198650028493069063131024157845544109232183474019853023445791828583342974762970116208832042443044943668492491185080557228599498547411153679241343882021582988188149358722737689806215390639090787190149328473347812256014621672274170658721921220244550427634819219362576320521053981206145637212296885748233484428684106528950588033407679858887066127601712837460889352700776933817899741423074208021007121601559346128785260368039437288180619491038277509316469096265974144500370390025598541926268966991273351074192019181766879397933295145912777536707564432338432332685262426166922771366275146866088564122596130828757490597352243454300873040917192433912506366963019807615666882856350183483405312226736871736023471131309911279941053648448418839455793505622718158718054756408916077068520323818150863756504978273790395856094143820468792701945414620580093043753596255946424114180668660737036794093846376332332498589701072881834223283593182735092108405573789471615351156370186824831022674498526776866187684768538874196174210130537767303817116472466368247157052750241053064923246501157866462812690092756461197590325208815488559533967853448923612572000371776122219040874033966869294831228854305061086519094624130838048008037213946621014193405882170240968916610293193599993759524736059233720655063539737714903128310086743742021845552780330342524272272254563847545871651994538612619934385699745121557349800263616537474951245577400534586471217872306034017978337930025353082642379145176413700828861090557893847616229772475845301807186724500491719384073583330400183684399093856965237788747505163830100612841702225900632391263667475064907852411517182187011838317589725024158880780143407055346282197153793040248025352473536538854586286312290400156032250279063187295187149122008328598088731350662957524582573795669640537541044608560939944426567746961932898304614452443370227005333466272887517300640430972754403267427969042819923226128286121623653601834114225264238614615332620687047985295404176420527738401034145401993260173794846353047440652754211543196395816146525982941441133499050259298763931651294364553191249374520272128978621082199723203913610149685688125186218681756193839852117405548140167502048548199565328997581892013900581842921590642006849843378880860865943614036420274740522634386203009549451209982820888815501154263564341227939118496984635349623006105978730942388934438999129281453390603024184122243350034383267958579845658103661448089300411180881882812951179459845260405227079667230959297248721122706178112695037727030538619236945985849794213723950331715803910119124250624547071556845335292267530727533561366266356641650946417810210840488823105309003369801812199314619163786038088569270958700210652145467915452483883406253408072662271470296193871464653312992124099876648911644761255411159944567863019923832237644705456260487729517585895266285037752521845594649921469036158572113930634873777572461925762914762586801502087862290813710669260578188354979957275403556932972318131819229135105240053044143930856736757978056138180338291908898691617558407145024807177804276234230531979172891369270134608365299989954256482471684548314327815998936061268013848168107986563087173295304632754303557933645253294590306966118288883048382984135812373753028269495492548786568376752476467867923630654102218679180870583392032438949265817363698176034008552328197822882224049989083988351517937048641078370384523904228520582435864752397767212720237159916658836106573419124322137516799408844597261707644599010208583329986039064919352067223006287832474425685201669192719201805576431473581568386189561429261713634279837245244545768948720388351839689535399005729471955444272900485849511539475266824409421054667298175547081293921270029537830966058289105789273227401216656524060507428252929053929909572271232367384758896044402569839074813055157523085779552040089220487308192525980892747415961693199100225119093460554166641012187759703525983306023156167723647306563719822043487313546543023569645317753622090233934952135067613595589285646198367784323107030635311768749577108776603611964239722278478642583843670066731025850620233687608602900637237753257243070513382811898841818476225548694968376931240752138498497014743792169558971739279062084654470352913641580137838779068704687993947344043318279260725486765540466043120996159895636154460570951684836927572080733238003928471443569066434097543087956599166655592062850858919284093312821761782899892098689350646729888624318050298173538381224167008030248266928772323365574509911724387246059838082349272040072738359714856885377394029935953298930329649994372926253348103838636688399474585692941146487350883402213293274501093802974013606371558196861298817917539415338055455622554803738050160119316871446092203793844203918967687036448928660724514662445462419355160924898164132960134593245498879537636989399498246197544220858379653378748457663109168110604829124160033178919461072607673665842424387506182571225839500990523625468562278891692110697770805685612894842235939865254209179303498180130074951302396127555037892807259208926831495449670285360662921279147721887873701261630029078251538832868906124523255909422542428194012872211618869010670984772789768067145666524823464399573948820398705801649533371199523111995641946562047736826137857228046690693660791397602635721363045380830052951072372503331009384875238267900410538202010504797680554097805904713748780784206964630934161859588921538599436431841387842671869877961478339774057398765118426423051533184639679008624427436702827379170844283195765276640313715887197347985401110361395471432917770156753885970720787072580400247637031666510518326883246180279632388861430371899128044340794676191145603800787018126871526194033220316232143048406890815622186210496364277540402328481349442204191053017807758001454374563501601489301966854222871393101767616073510550487266390070887455179140112101478442875219990830621757865326205266359862878010659448515781201791094456986579608599603466386428042894882119564582513992138903489891533636794384219448694259846354825665989121893046691983010501362950137609144383102009408840709697454431817662097218777302210338015716280400640742830287100235284620397686153150196016002189976222446404230580219366227505703386166492297046405885554169919227773227477145209984105158892018012623558878804623445529954096605285318950907255800788149212379065229589855311188157447874593377877839686418598802890390151643275510029923931381602751436422637378072888471537072157997061309805822481458340886694034309909951154402193127175305628638020353593046712318779210107100512692878448681856183979271778810337945503242999414307314525756747307140931265315867174259088437846379931359974462188214915382656326497324852732806404294684093763158686936205723424547570391784272628053165037476473360811690934699810282276345681688954465452435553884701010276672176622762215734566780516405098011001941095798306537375460069445337753920999413194268440078771312627122154162843751702144057721467456518543247275052489471984940029985166835286726825548921798029041437865764573276797952198221608526604739576859817677585352510482748273849107304088146148186249577832508723051741282445723855917723995177529874991560396020888916377962670816603718829288568736432522299998701802246699013743432955558552288594811851339073258548900522031953671940483417953467396098897256950993998188543266043356128990266866602511863094302508398365000068520032550907546999382302746560674415072185352394976366449901699106175033971203596926435996144260342888660953144867351222691430023254043018885858484223384134221296767115042789139789192994782681987318469640867254682096987626980893165566219933323083603988026575427469252086513909423093163603488363919420082108459563186361653028823522643459996582482604706408087094846537493189581661998332183604716422965098245651194868652828948087655010197710431574770708723927319976180022054632375183505216973273765581258819083945814193671913990638872742674556506730943845214292942437983305015994311848504588773430015507698849310891418920072739247124263636340872077777311475761312733305281659416908876419003591705220500083035701720512529634387814970927235651214172516857097329239418043044019514960155087693013105445192288377686884454759149677078379158759253110647064399305774908430669722316817532852583878666381071810976278954164475911612513093170193066101830691930388686144057878923651854962388375896210110739335853847550501044980493375682567632990197344384881102278618840647141530134835640422495360469889378183148563630247488686939810156983146586064643162706612864406131316727464494999514961467098322391032415869646446886364951051258140969729884141644526692784194283088764618049224672864082407960554076575479900719572835749273136713887917397894365007791065732730147819558984280030806980367918531668006052618595419422334402362056247254178511124872792382703445611788410751684786887267325061273545506303543332965326635563610782173157940320488628525191286331652163882530092565749691822480064703082681823651215855420416311083833987959366291727710959275756934927618787963293466787452854461409647095098364177457821171799660906309467670773700175972078010383556254827860154193850054938450357406211179004150714309607145615590703030461165334574872433415089891997681708928829053099383944359043594534662668638100373073294717680214327059921139077075396789887414419632488593239693278649548032396635712900457906062052457610027891348220362160447360803169316021459858485200136507854166395402145333616434731163563798285314500812128501004319067076594336421105882144246855161735058014561572946962284076515965563931827749241890401041664217099487591533078527747288618578287653248136151398465598021572431340624489513789444479594850085023306539974442440451650792713777586822815761930709685989767517574420329810122389022641738689663990603800794294126774738277173171227077461400661751699618959145047943393024986575228148954616150242285821758984067374654408451975075253968985199485330132894343156866219761619894160230261226919016662835166663087350601801621602301338285788051168752201731934470945828108003939784796341299185876323345961546701740193701355735222452317452395133221469357095236122445261502168351053010687470499512872821640195074247431127194737273385636015516097321668155209436610420886854620430656810875837957431993770751320311483622675637095957714045329114955207592612249800922145577373566653585788574820853871275606944699611715484597482768176538634068626861300866885761399267699032864407986746602571063717758368124336055620361443092217320850992004555000422425458767231401999126482999097836183014068156463986744649610387603023638022774188018704385035089171736944326558320087349981991802025179277732858777424292974104329761547765999921655264258682679400329419063410702645263935988555553343918683587218928439197804138921151748129764519223350419514713925059447372549755931688155897217393559264672027866437737721129306006443462714051945741050404750347212642293685824332211811342912234150689194984563987176883127985330328237164008911927964101906679762727118784843485486388922841699450494822722520821082027394414214111226241588529484501989555917219817451799413144036650531903856495956570445910854953270980012528783136213659801319113454972711127015558256255809246510658648117196607495778339603865626543565324150479260651855092348264436072801763281094295685293335539368133609943902206681378940420298001737865362113456537946287425419387407488641406144627924176150451736820425474318702406203048102145327726574561244575768808808555093182203273422321742416775831114046146739914861193027786509526456582475538295295902656813285419407561380111523084713277016222719797179328037023102339117110227143280792529363746015040923019969251735593685407628322240158486127246262287057218989982390488009674513807648737983840370480399787384990231412460609495879545464228931041063103116933378125283375432560800705089793233016118447962187399646535010839135303402054328796671790227377212807258399069774256195453044904045062390611751097284616884209459824077020352868942318912602190194878084768214815104921021949724237364825710880903395337314839085385529145733037685291568686688016024187440868455296600464185905349121174818599669884810463317939592555305554180419647465710983760260013603150560371097532956504553740812379334754687882423370017397884203993292813990476158318085615938212850309942113692499888663350557972167810290801786021302446869562070718084536860071511936846408756507832833374499617635251314655254504997081845095888848690831753571831223079271035955677931627211676033580402560315630596769371072028206608112661425489038187490127033330264631630544478361260654125365658051935364188328492433481189852149141110242505188488794063520074580945838519705082540226733056805040526824868481552995948760004116901698376598112936852622452365627435095216171325549374926900771029741597114487855099954896212902185597898525347594530494734361979713537852692590883383668993292414877093475981309389063428367499597027229495462716426834752433298904595561034412176818568147810585206687286071287936360823879894800835447527161660195581324202501529585588106467903749796364122949330820937397979851339659984531624019558949577973050554557273547332129799412599376842171225854786839347803533960935007409138267722794814834677076174103039037095512489015121849201960039409776619090748411493463605313472906846358478569977807749203446343248564413876031325108757944890892076121752418470551695778402783698394070396367366392474408685425513075621103525498290753085834722580665336723480386698085530132269979853530641239294340869039389743696310573784866439900400560409771330082333394524213850622729985161395442382766392940228974997991841067332429196680299131598911480741957929881815535504841575299698721761877478765738028717522469454189325604987311229305044089015207523100172435723883284496603622826334603662651845132341887554294591952257268203768790234542381973716611467865857115807911795043377453969204354558913679788625447526255969307662885907771014633568468404168816476185896763757481688602422443305972840527244908209339799139538472927576909103328979154315619571897023310102789593691220572912681980386154759342327110706053326287732779173776878152235994376461818741152186162121984899426762524792512823717546201044143611233988719663406771547012221777703146605800891833722698742963069644943922903027488028808661268104782057052327296391709879024121832296934432589657170773636817670359133725428679971380400434511797522522109683102487106912789956439227251220451849095724501725816524192755186070804673385521489224590292864373356471604003523178494780601990496157556400791189605944878850968831706675346076719815267883308734166027710040337247657246711090051184989673818218039369804091285445461938688888215541315637472354560385708717337351670236035857448321091067972567989638111540786242277522807720164807398443418720472563951187298395710264562073443365307747730601136967198320672349142501763126449876518934935058871438086427855086336541598250319065639832409051706617123444574448941053353001126352426080899625132048130676157113056691780374599514400138522363190401475910413150589164755552792397209364356527971223153650150860463998332433561889141035657564801354763003832488307995485130025019521710128523497652148480009173896890178223590458134388112355112537557608265261691844161544195315611369854283382088531983010213662403180507653907751169127945479122838094957988064729528720996814184623741106368745909658433842665945915241567140159187499804475604642443747446323903998655139325957352785532354408256364706686281707539713616805614079138215205198882001641350179478394715264247680200829496821489369263647398443898669232225665348865740198124139302648833963944723951014017513805807262122730271474811705392377640412583914182412137202396702333727788886417828062720066052495688563398805158321061960894257858900017891853762547058733831768335700164100113210448879449474868386928427983094376871367662501685463521856821592100681833982584159136473394610047028969184336040933068628342098824804322332226578502353966105554017148856038672715217477793349905659134332188244355045955693454366239221564579513241349048761618401951048410262549286711059928130233402469146739002578885352746591351603190821980452847494225013968521376889232561601205923233075397315337293296530604861964434788909052444855483898536696206109023827287386391586886979046251958034523430848376871738895388631529091362854543361800037293493380196066484660571499040376171647233129937890921279578363166744702699753788095210271387714696479028230790170540104303032139707887426032727104417926954077209488054134928277336409046632826820961035517088460410036223886452176888100070705416461012907392214119800843925040623352437142338957330648680726684509051782895107522065651705130016583127156046236122414469339001559108688561190009512657209783184572160259311034052902659140757834015731104656176857889817321627948271507645775690209485399406555539570204959568531266786261415425422907717001849269596218990985957897187950643396421925775679087891875081415445079628351219633819491015841048688722467235231656995497503526691019715858402625409961272940568804586563356923138808607446374097530572396923626320452413445170666182495949384976865270604406518550028966288342231696033068008701625634521959678600275959924232126325215534912043060341183925857865417098790397881278200088729557059304213547413820611586197048199561147794117694540729654626910749143399983057139970063134753056529985830555702032745924484127014335397048667236929398309816498508536211439025095552099398902369673628632745795288378700512392631507701006448538704995291650064627967214614290698337417328597436420139333075925676364366305694852473882323580068591894603313215798570306247715758385006524385464570669211010476562120895292074772917549037456633769489682395911769910015473576692747985933101788517178219071035133054288987299001437125854237782585403604163624960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Contains 56130 digits.
Execution time: 25421 milliseconds (~25 sec).

Also, to get a respectable time, it must be compiled in non-debug mode. I'll shoot the source over to avansc.