I would be much more impressed if I hadn't taken a compilers course. I reckon (god alone knows exactly what GCC does) this is just linear induction variable substitution[1] (so `x` gets replace with `i*2`), then associativity of integer multiplication, then some (probably builtin) rule that `n%n` is always 0. From there, it is pretty straightforward.
Don't get me wrong - the devil is in the details and getting optimizations that are both powerful and only applied when they are valid, and at the right time is difficult as hell. That said, I do expect compilers to be at least this smart.
[1]: https://en.wikipedia.org/wiki/Induction_variable#Induction_v...
Does anyone know if, internally, compilers second-guess / double-check themselves ? For instance, when they detect a clever shortcut do they generate and quickly run [1] the optimized bytecode on a sampling of inputs to verify it is functionally-equivalent to what non-optimized bytecode outputs ?
[1] obviously cross-compilers are a thing, so this wouldn't be possible if it were compiling/optimizing for a separate architecture.
No. Optimization transformations are generally expected to result in provably identically-functional code (or sufficiently identical, in case of e.g. floating-point optimizations). Otherwise it is a bug.
There are people who do do more exhaustive checks of the peephole optimizations for correctness--or finding new opportunities (see John Regehr's Souper work). But production compilers are well-known (at least by anyone who works on them) for having lots of bugs in these kinds of optimizations.
Is this quite right? It's not true in general that (a * b) % c = a * (b % c). E.g. it's not true for 2,3,4. The relevant generalization is that (a * b) % b = 0, which has nothing to do with associativity.
Now here's a more efficient algorithm which does produce the currect result:
int square(int num) {
int a = 0;
for (int x = 1, n = num; x <= num; x+=x, n+=n) {
if( num & x) {
a += n;
}
}
return a;
}
http://mathandmultimedia.com/2010/09/15/sum-first-n-positive...
magic constants galore... where does 3435973837 come from? ;)
if (num <= 0) {
return 0;
}
int a = 0;
int loop_n = (unsigned)(num - 1) / 5;
for (int x = 0; x <= loop_n; x++) {
a += x * 5 - 1;
}
return a;
From there you just have a summation, which has two components.
((loop_n + 1) * loop_n / 2) * 5 // 5x
- loop_n - 1 // -1
[edit] and playing around with the increment of x it keeps throwing in some magical values which are a repeating pattern in hex, with the LSB off by one usually...
0.CCCCCCCC.... = 4/5 had anything to do with it.
Using hexadecimal we have
5 * 3 = 10 - 1, so
5 * C = 40 - 4 so
5 * (1 + C + C0 + C00 + C000...) = 5 - 4 + 40 - 40 + 400... where the last term is = 0 mod 2^32
-----
D
0.CCCCCC.... = 4 / 5
So why would it take its digit from 4 / 5 and not 1 / 5? Because it takes x=4 to make the 5-x subtraction in 5 - x + x0 - x0 + x00 to come out to 1.
So this gives us a general rule for inversion (for numbers less than 16). Take the hexadecimal expansion of (n-1) / n, truncate to get enough hex chars, add 1 to the least significant hex digit.
I.e. the inversion of 3 would be 0xAAAAAAAB
square(int): # @square(int)
xor eax, eax
ret
From this we can see that gcc and clang have figured out that the "if" can never be true, then they elided the loop, then optimized out the variable, ending in the equivalent of "return 0;".
> Now remove the "!"
Also as pointed out elsewhere clang turns the "!" version into a simple equation in terms of n, so I'm actually kind of disappointed in GCC here.
Not sure if that's smart or stupid.
(1 * 5 * 9 * 13 * 17 * ...) * (2 * 6 * 10 * 14 * 18 * ...) * (3 * 7 * 11 * 15 * 19 * ...) * (4 * 8 * 12 * 16 * 20 * ...)
(it's not precisely that, but close enough)
It isn't optimal however, optimal code would be pre-computed results (signed integer overflow is undefined, so n <= 12 is defined)
(if signed integer overflow would be defined to be 2's complement overflow, you can still use a table, as n > 33 gives 0)
1. Turned from recursive form into iterative form 2. Unrolled heavily 3. Autovectorized (!)
The throughput will be substantially more than the simple version.
I'd like to know how the recursion to iteration step was done.
vs. what it does with 64-bit ints:
Can anybody explain the 32 bit version?