Click here to Skip to main content
15,616,432 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 
GeneralRe: Unit testing Pin
Sander Rossel14-Aug-12 19:37
professionalSander Rossel14-Aug-12 19:37 
GeneralRe: Unit testing Pin
patbob15-Aug-12 7:47
patbob15-Aug-12 7:47 
GeneralRe: Unit testing Pin
R. Erasmus13-Aug-12 21:14
R. Erasmus13-Aug-12 21:14 
GeneralRe: Unit testing Pin
RafagaX14-Aug-12 7:01
professionalRafagaX14-Aug-12 7:01 
GeneralRe: Unit testing Pin
cmger14-Aug-12 1:58
cmger14-Aug-12 1:58 
GeneralRe: Unit testing Pin
Matt McGuire15-Aug-12 7:37
professionalMatt McGuire15-Aug-12 7:37 
GeneralRe: Unit testing Pin
jschell18-Aug-12 4:24
jschell18-Aug-12 4:24 
GeneralDivisibility and modular multiplication PinPopular
harold aptroot13-Aug-12 2:07
harold aptroot13-Aug-12 2:07 
Typically, all computer math is done modulo 232 (or 2something, which the rest of my post trivially generalizes to). This leads to sometimes surprising effects, such as that the sum of a and b, while both positive, can end up being lower than min(a, b), which is rather well-known. Less well known is that it also means that some numbers have a multiplicative inverse[^], ie a number x<sup>-1</sup> such that x<sup>-1</sup>x=1. As mentioned in the wikipedia article, the numbers which have multiplicative inverses are precisely those coprime to the modulo. The modulo is a power of two, which means that a number has a multiplicative inverse iff it is odd.

And it turns out to be actually useful, too. One application is, as you might guess from the title, divisibility testing.

Multiplying a number by an odd number is reversible - you can take the multiplicative inverse of the odd number and then multiply by it to get the original number back. Put differently, the function f(x) = x * k (for k odd) is a bijection.

Modular multiplication is associative, so a multiple of k, say n * k multiplied by inv(k) (the multiplicative inverse of k), is n, because
(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
n

That means that in x * inv(k), the multiples of k "use up" the results from 0 through (232-1)/k, they can't be used twice because it's a bijection, leaving just the numbers bigger than (232-1)/k for non-multiples-of-k. Which suggest a very simple divisibility test:
C#
static bool IsDivisibleByOdd(uint x, uint divisor)
{
    if ((divisor & 1) == 0)
        throw new ArgumentException("divisor must be odd");
    uint d_inv = inv(divisor);
    uint biggest = uint.MaxValue / divisor;  // problem right here
    return (x * d_inv) <= biggest;
}

static uint inv(uint d)
{
    // see Hacker's Delight,
    // Computing the Multiplicative Inverse by Newton's Method
    // use extra iteration when extending to 64 bits
    uint x = (d * d) + d - 1;
    uint t = d * x;
    x *= 2 - t;
    t = d * x;
    x *= 2 - t;
    t = d * x;
    x *= 2 - t;
    return x;
}

And there is a problem. It didn't avoid the division, it turned it into an other division. So this doesn't actually help - in fact it's slower than the usual way.

It also fails to work when the divisor is 1 (but that's a silly thing to ask of it anyway).

But. And there is a but. If you want to test for a lot of number whether they are divisible by some odd number1 that doesn't vary in that test (but isn't a constant2), you only have one division, one inv, and the cost per item is only a multiplication and a test. What's more, no compiler I know of automatically does this for you, so this can actually save time.

1. the principle is extendible to even numbers (except zero, of course) as well - shift it right by the number of trailing zeroes and shift left by the same amount after the multiplication. This also means it won't work for powers of two (which would become 1 after the shift), but of course for powers of two there is an even faster way anyway. Unfortunately, C# lacks _BitScanforward[^] or a replacement, making the algorithm "less nice" if it has to account for even numbers.
2. otherwise the compiler would optimize it anyway and you'd gain nothing.

ps: perhaps I should start a blog instead of dumping things like this in the Lounge every week..
edit: this post has been bloggified: http://bitmath.blogspot.com/2012/09/divisibility-and-modular-multiplication.html[^]
GeneralRe: Divisibility and modular multiplication Pin
Kenneth Haugland13-Aug-12 2:11
professionalKenneth Haugland13-Aug-12 2:11 
GeneralRe: Divisibility and modular multiplication Pin
NormDroid13-Aug-12 2:18
professionalNormDroid13-Aug-12 2:18 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 2:19
harold aptroot13-Aug-12 2:19 
GeneralRe: Divisibility and modular multiplication Pin
NormDroid13-Aug-12 2:33
professionalNormDroid13-Aug-12 2:33 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 2:45
harold aptroot13-Aug-12 2:45 
GeneralRe: Divisibility and modular multiplication Pin
AspDotNetDev13-Aug-12 6:43
protectorAspDotNetDev13-Aug-12 6:43 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 6:58
harold aptroot13-Aug-12 6:58 
GeneralRe: Divisibility and modular multiplication Pin
AspDotNetDev13-Aug-12 7:16
protectorAspDotNetDev13-Aug-12 7:16 
GeneralRe: Divisibility and modular multiplication Pin
wout de zeeuw13-Aug-12 7:40
wout de zeeuw13-Aug-12 7:40 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 7:51
harold aptroot13-Aug-12 7:51 
GeneralRe: Divisibility and modular multiplication Pin
Sentenryu14-Aug-12 0:54
Sentenryu14-Aug-12 0:54 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot19-Aug-12 5:09
harold aptroot19-Aug-12 5:09 
GeneralGoogle, M$ and Obama .. Pin
UBX13-Aug-12 1:49
UBX13-Aug-12 1:49 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 1:52
subeditorPete O'Hanlon13-Aug-12 1:52 
GeneralRe: Google, M$ and Obama .. Pin
JimmyRopes13-Aug-12 1:56
professionalJimmyRopes13-Aug-12 1:56 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 2:09
subeditorPete O'Hanlon13-Aug-12 2:09 
JokeRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 3:21
enhzflep13-Aug-12 3:21 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.