Szybki algorytm/formuła dla zakresu szeregowego modulo liczb pierwszych co-pr.

Question

W moim projekcie jest jedna część problemu. Ale aby uprościć, tutaj problem jest formułowany. Istnieją dwie dodatnie liczby całkowite "co-prime": a i b, gdzie a < b. Wyświetlane są wielokrotności a od 1 do b-1, po których następuje operacja modulowania przez b.

a mod b, 2*a mod b, 3*a mod b, ... (b-1)*a mod b

Teraz jest inna liczba całkowita, powiedzmy n (1 <= n < b). Przez pierwsze numery n na liście musimy ustalić, ile liczb jest mniejszych niż, powiedzmy m ((). Można tego dokonać metodą brutalnej siły, dając w ten sposób O(n).

Przykład:

a=6, b=13, n=8, m=6

lista jest:

6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7

to permutacji o numerach od 1 do 12, ponieważ operacja modulo z dwoma współpracowników bodźce wytwarza permutacja liczb, jeśli dołączymy inny numer, czyli 0. Jeśli weźmiemy a= 2, b=13, wtedy lista byłaby 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11, która daje wzór. Natomiast jeśli a i b są bardzo duże (w moim projekcie mogą one wzrosnąć nawet do 10^20), to nie mam pojęcia, jak wydedukować wzorzec o tak dużej liczbie.

Teraz wracając do przykładu, bierzemy pierwsze n = 8 numerów z listy, co daje

6, 12, 5, 11, 4, 10, 3, 9

Zastosowanie operatora less-than z m = 6, daje łączną liczbę numerów mniej niż m samopoczucia 3, jak wyjaśniono poniżej w wykazie

0, 0, 1, 0, 1, 0, 1, 0

gdzie 0 oznacza nie mniejszy niż m, a 1 oznacza mniej niż m.

Ponieważ algorytm powyżej jest O(n), który jest nie do zaakceptowania dla zakresu [0, 10^20], dzięki czemu społeczność dać wskazówkę/clue/końcówki, aby umożliwić mi się osiągnąć O(log n) rozwiązanie, albo jeszcze lepiej O(1) rozwiązanie?

Answer 1

(Uwaga: trochę się pokręciłem, ponieważ zakres mnożników nie jest [0, n], więc dostosowałem go. Łatwo to zrekompensować.)

Zamierzam szkicować, z przetestowanym kodem Pythona, implementację, która działa w czasie O (log max {a, b}). Po pierwsze, oto kilka funkcji narzędziowych i naiwna implementacja.

from fractions import gcd 
from random import randrange 


def coprime(a, b): 
    return gcd(a, b) == 1 


def floordiv(a, b): 
    return a // b 


def ceildiv(a, b): 
    return floordiv(a + b - 1, b) 


def count1(a, b, n, m): 
    assert 1 <= a < b 
    assert coprime(a, b) 
    assert 0 <= n < b + 1 
    assert 0 <= m < b + 1 
    return sum(k * a % b < m for k in range(n)) 

Jak możemy przyspieszyć?Pierwszą poprawą jest podzielenie mnożników na rozłączne zakresy tak, że w zakresie, odpowiednie wielokrotności a są między dwoma wielokrotnościami b. Znając najniższe i najwyższe wartości, możemy liczyć poprzez podział na suficie liczbę mnożników mniejszą niż m.

def count2(a, b, n, m): 
    assert 1 <= a < b 
    assert coprime(a, b) 
    assert 0 <= n < b + 1 
    assert 0 <= m < b + 1 
    count = 0 
    first = 0 
    while 0 < n: 
     count += min(ceildiv(m - first, a), n) 
     k = ceildiv(b - first, a) 
     n -= k 
     first = first + k * a - b 
    return count 

To nie jest wystarczająco szybkie. Drugą poprawą jest zastąpienie większości pętli while wywołaniem rekursywnym. W poniższym kodzie j jest liczbą iteracji, które są "kompletne" w tym sensie, że istnieje zawijanie. term3 konta dla pozostałej iteracji, używając logiki podobnej do count2.

Każda z kompletnych iteracji zawiera w sobie pozostałości o wartości poniżej progu m. To, czy otrzymamy + 1 zależy od tego, co jest first dla tej iteracji. first rozpoczyna się od 0 i zmienia przez a - (b % a) modulo a na każdej iteracji przez pętlę while. Otrzymujemy wartość + 1, gdy jest ona poniżej pewnego progu, a ta liczba jest obliczana za pomocą wywołania rekursywnego.

def count3(a, b, n, m): 
    assert 1 <= a < b 
    assert coprime(a, b) 
    assert 0 <= n < b + 1 
    assert 0 <= m < b + 1 
    if 1 == a: 
     return min(n, m) 
    j = floordiv(n * a, b) 
    term1 = j * floordiv(m, a) 
    term2 = count3(a - b % a, a, j, m % a) 
    last = n * a % b 
    first = last % a 
    term3 = min(ceildiv(m - first, a), (last - first) // a) 
    return term1 + term2 + term3 

Czas pracy można analizować analogicznie do algorytmu ECD Euclidean.

Oto kod testowy, który ma potwierdzić moje twierdzenia o poprawności. Pamiętaj o usunięciu asercji przed testowaniem wydajności.

def test(p, f1, f2): 
    assert 3 <= p 
    for t in range(100): 
     while True: 
      b = randrange(2, p) 
      a = randrange(1, b) 
      if coprime(a, b): 
       break 
     for n in range(b + 1): 
      for m in range(b + 1): 
       args = (a, b, n, m) 
       print(args) 
       assert f1(*args) == f2(*args) 


if __name__ == '__main__': 
    test(25, count1, count2) 
    test(25, count1, count3)