6
\$\begingroup\$

As my question Modular arithmetic was hard to review and terribly long, I've added a few comments to the easier part, namely IntModulus.

The code uses Guava and Lombok. As usual, feel free to ignore my slightly deviating coding conventions.

My concerns are speed and correctness. The whole code including the test can be found on github. If someone feels like reviewing the test, I'll add it here.

IntModulus

import static com.google.common.base.Preconditions.checkArgument;

import lombok.Getter;

/**
 * This class provides common modular arithmetic.
 * Results of all methods are ints guaranteed to be non-negative and less then modulus.
 *
 * <p>The method names were chosen to be as short as {@code Math.pow}.
 */
public final class IntModulus {
    private IntModulus(int modulus) {
        this.modulus = modulus;
    }

    @SuppressWarnings("boxing") public static IntModulus newModulus(int modulus) {
        checkArgument(modulus>0, "Modulus must be positive, got %s", modulus);
        return new IntModulus(modulus);
    }

    public int pow(long base, long exp) {
        checkArgument(exp>=0, "Only non-negative exponents are implemented.");  //TODO allow negative exponents
        if (modulus==1) return 0;
        if (exp==0) return 1;
        return powInternal(mod(base), exp);
    }

    private int powInternal(int base, long exp) {
        assert base>=0;
        if (base<=1) return base; // For both 0 and 1, no exponentiation is needed.

        // See https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
        int result = 1;
        for (int x=base; exp>0; exp>>=1) {
            if ((exp&1) != 0) result = mul(result, x);
            x = square(x);
        }
        return result;
    }

    private int square(int x) {
        final long x2 = x;
        return (int) ((x2 * x2) % modulus); // The cast is safe and the result is surely non-negative.
    }

    /** Return a non-negative value less than modulus and congruent to the exact product. */
    public int mul(long x, long y) {
        return mul(mod(x), mod(y));
    }

    /** Return a non-negative value less than modulus and congruent to the exact product. */
    public int mul(int x, int y) {
        return mod((long) x * y);
    }

    /** Return a non-negative value less than modulus and congruent to the exact sum. */
    public int add(int x, int y) {
        return mod((long) x + y);
    }

    /** Return a non-negative value less than modulus and congruent to the exact difference. */
    public int sub(int x, int y) {
        return mod((long) x - y);
    }

    /** Return a non-negative value less than modulus and congruent to the operand. */
    public int mod(long x) {
        return fixMod((int) (x % modulus)); // As modulus is an int, the cast is safe.
    }

    /** Return a non-negative value less than modulus and congruent to the operand. */
    public int mod(int x) {
        return fixMod(x % modulus);
    }

    private int fixMod(int result) {
        return result<0 ? result+modulus : result;
    }

    @Getter private final int modulus;
}
\$\endgroup\$
3
\$\begingroup\$

The use of a factory-method constructor appears to be gratuitous. There's no apparent reason for it. The class is public, and final, so there's no ambiguity, the constructor arguments are simple, and there's no factory manipulation before calling it. The constructor should just be:

public IntModulus(int modulus) {
    checkArgument(modulus>0, "Modulus must be positive, got %s", modulus);
    this.modulus = modulus;
}

Your powInternal is also a functional extraction that is redundant. I suspect this is a copy/paste issue, or a refactoring that was partially undone. Still, the assert is meaningless, and cannot happen, and the function should just be re-integrated in to the public pow(...) function. Then, I would also make base the variable that mutates in the loop, and remove the x variable, allowing you to convert the loop to a while loop. Finally, I know it is pedantic, but you should sjift the exponent with >>>= instead of >>=, even though the exponent is not negative. Something like:

public int pow(long base, long exp) {
    checkArgument(exp>=0, "Only non-negative exponents are implemented.");  //TODO allow negative exponents
    if (modulus==1) return 0;
    if (exp==0) return 1;

    base = mod(base);
    if (base<=1) return base; // For both 0 and 1, no exponentiation is needed.

    // See https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
    int result = 1;
    while(exp>0) {
        if ((exp&1) != 0) result = mul(result, base);
        base = square(base);
        exp >>>= 1;
    }
    return result;
}

