2

I am trying to calculate very large numbers factorial in cpp. But I encountered several problems:

  1. The biggest number in cpp is: unsigned long long. 18,446,744,073,709,551,615 which is quite small for my task.
  2. I used arrays like this way but I get runtime error.
  3. Then I used this idea, I get result on my local system but I got compile error while uploading it on the autograder.

Do you have any other idea? I almost tried everything but 7000! is very very large!

Zahra Hosseini
  • 478
  • 2
  • 4
  • 14
  • 2
    Install (likely already installed) GMP, use `mpz_t`s (or since it's C++, `mpz_class`es)? That's how real code does it (it's usually either that or a similar set of APIs that ship with OpenSSL), so unless you've got some strict limitations on what you're allowed to do, it's the solution. Alternatively, you've gotta fix your array-based solution. – ShadowRanger May 19 '22 at 11:20
  • 1
    There are a few libraries which can handle arbitrarily large numbers. You might want to do some research into such libraries. – Some programmer dude May 19 '22 at 11:21
  • I am developing a library like this right now. My concept is to basically store a number using an array of `long long int`s / `const char*`. You can also use a premade library. – The Coding Fox May 19 '22 at 11:24
  • [Found it](https://www.google.com/search?q=c%2B%2B+bignum+libraries) – Ted Lyngmo May 19 '22 at 11:26
  • [To Find factorial of large number(number of digits >20)](https://stackoverflow.com/q/67651282/995714), [How to find the factorial of 100 in C++?](https://stackoverflow.com/q/66293620/995714), [Calculate the factorial of an arbitrarily large number, showing all the digits](https://stackoverflow.com/q/1966077/995714) – phuclv May 19 '22 at 11:29
  • _"I got compile error while uploading it on the autograder."_ Since, as eerorika's answer states, there is no builtin numerical type, how does the autograder expect the answer? Should you print it to the console, for example? – CompuChip May 19 '22 at 11:31
  • 1
    If you copied the code from https://www.hackerearth.com/practice/notes/factorial-of-large-number/ without changing MAX then that would be the cause of your error, as 7000! has more than 500 digits. – Pete Kirkham May 19 '22 at 11:38
  • _Why_ do you need to compute 7000! What are you going to do with the result? This question smells like an X-Y problem. If it's from a challenge problem, for example, there's a very strong likelihood that you don't need to compute the full value of 7000! at all. If you're doing combinatorics for the purposes of computing probabilities, then logs may get you what you need. What's the full statement of the problem you're trying to solve? – Mark Dickinson May 19 '22 at 11:42
  • Basically (and very naively), use zero-padded arrays of *single digits* for the numbers. Do all arithmetic on the numbers as you were taught in basic school (digit by digit). – Some programmer dude May 19 '22 at 12:52
  • 1
    Do you actually need the whole number? There are popular exercises like "calculate N! mod M", which don't involve actually calculating N!. – HolyBlackCat May 19 '22 at 13:51

2 Answers2

7

  1. You need fixed or arbitrary bit width unsigned integers that match result magnitude

    So use some lib for that or implement it yourself (as Array of unsigned integers) this might help:

    The number of needed bits can be obtained like this:

    int i,n=7000;
double bits=0;
for (i=1;i<=n;i++) bits+=log(double(i));
bits/=log(2.0);

    because bit width of result of multiplication is sum of bits of all operands ... The result is:

    expected bits = 79320.8214956583

    so use any bigger integer bitwidth than that but beware the more bits you have the slower the computations ...

  2. You need to use any fast factorial algorithm

    there are quite a few of them here is mine:

    otherwise you will computing a long time. If you want to use that do not forget to add all primes up to 7000 to that list or compute them with SoE on the run...

    Other option is to go parallel instead (like with CUDA / GPU) however I am afraid all the fast algorithms will be not paralleli-sable so it will have a benefit only if you have a lot of cores and small n! ...

  3. Use fast multiplication

    At least Karatsuba but after you hit the threshold NTT based multiplication is much better for this see (both included there):

Putting all together results in this:

time needed: 13341.269 ms
fast_fact(7000) = 8842007956963112247864993696897726515146668063888148614063859617175175754725158649547982070366735592564635779100693064454178170961165752167765531817139213752103794651539384390492636168838534846437298449406744756476508706043448242696421599161649582730137919744173960058745503156484236750681100551779049914848885650142637380063005458258029028181186529979826345217904875468785904316332265112387938639672254223533573193327210944965539025610945034395680899103907477208996101593045865114444196767132235742754582381003526477608451190796731555803362142602285756979937545243909457235874042110187883785273337882048580752640943965904045132851304920226173796679153992666480387236959191001668175647982690528811969387561291151514484716897379863560430488762024469208016520576844153800946547443547988444323673929979976425681778548000318465404733311398456692655883988018153215141483857339738890618563250737385855609985481858844431849430640044987314360206602852182563396473431341949326406990788042014146528986829611680020927770551645063937236393875523763882980698155834877885570464834887214403527613806603874035035842378811567543978436182416081255413171254955699983155919253892606545822094514369667806088854682965864846929015090559171012066420663809079279792972532271398769231017290400982361484308650813321962806458341044422281378610879469201234982769525322942300103063592007385662470399869873889322027588175767436845753111326351331375771824892602713670158430550410057726579046329970102843722345639407168583975567752007205506131110761110861356294292674808600572426981882015788994401461260659121671568622152868090271415816338563094882579211416763856973775592629908794628457052517710417120267481696217048902118115125605882488633885970460765348819872115584507468587241235694364474351592396233305833293632083248628644761405430111558758624035958582096670821062268201536940251875722431910866217530509249522090384629909059019727808549978649211796834037499155277345140383958733236579130264058169024644076078187735460888179089736898177406096448784487616097333930802197031790251162361409283284240601000295120768995192920580120152200259199246677059479621282511313316843181735056691183920273117611317112801980061951294385675181292331418681345227295964218912032304207123457253381142044752764791607747614221937274986120855600184517668312822490435076081691295863552215293513572301503852263294858892127294771294822729411748696675194436857982470777255694243051477901244805500830053137014008164400182344143596348584227596152052211574462519515535403270714238652416208509658061435002706298770494619767814978821366569002196288208378908693257956280092472411189962114278221936023989601788776938997557080304634260416434749989494355295058878635663769058501600260317367047665159594987503133823850560492216858748919262953169998314444590379209501535394692690658432871437861942633645638637138091381848717515750505444423488345113481084886974445898178890195975816126246915618498528079320848558421401821469856620426217343200432831040792604352164356484715310662108947471696692557909184823897498276569113569949755034629352092582279466530840152019262346749107273406212748708093568968586045553827091900900861887263842037884945420014371577245917129570378021232830046487903874044753310855219828245628085113873321275455272470433588383735394846636383604600473850069215837869293905982564295863846812779186900468275169367750371895523520226600290613003458993439142012174628044624611290312013258917283927021650438369208310266411796053502624775891072063018657046624869132893320446218568972657910998268776774395737926198284857511418598112020655695096411472891389500274800422429847267050507394386121944962297412886796095062227806879431705939009075863264057381993663953114101557360914958870016279029688196656773837860632794556200126637298379109602404798818442575847973492506331882145603107582106413695437539880836193014800253379822738014794915699821130249628149281436638565551908697126344507019279823765912491697621497302172417880934214987528715743450659793778804600497400584893293844663778329880087625383573916035873157302339738234257081911794709860677947013122214682749333403201976889693678084593155060187502388418594359414885973480331335534606175208197985019466022346755516750458368739823148921958404711266305635524457671282178245724228998100419228433521229716515613544038873782447633761330637156923679960869608573936927659682507718825770333947034126371922516944152252362083875868600924386764597718318182090480102290713119675545551643468533248755319990451701820058519326755032637656406914555970848386839956873547286705839189039814125964627482830929340651309314551660258298763791714811598562127907422291452195841044997796769983502566328438661824613428635077462458711668458709025671303283934715061424258099218542654112369509099772366269879369176380284082324820182955255688669845779043072338339536998003660818964719037885171177238929800353649662420713130211916209142489285453451105601980100872861113799550022103984273760999241052905774946164745487508285126538180261587268121834611622425013386195174699693073737629643895744807365329080259010601575969326329903210733144456032166204932138209427032647629649123619921157625969382371617974490459448436163362030698687247681206945367116937169167296358437817597527700432353937561546113024655435889597887204261937443656307072063236307889796600213047518289195405889446912318445469973847024469858005371965345728196768394306557150364496640059288072753899298366397532079263921876147551816820494105077792995685458506470571277610222300983409909667197632059627713914622540647221860481906463532385030847241918734752936048650745172841749460072620360204757629270589581110119970074345641749593655376972375702154402470375543371274882095123401020372911660045621841753203920568971306384963460682795141387452657134925253315363714572752387955510621439183525338047972181476683295477447576141011732423681010390229919962653364511549798609032752484505186563916391161167858306521674510768045222882362961469344625788320072376478678862132150450515281860087274445411519618647777050918856992270739775598294529375612661136680456187611891522664755381553044168817376752714719426093162756061572458041836294049654591592412925945677095920377387910800592917962615135589892143406097194862888638612226221607212795649691727901443921062398798491651582363771337866628214150609547476905292032766180527006210218562107726705655294522769166693405409784447807841980380520647455130773843989329917896404982086822794993035403290168615629581444217769679556045109873117376252867255073205919462234696007663906298962209329959805413934437140697480425099640763608017915540368053201237694819804102420946954806391582775602861591944892575946406039364587789445108787873135533375100417108793007636424646045581906792352748202787840636921616892624656636644487435407408294398420039271300035224122052470538167655367651436397606778816209059946503448080658456061421692012489174331210572234357126539792750645878634516899369304733276327577979324540378129811923518915129397993734786296667634253871125180483597971910932030897131353550045669988369405972212725497973424888275603687611577906074704902699724353321155313123456090870287756924857081031037126914705556280841379500440645762818583293085216736204259467989654172750621933739504797635183465849904565860335010409483850498461100224648287711109625346067241439286586246931112640332304279552304980859585427459247513356912940253530890140401845499439913711289687438143819406607305545360731656328994007731917706468934069016715102915878838388887343905164662717825178185623887434809345456647266313478367736152637862569959297383572462071213613206820767118695060174516019329837431837396085008807497031854638696147400056679336043313314531173593111272220465824177480090454905892729285633009196785256660078156295158730147765804596494310454815911086383366730799118079056670406720517828380860565501996816985809809259882618671255864501179375339735017158528579896499464395836899496310479879811792249949620173091138228854717637573439749597589905561316418695369388564112128235759823135603626423435028930771266769063098087199197953342530828107580425113911784642768662343982428347496384308615476027289689975161561368341451576970998980118486666356074258479747949436520306808734340120012644404535406326793221839131363837589328822437786440954000915916913826758142203491149568205941758687732786820063215506321663803259271407420979270414726640159850458401223832637877828728575585847078974319153681146579450730914086583154675083441064558537512243113986882494551167315378710589133362110807667261797859227314924435584761643523077008201981896036591171491157472768958092393197445840693400845907432512551336975554223570164273637043212034969852788812989539526676062117671849316905168504661290515042356889868895746686930270069254020687929392853892406251553600871064117890361962767532778730157952534428432978606703698373004647474795024526619530564958604679431657922772240120825721074089342298403799640713709403875020834103832312470387088784084345863171276641962719063344846610252396351578331508106381171235011419445491052453538405984003924044308581111866591871408310071132913199851771662251486081720435217044696705582813615351360235808844668829213080886663665783526706039279283630860103842405954890467324933808950065590146178234743148560580828057661676254229650448955510421552653232820634578111988805720691675041497237896230024544476710225315967181199647094405246948842156350033908521579509770461962421713022517471168553650583627021101997073312094880208842388234622344395861379186284607758580868314219014570775024127006827333813621308663524932597472050120426064449203238065131899050585568906611650474672449058221757674356431365393740764260505354626189401639735433438258042806139878149564416743303774459553478963829645153251859893832181564277778561576024909771529303092937492005228737458904622702047905225725745924759265173791063965860533905455284528561949242546209826314415743767254553264661686211075508774121548453589969572749197766058576609631846279395804131175468948871800826599061320069240094169583748014872660702435901820051902406230628013059730956744434251949510616806025548818172719729659930276217684164614526016875741127404348765963689163830620494709216022380453485600160405524490642402632025410484747137235386732652232752236177609174138885261771162912046713108018305709447678461754430673358853665803322370749018996725646355545033156494379740474960866423275910545764660790879011617007175611203785213222820552261648337998653447296736065109953347769865897998866653745457948159026423098446820451198009607350775408599145914089630194175726752197736126519106059735030310875429352578381472862363295860258036019033610267279559291831556149561100335068317590357697220476907897906381158855811082243209785002555423176805724340538974305628898639938045062180815083139963414156732856757219026540986108730855979009922905206263189907209412329125650648053090080845774924906128708722967267739207112115056429530787422668241520181252130458960198339731051989906389910044265380722261892417493307023953377643743380009353131780726096115941073384803736335759673140183558853440828446700906145095389715678518257037878923428333454374493739022355020021677316074568899462118915462007288010275939191507913745615737385554523389546276528026337012314807043775526231634766169857229649515693956808883587670323834113790884960824807694923198082678108278625853678908247262243367429609503272599790030374638799248889278203345697674373085629085582670969247115293337241160622736642006586798040218177670639088747762351402878671296759360410473233115043811253528198352427411887427398569327188420013688757802276094081448396878018298577826122723235489507636268929512139275147351121739616643606381808260599808283592605824248970210573925510317120194402208191725398016973923036545362032844566446276550220518334282238252939000062857760651722517037755260453217678507731303348064380195355351189926604551120374208515258481644746254865921828394497652830208456401972049585497195890436501382796841210603823370495053178433592393713631712625607812398685788471522674869077512718342330349433914471443700610365494010605485056022769700562471842481180425793626844559012718514981436519670301189557246200987832284704855457887038730287978485590415989820295935001082470691301462412286057510367429857112021232107983042585660282403002471004039927396247770627310502368928834839108127100127591466536370475614801184392200060095727565270790829802012792590459606121469700382786877588504653040427124444269188372086785932043601903833256700840591967506326984102657830542883323241794915890949017033053538293704497424423206603813727956121729287303747148983832915146139090032854229974673499651406991923992843184532551801338927616322679905071007320992480345431992509023269288028937327288336810606104571724062847020363685911491186485619927226414304629058490723221909730246947119366605050872059908029229434652500377193162921569451468509043519811226839240938989605831100183071279744606024687572550415766945510654206393227193414824888870858695909465092668088550874015506278791838017368713964039921215040330152033737692197580015792692015683151829354073994472332531306869062421067869746642085375479344299958792387236753048663675344819567340017562889064789782603230186734381727040963239371235985743665795714601298322286889968420313318929363282436487174116593566382545284159176096231857032644823701156827188286293820000588886928515388995731487420885393777056327260015900246440709859850101782311937996535049626858978666326747580205014732235035876026218211232658316944683112399217799624938866678425551889658970236463502077554923179280795897003594575270071423531714148238356971302777605133052270554682471403821946433782133389235174654038757623139890591741106212329134382553613317016760724878525836643211954199824202925828980153819911619492351326913909012230654367009862825763818272395576036940037966861445984833349910599601206139205599897703926738691824255744161531312519925753916504756146657117949653821277358370385017782325242837879125827879620018276625966127984565084705897974704909163683495829491717555528804388015538020635445294733092541715540712243367579782442568701233714558304190838924169752746151512514017503691268326526031096968761427581051636107236218435366175901191486666572086323442175661147177744145557869686147692970984423431321012842666564856803397408302432517594767756481793767846879783632253080360112527761565940301824955421028197824603971606483808303852187627299919036414170094736838666458138093112178647803770483543402720555724672085615330318252121037302989006383293139974703869616780677108950503206737311925239572837634982963031862607920370946753055655823047228051579561925934195035375959471729338211006764404260454744882372595183979521150395869780988176903633447944372420415634316176392732535684677530587308640227319154181384905277981743353957927089759832286345937464366371816072922410307580994569048129860914064559145606238486593401308065504095231337173885985667109232722556096660067523258702867306771208668072414736143322096311873018314753143211719636207027587553113045684216013603057103425495751717631576533789853818717848928256926314476193311450257802685877968616780446657057311630912756542543000128156922299988836871646089142722770381794497615799721154816130335181005212666870960823502062657033550807131971798414171093380714278658430126450363602443601852800339030173061328728508815355311917814848306527390616763921359714469206688863755779000652416935493342139253265711965234773055006806651265376387383080900707657250201503873476332533626992067931801675040955619957918670860919566754959324283307488715597661837315485713226227634796652941210790519096927232367464636695739466558653091439470403618978318245245014032832372575779874721440304993624845957742689575091186801285806103804078547869563525581490497429827237572068489266813323244873593654146034708436716158509367521941420769451899453718871396641253405191728810591144060940208163590797006472448183361830642174534696354536239004672991764502065294331885320999026150879555259072669002049626712576091101480392688889497034559584620170654396275788885805937276773412250869306936120594669210689961158075882659889987934746451132788812283175647868236562529818639465472990070489382491149735486131735594584348551368857543032292336404546877793610120890690896598253055033721337723833810783501729729101103073656135268574009579240644996897181681846276823196412672704134870990545152362095118408854767031519179986602744766530722971358631785423695307919242153327602697445128796472631329222205540940459825832363180368446128210863403024962298932846963424807491118149782324581088374162105912409998414005885818753787030710258834172044652642868373235718297618517009368271902305917975269964086599524482063419752022378552996861488101534489622788987234532346160220546871768580739172280409514979530643522846459162463631651133534276299863755493301165882552919926688001500492480138360931648163112217816099215109900204560565798355825095250870134876718920867070281404081425524783641117898210252772104396203239216831126172277297473487026393738007538368287982810020334185637086168175869654397729419226186227097460322175997227525379873684182241588831514100405171632451724964534357163485352132872684310165383240239049326101273657010810922730272486366883238826552891884412352243859177583541190066501978273419774750409901265967018588007958553076711632261981614625247201186570453449290104270982894306595886088830020406122018186436888682146678376648455847150607512900244124113157707089780004805812292396307480052961604675260531558884311612101369685338016932998773005455285740235427524352649646085168908964618075111729714647185367199093686381724855918123737582800678016283139105611441264309914490354454979042514799965509590264458199057434664384884514973338721948228424379983973972932798123399187126221984463214805241861782545990725355678116024504274478404577009622438882234020320364136749640979388235357861691472231989715687034921481279441054865409631489165041260721141702703986408187582127358145352577159087898554729658433487025204297868124382699849588234048916631307295531741903186183692448056209260567267931644941714580055660736679212252780322738261531612884996229263094934855214126627710738102612667104256352069511352239938211172511381920046031038771399811320758298159964394185855115310002207043012325625007270591174389263486571646606875430317714864454680275406144363207923935001275388215590920610700669931440132167224681157126546481839502287808784289966590177994634972542152849536332377358475412617143270336040960423566900109253285428622070862698305008908589677590131609018977263682696316200643778843161735099829740156501879731589681401567397335933486069095940474328299667412623359974027939434951348927750773853681668019069399406781666625332617457302397083389666057886457808998619395393566263556139308323102093486249806689444231779495151012819518344532257625430709831394295201770268450908118975365461895662669733434966259208685943529606557683652277828513050767665902236938170346206456130134138099500885388303539848485203891162641023175078504223835115948176979758943124213999035625054973959504353300770935372427838157664000044653540547828547532022784160093071994927448523304593899163245416824410973609519343210127500332877628050096483671050527705522536034100561848103480483996335716818909945346925169328487950159610999747607551344198102121142088360726479601656367862097657327563455396637196986555508541448192208751591270941291159097576872227102181516156966731212168210693375028192325704448378188841343502357081442828839426106419439348617060865469631902955774783849219824005183982974689284291941589065021319296582424045567925701038356169877224902920340486187458299591893240464750520691144485979022776425270208743797951386390199123936558173241632222488944261745402847894473976555350081432144866614637857554591633279934514853661464493987403205997397458369692846605597944248742724403978104973858531241060728950882595408820363395882436673454787853920301339249229909950171481442050639388410869597533259021500918455874863567839045663976416550670334786311490741901605722314907216319854101770862782137046399123250504134667048450235296155155532642929688938862525609520042526186890874372174864406092800348005291475191366197355754323963642245066272789903719673247631899030917848880372932922997891885337201170125615208433293006570268471793133047152162269773600855259182812268381714257773480874338784766470396928127076195131845684020898459540348264882218260268361992767624802415559216416749912676824168086656742582578749840821037923616040451639582694473651403606828181407325128265288487073849511804960076604842288378815705692213410491992226122252021671854567736540725288480768171418912859397923681577360867062407113694488534144972062751589549376557718365210148420852186107436395121338364519129770959647257915550868182766324827628806648160273671305559728510106052070366994319397187107942866241450427154345178753694943373593305589208411575170551616986686312197944530777574773269089363327846664716222143774108498095518030396934886290747534528476719126081622432202775848309958506247059781647350681229754569611833183329495250354022483640430199023657687862947271378635608442934014868419699609344423172372010707286132922086898815551088470743069762511629038927558915846369896769896518887810618564111049567558758257755443696864200777528280925377230604811804584120433095001773186736519137285568151745093016404227135682008633765652528370550116690728224132751799957431390657839629977713722427054267728901874756795186779132521352842928522861848510834797677608452733797108927445053436823143164037887223448288665802701402638341041319796484158181479455910768706723755753840006093434900133133971334216022080041821343994592664967160869528906276828647971887128267347011231166437095521448821423587061476663501326128146101174347401691870497131547536408286740644172308641800349628039977509438629006224673218460637862511635092031244066549970562889597183158320132317025413304880693015158191541630195665087816334676815514083163649442676987193953772545057668586006975603047679171867429717691058434006387190296527571830707967726165877262012390067609824498873411211946558971925135310993752064000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

result bits = 79321

The computation took ~13.3 sec with my unsophisticated 32 bit code arithmetics on AMD A8-5500 3.2 GHz (using fixed bitwidth 2500*32 bits = 80000 bits )

Spektre
  • 49,595
  • 11
  • 110
  • 380
1

No numerical fundamental type of C++ can represent such large values.

You can represent arbitrarily large numbers using arrays (constrained by available memory). But in order to perform calculations using arrays that represent numbers, you need to define the operations first. This is called "arbitrary precision arithmetic", and the C++ standard library doesn't provide an implementation of those operations.

eerorika
  • 232,697
  • 12
  • 197
  • 326