1

I am given with three integers A, B and C. I need to implement a program to perform the operation A^B modulus C. I without thinking much, wrote the following code:-

public int Mod(int A, int B, int C) 
{
    return (int)Math.pow(A,B) % C;
}

testcase : A = -1, B = 1, C = 20, the expected o/p was 19 whereas my code gave -1 as output.

I found out that this approach is incorrect when there is a negative number, in this example, when A < 0. I referred to explanations in few websites, but was unable to understand this behavior. Please help me on this one. Thank you.

  • that is not how modpow works. first of all If I see it right what you did is `(A%B)%C` and also mixing floating point with this is not a good idea ... see my C++ [`DWORD fourier_NTT::modpow(DWORD a,DWORD b)`](https://stackoverflow.com/q/18577076/2521214) for some inspiration – Spektre Apr 12 '21 at 16:20
  • 1
    Also, why read stuff from random website when the [official documentation](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Math.html#pow(double,double)) is rather exhaustive? – Federico klez Culloca Apr 12 '21 at 16:20
  • my mistake i wrote Math.mod instead of Math.pow –  Apr 12 '21 at 16:22
  • using floating point `pow` for this is wrong and will lead to wrong results on bigger A^B values ... – Spektre Apr 12 '21 at 16:22
  • Note that there is the modulus function and the java version of the mod function. -1 mod 10 = 9. Java's -1 % 10 = -1 – cup Apr 12 '21 at 16:33
  • For `19` as the result using these three values, you will have to do `(int)Math.pow((C + A), B)`. – Arvind Kumar Avinash Apr 12 '21 at 17:00

3 Answers3

1

% Operator in Java

In java, when calculating

A % B

the answer is produced according to following conditions:

When the dividend is negative, the answer produced will also be negative and when the dividend is positive, the answer produced will also be positive.

Do note that this behavior is language specific. In python, the above program will produce 19 as output.

Flaw in the code

If one only wants A % B to produce positive results, then simply using A % B will produce wrong output because of reasons mentioned above.

Also, calculating A^B % C where B can take large values directly is not the right approach. I suggest you use fast exponentiation to do so. It is a famous algorithm and you can easily find it online.

Solution

If you want only positive result, use this:

r = a % b > 0 ? a % b : Math.abs(b) + a % b;

Here r is remainder, a is dividend and b is divisor.

I hope I have helped you. If you want to understand why this happens, do comment and I will be happy to edit my answer to help you.

AKSingh
  • 1,535
  • 1
  • 8
  • 17
0

There is no 'modulus' operator in Java; there is a remainder operator.

Negative one to the power one is negative one.

The remainder of dividing negative one by 20 is negative one.

The JLS (link above) specifically says that the sign of the result is the same as the sign of the left-hand side. Thus -1 and not +19.

The definition of % is

The remainder operation for operands that are integers after binary numeric promotion (§5.6.2) produces a result value such that (a/b)*b+(a%b) is equal to a.

user15187356
  • 807
  • 3
  • 3
  • _Mathematically_ the operation is called modulus, and the _result_ is called remainder: https://en.wikipedia.org/wiki/Euclidean_division. So strictly speaking `%` is neither a remainder, nor a modulus. It's a _Java modification_ of modulus. In other programming languages it could be a different modification. – Stanislav Bashkyrtsev Apr 14 '21 at 09:59
  • Of course, but this is specifically a Java programming question, so the Java definjtion of "%" is what is pertinent here, and the name that Java gives to "%" is the thing to use when talking about Java programming. I note that machine addition is often not mathematical addition either (adding two positive machine integers can produce a negative result). – user15187356 Apr 14 '21 at 11:59
  • "_so the Java definjtion of "%" is what is pertinent here_" - I think everyone would be okay if you name it either way. It's just they wouldn't give 2 names to the same operator in the specs.. "_I note that machine addition is often not mathematical addition either (adding two positive machine integers can produce a negative result)_" - actually in this case it's a mathematical addition :) Sign doesn't play a role in the operation itself - it shows up when interpreting bytes. Same bytes will be interpreted differently in case of a signed and unsigned integer (Java has only signed). – Stanislav Bashkyrtsev Apr 14 '21 at 13:16
0
function pow(A,B,C)
{
    if(A == 0) {
        return 0;
    }
    else if(B == 0) {
        return 1;
    }
    else if(B%2 == 0) {
        let half = this.power(A,Math.floor(B/2),C);
        return (half * half)%C;
    }
    else {

        return ((this.power(A,B-1,C)) * A%C)%C;
    }
}
Abhijeet Pratap Singh
  • 3
  • 2
  • 1
    Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Jul 02 '22 at 20:24