Tim Wescott wrote:
> You have a Very Large Number, expressed as an binary integer, in the
> memory of a machine that allows for byte-wide operations. For some
> unfathomable reason, you need to determine if this number is evenly
> divisible by 17.
>
> Without using long division or repeated subtraction, and without ever
> performing a multiply or divide on a number greater than eight bits long,
> how can you determine if your number is divisible by 17?
>
> Once you know this technique, what other potential divisors can you test
> for using this method?
That's simple: X must be (a << 4) + a; check the lowest byte.
The magic numbers are 2^n +/- 1
Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Similar Threads
Linear Mode
