https://link.medium.com/X00MV3UWb0

In the end, I feel like I could have reinvented this method on my own before ever understanding what was written about it.

It is very easy to divide this by a large power of two simply by discarding the trailing zeros.

Eventually you will have a much larger number with a lot of trailing zeros in its binary representation, which means it is a multiple of a large power of two.

Basically you have a number you want to invert with respect to a large power of two. You represent the number and whatever modulus you are using in binary. Then you add the modulus strategically, shifting it as needed in order to cancel out the 1s in the number you want to invert.

Finally I picked some small numbers and worked through the algorithm with pencil and paper. It worked perfectly and I instantaneously understand the method.

The explanations for how the algorithm works were very rigorous and at a high level. So, not very helpful for understanding. I got frustrated with it.

I took a 768 bit number to a 768 bit exponent on an old laptop and it was no problem. A 256 bit number is enough to enumerate every atom in the observable universe, so just one of these numbers could enumerate the number of atoms in *checks calculator* an imaginary universe in which every atom contains in own universe, and every atom in that universe contained it's own universe, too.

It gives me great appreciation for the Hindu-Arabic numeral system. That huge numbers can be represented in a small space, and that addition, multiplication, and exponentiation can be done digit-by-digit is so crucial to efficient computing. It's really amazing.

By the way, I am trying to make a playlist of the best songs about numbers. Something mathematical must appear in the lyrics to qualify. "Carry the Zero" by Built to Spill counts, as does "One" by Three Dog Night, which literally counts: 1, 2. "One" by U2 does NOT count and therefore does not count. "1234" by Feist technically counts but does not count as a number song since she is counting beats in a musical capacity rather than referring to quantities.

What are your favorite number songs?

Near the end of Built to Spill's "Carry the Zero" I involuntarily stood up as if I were in a charismatic church service.

Joined Jun 2017