12,825,921 members (35,192 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: Thank God It Didn't Go Off! Mike Mullikin15-Jun-13 9:25 Mike Mullikin 15-Jun-13 9:25
 Re: Thank God It Didn't Go Off! Mark_Wallace17-Jun-13 4:19 Mark_Wallace 17-Jun-13 4:19
 Re: Thank God It Didn't Go Off! Marc A. Brown17-Jun-13 4:18 Marc A. Brown 17-Jun-13 4:18
 Re: Thank God It Didn't Go Off! Mark_Wallace17-Jun-13 4:25 Mark_Wallace 17-Jun-13 4:25
 Re: Thank God It Didn't Go Off! Marc A. Brown17-Jun-13 7:45 Marc A. Brown 17-Jun-13 7:45
 Re: Thank God It Didn't Go Off! Marc A. Brown17-Jun-13 4:15 Marc A. Brown 17-Jun-13 4:15
 Re: Thank God It Didn't Go Off! Roger Wright17-Jun-13 19:24 Roger Wright 17-Jun-13 19:24
 Beating the compiler harold aptroot14-Jun-13 12:29 harold aptroot 14-Jun-13 12:29
 There was a question on That Other Site about checking for divisibility by 5 without using the % or / operators, and it had to be as fast as possible.In proper "That Other Site"-style, the question was immediately closed for not including anything the OP tried, but had the OP done that, I'm sure the OP would have been lambasted for premature optimization.But whatever. The real point is, the obligatory "you can't beat the compiler" comment was made.And that turns out to be wrong - here[^]'s the proof. apparently that link doesn't work. Nice job implementing permalinks there. Well just paste this code into this[^]:```#include bool divisible_by_5(uint32_t x) { return x % 5 == 0; } bool divisible_by_5_fast(uint32_t x) { return x * 0xCCCCCCCD <= 0x33333333; }```Be sure to set at least -O1.But wait, is that really equivalent?Actually yes. I've posted about that before, as you may recall.In arithmetic modulo 2n, 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.So it's proven, and for good measure I tried it for all x just to be absolutely certain.0xCCCCCCCD is, of course, the multiplicative inverse of 5 (modulo 232) and 0x33333333 is (232 - 1)/5So there, the compiler has been beaten, once again disproving the "the Compiler is a God"-theory. It does use a closely related trick, namely dividing by 5 without a division (then it multiplies by 5 and compares that to the input), and that trick is pretty good too. Compilers are good - putting blind faith in them is not.modified 15-Jun-13 6:15am.
 Re: Beating the compiler _Maxxx_14-Jun-13 12:47 _Maxxx_ 14-Jun-13 12:47
 Re: Beating the compiler Ron Beyer14-Jun-13 13:00 Ron Beyer 14-Jun-13 13:00
 Re: Beating the compiler Big Daddy Farang14-Jun-13 13:06 Big Daddy Farang 14-Jun-13 13:06
 Re: Beating the compiler Ron Beyer14-Jun-13 13:17 Ron Beyer 14-Jun-13 13:17
 Re: Beating the compiler Big Daddy Farang14-Jun-13 13:20 Big Daddy Farang 14-Jun-13 13:20
 Re: Beating the compiler _Maxxx_14-Jun-13 14:09 _Maxxx_ 14-Jun-13 14:09
 Re: Beating the compiler Ron Beyer14-Jun-13 14:14 Ron Beyer 14-Jun-13 14:14
 Re: Beating the compiler jschell17-Jun-13 9:29 jschell 17-Jun-13 9:29
 Re: Beating the compiler Ron Beyer17-Jun-13 9:36 Ron Beyer 17-Jun-13 9:36
 Re: Beating the compiler PIEBALDconsult14-Jun-13 17:42 PIEBALDconsult 14-Jun-13 17:42
 Re: Beating the compiler BillWoodruff14-Jun-13 21:39 BillWoodruff 14-Jun-13 21:39
 Re: Beating the compiler BillWoodruff15-Jun-13 16:57 BillWoodruff 15-Jun-13 16:57
 Re: Beating the compiler A. A. J. Rodriguez17-Jun-13 4:33 A. A. J. Rodriguez 17-Jun-13 4:33
 Re: Beating the compiler ahmed zahmed16-Jun-13 7:18 ahmed zahmed 16-Jun-13 7:18
 Re: Beating the compiler BillWoodruff16-Jun-13 16:21 BillWoodruff 16-Jun-13 16:21
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Mar-17 7:47 Refresh « Prev1...11131111321113311134111351113611137111381113911140 Next »