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

ph
이동: 둘러보기, 검색
(Not available at the moment <a href=" http://lenukuamile.blog4ever.com/blog/lire-article-668075-8671304-latina_model_preteen.html ">preteen fotoplenka</a> =DD <a href=" http://nufycebyjepe.blog4ever.)
 
(사용자 100명 이상의 중간 판 608개는 보이지 않습니다)
1번째 줄: 1번째 줄:
Not available at the moment <a href=" http://lenukuamile.blog4ever.com/blog/lire-article-668075-8671304-latina_model_preteen.html ">preteen fotoplenka</a>  =DD <a href=" http://nufycebyjepe.blog4ever.com/blog/lire-article-668071-8671295-black_horny_preteens.html ">korean preteens photos</a> 32106 <a href=" http://yupusasorahe.blog4ever.com/blog/lire-article-668076-8671305-cunt_little_preteens.html ">uncensored little preteens</a> 320426 <a href=" http://enedemeoqafu.blog4ever.com/blog/lire-article-668078-8671310-preteen_model_kds.html ">archive youngest preteen</a> grera <a href=" http://yfyretegaqyf.blog4ever.com/blog/lire-article-668070-8671294-pussy_sex_preteen.html ">candid preteen sites</a> =) <a href=" http://luqygitynyj.blog4ever.com/blog/lire-article-668077-8671308-nude_preteen_russians.html ">little pussy preteens</a> >:-DDD <a href=" http://unitomyai.blog4ever.com/blog/lire-article-668072-8671297-preteens_angels.html ">katia preteen model</a>  :OOO <a href=" http://cirefahyjyj.blog4ever.com/blog/lire-article-668069-8671293-preteen_g_rls.html ">preteen movie home</a>  09648 <a href=" http://onaotahapaja.blog4ever.com/blog/lire-article-668068-8671292-penetracuion_anal_preteens.html ">non nudepreteen list</a>  743 <a href=" http://isymycunefa.blog4ever.com/blog/lire-article-668073-8671300-nude_teen_preteen.html ">art nude preteens</a>  12015
+
#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&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

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

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