"1 million factorial"의 두 판 사이의 차이
ph
(Thanks funny site <a href=" http://www.indabamusic.com/people/139021348/blog/13971-virgin-little-lolita-tgp ">lolita nn model post</a> 626 <a href=" http://www.indabamusic.com/people/476660470/blog/1) |
|||
| 1번째 줄: | 1번째 줄: | ||
| − | + | #ril https://www.quora.com/What-is-an-efficient-algorithm-to-find-the-factorial-of-huge-numbers-which-lie-in-the-range-100000-1000000 | |
| + | |||
| + | == just by using [http://www.manpagez.com/man/1/bc/ bc] == | ||
| + | rewrote a factorial function not to use recursive calling. | ||
| + | <syntaxhighlight lang="c"> | ||
| + | define g(x) { | ||
| + | answer=1; | ||
| + | for(i=1;i<x+1;i++) { | ||
| + | answer *= i; | ||
| + | } | ||
| + | return answer; | ||
| + | } | ||
| + | |||
| + | g(1000000); | ||
| + | </syntaxhighlight> | ||
| + | real 578m28.905s<br> | ||
| + | user 450m56.192s<br> | ||
| + | sys 12m33.006s<br> | ||
| + | (with poor computing power (centOS virtual machine on windows7. i5 processor)) | ||
| + | 5,565,709 digits starting <div style='word-wrap: break-word;'>82639316883312400623766461031726662911353479789638730451677758855633796110356450844465305113114639733516068042108785885414647469506478361823012109754232995901156417462491737988838926919341417654578323931987280247219893964365444552161533920583519938798941774206240841593987701818807223169252057737128436859815222389311521255279546829742282164292748493887784712443572285950934362117645254493052265841197629905619012120241419002534128319433065076207004051595915117186613844750900755834037427137686877042093751023502633401248341314910217684549431273636399066971952961345733318557782792616690299056202054369409707066647851950401003675381978549679950259346666425613978573559764142083506… </div>ending with 249,998 zeros(about 4.49% of the whole digits) | ||
| + | * more easy way to get the number of trailing zeros(from [http://answers.yahoo.com/question/index?qid=20071017145425AAaGkd2 here]) | ||
| + | <blockquote> | ||
| + | Every multiple of 5 contributes a zero.<br> | ||
| + | Every multiple of 25 contributes a second zero<br> | ||
| + | Every multiple of 125 contributes a third zero<br> | ||
| + | Every multiple of 625 contributes a fourth zero<br> | ||
| + | etc.<br> | ||
| + | <br> | ||
| + | floor(1000000/5) + floor(1000000/25) + ... floor(1000000/5^8)<br> | ||
| + | = 200,000 + 40,000 + 8,000 +1,600 +320 + 64 +12 + 2 <br> | ||
| + | = 249,998 trailing zeros | ||
| + | </blockquote> | ||
| + | * someone can get this in about only 10sec!! [http://www.makewebgames.com/showthread.php/24362-Factorial-Program-in-C-1-Million-Factorial here]<br>He's saying he used FFT | ||
| + | == ref == | ||
| + | http://www.luschny.de/math/factorial/FastFactorialFunctions.htm | ||
| + | |||
| + | http://www.luschny.de/math/factorial/csharp/FactorialPrimeSwing.cs.html | ||
| + | |||
| + | http://answers.google.com/answers/threadview/id/509662.html | ||
| + | |||
| + | http://en.wikipedia.org/wiki/Elliptic_curve_factorization | ||
2017년 6월 19일 (월) 12:19 기준 최신판
just by using bc
rewrote a factorial function not to use recursive calling.
define g(x) {
answer=1;
for(i=1;i<x+1;i++) {
answer *= i;
}
return answer;
}
g(1000000);
real 578m28.905s
user 450m56.192s
sys 12m33.006s
(with poor computing power (centOS virtual machine on windows7. i5 processor))
5,565,709 digits starting
82639316883312400623766461031726662911353479789638730451677758855633796110356450844465305113114639733516068042108785885414647469506478361823012109754232995901156417462491737988838926919341417654578323931987280247219893964365444552161533920583519938798941774206240841593987701818807223169252057737128436859815222389311521255279546829742282164292748493887784712443572285950934362117645254493052265841197629905619012120241419002534128319433065076207004051595915117186613844750900755834037427137686877042093751023502633401248341314910217684549431273636399066971952961345733318557782792616690299056202054369409707066647851950401003675381978549679950259346666425613978573559764142083506…
ending with 249,998 zeros(about 4.49% of the whole digits)
- more easy way to get the number of trailing zeros(from here)
Every multiple of 5 contributes a zero.
Every multiple of 25 contributes a second zero
Every multiple of 125 contributes a third zero
Every multiple of 625 contributes a fourth zero
etc.
floor(1000000/5) + floor(1000000/25) + ... floor(1000000/5^8)
= 200,000 + 40,000 + 8,000 +1,600 +320 + 64 +12 + 2
= 249,998 trailing zeros
- someone can get this in about only 10sec!! here
He's saying he used FFT
ref
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
http://www.luschny.de/math/factorial/csharp/FactorialPrimeSwing.cs.html