CODEWITHSUNDEEP
javamathbigintegermodulus
Constant
Constant

Reputation: 830

Reverse Multiplication

I have the following number; let's call it number one

-1757151608

then I have a second number, let's call it unknown

94507795

and finally, I have the product, let's call it number two

-1000

If I multiply the first two numbers in form, I get the answer as -1000. Problem is, I have the number one and number two at my disposal, but I need to get the unknown from this.

I've tried using the BigInteger class and a few of it's functions with no luck.

Thanks in advance.

Upvotes: 1

Views: 2513

Answers (2)

Edward Doolittle
Edward Doolittle

Reputation: 4100

I believe what you want is to multiply -1000 by the multiplicative inverse of -1757151608 modulo 2^32; see, e.g., the calculation in Wolfram Alpha.

I have written a program which I believe correctly calculates the answer to your question, when one exists.

public class InverseMultiplication {

  // multiplicative inverse of a multiplied by b mod 2^32
  public static long invertAndMultiply(long a, long b) { 
    // take out common factors of 2
    while (a % 2 == 0 && b % 2 == 0) {
      a /= 2;
      b /= 2;
    }
    long m = 256L*256L*256L*256L; // modulus is 2^32
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    while (nr != 0) {
      long q = r/nr;
      long tmp;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) throw new IllegalArgumentException(a + " has no inverse");
    t = (t*b) % m;
    while (t < Integer.MIN_VALUE) t += m;
    while (t > Integer.MAX_VALUE) t -= m;
    return t;
  }

  public static void main(String[] args) {
    long twoPow32 = 256L*256L*256L*256L;
    int n1 = -1757151608;
    int n2 = -1000;
    long unk = invertAndMultiply(n1,n2);
    System.out.println(unk);
    long pro = n1 * unk % twoPow32;
    if (pro > Integer.MAX_VALUE) pro -= twoPow32;
    System.out.println(pro);
    int pro1 = -1757151608 * 94507795;
    System.out.println(pro1);
  }
}

There are a few important points to note, however. If your "number one" is odd, there is a unique answer which the program will find quickly.

An even "number one" will not have an inverse mod 2^32, so in general you will be out of luck in that case. However, if your "number two" is also even, you can keep dividing both by 2 ("taking out common factors of 2") until one or both are odd. Hopefully "number one" is odd, in which case you'll get an answer; if "number one" is even after taking out all common factors of 2, you won't get any answer. In that case there is no answer.

If there is an answer in the even case, there's more than one answer. If you run my program, you'll see that it arrives at a different answer from yours.

Please check it out and let me know whether it works the way you expect.

Upvotes: 1

Gilbert Le Blanc
Gilbert Le Blanc

Reputation: 51445

It's impossible to reverse this multiplication.

First, let's take the two's complement of the first number.

3904635256 = 2147483648 - -1757151608

Next, we'll multiply the second number

369018468323820520 = 3904635256 * 94507795

Now, here's the tricky part. We convert the product to hex, and drop the digits larger than a 32 bit integer.

51F0457800003E8 (hex) = 369018468323820520 (decimal)
800003E8 = 51F0457800003E8 moved to a 32 bit signed integer

Now, we convert the hex value back to decimal

2147484648 (dec) = 800003E8 (hex)

Finally, we take the two's complement of the decimal

-1000 = 2147483648 - 2147484648

Since we threw away the 51F0457 (hex), we have no way of getting that back. The reverse of this operation is impossible.

Upvotes: 3

Related Questions