Click here to Skip to main content

Welcome to the Lounge

   

For lazing about and discussing anything in a software developer's life that takes your fancy.
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 and please don't post ads.

Technical discussions are welcome, but if you need specific help please use the programming forums.


 
GeneralRe: Thank God It Didn't Go Off! PinprofessionalMike Mullikin15-Jun-13 8:25 
GeneralRe: Thank God It Didn't Go Off! PinmemberMark_Wallace17-Jun-13 3:19 
GeneralRe: Thank God It Didn't Go Off! PinmemberMarc A. Brown17-Jun-13 3:18 
GeneralRe: Thank God It Didn't Go Off! PinmemberMark_Wallace17-Jun-13 3:25 
GeneralRe: Thank God It Didn't Go Off! PinmemberMarc A. Brown17-Jun-13 6:45 
GeneralRe: Thank God It Didn't Go Off! PinmemberMarc A. Brown17-Jun-13 3:15 
GeneralRe: Thank God It Didn't Go Off! PinmemberRoger Wright17-Jun-13 18:24 
GeneralBeating the compiler [modified] Pinmemberharold aptroot14-Jun-13 11: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 <stdint.h>
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)/5
 
So 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.

GeneralRe: Beating the compiler Pinmember_Maxxx_14-Jun-13 11:47 
GeneralRe: Beating the compiler PinprofessionalRon Beyer14-Jun-13 12:00 
GeneralRe: Beating the compiler PinmemberBig Daddy Farang14-Jun-13 12:06 
GeneralRe: Beating the compiler PinprofessionalRon Beyer14-Jun-13 12:17 
GeneralRe: Beating the compiler PinmemberBig Daddy Farang14-Jun-13 12:20 
GeneralRe: Beating the compiler Pinmember_Maxxx_14-Jun-13 13:09 
GeneralRe: Beating the compiler PinprofessionalRon Beyer14-Jun-13 13:14 
GeneralRe: Beating the compiler Pinmemberjschell17-Jun-13 8:29 
GeneralRe: Beating the compiler PinprofessionalRon Beyer17-Jun-13 8:36 
GeneralRe: Beating the compiler PinprofessionalJörgen Andersson15-Jun-13 8:03 
GeneralRe: Beating the compiler PinprofessionalPIEBALDconsult14-Jun-13 16:42 
GeneralRe: Beating the compiler PinmemberBillWoodruff14-Jun-13 20:39 
GeneralRe: Beating the compiler PinmemberKlaus-Werner Konrad15-Jun-13 12:07 
GeneralRe: Beating the compiler PinmemberBillWoodruff15-Jun-13 15:57 
GeneralRe: Beating the compiler PinmemberA. A. J. Rodriguez17-Jun-13 3:33 
GeneralRe: Beating the compiler Pinmemberahmed zahmed16-Jun-13 6:18 
GeneralRe: Beating the compiler PinmemberBillWoodruff16-Jun-13 15:21 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    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 | Mobile
Web01 | 2.8.140827.1 | Last Updated 28 Aug 2014
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid