5 ms·

If you've never seen it before, this is a beautiful blog post on related matters: "Optimising pointer subtraction with 2-adic integers" http://blog.sigfpe.com/2

by svat 6y ago

If you've never seen it before, this is a beautiful blog post on related matters: "Optimising pointer subtraction with 2-adic integers" http://blog.sigfpe.com/2010/05/optimising-pointer-subtraction-with-2.html http://blog.sigfpe.com/2010/05/optimising-pointer-subtractio...

kevinventullo 6y ago
A few months back I wrote a blog post very much inspired by Dan’s post, though a little more academic: https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-fast-exponentiation/ https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-f... The idea is to exploit deeper structures in p-adic number theory to develop useful and novel algorithms with unsigned integer arithmetic, e.g. fast integer exponentiation. Feedback welcome! (Warning: math heavy)
- svat 6y ago
  This was a nice post, thank you! I don't yet have an intuition for how to think about these 2-adic exponentials and logs (e.g. what does it mean to say that log_2(5) =6713115954038056572) but clearly the mathematics works out and even leads to faster code, so it's very cool and I hope to read it again and understand it better. (As a sidenote on the motivation, I do wonder how common/useful it is to compute x^y mod (2^64) for random 64-bit integers x and y (so they'd be close to 2^63 on average)... from this perspective, the promised future post about computing the k-th root of a perfect k-th power integer sounds very interesting!)
  - kevinventullo 6y ago
    Thanks, that serves as good motivation to complete that post! As far as the statement that log_2(5) = 6713115954038056572, really that number is only an approximation; it is the last 64 bits of the “true” log_2(5), which has infinitely many bits. That is, the above equation in binary would be log_2(5) = 101110100101001110001110110010010000000011100100010011001111100. In the true 2-adic world, log_2(5) = ...101110100101001110001110110010010000000011100100010011001111100, where there are infinitely many leading bits. (Classical positive integers embed into the 2-adic world as numbers with all but finitely many bits set to 0, and similarly classical negative integers have all but finitely many bits set to 1.)
thechao 6y ago
> I don't know how gcc generates its approximate 2-adic reciprocals. Possibly it uses something based on the Euclidean GCD algorithm. I wasn't able to find the precise line of source in a reasonable time. It's 0x1FFF...F / 7 = 0x249...249249249. Just about the oddest thing I've seen; I guess, if I were the author, it'd be my "1 in 10000" day?
- xyzzy_plugh 6y ago
  Makes more sense in binary: 0xFFF..F 111111111111111111111111 0x7 000000000000000000000111 0x249..9 001001001001001001001001
- svat 6y ago
  I think you're trying to explain what's special about the number -1227133513 or how it comes about / how one could arrive at it. This is something the author understands very well; in fact that's what the whole post is about (well, it's about more advanced matters, using this as a "hook"), and many nice methods to arrive at that number are discussed in the post and comments. (And BTW your computation corresponds to 1227133513 or -1/7, not to -1227133513 or 1/7.) The sentence you quoted is merely asking which of the many discussed methods gcc is actually using, and this cannot be answered by mathematics; it needs to be answered by pointing to the relevant source code.
spoonjim 6y ago
For a total n00b, could you explain why subtracting a char is a division? “It doesn't seem like there could be much to say about that. The A structure is 7 bytes long so the subtraction implicitly divides by 7. That's about it.”
- throw8away 6y ago
  35 / 7 = 5 35-7 = 28, 1 28-7 = 21, 2 21-7 = 14, 3 14-7 = 07, 4 07-7 = 00, 5 thus we can see that in essence, division is repeated subtraction in some contexts, especially computationally. An easy way to count the amount of X that fits into Y is to simply count the amount of times you can subtract X from Y before Y is a negative value
- svat 6y ago
  (Note that the subtraction is between two pointers to "struct A", not two chars. In the snippet "char" is used simply because it's 1 byte; one could also use int8_t, assuming a byte is 8 bits long.) It's a fact about how the C language does pointer arithmetic. For instance, suppose you have an array of many 64-bit integers, and a pointer to one of the elements of the array: int64_t arr[100]; int64_t *p; p = &arr[50]; Now, the value of p is a certain address in memory. As each element of the array takes 8 bytes (64 bits = 8 bytes), the address of the next element of the array is 8 bytes past the location of p. In some languages (including assembly), you have to refer to this address by manually adding 8 to the address stored in p. In C, to refer to the next element of the array, you write "p + 1", and the compiler translates that into adding 8 bytes. Conversely, if you give the new pointer a name: int64_t *q; q = p + 1; then you expect (q - p) to be 1, not 8 (even though the value stored in q is 8 more than the value stored in p). That is, when subtracting pointers (of the same type), the result implicitly divides by the size of the type. In the code example in the blog post, as the size of "struct A" is 7 bytes, subtracting two pointers to A will subtract the memory addresses and divide by 7. If that wasn't clear, see this sentence on Wikipedia: https://en.wikipedia.org/w/index.php?title=Pointer_(computer_programming)&oldid=1015276279#:~:text=In%20languages%20that%20allow,above https://en.wikipedia.org/w/index.php?title=Pointer_(computer... or the answers to this question: https://stackoverflow.com/questions/3238482/pointer-subtraction-confusion https://stackoverflow.com/questions/3238482/pointer-subtract... or play with it yourself here: https://godbolt.org/z/M6PEWYeYx https://godbolt.org/z/M6PEWYeYx

by svat 6y ago

kevinventullo 6y ago

A few months back I wrote a blog post very much inspired by Dan’s post, though a little more academic: https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-fast-exponentiation/ https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-f... The idea is to exploit deeper structures in p-adic number theory to develop useful and novel algorithms with unsigned integer arithmetic, e.g. fast integer exponentiation. Feedback welcome! (Warning: math heavy)

svat 6y ago
This was a nice post, thank you! I don't yet have an intuition for how to think about these 2-adic exponentials and logs (e.g. what does it mean to say that log_2(5) =6713115954038056572) but clearly the mathematics works out and even leads to faster code, so it's very cool and I hope to read it again and understand it better. (As a sidenote on the motivation, I do wonder how common/useful it is to compute x^y mod (2^64) for random 64-bit integers x and y (so they'd be close to 2^63 on average)... from this perspective, the promised future post about computing the k-th root of a perfect k-th power integer sounds very interesting!)
- kevinventullo 6y ago
  Thanks, that serves as good motivation to complete that post! As far as the statement that log_2(5) = 6713115954038056572, really that number is only an approximation; it is the last 64 bits of the “true” log_2(5), which has infinitely many bits. That is, the above equation in binary would be log_2(5) = 101110100101001110001110110010010000000011100100010011001111100. In the true 2-adic world, log_2(5) = ...101110100101001110001110110010010000000011100100010011001111100, where there are infinitely many leading bits. (Classical positive integers embed into the 2-adic world as numbers with all but finitely many bits set to 0, and similarly classical negative integers have all but finitely many bits set to 1.)

thechao 6y ago

> I don't know how gcc generates its approximate 2-adic reciprocals. Possibly it uses something based on the Euclidean GCD algorithm. I wasn't able to find the precise line of source in a reasonable time. It's 0x1FFF...F / 7 = 0x249...249249249. Just about the oddest thing I've seen; I guess, if I were the author, it'd be my "1 in 10000" day?

xyzzy_plugh 6y ago
Makes more sense in binary: 0xFFF..F 111111111111111111111111 0x7 000000000000000000000111 0x249..9 001001001001001001001001
svat 6y ago
I think you're trying to explain what's special about the number -1227133513 or how it comes about / how one could arrive at it. This is something the author understands very well; in fact that's what the whole post is about (well, it's about more advanced matters, using this as a "hook"), and many nice methods to arrive at that number are discussed in the post and comments. (And BTW your computation corresponds to 1227133513 or -1/7, not to -1227133513 or 1/7.) The sentence you quoted is merely asking which of the many discussed methods gcc is actually using, and this cannot be answered by mathematics; it needs to be answered by pointing to the relevant source code.

spoonjim 6y ago

For a total n00b, could you explain why subtracting a char is a division? “It doesn't seem like there could be much to say about that. The A structure is 7 bytes long so the subtraction implicitly divides by 7. That's about it.”

throw8away 6y ago
35 / 7 = 5 35-7 = 28, 1 28-7 = 21, 2 21-7 = 14, 3 14-7 = 07, 4 07-7 = 00, 5 thus we can see that in essence, division is repeated subtraction in some contexts, especially computationally. An easy way to count the amount of X that fits into Y is to simply count the amount of times you can subtract X from Y before Y is a negative value
svat 6y ago
(Note that the subtraction is between two pointers to "struct A", not two chars. In the snippet "char" is used simply because it's 1 byte; one could also use int8_t, assuming a byte is 8 bits long.) It's a fact about how the C language does pointer arithmetic. For instance, suppose you have an array of many 64-bit integers, and a pointer to one of the elements of the array: int64_t arr[100]; int64_t *p; p = &arr[50]; Now, the value of p is a certain address in memory. As each element of the array takes 8 bytes (64 bits = 8 bytes), the address of the next element of the array is 8 bytes past the location of p. In some languages (including assembly), you have to refer to this address by manually adding 8 to the address stored in p. In C, to refer to the next element of the array, you write "p + 1", and the compiler translates that into adding 8 bytes. Conversely, if you give the new pointer a name: int64_t *q; q = p + 1; then you expect (q - p) to be 1, not 8 (even though the value stored in q is 8 more than the value stored in p). That is, when subtracting pointers (of the same type), the result implicitly divides by the size of the type. In the code example in the blog post, as the size of "struct A" is 7 bytes, subtracting two pointers to A will subtract the memory addresses and divide by 7. If that wasn't clear, see this sentence on Wikipedia: https://en.wikipedia.org/w/index.php?title=Pointer_(computer_programming)&oldid=1015276279#:~:text=In%20languages%20that%20allow,above https://en.wikipedia.org/w/index.php?title=Pointer_(computer... or the answers to this question: https://stackoverflow.com/questions/3238482/pointer-subtraction-confusion https://stackoverflow.com/questions/3238482/pointer-subtract... or play with it yourself here: https://godbolt.org/z/M6PEWYeYx https://godbolt.org/z/M6PEWYeYx