If you are interested in categories, computation, cryptography, or zero-knowledge proofs, check out my writing for Statebox on zero-knowledge proofs of boolean circuit satisfiability:
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.

Show thread

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

Show thread

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.

Show thread

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.

Show thread

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

Show thread

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.

Show thread

I'm learning about the Montgomery reduction method for modular multiplication of large integers. I read from several sources. Reading the wikipedia article was not enlightening. Reading a chapter from Handbook of Practical Cryptography was better but still not helpful. The Handbook had tidy psuedocode for it, which I successfully implemented in Rust. I still had no clue how it worked.

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.

Show thread

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.

Show thread

I'm doing some programming involving multiple precision arithmetic. It's like doing second grade math all over again. Carry the one. Borrow 10. (Or 2⁶⁴ in this case).

I'm participating in Coda's zkSNARK challenge. I am going to learn A LOT. I know the math, but there's so much developer stuff I've never done before. Docker, CUDA, Rust,.... Thousands in prizes would be great, but all I want is a participant t-shirt and a learning experience.

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.

Show thread

Now playing: The Smiths, Echo and the Bunnymen, Built to Spill

Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!