5 ms·

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 343597383

by 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.

by 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.