wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Divisible by 3 or 7
        
(Message started by: johny_cage on Nov 24^th, 2007, 4:57am)

Title: Divisible by 3 or 7
Post by johny_cage on Nov 24^th, 2007, 4:57am

Q(1) Check for the divisibility of a number by 3 in most optimized way.
Q(2) Check for the divisibility of a number by 7 in most optimized way.

Title: Re: Divisible by 3 or 7
Post by towr on Nov 24^th, 2007, 6:19am

[hide]In reality, using n%==3 and n%7==0 is probably fastest.[/hide]
For other suggestions you could read the previous (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1185094398;) threads (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1142940086;) on the subject.

Title: Re: Divisible by 3 or 7
Post by swami on Nov 28^th, 2007, 12:58am

Quote:

For other suggestions you could read the previous threads on the subject.

I am not able to understand the logic for divisibility by 11 testing in the following code

div11(x)
{
if(x < 16)
return x == 0 || x == 11;

l4 = x&15;
f16 = x>>4;

return div11(l4 + f16 + f16<<2 );
}

Can u pls. clarify???

Also, what about testing divisibility by 7?? Is there any general technique for testing divisibility in binary that I am missing?

Title: Re: Divisible by 3 or 7
Post by towr on Nov 28^th, 2007, 1:59am

on 11/28/07 at 00:58:01, swami wrote:

I am not able to understand the logic for divisibility by 11 testing in the following code

First note that 16 % 11 = 5 = 1+4
So if we have N=16*x+y (take 0 <= 0 < 16), N is divisible by 11, if 5x + y is divisible by 11, i.e. if y + x + x << 2 is divisible by 11.
By repeating this we can repeatedly reduce N (if x > 0, the new N' is at most slightly more than 1/3rd the size)

And if N < 16, obviously it's only divisible by 11 if it's 0 or 11.

Quote:

Also, what about testing divisibility by 7??

8%7 = 1,
so if N = 8*x + y (take 0 <= 0 < 8), then you can equivalently test N' = x+y

Quote:

Is there any general technique for testing divisibility in binary that I am missing?

It's a general method for all bases, not just binary, also decimal, hexadecimal or anything else.

d divides b^k*x + y (with 0 <= y < b^k) if and only if d divides (b^k % d)x + (y % d)

The choice you make for k can make a big difference to how simple your calculation becomes, and of course you can generalize it.
If you take decimal for example, and divisibility by 9, you have that 10ⁱ % 9 = 1, so for a decimal number you can just add all the digits and test whether that's divisible by 9 (rather then removing the last digit and adding it to the rest repeatedly; i.e.
12345 ->1+2+3+4+5 (=15) -> 1+5 (=6), rather than 12345 -> 1234+5 (=1239) -> 123+9 (=132) -> 13+2 (=15) -> 1+5 (=6) ).