Другие языки программирования и технологии
Алгоритм быстрого фактариала.
Юзаю длинные числа для одной лабы и там задания посчитать факториал от моего числа . Задав в проге числи то хотя бы 500 сижу и жду уже пол часа пока посчитает . Помогите плиз кто знает . Желательно не рекурсивный
Ну можно попробовать использовать другие типы данных (к примеру 64-битные) и формировать произведения по небольшим отрезкам в стек, а потом уже в длинных числах перемножить данные из стека.
Я бы так поступил.
Я бы так поступил.
ну, примерно вот так будет:
500! = 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
500! = 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
pastebin.com
сюда код загрузи
сюда код загрузи
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
`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 (возможно такой порядок перемножения неоптимален) . ПОтом уже переходи на длинные числа
Проверь его на скорость, посмотри про алгоритм карацубы.
Дальше, можно числа, пока влазят перемножать как 64 битные.
То есть первым шагом умножаешь (в 64 битных)
[1*500, 2*499, 3*498 ...]
потом еще раз до тех пор пока не случится overflow (возможно такой порядок перемножения неоптимален) . ПОтом уже переходи на длинные числа
Просто используйте функциональный язык программирования, например Lisp. Наверное вы используете процедурный язык
Похожие вопросы
- Проблема с алгоритмом быстрой сортировкой С++
- Изучил несколько простых алгоритмов сортировки, осталось изучить быструю и слияние, нужно ли вообще писать эти алгоритмы
- Почему программирование на первый взгляд такое сложное? Потому что многие не умеют составлять алгоритмы?
- Нужно ли быть очень сильным математиком и хорошо уметь конструировать алгоритмы на позиции Software Engineer?
- Посчитань N!(фактариал)
- алгоритм... по нахождению общих элементов двух массивов
- Вопрос про алгоритмы
- Подскажите мне пожалуиста что такое алгоритм и зачем компьютеру. нужен алгоритм.И что такое прога Паскаль и зачем она
- Как может время работы алгоритма не изменятся при переходе к более скоростному алгоритму ?
- Скорость тупого алгоритма