Быстрый способ рассчитать! мод м, где м простое число?

Question

Мне было любопытно, если бы был хороший способ сделать это.Мой текущий код выглядит примерно так:

def factorialMod(n, modulus):
    ans=1
    for i in range(1,n+1):
        ans = ans * i % modulus    
    return ans % modulus

Но он выглядит довольно медленно!

Я тоже не могу вычислить n!и затем примените простой модуль, потому что иногда n настолько велико, что n!просто не представляется возможным рассчитать явно.

Я также сталкивался с http://en.wikipedia.org/wiki/Stirling%27s_approximation и задаюсь вопросом, может ли это вообще использоваться здесь каким-либо образом?

Или, как я могу создать рекурсивную запоминаемую функцию в C ++?

Answer 1

n может быть сколь угодно большим

Ну, n не может быть произвольно большим - если n >= m, то n! ≡ 0 (mod m) (потому что m является одним из факторов по определению факториала) .

---

Предполагая, что n << m и вам нужно точное значение, ваш алгоритм не может работать быстрее, насколько мне известно. Однако, если n > m/2, вы можете использовать следующее тождество ( Теорема Вильсона - Спасибо @Daniel Fischer!)

для ограничения числа умножений на m-n

(m-1)! ≡ -1 (mod m)
1 * 2 * 3 * ... * (n-1) * n * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m)
n! * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m)
n! ≡ -[(n+1) * ... * (m-2) * (m-1)]<sup>-1</sup> (mod m)

Это дает нам простой способ вычисления n! (mod m) в m-n-1 умножениях плюс модульное обратное :

def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(n+1,modulus):
            ans = (ans * i) % modulus
        ans = <a href="http://www.algorithmist.com/index.php/Modular_inverse" rel="noreferrer">modinv(ans, modulus)</a>
        ans = -1*ans + modulus
    return ans % modulus

---

Мы можем перефразировать вышеприведенное уравнение другим способом, который может или не может работать немного быстрее. Используя следующий идентификатор:

мы можем перефразировать уравнение как

n! ≡ -[(n+1) * ... * (m-2) * (m-1)]<sup>-1</sup> (mod m)
n! ≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)]<sup>-1</sup> (mod m)
       (reverse order of terms)
n! ≡ -[(-1) * (-2) * ... * -(m-n-2) * -(m-n-1)]<sup>-1</sup> (mod m)
n! ≡ -[(1) * (2) * ... * (m-n-2) * (m-n-1) * (-1)<sup>(m-n-1)</sup>]<sup>-1</sup> (mod m)
n! ≡ [(m-n-1)!]<sup>-1</sup> * (-1)<sup>(m-n)</sup> (mod m)

Это можно записать на Python следующим образом:

def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus   
    else:
        #Fancypants method for large n
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = <a href="http://www.algorithmist.com/index.php/Modular_inverse" rel="noreferrer">modinv(ans, modulus)</a>

        #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd
        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus

---

Если вам не нужно точное значение, жизнь становится немного проще - вы можете использовать приближение Стирлинга , чтобы вычислить приблизительное значение за O(log n) время ( используя возведение в степень путем возведения в квадрат ) .

---

Наконец, я должен отметить, что если это критично ко времени, и вы используете Python, попробуйте переключиться на C ++. Исходя из личного опыта, следует ожидать увеличения скорости на порядок или более, просто потому, что это именно тот тип замкнутого цикла с привязкой к процессору, который изначально скомпилированный код превосходит при (также, по любой причине, GMP кажется намного более точно настроенным, чем Bignum Python) .

Answer 2

Расширение моего комментария до ответа:

Да, есть более эффективные способы сделать это. Но они очень грязные.

Поэтому, если вам действительно не нужна эта дополнительная производительность, я не советую пытаться реализовать их.

---

Ключ должен отметить, что модуль (который по сути является делением) будет узким местом.К счастью, есть несколько очень быстрых алгоритмов, которые позволяют выполнять модуль над одним и тем же числом много раз.

• Деление на инвариантные целые числа с использованием умножения
• Сокращение Монтгомери

Эти методы быстрые, потому что они существенно устраняют модуль.

---

Эти методы сами по себе должны дать вам умеренное ускорение.Чтобы быть по-настоящему эффективным, вам, возможно, потребуется развернуть цикл, чтобы учесть лучший IPC:

Примерно так:

