Email or username:

Password:

Forgot your password?
Ken's posts Post Back to profile
Top-level
William D. Jones

@kenshirriff I implemented restoring/non-restoring dividers earlier this year for an HDL library.

They are both naive impls; the restoring divider is better on Just About Every metric. But the SRT algorithm is based on the non-restoring division by extending quotient digits from (-1, 1) to (-2, -1, 0, 1, 2), among other choices. So I keep the non-restoring divider around so I can use it as a base for whenever I implement SRT.

See here for derivations if interested: smolarith.readthedocs.io/en/la

6 December at 16:57 | Wall-to-wall | Open on mastodon.social
3 comments
Robin Green

@cr1901 @kenshirriff
I'd recommend getting the book "Digital Arithmetic" by Ercegovac et al. for a great chapter on high radix division/sqrt that goes through radix-2, radix-4 and radix-8 quotient digit selection table generation using P-D diagrams, fully worked with the quotient in both adder and carry-save form (slightly different tables).

6 December at 21:31 | Open on mastodon.gamedev.place
William D. Jones

@fatlimey @kenshirriff That will have to wait until I re-derive how to do square roots by hand again. For the 4th time.

Would be nice to commit it to memory and my ego refuses to look it up :D.

6 December at 22:15 | Open on mastodon.social
Robin Green

@cr1901 @kenshirriff The way to think about it is the quotient is trying to be the square of your current output, and the difference between that and your input guides selection of your next digit.

6 December at 23:04 | Open on mastodon.gamedev.place
Go Up