CODEWITHSUNDEEP
algorithm
marco quezada
marco quezada

Reputation: 29

Modulo Algorithm creation

Alright this is a homework question that I've been wracking my brain about

Show an Algorithm that on input integers a,b where a is n bit long and b < a, computes a mod b in O(n^2)

I've come up with the following algorithm and I wondered if I'm in the right track: 

modulus(a,b)
c = a-b;
modulus (c,b)
result c;

Would this be correct? Or am I doing it too intuitively? Any tips?

I was trying to write out the algorithm in pseudo code. and yes it's asking about implementing modulus.

Upvotes: 0

Views: 542

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58369

To compute a mod b, you have to subtract multiples of b from a until the result is less than b. For simplicity, I'll assume a >= 0, b > 0, but you can use the relations mod(-a, b) = mod(a, -b) = -mod(a, b) to recover the negative-signed cases.

The most naive (but inefficient) way to implement mod is this:

def mod(a, b):
    while a >= b:
        a -= b
    return a

This is awful when a is much larger than b. The complexity is O(a/b) which is O(2^n) in the worst cases where n is the number of bits. Instead, we can try subtracting large multiples of b, and we can do this with bit-shifting.

def mod(a, b):
    bs = b
    while bs <= a:
        bs <<= 1
    while bs > b:
        bs >>= 1
        if a >= bs: a -= bs
    return a

In this code, we keep shifting b (in the variable bs) left until it's larger than a. Then one step at a time, we shift it back to b, subtracting the value from a if we can. This is essentially an implementation of long division in binary.

As for time complexity: a left-shift is O(n) (assuming we're dealing with arbitrary large numbers where n is the number of bits), as is comparison and subtraction. That makes both of the while loops in this implementation O(n^2) as required.

Upvotes: 1

Related Questions