Division algorithm: Difference between revisions

Revision as of 15:32, 30 December 2024

Revision as of 02:24, 1 January 2025

Line 146:

===Non-restoring division===

Non-restoring division uses the digit set {&minus;1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the subtraction,<ref>{{Cite journal |last=Shaw |first=Robert F. |date=1950 |title=Arithmetic Operations in a Binary Computer |url=http://aip.scitation.org/doi/10.1063/1.1745692 |journal=Review of Scientific Instruments |language=en |volume=21 |issue=8 |pages=690 |doi=10.1063/1.1745692 |bibcode=1950RScI...21..687S |issn=0034-6748 |access-date=2022-02-28 |archive-date=2022-02-28 |archive-url=https://web.archive.org/web/20220228182241/https://aip.scitation.org/doi/10.1063/1.1745692 |url-status=live }}</ref> which potentially cuts down the numbers of operations by up to half and lets it be executed faster.<ref>{{Cite web|url=https://web.stanford.edu/class/ee486/doc/chap5.pdf|title=Stanford EE486 (Advanced Computer Arithmetic Division){{snd}} Chapter 5 Handout (Division)|last=Flynn|website=Stanford University|access-date=2019-06-24|archive-date=2022-04-18|archive-url=https://web.archive.org/web/20220418044630/http://web.stanford.edu/class/ee486/doc/chap5.pdf|url-status=live}}</ref> The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is:{{check|reason=See talk page}}

<syntaxhighlight lang="lua">