"1 million factorial"의 두 판 사이의 차이

2017년 6월 19일 (월) 12:19 기준 최신판

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

http://answers.google.com/answers/threadview/id/509662.html

http://en.wikipedia.org/wiki/Elliptic_curve_factorization

@@ 1번째 줄: / 1번째 줄: @@
-<p>How much is a First Class stamp? http://auneteycelu.de.tl bbs boy pic  IF ALL WOMEN WERE LIKE THIS THERE WOULD BE NO VIOLENCE IN THIS WORLD, WE'D BE TOO BUSY HOME FUCKING THEM, YOU CAN WATCH SHIT LIKE THIS ON TV IN OTHER COUNTRYS OR AT LEAST A LOT MORE THEN YOU COULD HERE, THIS COUNTRY IS TOO FUCKING SEXUALLY REPRESSED
+#ril https://www.quora.com/What-is-an-efficient-algorithm-to-find-the-factorial-of-huge-numbers-which-lie-in-the-range-100000-1000000
-</p>
+== 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))
+,565,709 digits starting <div style='word-wrap: break-word;'>82639316883312400623766461031726662911353479789638730451677758855633796110356450844465305113114639733516068042108785885414647469506478361823012109754232995901156417462491737988838926919341417654578323931987280247219893964365444552161533920583519938798941774206240841593987701818807223169252057737128436859815222389311521255279546829742282164292748493887784712443572285950934362117645254493052265841197629905619012120241419002534128319433065076207004051595915117186613844750900755834037427137686877042093751023502633401248341314910217684549431273636399066971952961345733318557782792616690299056202054369409707066647851950401003675381978549679950259346666425613978573559764142083506&hellip; </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