Ich muss in der Lage sein, (a ^ b)% c für sehr große Werte von a und b zu berechnen (die einzeln Schubgrenzen sind und Überlauffehler verursachen, wenn Sie versuchen, a ^ b zu berechnen). Für klein genug Zahlen funktioniert die Verwendung der Identität (a ^ b)% c = (a% c) ^ b% c, aber wenn c zu groß ist, hilft das nicht wirklich. Ich habe eine Schleife geschrieben, um die Mod-Operation einzeln manuell auszuführen:
%Vor%aber das dauert sehr lange. Gibt es einen einfachen und schnellen Weg, um diese Operation auszuführen, ohne tatsächlich die Macht von b UND ohne zeitaufwendige Schleifen zu nehmen? Wenn alles andere fehlschlägt, kann ich ein Bool-Array erstellen, um einen riesigen Datentyp darzustellen und herauszufinden, wie man das mit bitweisen Operatoren macht, aber es muss einen besseren Weg geben.
Ich denke, Sie suchen: Ссылка oder der einfachere Weg basierend auf Modular Exponentiation (aus Wikipedia)
%Vor%Fast Modular Exponentiation (ich glaube, so heißt es) könnte funktionieren.
%Vor%Nun, wie Sie das mit Datentypen machen werden, weiß ich nicht. Solange Ihr Datentyp c ^ 2 unterstützt, denke ich, dass es Ihnen gut geht.
Wenn Sie Strings verwenden, erstellen Sie einfach String-Versionen von addieren, subtrahieren und multiplizieren (nicht zu schwer). Diese Methode sollte schnell genug sein. (und Sie können Schritt 1 mit einem Mod c beginnen, so dass a nie größer als c ist).
EDIT: Oh, schau mal, eine Wiki-Seite auf Modular Exponentiation .
Ich würde empfehlen, die Decimal-Dokumentation zu überprüfen und zu überprüfen, ob sie Ihren Anforderungen entspricht, da es sich um einen eingebauten Typ handelt und Sie den Mod-Operator verwenden können. Wenn nicht, dann brauchst du eine beliebige Präzisions-Bibliothek wie Java's Bignum.
Sie können factoring 'a' in ausreichend kleine Zahlen eingeben.
Wenn die Faktoren von 'a' 'x', 'y' und 'z' sind, dann
a ^ b = (x ^ b) (y ^ b) (z ^ b).
Dann können Sie Ihre Identität verwenden: (a ^ b)% c = (a% c) ^ b% c
Es scheint mir, als gäbe es eine Art Beziehung zwischen Macht und Mod. Macht ist nur wiederholte Multiplikation und Mod ist mit Division verbunden. Wir wissen, dass Multiplikation und Division Inverse sind, daher würde ich annehmen, dass zwischen dieser Beziehung und der Mod eine Korrelation besteht.
Nehmen Sie zum Beispiel Potenzen von 5:
%Vor%Das Muster ist klar, dass 5 ^ b% 4 = 1 für alle Werte von b gilt.
In dieser Situation ist es weniger klar:
%Vor%Aber es gibt immer noch ein Muster.
Wenn du die Mathematik hinter den Mustern ausarbeiten könntest, wäre ich nicht überrascht, wenn du den Wert des Mods herausfinden könntest, ohne die eigentliche Kraft zu nutzen.
Du könntest das versuchen:
C #: Ausführen einer Modulo (mod) Operation für eine sehr große Anzahl (& gt; Int64.MaxValue)
Ссылка
Kurz vor dem Schreiben Ihrer eigenen schnellen modularen Potenzierung , die einfachste Idee, die ich mir vorstellen kann, ist die Verwendung der F # BigInt-Typ: Microsoft.FSharp.Math.Types.BigInt , der Operationen mit beliebig großem Maßstab unterstützt - einschließlich Potenzierung und modularer Arithmetik.
Es ist ein integrierter Typ, der mit der nächsten Version Teil des vollständigen .NET-Frameworks sein wird. Sie müssen F # nicht verwenden, um BitInt zu verwenden - Sie können es direkt in C # verwenden.
Können Sie a, b oder c faktorisieren? Hat C einen bekannten Bereich?
Dies sind 32-Bit-Ganzzahlen! Überprüfen Sie diese Website
Zum Beispiel erhalten Sie hier die Mod von n% d mit d 1 & gt; s (1,2,4,8, ...)
%Vor%Es gibt Code für n% d, wobei d 1 ist & gt; & gt; s - 1 (1, 3, 7, 15, 31, ...)
Das wird nur wirklich helfen, wenn c wie gesagt klein ist.
Sieht wie Hausaufgaben in der Kryptographie aus.
Hinweis: Fermat's kleiner Satz .