3 ms·

Wait, that contains no loop. Is clang using mathematical rules for series summation? Awesome!

janekm 10y ago
It gets even better after playing with the code a bit: https://godbolt.org/g/kUMCpl https://godbolt.org/g/kUMCpl magic constants galore... where does 3435973837 come from? ;)
- frederikvs 10y ago
  It's 0xCCCCCCCD in hex, which looks a lot more structured at least. Though how exactly this makes sense is still unclear :-) [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...
  - john_reel 10y ago
    Well if A=1 (I know it’s not), D is 5-1. I’ve noticed that whatever you change five to fits this pattern. Ex: +=3 in the code gives you AAAAAAAB, and B would be (3-1) if A=1. I
  - im3w1l 10y ago
    I thought 0xCCCCCCCD was a very nice number so I asked myself why it would come out like that. I wondered whether 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 This relates to 0.CCCCCC.... = 4 / 5 Because in order for that to come out right, multiplying 0.CCCC... with 5 has to have all intermediate terms cancel, leaving only a 4. 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
- Veedrac 10y ago
  First it normalizes to 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; Division by 5 is done by multiplying by the modular inverse, 3435973837. From there you just have a summation, which has two components. ((loop_n + 1) * loop_n / 2) * 5 // 5x - loop_n - 1 // -1 The assembly between these the manual and automatic methods is slightly different, but the difference is fairly trivial and opaque.

It gets even better after playing with the code a bit: https://godbolt.org/g/kUMCpl https://godbolt.org/g/kUMCpl magic constants galore... where does 3435973837 come from? ;)

frederikvs 10y ago
It's 0xCCCCCCCD in hex, which looks a lot more structured at least. Though how exactly this makes sense is still unclear :-) [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...
- john_reel 10y ago
  Well if A=1 (I know it’s not), D is 5-1. I’ve noticed that whatever you change five to fits this pattern. Ex: +=3 in the code gives you AAAAAAAB, and B would be (3-1) if A=1. I
- im3w1l 10y ago
  I thought 0xCCCCCCCD was a very nice number so I asked myself why it would come out like that. I wondered whether 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 This relates to 0.CCCCCC.... = 4 / 5 Because in order for that to come out right, multiplying 0.CCCC... with 5 has to have all intermediate terms cancel, leaving only a 4. 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
Veedrac 10y ago
First it normalizes to 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; Division by 5 is done by multiplying by the modular inverse, 3435973837. From there you just have a summation, which has two components. ((loop_n + 1) * loop_n / 2) * 5 // 5x - loop_n - 1 // -1 The assembly between these the manual and automatic methods is slightly different, but the difference is fairly trivial and opaque.