13,252,206 members (56,920 online)

# Welcome to the Lounge

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.

 Re: Unit testing CodeBubba15-Aug-12 3:39 CodeBubba 15-Aug-12 3:39
 Re: Unit testing Naerling13-Aug-12 20:38 Naerling 13-Aug-12 20:38
 Re: Unit testing Slacker00714-Aug-12 1:15 Slacker007 14-Aug-12 1:15
 Re: Unit testing CodeBubba14-Aug-12 11:04 CodeBubba 14-Aug-12 11:04
 Re: Unit testing Naerling14-Aug-12 12:10 Naerling 14-Aug-12 12:10
 Re: Unit testing CodeBubba14-Aug-12 13:05 CodeBubba 14-Aug-12 13:05
 Re: Unit testing Naerling14-Aug-12 20:37 Naerling 14-Aug-12 20:37
 Re: Unit testing patbob15-Aug-12 8:47 patbob 15-Aug-12 8:47
 Re: Unit testing R. Erasmus13-Aug-12 22:14 R. Erasmus 13-Aug-12 22:14
 Re: Unit testing RafagaX14-Aug-12 8:01 RafagaX 14-Aug-12 8:01
 Re: Unit testing cmger14-Aug-12 2:58 cmger 14-Aug-12 2:58
 Re: Unit testing Matt McGuire15-Aug-12 8:37 Matt McGuire 15-Aug-12 8:37
 Re: Unit testing jschell18-Aug-12 5:24 jschell 18-Aug-12 5:24
 Divisibility and modular multiplication harold aptroot13-Aug-12 3:07 harold aptroot 13-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-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: ```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 3:11 Kenneth Haugland 13-Aug-12 3:11
 Re: Divisibility and modular multiplication Norm .net13-Aug-12 3:18 Norm .net 13-Aug-12 3:18
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 3:19 harold aptroot 13-Aug-12 3:19
 Re: Divisibility and modular multiplication Norm .net13-Aug-12 3:33 Norm .net 13-Aug-12 3:33
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 3:45 harold aptroot 13-Aug-12 3:45
 Re: Divisibility and modular multiplication AspDotNetDev13-Aug-12 7:43 AspDotNetDev 13-Aug-12 7:43
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 7:58 harold aptroot 13-Aug-12 7:58
 Re: Divisibility and modular multiplication AspDotNetDev13-Aug-12 8:16 AspDotNetDev 13-Aug-12 8:16
 Re: Divisibility and modular multiplication wout de zeeuw13-Aug-12 8:40 wout de zeeuw 13-Aug-12 8:40
 Re: Divisibility and modular multiplication harold aptroot13-Aug-12 8:51 harold aptroot 13-Aug-12 8:51
 Re: Divisibility and modular multiplication Sentenryu14-Aug-12 1:54 Sentenryu 14-Aug-12 1:54
 Re: Divisibility and modular multiplication harold aptroot19-Aug-12 6:09 harold aptroot 19-Aug-12 6:09
 Google, M\$ and Obama .. UBX13-Aug-12 2:49 UBX 13-Aug-12 2:49
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 2:52 Pete O'Hanlon 13-Aug-12 2:52
 Re: Google, M\$ and Obama .. JimmyRopes13-Aug-12 2:56 JimmyRopes 13-Aug-12 2:56
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 3:09 Pete O'Hanlon 13-Aug-12 3:09
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 4:21 enhzflep 13-Aug-12 4:21
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 4:24 Pete O'Hanlon 13-Aug-12 4:24
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 5:27 enhzflep 13-Aug-12 5:27
 Re: Google, M\$ and Obama .. James Lonero14-Aug-12 19:20 James Lonero 14-Aug-12 19:20
 Re: Google, M\$ and Obama .. harold aptroot13-Aug-12 6:49 harold aptroot 13-Aug-12 6:49
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 6:51 enhzflep 13-Aug-12 6:51
 Re: Google, M\$ and Obama .. harold aptroot13-Aug-12 6:52 harold aptroot 13-Aug-12 6:52
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 7:00 enhzflep 13-Aug-12 7:00
 Re: Google, M\$ and Obama .. harold aptroot13-Aug-12 7:02 harold aptroot 13-Aug-12 7:02
 Re: Google, M\$ and Obama .. enhzflep13-Aug-12 7:17 enhzflep 13-Aug-12 7:17
 Re: Google, M\$ and Obama .. JimmyRopes13-Aug-12 4:25 JimmyRopes 13-Aug-12 4:25
 Re: Google, M\$ and Obama .. ChrisElston13-Aug-12 3:14 ChrisElston 13-Aug-12 3:14
 Re: Google, M\$ and Obama .. Andrei Straut13-Aug-12 4:54 Andrei Straut 13-Aug-12 4:54
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 5:03 Pete O'Hanlon 13-Aug-12 5:03
 Re: Google, M\$ and Obama .. Andrei Straut13-Aug-12 5:07 Andrei Straut 13-Aug-12 5:07
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 5:11 Pete O'Hanlon 13-Aug-12 5:11
 Re: Google, M\$ and Obama .. Andrei Straut13-Aug-12 5:30 Andrei Straut 13-Aug-12 5:30
 Re: Google, M\$ and Obama .. Mike Hankey13-Aug-12 6:19 Mike Hankey 13-Aug-12 6:19
 Re: Google, M\$ and Obama .. Nemanja Trifunovic13-Aug-12 3:38 Nemanja Trifunovic 13-Aug-12 3:38
 Re: Google, M\$ and Obama .. Pete O'Hanlon13-Aug-12 3:45 Pete O'Hanlon 13-Aug-12 3:45
 Last Visit: 31-Dec-99 19:00     Last Update: 20-Nov-17 17:44 Refresh « Prev1...7960796179627963796479657966796779687969 Next »