ans0 = 1
ans1 = 1
for i in range(1,(n+1) / 2):
    ans0 = ans0 * (2*i + 0) % modulus    
    ans1 = ans1 * (2*i + 1) % modulus    

return ans0 * ans1 % modulus

, но с учетом нечетного числа итераций и объединения егос одним из методов, на которые я ссылался выше.

Некоторые могут утверждать, что развертывание цикла должно быть оставлено на усмотрение компилятора.Я буду утверждать, что компиляторы в настоящее время недостаточно умны, чтобы развернуть этот конкретный цикл.Присмотритесь поближе, и вы поймете, почему.

---

Обратите внимание, что хотя мой ответ не зависит от языка, он предназначен главным образом для C или C ++.

Answer 3

п! mod m может быть вычислено в операциях O (n ^{1/2 + & epsilon;} ) вместо наивного O (n). Это требует использования полиномиального умножения БПФ и имеет смысл только для очень больших n, например n> 10 ⁴ .

Схема алгоритма и некоторые временные характеристики можно увидеть здесь: http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/

Answer 4

Если мы хотим вычислить M = a*(a+1) * ... * (b-1) * b (mod p), мы можем использовать следующий подход, если предположим, что мы можем быстро сложить, вычесть и умножить (mod p) и получить сложность во время выполнения O( sqrt(b-a) * polylog(b-a) ).

Для простоты предположим, что (b-a+1) = k^2 - это квадрат.Теперь мы можем разделить наш продукт на k частей, то есть M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b].Каждый из факторов в этом продукте имеет форму p(x)=x*..*(x+k-1), для соответствующих x.

Используя алгоритм быстрого умножения полиномов, такой как алгоритм Шёнхаге-Штрассена , вразделяя и властвуй, можно найти коэффициенты многочлена p(x) in O( k * polylog(k) ).Теперь, по-видимому, существует алгоритм для замены k точек в одном и том же полиноме степени k в O( k * polylog(k) ), что означает, что мы можем вычислить p(a), p(a+k), ..., p(b-k+1) fast.

Этот алгоритм замены многих точек в одинПолином описан в книге «Простые числа» К. Померанса и Р. Крэндалла.В конце концов, когда у вас есть эти k значения, вы можете умножить их на O(k) и получить желаемое значение.

Обратите внимание, что все наши операции были приняты (mod p).Точное время работы O(sqrt(b-a) * log(b-a)^2 * log(log(b-a))).

Answer 5

Если развернуть мой комментарий, это займет около 50% времени для всех n в [100, 100007], где m = (117 | 1117):

Function facmod(n As Integer, m As Integer) As Integer
    Dim f As Integer = 1
    For i As Integer = 2 To n
        f = f * i
        If f > m Then
            f = f Mod m
        End If
    Next
    Return f
End Function

Answer 6

Я нашел эту следующую функцию в кворе:
С f (n, m) = n!mod m;

function f(n,m:int64):int64;
         begin
              if n = 1 then f:= 1
              else f:= ((n mod m)*(f(n-1,m) mod m)) mod m;
         end;

Вероятно, бить, используя длительный цикл и умножение большого числа, хранящегося в строке.Также это применимо к любому целому числу m.
Ссылка, где я нашел эту функцию: https://www.quora.com/How-do-you-calculate-n-mod-m-where-n-is-in-the-1000s-and-m-is-a-very-large-prime-number-eg-n-1000-m-10-9+7

Answer 7

Если n = (m - 1) для простого m, то на http://en.wikipedia.org/wiki/Wilson's_theorem n!mod m = (m - 1)

Также, как уже было указано, n!мод m = 0, если n> m

Answer 8

Предполагая, что оператор "mod" выбранной вами платформы достаточно быстр, вы ограничены прежде всего скоростью, с которой вы можете рассчитать n!, и пространством, которое у вас есть для его вычисления.

Тогда это по существу двухэтапная операция:

1. Рассчитайте n!(есть много быстрых алгоритмов, поэтому я не буду повторять их здесь)
2. Возьмите мод результата

Нет необходимости усложнять вещи, особенно если скорость критичнасоставная часть.В общем, выполняйте как можно меньше операций внутри цикла.

Если вам нужно повторно вычислять n! mod m, то вы можете запомнить значения, выходящие из функции, выполняющей вычисления.Как всегда, это классический компромисс между пространством и временем, но справочные таблицы очень быстрые .

Наконец, вы можете комбинировать запоминание с рекурсией (и батуты, если необходимо), чтобы получить вещи действительно быстро.