4
\$\begingroup\$

This question already has an answer here:

In this thread we use 32-bit signed integers (assuming the usual two's complement). For simplicity I shall call this type Int32. The range is from -2147483648 through 2147483647. Any two values can be successfully multiplied (the result is an Int32 as well) since we use multiplication without overflow checking (we only keep the 32 least significant bits of the product).

For example, we have:

2147483647 * 2 == -2

and so on.

If your language does not have native support for 32-bit signed integers (with two's complement), you must emulate it.

Your task is to solve the equation:

a * x == b

where a and b are given as input, and it is assumed that a is an odd number (i.e. least significant bit is 1). You output an Int32 value.

  • The input to your program shall be two Int32 values a and b, and a will be odd
  • The output must be one Int32 value such that (if we call the output x) a*x == b
  • You do not have to handle invalid input; in particular, if the argument a is an even number, it does not matter what your code does
  • Code golf

Test cases:

Input                  Output

1,42                   42
3,126                  42
5,5                    1

-3,126                 -42
3,-126                 -42
-3,-126                42

2147483647,-2          2
2147483647,2           -2
2147483647,666         -666

3,0                    0
3,1                    -1431655765
3,2                    1431655766

-387907419,1342899768  1641848792
348444091,1076207126   -1334551070
10,14                  irrelevant (illegal input)

In the last case [a,b]==[10,14], even if there is a solution x = -1717986917 (not unique, x = 429496731 also works), you do not have to handle that case (10 is not odd).

\$\endgroup\$

marked as duplicate by Peter Taylor code-golf Oct 31 '17 at 13:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ @PeterTaylor, is this an exact duplicate? The other thread takes in the "denominator" (which they call a) and the modulus (which they call b) and asks you to find "1/a" modulo b, stating the result in the interval 0...(b-1). My question says input is a "denominator" (which I also call a) and a "numerator" b, and the modulus is always 2**32, and I want the result "b/a" modulo 2**32, representative in the interval (-2**31)...(2**31-1). I can see the threads are very related, but answers to one challenge cannot be used for the other. \$\endgroup\$ – Jeppe Stig Nielsen Oct 31 '17 at 14:09
  • \$\begingroup\$ (continued) My question is actually much less general because I ask for only one magical modulus. And there are also different requirements when a is not invertible modulo the relevant modulus. Addition: The other thread also links Compute modular inverse which is very similar. I admit I do not know just how similar to challenges must be to be considered duplicates, here on Code Golf. \$\endgroup\$ – Jeppe Stig Nielsen Oct 31 '17 at 14:15
  • \$\begingroup\$ The basic rule of thumb is: could answers be copied across with only minor changes? Things like hard-coding a parameter or adding a loop over a parameter are considered sufficiently minor. The difference of range between 0...(b-1) and (-2**31)...(2**31-1) is completely trivial, because when working with 32-bit integers that just drops out. \$\endgroup\$ – Peter Taylor Oct 31 '17 at 14:51
  • \$\begingroup\$ An answer such as the earliest one below, by HyperNeutrino, could never be copied to the other thread because the other thread requires arbitrary modulus, and HyperNeutrino's answer only works with modulus 2**32. However, in the opposite direction, most answer from the other thread can be copied to here, though you need to insert a new multiplication by my b modulo 2**32, but I suppose they would not "compete" well in here because they are designed to also be well-behaved in the case where the inverse is impossible. \$\endgroup\$ – Jeppe Stig Nielsen Oct 31 '17 at 15:59
3
\$\begingroup\$

Python 3, 39 bytes

lambda a,b,h=2**31:(a**~-h*b+h)%(2*h)-h

This is a theoretical solution that will take a long time unless a = 1. It uses the Euler-Fermat theorem to determine the modular inverse of a.

Alternate version, 47 bytes

lambda a,b,h=2**31:(pow(a,h-1,2*h)*b+h)%(2*h)-h

This does exactly the same, but in a more efficient manner.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK 8), 44 bytes

a->b->{for(int i=0;;i++)if(a*i==b)return i;}

Try it online!

-12 bytes by using a currying lambda thanks to Kevin Cruijssen

\$\endgroup\$
  • \$\begingroup\$ Dang, you beat me to it.. Btw, since you're using OpenJDK 8, you can change int f(int f,int p) to f->p->. Try it here. \$\endgroup\$ – Kevin Cruijssen Oct 31 '17 at 12:51
  • \$\begingroup\$ I wonder if most answers are going to simply use brute force like that. \$\endgroup\$ – Jeppe Stig Nielsen Oct 31 '17 at 12:53
  • \$\begingroup\$ @JeppeStigNielsen Probably, yes. 2^32 isn't much to bruteforce in most languages actually. Java is probably one of the most inefficient ones for it. Also, too bad it's multiplication, because if it was addition it would be similar to a deleted Sandbox question of mine. \$\endgroup\$ – Kevin Cruijssen Oct 31 '17 at 12:55
  • \$\begingroup\$ @KevinCruijssen Oh cool, thanks! \$\endgroup\$ – HyperNeutrino Oct 31 '17 at 13:01
1
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

Mod[#2PowerMod[#,-1,m=2^32],m,-m/2]&

Try it online!

\$\endgroup\$

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