4 ms·
The "non-adjacent form" optimization appears to just be radix-8 booth recoding, no?
by evancox100 8y ago
The "non-adjacent form" optimization appears to just be radix-8 booth recoding, no?
- loup-vaillant 8y ago<looks up what the heck is "booth recoding"…> I think they're different. In booth recoding, the windows are fixed, and non adjacent form is a special case of sliding windows (2-bit wide). I don't think booth recoding does minimise the number of non-zero digits. That said, it does seem to produce similar results in some cases: 01111111 100 (binary) 10000000-100 (NAF) -- radix-4 Booth recoding 01111111100 000 -> 00 110 -> 0-1 111 -> 00 111 -> 00 111 -> 00 001 -> 01 010000000-100 (same as NAF) But I think it's just a coincidence, here.
- detaro 8y agosemi-OT: big thumbs up for your Poly1305 "tutorial", clearest explanation of it I've seen yet.