„Cofanie” zawijania liczby całkowitej

Kilka lat temu natrafiłem na ciekawy problem teoretyczny. Nigdy nie znalazłem rozwiązania i nadal mnie prześladuje, kiedy śpię.

Załóżmy, że masz aplikację (C #), która zawiera pewną liczbę w int, o nazwie x. (Wartość x nie jest stała). Po uruchomieniu programu x jest mnożone przez 33, a następnie zapisywane w pliku.

Podstawowy kod źródłowy wygląda następująco:

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

Kilka lat później odkrywasz, że potrzebujesz oryginalnych wartości X. Niektóre obliczenia są proste: wystarczy podzielić liczbę w pliku przez 33. Jednak w innych przypadkach X jest wystarczająco duży, aby zwielokrotnienie spowodowało przepełnienie liczb całkowitych. Zgodnie z dokumentacją , C # obetnie bity wysokiego rzędu, aż liczba będzie mniejsza niż int.MaxValue. Czy w tym przypadku można:

1. Odzyskaj sam X lub
2. Odzyskać listę możliwych wartości dla X?

Wydaje mi się (choć moja logika mogłaby być z pewnością błędna), że jeden lub oba powinny być możliwe, ponieważ prostszy przypadek dodawania działa (Zasadniczo, jeśli dodasz 10 do X i zostanie on zawinięty, możesz odjąć 10 i skończyć z X ponownie ), a mnożenie jest po prostu powtarzanym dodawaniem. Pomagam również (jak sądzę) fakt, że X jest mnożony przez tę samą wartość we wszystkich przypadkach - stałą 33.

Od lat tańczy to wokół mojej czaszki. Przychodzi mi do głowy, poświęcę trochę czasu na przemyślenie tego, a potem zapomnę o tym na kilka miesięcy. Mam dość pogoni za tym problemem! Czy ktoś może zaoferować wgląd?

(Uwaga dodatkowa: Naprawdę nie wiem, jak oznaczyć ten tag. Sugestie mile widziane.)

Edycja: Pozwól mi wyjaśnić, że jeśli mogę uzyskać listę możliwych wartości dla X, są inne testy, które mogę zrobić, aby pomóc mi zawęzić ją do pierwotnej wartości.

Pomnóż przez 1041204193.

Kiedy wynik mnożenia nie pasuje do int, nie otrzymasz dokładnego wyniku, ale otrzymasz liczbę równoważną dokładnemu wynikowi modulo 2 ** 32 . Oznacza to, że jeśli pomnożona liczba była coprime do 2 ** 32 (co oznacza, że ​​musi być nieparzysta), możesz pomnożyć przez jej multiplikatywną odwrotność, aby odzyskać swój numer. Wolfram Alpha lub rozszerzony algorytm euklidesowy mogą nam powiedzieć, że multiplikatywny odwrotny moduł 33 ** 32 to 1041204193. Zatem pomnóż przez 1041204193, a otrzymasz oryginalne x.

Gdybyśmy mieli, powiedzmy, 60 zamiast 33, nie bylibyśmy w stanie odzyskać oryginalnej liczby, ale moglibyśmy zawęzić ją do kilku możliwości. Łącząc 60 w 4 * 15, obliczając odwrotność 15 mod 2 ** 32 i mnożąc przez to, możemy odzyskać 4-krotność oryginalnej liczby, pozostawiając tylko 2 bity wysokiego rzędu liczby brutalnej sile. Wolfram Alpha daje nam 4008636143 na odwrotność, co nie pasuje do int, ale to jest w porządku. Po prostu znajdujemy liczbę równoważną 4008636143 mod 2 ** 32 lub w każdym razie zmuszamy ją do int, aby kompilator zrobił to za nas, a wynikiem będzie również odwrotność 15 mod 2 ** 32. ( Otrzymujemy -286331153. )

Może to lepiej nadaje się jako pytanie do Math (sic) SE. Zasadniczo masz do czynienia z modułową arytmetyką, ponieważ upuszczanie najbardziej lewych bitów jest tym samym.

Nie jestem tak dobry w matematyce jak ludzie, którzy są na Math (sic) SE, ale spróbuję odpowiedzieć.

Mamy tutaj mnożoną liczbę przez 33 (3 * 11), a jej jedynym wspólnym mianownikiem dla twojego modu jest 1. To dlatego, że z definicji bity w komputerze są potęgami dwóch, a zatem twój mod jest trochę mocy dwóch.

Będziesz mógł zbudować tabelę, w której dla każdej poprzedniej wartości obliczasz następującą wartość. I pojawia się pytanie, czy następujące liczby odpowiadają tylko jednej poprzedniej.

Gdyby nie było 33, ale liczba pierwsza lub jakaś moc liczby pierwszej, wierzę, że odpowiedź byłaby tak, ale w tym przypadku ... zapytaj na Math.SE!

Test programowy

Jest to w C ++, ponieważ nie znam C #, ale koncepcja nadal obowiązuje. Wygląda na to, że możesz:

#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;
}

