A while back, an FPGA engineer noticed I was using the modulus (%) operator and chided me because of it's inefficiency. For even or odd numbers, you really only need to check if the least significant bit is zero. Recently, I've been working with the Korn shell and have discovered some interesting features that would allow me to perform the modulus operation on arbitrary numbers without using the mod operator or division (at least, not directly!).
This is an open ended puzzle (no wrong answers!) to see how many ways one can implement finding the modulus without the mod (%) operator or explicit division.
The Korn shell trick that I found was that one can use typeset to set the base of a number, for example, for base 3, one could define the variable 'three' as follows:
typeset -i3 three=9
echo "$three"
3#100
Any number divisible by the selected base has the least significant digit equal to zero, which is equivalent to the modulus. Seven, which is not an exact multiple of 3, results in 3#21.
One can also use the binary calculator, bc, to adjust the base.
a really nice trick. I looked at the source code of ksh and so far haven't figured out how typeset -iN works. So it could be that ksh uses division internally
Here is one way that uses multiplication instead of division:
for ((a=42,b=9,c=a-b,i=0;b*++i<=c;));do :;done;echo $((a-i*b))
A bit inefficient I guess, but it answers the topic, doesn't it?
