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.

 Re: Unit testing Sander Rossel14-Aug-12 19:37 Sander Rossel 14-Aug-12 19:37
 Re: Unit testing patbob15-Aug-12 7:47 patbob 15-Aug-12 7:47
 Re: Unit testing R. Erasmus13-Aug-12 21:14 R. Erasmus 13-Aug-12 21:14
 Re: Unit testing RafagaX14-Aug-12 7:01 RafagaX 14-Aug-12 7:01
 Re: Unit testing cmger14-Aug-12 1:58 cmger 14-Aug-12 1:58
 Re: Unit testing Matt McGuire15-Aug-12 7:37 Matt McGuire 15-Aug-12 7:37
 Re: Unit testing jschell18-Aug-12 4:24 jschell 18-Aug-12 4:24
 Divisibility and modular multiplication harold aptroot13-Aug-12 2:07 harold aptroot 13-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-1` such that `x-1x=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[^]
 Re: Divisibility and modular multiplication Kenneth Haugland13-Aug-12 2:11 Kenneth Haugland 13-Aug-12 2:11
 Re: Divisibility and modular multiplication NormDroid13-Aug-12 2:18 NormDroid 13-Aug-12 2:18
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 2:19 harold aptroot 13-Aug-12 2:19
 Re: Divisibility and modular multiplication NormDroid13-Aug-12 2:33 NormDroid 13-Aug-12 2:33
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 2:45 harold aptroot 13-Aug-12 2:45
 Re: Divisibility and modular multiplication AspDotNetDev13-Aug-12 6:43 AspDotNetDev 13-Aug-12 6:43
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 6:58 harold aptroot 13-Aug-12 6:58
 Re: Divisibility and modular multiplication AspDotNetDev13-Aug-12 7:16 AspDotNetDev 13-Aug-12 7:16
 Re: Divisibility and modular multiplication wout de zeeuw13-Aug-12 7:40 wout de zeeuw 13-Aug-12 7:40
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 7:51 harold aptroot 13-Aug-12 7:51
 Re: Divisibility and modular multiplication Sentenryu14-Aug-12 0:54 Sentenryu 14-Aug-12 0:54
 Re: Divisibility and modular multiplication harold aptroot19-Aug-12 5:09 harold aptroot 19-Aug-12 5:09
 Google, M\$ and Obama .. UBX13-Aug-12 1:49 UBX 13-Aug-12 1:49
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 1:52 Pete O'Hanlon 13-Aug-12 1:52
 Re: Google, M\$ and Obama .. JimmyRopes13-Aug-12 1:56 JimmyRopes 13-Aug-12 1:56
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 2:09 Pete O'Hanlon 13-Aug-12 2:09
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 3:21 enhzflep 13-Aug-12 3:21
 Last Visit: 31-Dec-99 18:00     Last Update: 31-Mar-23 9:57 Refresh ᐊ Prev1...24248242492425024251242522425324254242552425624257 Next ᐅ