Po wypełnieniu takiej mapy zawsze będziesz w stanie zdobyć poprzedni X, jeśli znasz następny. Przez cały czas jest tylko jedna wartość.

Jednym ze sposobów na uzyskanie tego jest użycie brutalnej siły. Niestety nie znam C #, ale poniższy przykład to pseudo-kod podobny do c, ilustrujący rozwiązanie:

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

Technicznie rzecz biorąc, potrzebujesz x*33%(INT_MAX+1) == test_valuetylko przepełnienia liczb całkowitych, które automatycznie wykonają %operację, chyba że Twój język używa liczb całkowitych o dowolnej precyzji (bigint).

To daje ci szereg liczb, które mogły być oryginalnymi numerami. Pierwsza wydrukowana liczba byłaby liczbą, która wygenerowałaby jedną rundę przepełnienia. Druga liczba to liczba, która wygeneruje dwie rundy przepełnienia. I tak dalej..

Jeśli więc znasz swoje dane, możesz lepiej zgadywać. Na przykład, wspólne matematyki zegarowe (przepełnienie co 12) zwiększają prawdopodobieństwo, że pierwsza liczba jest bardziej prawdopodobna, ponieważ większość ludzi interesuje się tym, co się dzisiaj wydarzyło.

Możesz solver SMT Z3 poprosić go o zadowalające przypisanie formuły x * 33 = valueFromFile. Odwróci to równanie i poda wszystkie możliwe wartości x. Z3 obsługuje dokładną arytmetykę bitvectorów, w tym mnożenie.

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

Dane wyjściowe wyglądają tak:

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

Cofnięcie tego wyniku da ci niezerową skończoną liczbę liczb (zwykle nieskończoną, ale intjest skończonym podzbiorem ℤ). Jeśli jest to do zaakceptowania, po prostu wygeneruj liczby (zobacz inne odpowiedzi).

W przeciwnym razie musisz zachować listę historii (o skończonej lub nieskończonej długości) historii zmiennej.

Jak zawsze istnieje rozwiązanie od naukowca i rozwiązanie od inżyniera.

Powyżej znajdziesz bardzo dobre rozwiązanie od naukowca, który zawsze działa, ale wymaga obliczenia „odwrotności multiplikatywnej”.

Oto szybkie rozwiązanie od inżyniera, które nie zmusi cię do wypróbowania wszystkich możliwych liczb całkowitych.

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

Jakie są pomysły?

1. Mamy przepełnienie, więc użyjmy większych typów do odzyskania ( Int -> Long)
2. Prawdopodobnie straciliśmy trochę bitów z powodu przepełnienia, odzyskajmy je
3. Przelew był nie większy niż Int.MaxValue * multiplier

Pełny kod wykonywalny znajduje się na stronie http://ideone.com/zVMbGV

Detale:

• val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
  Tutaj konwertujemy nasz przechowywany numer na Long, ale ponieważ Int i Long są podpisane, musimy to zrobić poprawnie.
  Więc ograniczamy liczbę za pomocą bitowego AND z bitami Int.
• val overflowBit = 0x100000000L
  Ten bit lub jego mnożenie może zostać utracony przez wstępne pomnożenie.
  Jest to pierwszy kawałek poza zakresem Int.
• for(test <- 0 until multiplier)
  Zgodnie z 3. pomysłem maksymalne przepełnienie jest ograniczone przez mnożnik, więc nie próbuj więcej, niż naprawdę potrzebujemy.
• if((problemAsLong + overflowBit * test) % multiplier == 0)
  Sprawdź, czy dodając potencjalnie utracone przepełnienie dochodzimy do rozwiązania
• val original = originalLong.toInt
  Pierwotny problem był w zakresie Int, więc wróćmy do niego. W przeciwnym razie moglibyśmy nieprawidłowo odzyskać liczby, które były ujemne.
• println(s"$original (test = $test)")
  Nie psuj się po pierwszym rozwiązaniu, ponieważ mogą istnieć inne możliwe rozwiązania.

PS: Trzeci pomysł nie jest ściśle poprawny, ale pozostawiony, aby był zrozumiały.
Int.MaxValuejest 0x7FFFFFFF, ale maksymalne przepełnienie wynosi 0xFFFFFFFF * multiplier.
Tak więc poprawny tekst brzmiałby „Przepełnienie nie było więcej niż -1 * multiplier”.
To prawda, ale nie wszyscy to zrozumieją.