Click here to Skip to main content
12,070,248 members (28,749 online)

Welcome to the Lounge

   

For lazing about and discussing anything in a software developer's life that takes your fancy except programming questions.

Technical discussions are encouraged, but click here to ask your programming question.

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: Thank God It Didn't Go Off! Pin
Mike Mullikin15-Jun-13 9:25
professionalMike Mullikin15-Jun-13 9:25 
GeneralRe: Thank God It Didn't Go Off! Pin
Mark_Wallace17-Jun-13 4:19
memberMark_Wallace17-Jun-13 4:19 
GeneralRe: Thank God It Didn't Go Off! Pin
Marc A. Brown17-Jun-13 4:18
memberMarc A. Brown17-Jun-13 4:18 
GeneralRe: Thank God It Didn't Go Off! Pin
Mark_Wallace17-Jun-13 4:25
memberMark_Wallace17-Jun-13 4:25 
GeneralRe: Thank God It Didn't Go Off! Pin
Marc A. Brown17-Jun-13 7:45
memberMarc A. Brown17-Jun-13 7:45 
GeneralRe: Thank God It Didn't Go Off! Pin
Marc A. Brown17-Jun-13 4:15
memberMarc A. Brown17-Jun-13 4:15 
GeneralRe: Thank God It Didn't Go Off! Pin
Roger Wright17-Jun-13 19:24
memberRoger Wright17-Jun-13 19:24 
GeneralBeating the compiler Pin
harold aptroot14-Jun-13 12:29
memberharold aptroot14-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 <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 Pin
_Maxxx_14-Jun-13 12:47
member_Maxxx_14-Jun-13 12:47 
GeneralRe: Beating the compiler Pin
Ron Beyer14-Jun-13 13:00
professionalRon Beyer14-Jun-13 13:00 
GeneralRe: Beating the compiler Pin
Big Daddy Farang14-Jun-13 13:06
memberBig Daddy Farang14-Jun-13 13:06 
GeneralRe: Beating the compiler Pin
Ron Beyer14-Jun-13 13:17
professionalRon Beyer14-Jun-13 13:17 
GeneralRe: Beating the compiler Pin
Big Daddy Farang14-Jun-13 13:20
memberBig Daddy Farang14-Jun-13 13:20 
GeneralRe: Beating the compiler Pin
_Maxxx_14-Jun-13 14:09
member_Maxxx_14-Jun-13 14:09 
GeneralRe: Beating the compiler Pin
Ron Beyer14-Jun-13 14:14
professionalRon Beyer14-Jun-13 14:14 
GeneralRe: Beating the compiler Pin
jschell17-Jun-13 9:29
memberjschell17-Jun-13 9:29 
GeneralRe: Beating the compiler Pin
Ron Beyer17-Jun-13 9:36
professionalRon Beyer17-Jun-13 9:36 
GeneralRe: Beating the compiler Pin
Jörgen Andersson15-Jun-13 9:03
professionalJörgen Andersson15-Jun-13 9:03 
GeneralRe: Beating the compiler Pin
PIEBALDconsult14-Jun-13 17:42
professionalPIEBALDconsult14-Jun-13 17:42 
GeneralRe: Beating the compiler Pin
BillWoodruff14-Jun-13 21:39
memberBillWoodruff14-Jun-13 21:39 
GeneralRe: Beating the compiler Pin
Klaus-Werner Konrad15-Jun-13 13:07
memberKlaus-Werner Konrad15-Jun-13 13:07 
GeneralRe: Beating the compiler Pin
BillWoodruff15-Jun-13 16:57
memberBillWoodruff15-Jun-13 16:57 
GeneralRe: Beating the compiler Pin
A. A. J. Rodriguez17-Jun-13 4:33
memberA. A. J. Rodriguez17-Jun-13 4:33 
GeneralRe: Beating the compiler Pin
ahmed zahmed16-Jun-13 7:18
memberahmed zahmed16-Jun-13 7:18 
GeneralRe: Beating the compiler Pin
BillWoodruff16-Jun-13 16:21
memberBillWoodruff16-Jun-13 16:21 

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 | Mobile
Web01 | 2.8.160208.1 | Last Updated 9 Feb 2016
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid