

Will Rogers never met me.





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.





I asked my wife, and she said: "There's no word for it, that's just how things are."
Be excellent to each other. And... PARTY ON, DUDES!
Abraham Lincoln






This is a fascinating topic, thanks, Harold, another example to me of a Lounge post that I think should be "hoisted" out of the Lounge, and preserved for posterity in some form in some other archival forum ... I'm not implying it should not remain on the Lounge, though.
Unfortunately, I'm too dumb to follow your mathematical analysis.
re: Ron Beyer's code example:
Assuming a random distribution of an infinite dataset of integers, the aleph of the infinity of numbers ending in five should have an aleph (ordinality) twice the aleph of the numbers ending in zero.
So, given the C# compilerproduced code will not evaluate beyond the first term of an  expression, if the first term evaluates to 'true, there should be a theoretical benefit by checking for last digit == "5" first ?
It would be interesting to see someone actually carry out a test using .NET C#.
yours, Bill
“Human beings do not live in the objective world alone, nor alone in the world of social activity as ordinarily understood, but are very much at the mercy of the particular language which has become the medium of expression for their society. It is quite an illusion to imagine that one adjusts to reality essentially without the use of language and that language is merely an incidental means of solving specific problems of communication or reflection." Edward Sapir, 1929





BillWoodruff wrote: So, given the C# compilerproduced code will not evaluate beyond the first term
of an  expression, if the first term evaluates to 'true, there should be a
theoretical benefit by checking for last digit == "5" first ?
No  all numerical values are stored in BINARY notation, so you have no 'Digit 5' to whom you could compare.
To accomplish this, you would have to do a MOD(10) calculation, to get the last DECIMAL digit.
Bacause of this you could do the MOD(5) in the first place.
A MOD() Operation is a Division, and is therefore (AFAIK) MUCH slower than a multiplication





Hi Klaus,
You are misinterpreting what I said: I spoke only of the circumstance where the programmer has implemented a string comparison with the strings "0" and "5" shown in the responses of _Maxxx_ and Byer, on this thread.
Of course, under the hood, everything at runtime some is distilled down to CIL, and opcodes, and binarysomething, jitted into executable code per .NET FrameWork/os version/hardware 32~64/cpu.
Personally, I would not choose to use .ToString(), and a string comparison in a case like this; I'd study what Harold said, and try to understand it
As for the ordinality of aleph's, well ... thinking about that was what drove both Cantor and Godel insane, for keeps, wasn't it.
yours, Bill
“Human beings do not live in the objective world alone, nor alone in the world of social activity as ordinarily understood, but are very much at the mercy of the particular language which has become the medium of expression for their society. It is quite an illusion to imagine that one adjusts to reality essentially without the use of language and that language is merely an incidental means of solving specific problems of communication or reflection." Edward Sapir, 1929





BillWoodruff wrote: Assuming a random distribution of an infinite dataset of integers, the aleph of the infinity of numbers ending in five should have an aleph (ordinality) twice the aleph of the numbers ending in zero.
I don't see how you come up with that conclusion. Wouldn't the aleph of the infinity of numbers ending in 5 be equal to the aleph of the infinity of numbers ending in zero, which itself is aleph zero (or aleph null, if you were taught using that term)? There's a onetoone relation between N and the above (N * 10 + 5 for numbers ending in 5, and N * 10 for numbers ending in 0).
AR





var c = number.ToString().ToCharArray();
return "01".IndexOf(c[c.Length1]) >= 0;
If your actions inspire others to dream more, learn more, do more and become more, you are a leader.John Q. Adams You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering.Wernher von Braun Only two things are infinite, the universe and human stupidity, and I'm not sure about the former.Albert Einstein





Sorry Ahmed, that code will not work to discriminate integers divisible by int #5 without remainder, but an interesting use of FrameWork 4.5 syntax. Your code will return 'true for numbers like #1001, and false for numbers like #5.
I am happy to inform you that you have been promoted to Manager of our Advanced Technology Group, starting immediately
yours, Bill
“Human beings do not live in the objective world alone, nor alone in the world of social activity as ordinarily understood, but are very much at the mercy of the particular language which has become the medium of expression for their society. It is quite an illusion to imagine that one adjusts to reality essentially without the use of language and that language is merely an incidental means of solving specific problems of communication or reflection." Edward Sapir, 1929





Ron Beyer wrote: Just hope that number is a whole number
Well obviously you'd just do something like this:
if (s.IndexOf(".") > 0 && s.IndexOf(".") != s.Length  1)
{
return false;
}





5.0 would return false






I'm sure it's just a joke  but for some (and I've seen these guys' code before) who might think it a good idea.
Since the act of converting to string in decimal is probably also using multiple mod 10's. If so not even the unequal mod optimization's possible, not to mention it would do one mod for each decimal digit (instead of only one mod 5). So before you can even compare the last character to "5" or "0" you've already made the code run a lot slower just to get to that point, never mind fractions.





harold aptroot wrote: The real point is, the obligatory "you can't beat the compiler" comment was made.
Been a long time since I cared what the compiler does. But then it has been a long time since I worked on anything even close to a stand alone small application.
Performance issues on big systems never resolve to small bottlenecks  or at least not in my code.





Then the compiler will be good enough, as usual, and none of this matters
Still, the comment was actually wrong in this case, so I had to do my duty[^]





