3 ms·
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
by 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 agoThanks, 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.)