int num = -340721550;
int multi = -214882771;
int result = num * multi; // = 10
If I know multi and result, how can I go backwards to num without brute forcing it?
Or improve the speed of my brute forcing method
public static int multiInverse(int multi, int result){
for (int i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i++){
if (multi * i == result){
return i;
}
}
return -1;
}
As pointed out in a prior answer, the problem can be attacked through calculating the inverse modulo 2^32 of the known divisor. java.math.BigInteger has a modInverse method that can be used.
As also pointed out in the answer, numbers that are not prime relative to the the modulo base do not have an inverse. In the context of a power-of-two base, that means even numbers lack an inverse. I worked around that by halving both the divisor and the product until the divisor is odd.
Unfortunately, all my method can do is find one result such that divisor * result == product in int arithmetic. There may be more than one such number, so it will not necessarily be the one you started with.
private static final BigInteger modulo = BigInteger.ONE.shiftLeft(32);
public static int unoverflowDivide(int product, int divisor) {
if (divisor == 0)
throw new IllegalArgumentException("No solution");
while((divisor & 1) == 0){
if ((product & 1) == 1)
throw new IllegalArgumentException("No solution");
divisor >>= 1;
product >>= 1;
}
BigInteger bigDivisor = BigInteger.valueOf(divisor);
BigInteger bigProduct = BigInteger.valueOf(product);
BigInteger bigInverse = bigDivisor.modInverse(modulo);
BigInteger bigResult = bigInverse.multiply(bigProduct);
return bigResult.intValue();
}
int a = 76; int b = 145; int x = unoverflowDivide(b, a); System.out.println("ax=" + a * x); The result is 144.
Simply put, your question is about solving the following equation:
x * b = a, where a and b are known.
Normally, this is very straightforward, because you can simply do:
x = a / b
However, since we are working with integers, this only gives a proper solution if a is a multiple of b. For example, if b = 2 and a = 4.
If a is not a multiple of b, then we know that a*x resulted in an integer overflow.
Now, think about what it means to divide with b. What you are actually doing, is applying the inverse of b. After all, b / b = 1. By dividing with b, you are 'undoing b'.
So what we have to do to find the solution, is to find the integer that we have to multiple b with, to get such an overflow that it results in 1.
I'll give a small example to show how this works.
Suppose we have a data type that has a range from 0 to 8, so it will overflow for any value outside of the range 0 to 8.
In this case, the following is true: 3 * 3 == 1. (Because 9 overflows to 1)
Now let's say we have 3 * 5 == 7 (Because 15 overflows to 7).
What you want, is to get back to 3, by knowing 5 and 7. More formally, you want to find x for 5x = 7 in modular 8.
In modular 8, the inverse of 5 is 5, because 5*5=25, which overflows to 1.
So your solution is 7 * 5 = 3 (because 35 overflows to 3)
However, it will not be so easy to find an easy way to find the inverse of a signed java integer. If you can even find it at all, because not every integer is guaranteed to have an inverse.