Click here to Skip to main content
13,252,206 members (56,920 online)

Welcome to the Lounge

   

For discussing anything related to a software developer's life. Technical discussions are encouraged, but click here to ask your programming questions.

The Lounge is rated PG. If you're about to post something you wouldn't want your kid sister to read then don't post it. No flame wars, no abusive conduct, no programming questions and please don't post ads.
 
GeneralRe: Unit testing Pin
CodeBubba15-Aug-12 3:39
memberCodeBubba15-Aug-12 3:39 
GeneralRe: Unit testing Pin
Naerling13-Aug-12 20:38
memberNaerling13-Aug-12 20:38 
GeneralRe: Unit testing Pin
Slacker00714-Aug-12 1:15
memberSlacker00714-Aug-12 1:15 
GeneralRe: Unit testing Pin
CodeBubba14-Aug-12 11:04
memberCodeBubba14-Aug-12 11:04 
GeneralRe: Unit testing Pin
Naerling14-Aug-12 12:10
memberNaerling14-Aug-12 12:10 
GeneralRe: Unit testing Pin
CodeBubba14-Aug-12 13:05
memberCodeBubba14-Aug-12 13:05 
GeneralRe: Unit testing Pin
Naerling14-Aug-12 20:37
memberNaerling14-Aug-12 20:37 
GeneralRe: Unit testing Pin
patbob15-Aug-12 8:47
memberpatbob15-Aug-12 8:47 
GeneralRe: Unit testing Pin
R. Erasmus13-Aug-12 22:14
memberR. Erasmus13-Aug-12 22:14 
GeneralRe: Unit testing Pin
RafagaX14-Aug-12 8:01
memberRafagaX14-Aug-12 8:01 
GeneralRe: Unit testing Pin
cmger14-Aug-12 2:58
membercmger14-Aug-12 2:58 
GeneralRe: Unit testing Pin
Matt McGuire15-Aug-12 8:37
memberMatt McGuire15-Aug-12 8:37 
GeneralRe: Unit testing Pin
jschell18-Aug-12 5:24
memberjschell18-Aug-12 5:24 
GeneralDivisibility and modular multiplication Pin
harold aptroot13-Aug-12 3:07
memberharold aptroot13-Aug-12 3: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:
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 3:11
memberKenneth Haugland13-Aug-12 3:11 
GeneralRe: Divisibility and modular multiplication Pin
Norm .net13-Aug-12 3:18
groupNorm .net13-Aug-12 3:18 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 3:19
memberharold aptroot13-Aug-12 3:19 
GeneralRe: Divisibility and modular multiplication Pin
Norm .net13-Aug-12 3:33
groupNorm .net13-Aug-12 3:33 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 3:45
memberharold aptroot13-Aug-12 3:45 
GeneralRe: Divisibility and modular multiplication Pin
AspDotNetDev13-Aug-12 7:43
protectorAspDotNetDev13-Aug-12 7:43 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 7:58
memberharold aptroot13-Aug-12 7:58 
GeneralRe: Divisibility and modular multiplication Pin
AspDotNetDev13-Aug-12 8:16
protectorAspDotNetDev13-Aug-12 8:16 
GeneralRe: Divisibility and modular multiplication Pin
wout de zeeuw13-Aug-12 8:40
memberwout de zeeuw13-Aug-12 8:40 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot13-Aug-12 8:51
memberharold aptroot13-Aug-12 8:51 
GeneralRe: Divisibility and modular multiplication Pin
Sentenryu14-Aug-12 1:54
memberSentenryu14-Aug-12 1:54 
GeneralRe: Divisibility and modular multiplication Pin
harold aptroot19-Aug-12 6:09
memberharold aptroot19-Aug-12 6:09 
GeneralGoogle, M$ and Obama .. Pin
UBX13-Aug-12 2:49
memberUBX13-Aug-12 2:49 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 2:52
protectorPete O'Hanlon13-Aug-12 2:52 
GeneralRe: Google, M$ and Obama .. Pin
JimmyRopes13-Aug-12 2:56
memberJimmyRopes13-Aug-12 2:56 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 3:09
protectorPete O'Hanlon13-Aug-12 3:09 
JokeRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 4:21
memberenhzflep13-Aug-12 4:21 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 4:24
protectorPete O'Hanlon13-Aug-12 4:24 
GeneralRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 5:27
memberenhzflep13-Aug-12 5:27 
GeneralRe: Google, M$ and Obama .. Pin
James Lonero14-Aug-12 19:20
memberJames Lonero14-Aug-12 19:20 
GeneralRe: Google, M$ and Obama .. Pin
harold aptroot13-Aug-12 6:49
memberharold aptroot13-Aug-12 6:49 
GeneralRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 6:51
memberenhzflep13-Aug-12 6:51 
GeneralRe: Google, M$ and Obama .. Pin
harold aptroot13-Aug-12 6:52
memberharold aptroot13-Aug-12 6:52 
GeneralRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 7:00
memberenhzflep13-Aug-12 7:00 
GeneralRe: Google, M$ and Obama .. Pin
harold aptroot13-Aug-12 7:02
memberharold aptroot13-Aug-12 7:02 
GeneralRe: Google, M$ and Obama .. Pin
enhzflep13-Aug-12 7:17
memberenhzflep13-Aug-12 7:17 
GeneralRe: Google, M$ and Obama .. Pin
JimmyRopes13-Aug-12 4:25
memberJimmyRopes13-Aug-12 4:25 
GeneralRe: Google, M$ and Obama .. Pin
ChrisElston13-Aug-12 3:14
memberChrisElston13-Aug-12 3:14 
GeneralRe: Google, M$ and Obama .. Pin
Andrei Straut13-Aug-12 4:54
memberAndrei Straut13-Aug-12 4:54 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 5:03
protectorPete O'Hanlon13-Aug-12 5:03 
GeneralRe: Google, M$ and Obama .. Pin
Andrei Straut13-Aug-12 5:07
memberAndrei Straut13-Aug-12 5:07 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 5:11
protectorPete O'Hanlon13-Aug-12 5:11 
GeneralRe: Google, M$ and Obama .. Pin
Andrei Straut13-Aug-12 5:30
memberAndrei Straut13-Aug-12 5:30 
GeneralRe: Google, M$ and Obama .. Pin
Mike Hankey13-Aug-12 6:19
memberMike Hankey13-Aug-12 6:19 
GeneralRe: Google, M$ and Obama .. Pin
Nemanja Trifunovic13-Aug-12 3:38
memberNemanja Trifunovic13-Aug-12 3:38 
GeneralRe: Google, M$ and Obama .. Pin
Pete O'Hanlon13-Aug-12 3:45
protectorPete O'Hanlon13-Aug-12 3:45 

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.


Advertise | Privacy |
Web01 | 2.8.171114.1 | Last Updated 20 Nov 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid