[Guest]

an algorithm for determining if a divides b would be the following.

if a is odd:

if b is evenly divisable by 2, divide by 2.

else subtract a.

repeat untill you get a value between 0 and a. this is the modulus.

is there a similar such algorithm if a is even?

(technically the above one does work, but it's rather slow if b is odd, find me a fast one.)

[Guest]

edit: the above algorithm does NOT give the modulus, sorry. it does however work as a divisability detector.

[witzar]

#1 The best algorithm is to divide b by a and check if reminder is zero or not.

#2 If division and multiplication is not allowed, then keep subtracting a from b while b<=a and check if the end value of b is 0.

#3 If only division by 2 is allowed, then method #2 can be improved by dividing both a and b by 2 in a loop while both a and b are even (prior to applying #2). If the above reduction terminates with even a and odd b, then there is an immediate answer "NO". If the above reduction terminates with odd a and even b, then keep dividing b by 2 until it is odd. Only with both a and b odd proceed to #2. Ah, and do not forget to check for special cases (a=0, a=1, a=2) to begin with.

Edited September 14, 2011 by witzar

[witzar]

#4 If addition (or multiplication by 2) is allowed, then #2 (from my post #3) can by significantly improved (in terms of computational complexity of the algorithm).

[Guest]

if a is even and b is odd it is not divisible