[CAS] Chinesischer Restsatz mit weiterem Modulo

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
[CAS] Chinesischer Restsatz mit weiterem Modulo
Ich habe den Chinesischen Restsatz als Computeralgorithmus und will nun Kongruenzen modulo einer weiteren Zahl berechnen. Ein Beispiel: die Reste sollen [1,2,3,4,5,6,7] sein, die dazugehörigen Moduln [2,3,5,7,11,13,17]. Mit dem unten stehenden Algorithmus kann ich als Lösung 299513 errechnen. Dieses Ergebnis unterziehe ich einer weiteren modulo-Division, in diesem Beispiel 127. Ergebnis ist 47, denn .

Im folgenden Python-Code wird die Liste mit den Resten als a und die Liste der Moduln als m an die Funktion chinese_remainder übergeben. Diese Listen sind beliebig erweiterbar und können u. U. tausende -garantiert paarweise koprim- Elemente enthalten.

Natürlich habe ich die Möglichkeit, die zusätzliche modulo-Division auf das Ergebnis anzuwenden. Bei entsprechend gearteten Liste a und m werden die Ergebnisse an sich aber schon unermesslich groß.

Kann mir jemand helfen, wie und wo ich die besagte modulo-Division in dem Quelltext einbaue, um diese riesigen Zahlen zu vermeiden?

Python:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
def extended_gcd(a, b):
    ''
    x, y = 0, 1
    last_x, last_y = 1, 0
    while b != 0:
        q, r = divmod(a, b)
        a, b = b, r
        x, last_x = last_x - q * x, x
        y, last_y = last_y - q * y, y
    return last_x, last_y

def chinese_remainder(a, m):
    ''
    a0, m0 = a[0], m[0]
    for i in range(1, len(a)):
        ai, mi = a[i], m[i]
        q = m0 * mi
        x, y = extended_gcd(m0, mi)
        r = (a0 + (ai - a0) * x * m0) % q
        a0, m0 = r, q
    return a0
HAL 9000 Auf diesen Beitrag antworten »
RE: [CAS] Chinesischer Restsatz mit weiterem Modulo
Zitat:
Original von Hosenschlange
Mit dem unten stehenden Algorithmus kann ich als Lösung 299513 errechnen. Dieses Ergebnis unterziehe ich einer weiteren modulo-Division, in diesem Beispiel 127. Ergebnis ist 47, denn .

Ich denke, das kann man so nicht stehen lassen: Die Lösung 299513 des Ausgangsproblems heißt ja in Wahrheit mit , d.h. repräsentiert durch die Zahlen mit ganzen Zahlen . Dementsprechend ergibt sich dann .

Man kann also allenfalls sagen, dass die kleinste positive (!) Lösung der Ausgangskongruenz dann die Eigenschaft hat, aber das trifft nicht auf alle Lösungen dieser Kongruenz zu. unglücklich



Zitat:
Original von Hosenschlange
Kann mir jemand helfen, wie und wo ich die besagte modulo-Division in dem Quelltext einbaue, um diese riesigen Zahlen zu vermeiden?

Wieso bist du dir so sicher, dass man diese riesigen Zahlen bei deinem Anliegen überhaupt vermeiden kann?

Vielleicht solltest du alternativ darüber nachdenken, mit Zahlenformaten zu arbeiten, die beliebige Genauigkeiten zulassen, wie sie z.B. die GMP-Library bietet (inwieweit die in Python einbindbar ist, entzieht sich meiner Kenntnis, ich hab die bisher nur mit C/C++ genutzt). "Beliebig" heißt natürlich, soweit das Speicherplatz und vor allem Rechenzeit zulassen. Augenzwinkern
Hosenschlange Auf diesen Beitrag antworten »

Danke, HAL, für die Berichtigung Freude

Meine selbstgestellte Frage ist, wie beispielsweise die letzten 9 Ziffern des Ergebnisses lauten, wenn man den Chinesischen-Restsatz-Algorithmus (CRA) mit einer Liste von 5000 Werte füttert.

Ein Beispiel (in dem auch die paarweise Teilerfremdheit gewahrt wird): als Reste setzt man eine Liste aus den Zahlen von 1 bis 5000 ein, als Moduln eine Liste aus den ersten 5000 Primzahlen, jeweils aufsteigend geordnet. Das Ergebnis (kleinste positive Lösung) hat dann eine Länge von 20974 Ziffern. Die letzten 9 Ziffern davon lauten 533085893.

Es wäre hierbei von Vorteil, die Zahlen kleiner zu halten, ohne das Ergebnis zu verfälschen. Das verkürzt auch die Rechenzeit, weil nicht immer riesige Datenmengen im Speicher verschoben und bearbeitet werden müssen.

Ich schätze, ich sollte grundlegend erstmal fragen, ob eine solche Möglichkeit überhaupt besteht, den CRA insoweit zu ändern, dass man nicht erst das Ergebnis ausrechnet, um dann erst das "finale" Modulo anzuwenden.
HAL 9000 Auf diesen Beitrag antworten »

Ich weiß nicht, was dir hier an Vereinfachungen/Reduktionen vorschwebt:

Wenn es um denselben Modul geht, ja, da ist einiges an Reduktionen der Zahlen möglich, hauptsächlich basierend auf



u.ä. Aber es gilt eben i.a. nicht



oder was immer du dir sonst noch hier vorstellen magst.
Hosenschlange Auf diesen Beitrag antworten »

Wenn ich es richtig verstehe, ist es nicht möglich, im Quelltext weitere Modulo-Operationen zu implementieren, um die Werte in der Berechnung an sich kleiner zu halten und dadurch keine multi-precision Bibliothek nutzen zu müssen?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »