Comment puis-je calculer efficacement l'exposant d'un `i` premier dans le terme T2 d'une factorielle, où exposant(i) = somme(j=1,2,3,4,5,...) de (4N/( je^j)) - (2N/(je^j)) ?

Le problème de la question est de trouver un moyen rapide de calculer le terme T2 dans l'expression de la factorielle bigint exacte rapide. Le terme T2 est défini comme :

T2(4N) = multiplication(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

C'est déjà assez rapide, et avec quelques astuces de programmation, la complexité se rapproche de ~ O(log(n)).

Pour être clair, mon la mise en œuvre actuelle est la suivante :

longnum fact(const DWORD &x,longnum &h) // h return (x>>1)! to speed up computation
    {
    if (x==0) { h=1; return  1; }
    if (x==1) { h=1; return  1; }
    if (x==2) { h=1; return  2; }
    if (x==3) { h=1; return  6; }
    if (x==4) { h=2; return 24; }
    int N4,N2,N,i; longnum c,q;
    N=(x>>2);
    N2=N<<1;
    N4=N<<2;
    h=fact(N2,q);                                          // get 2N! and N!
    c=h*h; for (i=(N2+1)|1;i<=N4;i+=2) c*=i; c/=q;         // c= ((2N)!).((2N)!)/ N!
    for (i=N4+1;i<=x;i++) c*=i; c.round(); c<<=N  ;        // convert 4N! -> x!, cut off precision losses
    for (i=(N2+1)|1,N2=x>>1;i<=N2;i++) h*=i; h.round();    // convert 2N! -> (x/2)!, cut off precision losses
    return c;
    }

longnum fact(const DWORD &x)

{
longnum tmp;
return fact(x,tmp);
}

Now my question:

Is there a fast way to obtain N! from this T2 **term**:

T2 = (4N) ! / (((2N)!).((2N)!))

so:

(4N)! = (((2N)!).((2N)!)).T2

This would help a lot because then it would not be needed to compute .../(N!) for factorial. 

The T2 term is always integer-decomposable to this:

T2 = T2 * N!

Finally, it hit me :) I have done a little program for primes decomposition of factorials and then suddenly all becomes much clearer:

4! = 2!.2!.(2^1).(3^1) = 24
8! = 4!.4!.(2^1).(5^1).(7^1) = 40320
12! = 6!.6!.(2^2).(3^1).(7^1).(11^1) = 479001600
16 ! = 8!.8!.(2^1).(3^2).(5^1).(11^1).(13^1) = 20922789888000
20 ! = 10!.10!.(2^2).(11^1).(13^1).(17^1).(19^1) = 2432902008176640000
24 ! = 12!.12!.(2^2).(7^1).(13^1).(17^1).(19^1).(23^1) = 620448401733239439360000
28 ! = 14!.14!.(2^3).(3^3).(5^2).(17^1).(19^1).(23^1) = 304888344611713860501504000000
32! = 16!.16!.(2^1).(3^2).(5^1).(17^1).(19^1).(23^1).(29^1).( 31^1) = 263130836933693530167218012160000000
36 ! = 18!.18!.(2^2).(3^1).(5^2).(7^1).(11^1).(19^1).(23^1).( 29^1).(31^1) = 37199332678990121746799944815083520000000
40 ! = 20!.20!.(2^2).(3^2).(5^1).(7^1).(11^1).(13^1).(23^1).( 29^1).(31^1).(37^1) = 815915283247897734345611269596115894272000000000

After analyzing the prime exponents of the T2 term (the rest after half factorials ^ 2) I derive the formula for them:

T2(4N) = multiplication(i=2,3,5,7,11,13,17,...) de ( i ^ somme(j=1,2,3 ,4,5,...) de (4N/(i^j))-(2N/(i^j)) )

The problem is that the divisions 4N/(i^j) and 2N/(i^j)  must be done in integer math so they cannot be simplified easily.

So I have another question:

How can I compute this: exponent(i) = sum(j=1,2,3,4,5,...) of (N/(i^j)) effectively?

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!