Факториала целого числа по модулю т быстрого вычисления

Question

Можно ли рассчитать факториал (х) по модулю т без циклов через всей экспрессию цепь

((1 % m) * (2 %m) * (3 % m) * ... (x % m)) % m? 

Чтобы быть более точным m может быть 1 < = m < = 10^7 и x: 1 < = x < м

Answer 1

есть несколько быстрых алгоритмов для Факториала там

• поэтому ответ: Да, вы можете вычислить факториал без зацикливания всех значений
• все, что я видел, использует простые числа разбиений (включая алгоритм шахтного)
• так от того, что это просто вопроса Усеина мод умножения вместо обычного умножения
• посмотреть здесь: Fast exact bigint factorial мой быстрый алгоритм
• и другой ответ также содержит ссылку на качающийся алгоритма простых чисел ...

[Примечания]

• для N! вам нужен список простых чисел до N
• , но остальная часть кода может работать на арифметике, способных удерживать N,m
• так нет необходимости в огромных количествах ...

[edit1] шахта 32bit C++ реализации

//--------------------------------------------------------------------------- 
DWORD modmul(DWORD a,DWORD b,DWORD n) 
    { 
    DWORD _a,_b,_n; 
    _a=a; 
    _b=b; 
    _n=n; 
    asm { 
     mov eax,_a 
     mov ebx,_b 
     mul ebx  // H(edx),L(eax) = eax * ebx 
     mov ebx,_n 
     div ebx  // eax = H(edx),L(eax)/ebx 
     mov _a,edx // edx = H(edx),L(eax) % ebx 
     } 
    return _a; 
    } 
//--------------------------------------------------------------------------- 
DWORD modfact0(DWORD n,DWORD m)   // (n!) mod m (naive approach) 
    { 
    DWORD i,f; 
    for (f=1,i=2;i<=n;i++) f=modmul(f,i,m); 
    return f; 
    } 
//--------------------------------------------------------------------------- 
DWORD modfact1(DWORD n,DWORD m)   // (n!) mod m (mine fast approach) 
    { 
    if (n<=4) 
     { 
     if (n==4) return 24; 
     if (n==3) return 6; 
     if (n==2) return 2; 
     if (n==1) return 1; 
     if (n==0) return 1; 
     } 
    int N4,N2,p,i,j,e; DWORD c,pp; 
    N4=(n>>2)<<2; 
    N2=N4>>1; 
    c=modfact1(N2,m); c=modmul(c,c,m); // c=((2N)!)^2; 
    for (i=0;;i++)      // c*= T2 
     { 
     p=primes_i32.dat[i]; 
     if (!p) break; 
     if (p>N4) break; 
     for (e=0,j=N4;j;e+=j&1,j/=p); 
     if (e)       // c*=p^e 
      { 
      if (p==2) c<<=e; 
      else for (pp=p;;) 
       { 
       if (int(e&1)) c=modmul(c,pp,m); 
       e>>=1; if (!e) break; 
       pp=modmul(pp,pp,m); 
       } 
      } 
     } 
    for (i=N4+1;i<=n;i++) c=modmul(c,i,m); 
    return c; 
    } 
//--------------------------------------------------------------------------- 

штрихами:

• DWORD primes_i32.dat[] будет предварительно вычислены отсортирован (по возрастанию) список всех простых чисел до n

Вот результат:

[ 18.529 ms] slow modfact0(1000000,1299721) = 195641 
[ 2.995 ms] fast modfact1(1000000,1299721) = 195641 
[ 96.242 ms] slow modfact0(5000000,9999991) = 2812527 
[ 13.305 ms] fast modfact1(5000000,9999991) = 2812527 

• 1299721 является первым премьер близко к 1000000 I Найдено
• если m не является простые и subresult хиты нуль, то вы можете игнорировать остальную часть умножения на массивную скорость до ...

Надежда результат ОК нет ничего, чтобы сравнить с ...