Einen ganzzahligen Wraparound rückgängig machen

Ich bin vor einigen Jahren auf ein interessantes theoretisches Problem gestoßen. Ich habe nie eine Lösung gefunden, und sie verfolgt mich weiter, wenn ich schlafe.

Angenommen, Sie haben eine (C #) - Anwendung, die eine Zahl in einem int enthält, genannt x. (Der Wert von x ist nicht festgelegt). Wenn das Programm ausgeführt wird, wird x mit 33 multipliziert und dann in eine Datei geschrieben.

Der grundlegende Quellcode sieht folgendermaßen aus:

int x = getSomeInt();
x = x * 33;
file.WriteLine(x); // Writes x to the file in decimal format

Einige Jahre später stellen Sie fest, dass Sie die ursprünglichen Werte von X zurück benötigen. Einige Berechnungen sind einfach: Teilen Sie einfach die Zahl in der Datei durch 33. In anderen Fällen ist X jedoch groß genug, dass die Multiplikation einen Ganzzahlüberlauf verursacht. Gemäß den Dokumenten schneidet C # die höherwertigen Bits ab, bis die Zahl kleiner als ist int.MaxValue. Ist es in diesem Fall möglich, entweder

1. Stellen Sie X selbst wieder her oder
2. Eine Liste der möglichen Werte für X wiederherstellen?

Es scheint mir (obwohl meine Logik sicherlich fehlerhaft sein könnte), dass einer oder beide möglich sein sollten, da der einfachere Fall der Addition funktioniert (im Wesentlichen, wenn Sie 10 zu X addieren und es umschließt, können Sie 10 subtrahieren und wieder mit X aufwickeln ) und Multiplikation wird einfach Addition wiederholt. Ebenfalls hilfreich (glaube ich) ist die Tatsache, dass X in allen Fällen mit dem gleichen Wert multipliziert wird - eine Konstante von 33.

Das tanzt seit Jahren in seltsamen Momenten um meinen Schädel. Es wird mir einfallen, ich werde einige Zeit damit verbringen, darüber nachzudenken, und dann werde ich es für ein paar Monate vergessen. Ich bin es leid, dieses Problem zu verfolgen! Kann mir jemand einen Einblick geben?

(Randnotiz: Ich weiß wirklich nicht, wie ich diesen taggen soll. Vorschläge erwünscht.)

Bearbeiten: Lassen Sie mich klarstellen, dass ich, wenn ich eine Liste der möglichen Werte für X erhalten kann, andere Tests durchführen kann, um sie auf den ursprünglichen Wert einzugrenzen.

Mit 1041204193 multiplizieren.

Wenn das Ergebnis einer Multiplikation nicht in ein int passt, erhalten Sie nicht das genaue Ergebnis, sondern eine Zahl, die dem genauen Ergebnis modulo 2 ** 32 entspricht . Das bedeutet , dass , wenn die Zahl , die Sie multipliziert war coprime zu 2 ** 32 (das bedeutet nur , dass es seltsam sein), können Sie vermehren sich durch seine multiplikative Inverse Ihre Nummer zurück zu bekommen. Wolfram Alpha oder der erweiterte euklidische Algorithmus können uns sagen, dass 33 das multiplikative inverse Modulo 2 ** 32 1041204193 ist. Multiplizieren Sie also mit 1041204193, und Sie haben das ursprüngliche x zurück.

Wenn wir zum Beispiel 60 statt 33 hätten, könnten wir die ursprüngliche Nummer nicht wiederherstellen, aber wir könnten sie auf einige Möglichkeiten eingrenzen. Indem wir 60 in 4 * 15 zerlegen, die Umkehrung von 15 mod 2 ** 32 berechnen und mit dieser multiplizieren, können wir das 4-fache der ursprünglichen Zahl zurückgewinnen, wobei wir nur 2 höherwertige Bits der Zahl brutaler Gewalt überlassen. Wolfram Alpha gibt uns 4008636143 für das Inverse, das nicht in ein Int passt, aber das ist okay. Wir finden einfach eine Zahl, die 4008636143 Mod 2 ** 32 entspricht, oder erzwingen sie in jedem Fall eine Ganzzahl, damit der Compiler dies für uns ausführt, und das Ergebnis ist auch eine Umkehrung von 15 Mod 2 ** 32. ( Wir erhalten -286331153. )

Dies ist möglicherweise besser als eine Frage an Math (sic) SE geeignet. Sie beschäftigen sich im Grunde genommen mit modularer Arithmetik, da das Löschen der am weitesten links stehenden Bits dasselbe ist.

Ich bin nicht so gut in Mathe wie die Leute, die bei Math (sic) SE sind, aber ich werde versuchen zu antworten.

Was wir hier haben, ist, dass die Zahl mit 33 (3 * 11) multipliziert wird und ihr einziger gemeinsamer Nenner mit Ihrem Mod 1 ist. Dies liegt daran, dass die Bits im Computer per Definition Zweierpotenzen sind und Ihr Mod somit eine Zweierpotenz.

Sie können die Tabelle erstellen, in der Sie für jeden vorherigen Wert den folgenden Wert berechnen. Und die Frage wird, ob die folgenden Zahlen nur einer vorherigen entsprechen.

Wenn es nicht 33 wäre, sondern eine Primzahl oder eine Potenz einer Primzahl, würde die Antwort meiner Meinung nach ja lauten, aber in diesem Fall… fragen Sie auf Math.SE!

Programmatischer Test

Dies ist in C ++, weil ich C # nicht kenne, aber das Konzept noch gilt. Dies scheint zu zeigen, dass Sie:

#include <iostream>
#include <map>

int main(void)
{
    unsigned short count = 0;
    unsigned short x = 0;
    std::map<unsigned short, unsigned short> nextprev;

    nextprev[0] = 0;
    while(++x) nextprev[x] = 0;

    unsigned short nextX;
    while(++x)
    {
            nextX = x*33;
            if(nextprev[nextX])
            {
                    std::cout << nextprev[nextX] << "*33==" << nextX << " && " << x << "*33==" << nextX << std::endl;
                    ++count;
            }
            else
            {
                    nextprev[nextX] = x;
                    //std::cout << x << "*33==" << nextX << std::endl;
            }
    }

    std::cout << count << " collisions found" << std::endl;

    return 0;
}

Nachdem Sie eine solche Karte ausgefüllt haben, können Sie immer das vorherige X abrufen, wenn Sie das nächste kennen. Es gibt immer nur einen einzigen Wert.

Ein Weg, es zu bekommen, ist brachiale Gewalt anzuwenden. Tut mir leid, ich kenne C # nicht, aber das Folgende ist ein C-ähnlicher Pseudocode, um die Lösung zu veranschaulichen:

for (x=0; x<=INT_MAX; x++) {
    if (x*33 == test_value) {
        printf("%d\n", x);
    }
}

Was Sie technisch gesehen brauchen, ist x*33%(INT_MAX+1) == test_value, dass ein Ganzzahlüberlauf die %Operation automatisch für Sie ausführt, es sei denn, Ihre Sprache verwendet Ganzzahlen mit willkürlicher Genauigkeit (bigint).

Dies gibt Ihnen eine Reihe von Nummern, die möglicherweise die ursprüngliche Nummer waren. Die erste gedruckte Zahl würde die Zahl sein, die eine Runde Überlauf erzeugen würde. Die zweite Zahl würde die Zahl sein, die zwei Runden Überlauf erzeugen würde. Und so weiter..

Wenn Sie also wissen, dass Ihre Daten besser sind, können Sie besser raten. Zum Beispiel neigen gewöhnliche Uhrberechnungen (Überlauf alle 12 Uhr) dazu, die erste Zahl wahrscheinlicher zu machen, da die meisten Menschen an Dingen interessiert sind, die heute passiert sind.

Sie können den SMT-Solver Z3 bitten, Ihnen eine zufriedenstellende Zuordnung für die Formel zu geben x * 33 = valueFromFile. Es kehrt diese Gleichung für Sie um und gibt Ihnen alle möglichen Werte von x. Z3 unterstützt die exakte Bitvektorarithmetik einschließlich Multiplikation.

    public static void InvertMultiplication()
    {
        int multiplicationResult = new Random().Next();
        int knownFactor = 33;

        using (var context = new Context(new Dictionary<string, string>() { { "MODEL", "true" } }))
        {
            uint bitvectorSize = 32;
            var xExpr = context.MkBVConst("x", bitvectorSize);
            var yExpr = context.MkBVConst("y", bitvectorSize);
            var mulExpr = context.MkBVMul(xExpr, yExpr);
            var eqResultExpr = context.MkEq(mulExpr, context.MkBV(multiplicationResult, bitvectorSize));
            var eqXExpr = context.MkEq(xExpr, context.MkBV(knownFactor, bitvectorSize));

            var solver = context.MkSimpleSolver();
            solver.Assert(eqResultExpr);
            solver.Assert(eqXExpr);

            var status = solver.Check();
            Console.WriteLine(status);
            if (status == Status.SATISFIABLE)
            {
                Console.WriteLine(solver.Model);
                Console.WriteLine("{0} * {1} = {2}", solver.Model.Eval(xExpr), solver.Model.Eval(yExpr), solver.Model.Eval(mulExpr));
            }
        }
    }

Die Ausgabe sieht folgendermaßen aus:

SATISFIABLE
(define-fun y () (_ BitVec 32)
  #xa33fec22)
(define-fun x () (_ BitVec 32)
  #x00000021)
33 * 2738875426 = 188575842

Wenn Sie dieses Ergebnis rückgängig machen, erhalten Sie eine endliche Anzahl von Zahlen ungleich Null (normalerweise unendlich, aber inteine endliche Teilmenge von ℤ). Wenn dies akzeptabel ist, generieren Sie einfach die Zahlen (siehe andere Antworten).

Andernfalls müssen Sie eine Liste der Historie (mit endlicher oder unendlicher Länge) der Historie der Variablen führen.

Wie immer gibt es eine Lösung von einem Wissenschaftler und eine Lösung von einem Ingenieur.

Oben finden Sie eine sehr gute Lösung eines Wissenschaftlers, die immer funktioniert, bei der Sie jedoch die „multiplikative Inverse“ berechnen müssen.

Hier ist eine schnelle Lösung von engineer, die Sie nicht zwingen wird, alle möglichen ganzen Zahlen auszuprobieren.

val multiplier = 33 //used with 0x23456789
val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL

val overflowBit = 0x100000000L
for(test <- 0 until multiplier) {
  if((problemAsLong + overflowBit * test) % multiplier == 0) {
    val originalLong = (problemAsLong + overflowBit * test) / multiplier
    val original = originalLong.toInt
    println(s"$original (test = $test)")
  }
}

Was sind die Ideen?

1. Wir haben einen Überlauf, verwenden wir also größere Typen, um wiederherzustellen ( Int -> Long)
2. Wir haben wahrscheinlich ein paar Teile durch Überlauf verloren, stellen wir sie wieder her
3. Der Überlauf war nicht mehr als Int.MaxValue * multiplier

Der vollständige ausführbare Code befindet sich unter http://ideone.com/zVMbGV

Einzelheiten:

• val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
  Hier konvertieren wir unsere gespeicherte Nummer in Long, aber da Int und Long signiert sind, müssen wir es richtig machen.
  Also begrenzen wir die Anzahl mit bitweisem UND mit Bits von Int.
• val overflowBit = 0x100000000L
  Dieses Bit oder seine Multiplikation könnte durch anfängliche Multiplikation verloren gehen.
  Es ist ein erstes Stück außerhalb des Int-Bereichs.
• for(test <- 0 until multiplier)
  Gemäß der 3. Idee ist der maximale Überlauf durch den Multiplikator begrenzt, versuchen Sie also nicht mehr, als wir wirklich brauchen.
• if((problemAsLong + overflowBit * test) % multiplier == 0)
  Prüfen Sie, ob wir durch Hinzufügen eines möglicherweise verlorenen Überlaufs zu einer Lösung kommen
• val original = originalLong.toInt
  Das ursprüngliche Problem lag im Int-Bereich. Kehren wir also zurück. Andernfalls könnten wir falsch Zahlen wiederherstellen, die negativ waren.
• println(s"$original (test = $test)")
  Unterbrechen Sie nicht nach der ersten Lösung, da es andere mögliche Lösungen geben kann.

PS: 3. Idee ist nicht strikt korrekt, aber so belassen, dass sie verständlich ist.
Int.MaxValueist 0x7FFFFFFF, aber maximaler Überlauf ist 0xFFFFFFFF * multiplier.
Der richtige Text wäre also "Der Überlauf war nicht mehr als -1 * multiplier".
Das ist richtig, aber nicht jeder wird es verstehen.