"1 million factorial"의 두 판 사이의 차이
ph
(Looking for work http://hogylamijap.de.tl bbs elweb child cant really talk shit about the little dick guy. he is all over this website getting his cock sucked by hot women and you all are sitting at) |
|||
| (사용자 75명의 중간 판 168개는 보이지 않습니다) | |||
| 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