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.



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 2^{n}, 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) =
n * (k * inv(k)) =
n * 1 =
n
That means that in x * inv(k), the multiples of k "use up" the results from 0 through (2^{32}1)/k, they can't be used twice because it's a bijection, leaving just the numbers bigger than (2^{32}1)/k for nonmultiplesofk.
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 2^{32}) and 0x33333333 is (2^{32}  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 15Jun13 6:15am.





I'd have done
String s = number.ToString();
s=s.substring(s.Length1);
return (s=="0"  s=="5")
But then I am entering the omgwtf coding competition
MVVM #  I did it My Way
___________________________________________
Man, you're a god.  walterhevedeich 26/05/2011
.\\axxx
(That's an 'M')





String s = number.ToString();
return (s[s.Length1]=="0"  s[s.Length1]=="5")
Even faster due to no substring Just hope that number is a whole number, not a decimal otherwise 9.5 is a multiple of 5...





Ron Beyer wrote: hope that number is a whole number
I wonder if you could determine that by the type of number.
BDF
The internet makes dumb people dumber and clever people cleverer.
 PaulowniaK





Or you could just explicitly cast it to one.





That sounds like cheating to me.
Could we come up with a more pointless conversation if we tried?
BDF
The internet makes dumb people dumber and clever people cleverer.
 PaulowniaK





Yes! Although increasing the performance on such a twaddle piece of code is  hmm there must be a name for it? optimising something that is just plain wrong? I bet the germans have a word!
MVVM #  I did it My Way
___________________________________________
Man, you're a god.  walterhevedeich 26/05/2011
.\\axxx
(That's an 'M')





Check to see if a million numbers are a multiple of 5, you'll take every optimization you can get





Ron Beyer wrote:
Check to see if a million numbers are a multiple
of 5, you'll take every optimization you can get
What language and/or platform do you think that would be a problem on?
And how long do you think it would take?





The point isn't this particular piece of code, its the comment about optimizing a short piece of code. Just because the code is short, doesn't mean it isn't expensive. String operations can be very expensive, especially in languages that intern strings. Even if this was written in assembly optimization isn't something that should be ignored because the code is trivial.







General News Suggestion Question Bug Answer Joke Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.