Schneller Algorithmus/Formel für den seriellen Bereich von Modulo von Co-Primzahlen

Question

In meinem Projekt ist ein Teil des Problems da. Aber zur Vereinfachung wird hier das Problem formuliert. Es gibt zwei positive Co-Primzahl-Ganzzahlen: a und b, wobei a < b. Ein Vielfaches von a von 1 bis b-1 ist aufgeführt, gefolgt von einer Moduloperation durch b.

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

Nun gibt es eine weitere ganze Zahl ist, sagen n (1 <= n < b). Durch die ersten n Zahlen in der Liste müssen wir herausfinden, wie viele Zahlen kleiner sind als, sagen m (1 <= m < b). Dies kann in Brute-Force-Ansatz erfolgen, wodurch sich ein O(n) ergibt.

Ein Beispiel:

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

Liste ist:

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

Dies ist eine Permutation der Zahlen von 1 bis 12 ist, weil Modulus Betrieb von irgendwelchen zwei co-Primzahlen a produziert Permutation von Zahlen, wenn wir eine andere Zahl einschließen, also 0. Wenn wir a= 2, b=13 nehmen, dann wäre die Liste 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11, was ein Muster ergibt. Während, wenn a und b sind sehr groß (in meinem Projekt können sie bis zu 10^20 gehen), dann habe ich keine Ahnung, wie ein Muster von so großen Zahlen abzuleiten.

Nun zurück zum Beispiel bekommen, nehmen wir die ersten n = 8 Nummern aus der Liste, die

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

Anwendung des less-than Operator mit m = 6 gibt, gibt es die Gesamtzahl der Zahlen kleiner als m Wesen 3 erläutert, wie in der unten stehenden Liste

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

wobei 0 bedeutet nicht weniger als m und 1 bezieht sich auf weniger als m.

Da oben ist der Algorithmus ein O(n), die für den Bereich von [0, 10^20] nicht akzeptabel ist, so kann die Gemeinschaft einen Hinweis/Hinweis/Tipp geben mir zu ermöglichen, eine O(log n) Lösung zu erreichen, oder noch besser O(1) Lösung?

Answer 1

(Warnung: Ich habe ein wenig zucken über den Bereich der Multiplikatoren nicht [0, n), also habe ich es angepasst. Es ist leicht genug zu kompensieren.)

Ich werde skizzieren, mit getestetem Python-Code, eine Implementierung, die in der Zeit läuft O (Protokoll max {a, b}). Zunächst einige nützliche Funktionen und eine naive Implementierung.

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

Nun, wie können wir das beschleunigen?Die erste Verbesserung besteht darin, die Multiplizierer in disjunkte Bereiche aufzuteilen, so dass innerhalb eines Bereichs die entsprechenden Vielfachen von a zwischen zwei Vielfachen von b liegen. Wenn wir die niedrigsten und höchsten Werte kennen, können wir über eine Deckenunterteilung die Anzahl der Vielfachen unter m zählen.

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 

Dies ist nicht schnell genug. Die zweite Verbesserung besteht darin, den größten Teil der while-Schleife durch einen rekursiven Aufruf zu ersetzen. Im folgenden Code ist j die Anzahl der Iterationen, die in dem Sinne "abgeschlossen" sind, dass es einen Umbruch gibt. term3 berücksichtigt die verbleibende Iteration mit einer Logik, die count2 ähnelt.

Jede der vollständigen Iterationen trägt floor(m/a) oder floor(m/a) + 1 Rückstände unter dem Schwellenwert m. Ob wir die + 1 bekommen, hängt davon ab, was first für diese Iteration ist. first beginnt um 0 und ändert sich um a - (b % a) modulo a bei jeder Iteration durch die While-Schleife. Wir erhalten die + 1 immer, wenn es unter einem Schwellenwert ist, und diese Anzahl ist über einen rekursiven Aufruf berechenbar.

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 

Die Laufzeit kann analog zum euklidischen GCD-Algorithmus analysiert werden.

Hier ist ein Testcode, um Beweise für meine Behauptungen der Richtigkeit zu beweisen. Denken Sie daran, die Assertionen vor dem Testen der Leistung zu löschen.

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)