3 ms·
Labor of Division (2010)
- kanobo 6y agoFor more algorithm fun exactly like this, check out the classic Hacker's Delight book (https://en.wikipedia.org/wiki/Hacker%27s_Delight https://en.wikipedia.org/wiki/Hacker%27s_Delight)
- Cieplak 6y agoAlso check out HAKMEM [1] [2]. [1] https://en.wikipedia.org/wiki/HAKMEM https://en.wikipedia.org/wiki/HAKMEM [2] https://dspace.mit.edu/handle/1721.1/6086 https://dspace.mit.edu/handle/1721.1/6086
- dvt 6y agoAs I was reading, I was slowly understanding that N-bit division would require (in the worst case) an N + 1 bit magic number. How in the world could this be solvable in the general case? My assumption was that we just did division for those numbers the "old-fashioned" way. But, at the end of the day, the actual solution -- ((n − q) ≫ 2) + q -- is ingenious, fantastic article!