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!

CodePudding user response：

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:

   • 32bit ALU in C

   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 bitwidth 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:

   • Fast Factorial

   otherwise you will computing a long time. Other option is to go parallel instead ...

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):

   • fast squaring

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 (using fixed bitwidth 2500*32 bits = 80000 bits )

CodePudding user response：

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.