Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I ran into an interesting theoretical problem a number of years ago. I never found a solution, and it continues to haunt me when I sleep.

Suppose you have a (C#) application that holds some number in an int, called x. (The value of x is not fixed). When the program is run, x is multiplied by 33 and then written to a file.

Basic source code looks like this:

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

Some years later, you discover that you need the original values of X back. Some calculations are simple: Just divide the number in the file by 33. However, in other cases, X is large enough that the multiplication caused an integer overflow. According to the docs, C# will truncate the high-order bits until the number is less than int.MaxValue. Is it possible, in this case, to either:

  1. Recover X itself or
  2. Recover a list of possible values for X?

It seems to me (though my logic could certainly be flawed) that one or both should be possible, since the simpler case of addition works (Essentially if you add 10 to X and it wraps, you can subtract 10 and wind up with X again) and multiplication is simply repeated addition. Also helping (I believe) is the fact that X is multiplied by the same value in all cases - a constant 33.

This has been dancing around my skull at odd moments for years. It'll occur to me, I'll spend some time trying to think through it, and then I'll forget about it for a few months. I'm tired of chasing this problem! Can anyone offer insight?

(Side note: I really don't know how to tag this one. Suggestions welcome.)

Edit: Let me clarify that if I can get a list of possible values for X, there are other tests I could do to help me narrow it down to the original value.

share|improve this question
13  
Something along the line of en.wikipedia.org/wiki/Modular_multiplicative_inverse –  rwong Jul 23 at 6:05
1  
@rwong: your comment is the only correct answer. –  kevin cline Jul 23 at 6:16
    
Yup, and Euler's method seems particularly effective since the factorization of m is just 2^32 or 2^64, plus the exponentiation of a modulo m is straightforward (just ignore overflow there) –  MSalters Jul 23 at 7:54
1  
I think the particular problem is in fact Rational Reconstruction –  MSalters Jul 23 at 7:57
1  
@MSalters: No, that's where you have r*s^-1 mod m and you need to find both r and s. Here, we have r*s mod m and we know everything but r. –  user2357112 Jul 23 at 11:17

6 Answers 6

up vote 46 down vote accepted

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 2**32 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 2**32 is 1041204193. So, multiply by 1041204193, and you have the original x back.

If we had, say, 60 instead of 33, we wouldn't be able to recover the original number, but we would be able to narrow it down to a few possibilities. By factoring 60 into 4*15, computing the inverse of 15 mod 2**32, and multiplying by that, we can recover 4 times the original number, leaving only 2 high-order bits of the number to brute-force. Wolfram Alpha gives us 4008636143 for the inverse, which doesn't fit in an int, but that's okay. We just find a number equivalent to 4008636143 mod 2**32, or force it into an int anyway to have the compiler do that for us, and the result will also be an inverse of 15 mod 2**32. (We get -286331153.)

share|improve this answer
4  
Oh boy. So all the work that my computer has done building the map was already done by Euclid. –  Volodya Jul 23 at 7:53
18  
I like the matter-of-fact-ness in your first sentence. "Oh, it's 1041204193, of course. Don't you have that memorized?" :-P –  Doorknob Jul 23 at 8:30
2  
It would be helpful to show an example of this working for a couple numbers, such as one where x*33 didn't overflow and one where it did. –  Rob Watts Jul 23 at 15:33
2  
Mind blown. Wow. –  Michael Gazonda Jul 23 at 16:47
4  
You don't need either Euclid nor WolframAlpha (certainly!) to find the inverse of 33 modulo $2^{32}$. Since $x=32=2^5$ is nilpotent (of order $7$) modulo $2^32$, you can just apply the geometric series identity $(1+x)^{-1}=1-x+x^2-x^3+\cdots+x^6$ (after which the series breaks off) to find the number $33^{-1}=1-2^5+2^{10}-2^{15}+\cdots+2^{30}$ which is $111110000011111000001111100001_2=1041204193_{10}$. –  Marc van Leeuwen Jul 23 at 16:59

This maybe better suited as an question to Math (sic) SE. You are basically dealing with modular arithmetic, since dropping the left-most bits is the same thing.

I am not as good at Maths as the people who are on Math (sic) SE, but i will try to answer.

What we have here is that the number is being multiplied by 33 (3*11), and its only common denominator with your mod is 1. That is because by definition the bits in the computer are powers of two, and thus your mod is some power of two.

You will be able to construct the table where for every previous value you calculate the following value. And the question becomes do the following numbers correspond to only one previous one.

If it were not 33, but a prime or some power of a prime, i believe that the answer would be yes, but in this case… ask on Math.SE!

Programmatic test

This is in C++ because i don't know C#, but the concept still holds. This seems to show that you can:

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

After populating such a map, you would be always able to get the previous X if you know the next one. There is only a single value at all times.

share|improve this answer
    
Why would working with a non-negative datatype be easier? Aren't signed and unsigned handled the same way in the computer, only their human output format differs? –  Xcelled194 Jul 23 at 5:10
    
@Xcelled194 Well, it's easier for me to think about these numbers. –  Volodya Jul 23 at 5:15
    
Fair enough xD The human factor~ –  Xcelled194 Jul 23 at 5:16
    
I have removed that statement about non-negative to make it more obvious. –  Volodya Jul 23 at 5:17
1  
@Xcelled194: Unsigned datatypes follow the usual rules of modular arithmetic; signed types do not. In particular, maxval+1 is 0 only for unsigned types. –  MSalters Jul 23 at 7:45

One way to get it is to use brute force. Sorry I don't know C# but the following is c-like pseudo code to illustrate the solution:

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

Technically, what you need is x*33%(INT_MAX+1) == test_value but integer overflow will automatically do the % operation for you unless your language uses arbitrary precision integers (bigint).

What this gives you is a series of numbers that may have been the original number. The first number printed would be the number that would generate one round of overflow. The second number would be the number that would generate two rounds of overflow. And so on..

So, if you know you data better you can make a better guess. For example, common clock maths (overflow every 12 o'clock) tend to make the first number more likely since most people are interested in things that happened today.

share|improve this answer
    
C# behaves like C with basic types - ie int is a 4 byte signed integer that wraps, so your answer is still good, though brute forcing wouldn't be the best way to go if you have a lot of inputs! :) –  Xcelled194 Jul 23 at 5:07
    
Yeah, I tried doing it on paper with modulo algebra rules from here: math.stackexchange.com/questions/346271/…. But I got stuck trying to figure it out and ended up with a brute-force solution :) –  slebetman Jul 23 at 5:10
    
Interesting article, though I'll have to study it a bit more in depth for it to click, I think. –  Xcelled194 Jul 23 at 5:12
    
@slebetman Look at my code. It seems that there is only a single answer when it comes to multiplying by 33. –  Volodya Jul 23 at 5:19
2  
Correction: C int is not guaranteed to wrap around (see your compiler's docs). It's true for unsigned types though. –  Thomas Eding Jul 23 at 5:41

You could the SMT solver Z3 to ask it to give you a satisfying assignment for the formula x * 33 = valueFromFile. It will invert that equation for you and give you all possible values of x. Z3 supports exact bitvector arithmetic including multiplication.

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

Output looks like this:

SATISFIABLE
(define-fun y () (_ BitVec 32)
  #xa33fec22)
(define-fun x () (_ BitVec 32)
  #x00000021)
33 * 2738875426 = 188575842
share|improve this answer

To undo that result will give you a non-zero finite amount of numbers (normally infinite, but int is a finite subset of ℤ). If this is this acceptable, just generate the numbers (see other answers).

Otherwise you need to maintain a list of history (of finite or infinite length) of the variable's history.

share|improve this answer

As always, there is a solution from a scientist and solution from an engineer.

Above you will find a very good solution from a scientist, which works always, but requires you to calculate “multiplicative inverse”.

Here is a quick solution from engineer, which will not force you to try all possible integers.

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

What are the ideas?

  1. We got overflow, so let’s use larger types to recover (Int -> Long)
  2. We probably lost some bits due to overflow, let’s recover them
  3. The overflow was not more than Int.MaxValue * multiplier

Full executable code is located on http://ideone.com/zVMbGV

Details:

  • val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
    Here we convert our stored number to Long, but since Int and Long are signed, we have to do it correctly.
    So we limit the number using bitwise AND with bits of Int.
  • val overflowBit = 0x100000000L
    This bit or multiplication of it could be lost by initial multiplication.
    It's a first bit outside of Int range.
  • for(test <- 0 until multiplier)
    According to 3rd Idea the maximal overflow is limited by multiplier, so don’t try more than we really need.
  • if((problemAsLong + overflowBit * test) % multiplier == 0)
    Check if by adding possibly lost overflow we come to a solution
  • val original = originalLong.toInt
    Original problem was in Int range, so let’s return to it. Otherwise we could incorrectly recover numbers, which were negative.
  • println(s"$original (test = $test)")
    Don’t break after the first solution, because there are could be other possible solutions.

PS: 3rd Idea is not strictly correct, but left so to be understandable.
Int.MaxValue is 0x7FFFFFFF, but maximal overflow is 0xFFFFFFFF * multiplier.
So the correct text would be “The overflow was not more than -1 * multiplier”.
This is correct, but not everybody will understand it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.