wu :: forums - Modulo 3 and 5

wu :: forums « wu :: forums - Modulo 3 and 5 » Welcome, Guest. Please Login or Register. May 19^th, 2024, 7:59am
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   cs (Moderators: towr, Grimbal, Eigenray, ThudnBlunder, SMQ, william wu, Icarus)
   Modulo 3 and 5

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Modulo 3 and 5 (Read 1386 times)

Barukh
Uberpuzzler

Gender:

Posts: 2276

Modulo 3 and 5
« on: Apr 6^th, 2004, 8:52am »

Quote

Modify

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

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

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

IP Logged

hsp246
Guest

Re: Modulo 3 and 5
« Reply #1 on: Apr 6^th, 2004, 9:23am »

Quote

Modify

Remove

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?

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Modulo 3 and 5
« Reply #2 on: Apr 6^th, 2004, 10:17am »

Quote

Modify

::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)::

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

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

[e2]
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;
[/e2]

« Last Edit: Apr 6^th, 2004, 10:44am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

hsp246
Newbie

Posts: 1

Re: Modulo 3 and 5
« Reply #3 on: Apr 6^th, 2004, 10:41am »

Quote

Modify

I see. Using the same idea I think:

we can use it on modulo 5 as well, with base 16

==

« Last Edit: Apr 6^th, 2004, 10:41am by hsp246 »

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Modulo 3 and 5
« Reply #4 on: Apr 6^th, 2004, 10:46am »

Quote

Modify

heh.. yes, indeed.. I was allready editing that in.. Grin

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

Barukh
Uberpuzzler

Gender:

Posts: 2276

Re: Modulo 3 and 5
« Reply #5 on: Apr 6^th, 2004, 11:37pm »

Quote

Modify

Well done, towr and hsp246! Cheesy

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

unsigned modulo_257(unsigned n);

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Modulo 3 and 5
« Reply #6 on: Apr 7^th, 2004, 3:13am »

Quote

Modify

on Apr 6^th, 2004, 11:37pm, Barukh wrote:

unsigned modulo_257(unsigned n);

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

« Last Edit: Apr 7^th, 2004, 3:13am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Modulo 3 and 5
« Reply #7 on: Apr 7^th, 2004, 3:36am »

Quote

Modify

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

  while (n > 256)
   n += 257;
::

« Last Edit: Apr 7^th, 2004, 3:37am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

Barukh
Uberpuzzler

Gender:

Posts: 2276

Re: Modulo 3 and 5
« Reply #8 on: Apr 7^th, 2004, 6:19am »

Quote

Modify

on Apr 7^th, 2004, 3:36am, towr wrote:

or (rather better)

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

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Modulo 3 and 5
« Reply #9 on: Apr 7^th, 2004, 6:37am »

Quote

Modify

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

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

John_Gaughan
Uberpuzzler

Behold, the power of cheese!

Gender:

Posts: 767

Re: Modulo 3 and 5
« Reply #10 on: Apr 7^th, 2004, 6:56pm »

Quote

Modify

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.

IP Logged

x = (0x2B | ~0x2B)
x == the_question

Barukh
Uberpuzzler

Gender:

Posts: 2276

Re: Modulo 3 and 5
« Reply #11 on: Apr 13^th, 2004, 11:30pm »

Quote

Modify

on Apr 7^th, 2004, 6:56pm, 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 that gives a very detailed description of both the division method and the flaw.

IP Logged