Другие языки программирования и технологии

Алгоритм быстрого фактариала.

Юзаю длинные числа для одной лабы и там задания посчитать факториал от моего числа . Задав в проге числи то хотя бы 500 сижу и жду уже пол часа пока посчитает . Помогите плиз кто знает . Желательно не рекурсивный
Vladimir Kychin
Vladimir Kychin
434
Ну можно попробовать использовать другие типы данных (к примеру 64-битные) и формировать произведения по небольшим отрезкам в стек, а потом уже в длинных числах перемножить данные из стека.
Я бы так поступил.
Илья Слобожан
Илья Слобожан
74 911
Лучший ответ
ну, примерно вот так будет:

500! = 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
pastebin.com

сюда код загрузи
Almat Amantaev
Almat Amantaev
22 045
1000! = 402`387`260`077`093`773`543`702`433`923`003`985`719`374`864`210
`714`632`543`799`910`429`938`512`398`629`020`592`044`208`486`969`404`800`479`988
`610`197`196`058`631`666`872`994`808`558`901`323`829`669`944`590`997`424`504`087
`073`759`918`823`627`727`188`732`519`779`505`950`995`276`120`874`975`462`497`043
`601`418`278`094`646`496`291`056`393`887`437`886`487`337`119`181`045`825`783`647
`849`977`012`476`632`889`835`955`735`432`513`185`323`958`463`075`557`409`114`262
`417`474`349`347`553`428`646`576`611`667`797`396`668`820`291`207`379`143`853`719
`588`249`808`126`867`838`374`559`731`746`136`085`379`534`524`221`586`593`201`928
`090`878`297`308`431`392`844`403`281`231`558`611`036`976`801`357`304`216`168`747
`609`675`871`348`312`025`478`589`320`767`169`132`448`426`236`131`412`508`780`208
`000`261`683`151`027`341`827`977`704`784`635`868`170`164`365`024`153`691`398`281
`264`810`213`092`761`244`896`359`928`705`114`964`975`419`909`342`221`566`832`572
`080`821`333`186`116`811`553`615`836`546`984`046`708`975`602`900`950`537`616`475
`847`728`421`889`679`646`244`945`160`765`353`408`198`901`385`442`487`984`959`953
`319`101`723`355`556`602`139`450`399`736`280`750`137`837`615`307`127`761`926`849
`034`352`625`200`015`888`535`147`331`611`702`103`968`175`921`510`907`788`019`393
`178`114`194`545`257`223`865`541`461`062`892`187`960`223`838`971`476`088`506`276
`862`967`146`674`697`562`911`234`082`439`208`160`153`780`889`893`964`518`263`243
`671`616`762`179`168`909`779`911`903`754`031`274`622`289`988`005`195`444`414`282
`012`187`361`745`992`642`956`581`746`628`302`955`570`299`024`324`153`181`617`210
`465`832`036`786`906`117`260`158`783`520`751`516`284`225`540`265`170`483`304`226
`143`974`286`933`061`690`897`968`482`590`125`458`327`168`226`458`066`526`769`958
`652`682`272`807`075`781`391`858`178`889`652`208`164`348`344`825`993`266`043`367
`660`176`999`612`831`860`788`386`150`279`465`955`131`156`552`036`093`988`180`612
`138`558`600`301`435`694`527`224`206`344`631`797`460`594`682`573`103`790`084`024
`432`438`465`657`245`014`402`821`885`252`470`935`190`620`929`023`136`493`273`497
`565`513`958`720`559`654`228`749`774`011`413`346`962`715`422`845`862`377`387`538
`230`483`865`688`976`461`927`383`814`900`140`767`310`446`640`259`899`490`222`221
`765`904`339`901`886`018`566`526`485`061`799`702`356`193`897`017`860`040`811`889
`729`918`311`021`171`229`845`901`641`921`068`884`387`121`855`646`124`960`798`722
`908`519`296`819`372`388`642`614`839`657`382`291`123`125`024`186`649`353`143`970
`137`428`531`926`649`875`337`218`940`694`281`434`118`520`158`014`123`344`828`015
`051`399`694`290`153`483`077`644`569`099`073`152`433`278`288`269`864`602`789`864
`321`139`083`506`217`095`002`597`389`863`554`277`196`742`822`248`757`586`765`752
`344`220`207`573`630`569`498`825`087`968`928`162`753`848`863`396`909`959`826`280
`956`121`450`994`871`701`244`516`461`260`379`029`309`120`889`086`942`028`510`640
`182`154`399`457`156`805`941`872`748`998`094`254`742`173`582`401`063`677`404`595
`741`785`160`829`230`135`358`081`840`096`996`372`524`230`560`855`903`700`624`271
`243`416`909`004`153`690`105`933`983`835`777`939`410`970`027`753`472`000`000`000
`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000
`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000
`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000
`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000`000

время определения размера 5,83742e-005 с
время вычисления 0,000362193 с
время форматирования 0,00392746 с

10000! = 28`462`596`809`170`545`189
,,,,
время определения размера 0,000534926 c
время вычисления 0,0455036 c
время форматирования 0,498927
произведение больших чисел сам писал?
Проверь его на скорость, посмотри про алгоритм карацубы.
Дальше, можно числа, пока влазят перемножать как 64 битные.
То есть первым шагом умножаешь (в 64 битных)
[1*500, 2*499, 3*498 ...]
потом еще раз до тех пор пока не случится overflow (возможно такой порядок перемножения неоптимален) . ПОтом уже переходи на длинные числа
Просто используйте функциональный язык программирования, например Lisp. Наверное вы используете процедурный язык
VK
Vip8222Kz Kondratev
2 833