Calculating modulo of 7 using bitshift and addition

Question

I'm hoping this question is ok here. It is in the context of programming, perhaps a bit simple for this audience, and a lot of the discussion here is far beyond me.

I'm trying to calculate modulo 7 using bitshift and addition according to this blog post.

Despite a few errors in that post I was able to get 32 bit versions working for divisors 3, 5, and 15 and with a simple guess I was able to get 64 bit versions working too. The math is a bit over my head and trying to get modulo 7 working has left me fruitless.

Here's the ---working--- not working 32 bit for modulo 7:

static public uint Mersenne7(uint a)
{
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits
    a = (a >> 12) + (a & 0xFFF);    // sum base 2**12 digits
    a = (a >> 6) + (a & 0x3F);      // sum base 2**6 digits
    a = (a >> 3) + (a & 0x7);       // sum base 2**2 digits
    a = (a >> 2) + (a & 0x7);       // sum base 2**2 digits
    if (a > 5) a = a - 6;
    return a;
}

This is my guess at 64 bit for modulo 7. It also does not work.

static public ulong Mersenne7(ulong a)
{
    a = (a >> 48) + (a & 0xFFFFFFFFFFFF); // sum base 2**48 digits
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits
    a = (a >> 12) + (a & 0xFFF);    // sum base 2**12 digits
    a = (a >> 6) + (a & 0x3F);      // sum base 2**6 digits
    a = (a >> 3) + (a & 0x7);       // sum base 2**2 digits
    a = (a >> 2) + (a & 0x7);       // sum base 2**2 digits
    if (a > 5) a = a - 6;
    return a;
}

For example, here is the working 32 bit version for modulo 15:

static public uint Mersenne15(uint a)
{
    a = (a >> 16) + (a & 0xFFFF); // sum base 2**16 digits */
    a = (a >> 8) + (a & 0xFF);   // sum base 2**8 digits */
    a = (a >> 4) + (a & 0xF);    // sum base 2**4 digits */
    if (a < 15) return a;
    if (a < (2 * 15)) return (a - 15);
    if (a < (3 * 15)) return (a - (2 * 15));
    return (a - (3 * 15));
}

My simple guess for 64 bit worked for modulo 3, 5, and 15 after a little tweaking. There was a pattern to some incorrect results I was getting at first.

static public ulong Mersenne15(ulong a)
{
    a = (a >> 32) + (a & 0xFFFFFFFF); // sum base 2**32 digits */
    a = (a >> 16) + (a & 0xFFFF); // sum base 2**16 digits */
    a = (a >> 8) + (a & 0xFF);   // sum base 2**8 digits */
    a = (a >> 4) + (a & 0xF);    // sum base 2**4 digits */
    if (a < 15) return a;
    if (a < (2 * 15)) return (a - 15);
    if (a < (3 * 15)) return (a - (2 * 15));
    if (a < (4 * 15)) return (a - (3 * 15));
    return (a - (4 * 15));
}

I don't see how your 32-bit Mersenne7 function can work. For instance, with input a=6, it would seem to return the value 2. Have you made a copy-paste error somewhere? — TonyK, Jun 08 '17 at 01:06
@TonyK you are correct I managed to miss running the test cases for the 32 bit modulo 7 and neither works correctly. I have updated the question to reflect this. — quentin-starin, Jun 08 '17 at 01:55

score 0 · Answer 1 · answered Jun 08 '17 at 03:41

0

The original blog had several errors, including one in the modulo 7 implementation that I was missing. These are correct.

32 bit:

static public uint Mersenne7(uint a)
{
    a = (a >> 24) + (a & 0xFFFFFF);
    a = (a >> 12) + (a & 0xFFF);
    a = (a >> 6) + (a & 0x3F);
    a = (a >> 3) + (a & 0x7);
    a = (a >> 3) + (a & 0x7);
    if (a < 7) return a;
    return a - 7;
}

64 bit:

static public ulong Mersenne7(ulong a)
{
    a = (a >> 48) + (a & 0xFFFFFFFFFFFF);
    a = (a >> 24) + (a & 0xFFFFFF);
    a = (a >> 12) + (a & 0xFFF);
    a = (a >> 6) + (a & 0x3F);
    a = (a >> 3) + (a & 0x7);
    a = (a >> 3) + (a & 0x7);
    if (a < 7) return a;
    return a - 7;
}

answered Jun 08 '17 at 03:41

quentin-starin

101

You have needlessly duplicated the line a = (a >> 3) + (a & 0x7); The second line does nothing, so you can delete it. (And then, I think, you can delete the whole question.) – TonyK Jun 08 '17 at 12:00
1

Seriously, delete the question? The second duplicate line appears necessary. Feel free to verify on 1658656468 or 2147483647 or 18446744073709551614 or many others. – quentin-starin Jun 08 '17 at 19:07

Calculating modulo of 7 using bitshift and addition

1 Answers1