New blog post – Bit-Twiddling: Addition with Unknown Bits
Conversation
This is really cool! Took me a minute to see the logic of the code, but it makes sense now. Here's a sketch of a linear time algorithm for multiplication that I think might be maximally precise: decompose the N-bit mul into N 1-bit mul + shift + adds
1
1
Kinda hard to explain the 1-bit mul in a tweet, so here's the Python I was writing to play with it: gist.github.com/zwegner/684168
I'll be impressed if you can do a maximally precise multiply!
here are the LLVM implementations if you want to peek:
3
I find these super fun and hard.
the reason I want to synthesize them is there are a million special cases where we can recover precision in principle, but it's hard to do it by hand:
- combinations of instructions like the shift-shift-or that makes a decomposed rotate
(cont'd)
1
2
Show replies
Here's a test that show's some places where it isn't maximally precise - I think the problem might be that each "add" operation is compressing the set and throwing away data, but it's hard to account for that:
3
2