wu :: forums - Print Page


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

        riddles >> cs >> Modulo 3 and 5
        
(Message started by: Barukh on Apr 6^th, 2004, 8:52am)

Title: Modulo 3 and 5
Post by Barukh on Apr 6^th, 2004, 8:52am

This one is not difficult, but may be a candidate for an interview question ;)

Propose the implementations for the following functions without using multiplication and division:

unsigned modulo_3(unsigned n);
unsigned modulo_5(unsigned n);

Title: Re: Modulo 3 and 5
Post by hsp246 on Apr 6^th, 2004, 9:23am

The naive solution is to iteratively subtract 3 and 5 until it is smaller that 3 and 5. Is there a better/faster way to do it though?

Title: Re: Modulo 3 and 5
Post by towr on Apr 6^th, 2004, 10:17am

::[hide]for modulo_3, you could add the base 4 digits (using shift, instead of divide). Base 4 should have the same property as base 10 in that the sum of the digits mod 3 is equal to the number mod 3.
If you throw out all digits that are 3, then you would be done in 3 steps, I think..
[e]~~hmm.. actually, it might suffice tho just XOR all the digits..~~ (or it might not)[/e]
(I really ought to work these ideas out on paper first)[/hide]::

[e][hide]
while (n > 3)
n = (n >> 2) + (n & 3);

if (n > 2)
n -=3;
[/hide][/e]

[e2][hide]
For modulo_5 it's pretty much the same, but with base 16 (Basicly for any modulo a, I'm looking for a base k*a+1 = 2^m)

while (n > 15)
n = (n >> 4) + (n & 15);

while (n > 4)
n -=5;
[/hide][/e2]

Title: Re: Modulo 3 and 5
Post by hsp246 on Apr 6^th, 2004, 10:41am

I see. Using the same idea I think:
[hide]
we can use it on modulo 5 as well, with base 16
[/hide]

==

Title: Re: Modulo 3 and 5
Post by towr on Apr 6^th, 2004, 10:46am

heh.. yes, indeed.. I was allready editing that in.. ;D

Title: Re: Modulo 3 and 5
Post by Barukh on Apr 6^th, 2004, 11:37pm

Well done, towr and hsp246! :D

I was thinking about something different in case of mod 5... What about:

unsigned modulo_257(unsigned n);

Title: Re: Modulo 3 and 5
Post by towr on Apr 7^th, 2004, 3:13am

on 04/06/04 at 23:37:25, Barukh wrote:

unsigned modulo_257(unsigned n);

how about,
::[hide]
a = 257 << 23;
for(int i=0; i < 24; i++)
{
if (n >= a)
n-=a;
a >>= 1;
}
[/hide]::

Title: Re: Modulo 3 and 5
Post by towr on Apr 7^th, 2004, 3:36am

or (rather better)
::[hide]
n = (n & 0xff)
- ((n >> 8) & 0xff)
+ ((n >> 16) & 0xff)
- (n >> 24);

while (n > 256)
n += 257;
[/hide]::

Title: Re: Modulo 3 and 5
Post by Barukh on Apr 7^th, 2004, 6:19am

on 04/07/04 at 03:36:14, towr wrote:

or (rather better)

You've got it towr! It's [hide]like a division by 11,[/hide] isn't it?

Title: Re: Modulo 3 and 5
Post by towr on Apr 7^th, 2004, 6:37am

Yep.. that's how I found it as well.. Interesting how these things work..

Title: Re: Modulo 3 and 5
Post by John_Gaughan on Apr 7^th, 2004, 6:56pm

Does anyone know of a computer that understands base 4? I suppose it would be trivial to translate the function to use base 2. The only bases I have seen computers use are 2, 8, 10, and 16.

Title: Re: Modulo 3 and 5
Post by Barukh on Apr 13^th, 2004, 11:30pm

on 04/07/04 at 18:56:31, John_Gaughan wrote:

Does anyone know of a computer that understands base 4? I suppose it would be trivial to translate the function to use base 2. The only bases I have seen computers use are 2, 8, 10, and 16.

Maybe the following is not exactly what you were asking, but still… A few modern processors (including Intel IA32) have a division unit that actually uses the radix 4 computations for speedup. Already the original Pentium processor with the famous FDIV flaw used this technique. I strongly recommend to read the following paper (http://groups.google.com/groups?q=%22the+pentium+division+flaw%22+deley&hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=deleydDGxuIB.417%40netcom.com&rnum=3) that gives a very detailed description of both the division method and the flaw.

Title: Re: Modulo 3 and 5
Post by grimbal on May 21^st, 2004, 1:10pm

on 04/07/04 at 03:36:14, towr wrote:

or (rather better)
::[hide]
n = (n & 0xff)
- ((n >> 8) & 0xff)
+ ((n >> 16) & 0xff)
- (n >> 24);

while (n > 256)
n += 257;
[/hide]::

Now, find the smallest n for which it does not work http://www.ocf.berkeley.edu/~wwu/YaBBImages/grin.gif .

Title: Re: Modulo 3 and 5
Post by towr on May 22^nd, 2004, 4:56am

on 05/21/04 at 13:10:42, grimbal wrote:

Now, find the smallest n for which it does not work http://www.ocf.berkeley.edu/~wwu/YaBBImages/grin.gif .

What n wouldn't it work for?
(note that n is unsigned)

Title: Re: Modulo 3 and 5
Post by grimbal on May 22^nd, 2004, 8:03am

For instance, it doesn't work with 0xff00ff. But that is not the smallest. A small change is needed in the program to fix this.

Title: Re: Modulo 3 and 5
Post by towr on May 23^rd, 2004, 7:57am

You mean because 255+255 > 256 ?
hmm.. I suppose so..