In your square function, you explicitly cast x as a long:

private int square(int x) {
    final long x2 = x;
    return (int) ((x2 * x2) % modulus); // The cast is safe and the result is surely non-negative.
}

This is OK, but, in other places, you cast the ints to longs in-place. I would prefer the consistency to be maintained, and since I prefer the in-place cast, I would recommend you change the square function:

private int square(int x) {
    // The cast is safe and the result is surely non-negative.
    return (int) (( (long)x * x) % modulus);
}

Note that I also put the end-of-line comments to be above the commented code. Since comments tell you what to expect in the code (and why), they should be there before the code, not as an afterthought.

The matching mod and multiply methods for both int and long arguments, are a bit messy, but hard to avoid. What's more problematic is that you don't have matching argument symmetry for add and subtract. You should have long versions of those.

The parameter names x and y for the mul() function are poor... multiplicand and multiplier are messy too. maybe x and y are better ;-)

The final comment I have is about the Javadoc comments on your methods. They are incomplete, and don't have @param and @return values. Does Lombok fill those in magically?

As for performance, I can't see anything that would make much difference. The fixmod method irks me... I don't like ternaries in tight loops, they have implications for branch predictions, but, even though I could match the logic with a non-ternary expression, it was just as efficient, and not as readable.

I don't believe performance can be improved much.

\$\endgroup\$
  • \$\begingroup\$ Some explanations just FYI: +++ factory-method: 1. for consistency with LongModulus. 2. There might be more implementations one day. +++ powInternal: 1. You missed the long -> int change for base. 2. I'm thinking about pow(int, long). +++ long versions of add/sub: don't know yet how to do them optimally (doing % three times like for mul is not needed). +++ @param and @return values: I'm ignoring the rule as I can't see what information they'd add. +++ ternaries: The JIT is smart and uses movcc which we can't. \$\endgroup\$ – maaartinus Jun 29 '15 at 4:20
4
\$\begingroup\$

Note: I changed a few things to fit my own personal style, but since it's solely opinion I didn't comment on them. It's mostly reordering things or whitespace.

I'd recommend renaming mul to multiply, just because there's no particular reason to have it short.

private int square(int x) {
    final long x2 = x;
    return (int) ((x2 * x2) % modulus); // The cast is safe and the result is surely non-negative.
}

Sure, it's the second x, but xLong would be a lot clearer then x2.

Also:

// The cast is safe and the result is surely non-negative.

Why is the cast safe? Sure, after a second I can understand that it's because modulus is an int and therefore the result has to be within the bounds of int, but... okay, maybe that's a bad example. The point I'm trying to make is that when you make an assertion, you should explain why. [This space intentionally left blank]

For your RTI binary method implementation: I would suggest adding a comment explaining how it works, but the Wikipedia article does a fine enough job.

I'm gonna clarify on a point I made in my last review: Be careful with asserts. You use them pretty well here, but there are a couple of things you should always do:

  1. Use the extended form -- assert condition : "why"; instead of just assert condition; and use the String to explain why failing that assert is bad. It'll make your code clearer, and when you want to debug, you won't have to struggle to remember why that assert has to pass -- it'll be right there in the error message.

  2. Only use them in places where they're expected to pass, and failing it is only ever caused by a bug in the program. You're already doing this, but I still feel like it's worth mentioning.

fixMod at first seemed like an odd name -- I kept reading it as fixedModulus, but if I'm reading it right, it's "fix" as in "correct", right? I'd suggest adding a quick Javadoc to that effect, so you can remember easier when you want to change this.

For consistency, you should add long versions of add and sub as well.

WRT performace: There's not much you could do, aside from manually inlining things to shave off some readability.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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