Content deleted Content added
Citation bot (talk | contribs) Added bibcode. Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 709/1032 |
|||
| (One intermediate revision by one other user not shown) | |||
Line 196:
==={{anchor|SRT}}SRT division===
SRT division is a popular method for division in many [[microprocessor]] implementations.<ref>{{cite tech report |url=http://pages.hmc.edu/harris/research/srtlong.pdf |title=SRT Division: Architectures, Models, and Implementations |first1=David L. |last1=Harris |first2=Stuart F. |last2=Oberman |first3=Mark A. |last3=Horowitz |publisher=Stanford University |date=9 September 1998 |access-date=23 December 2016 |archive-date=24 December 2016 |archive-url=https://web.archive.org/web/20161224030439/http://pages.hmc.edu/harris/research/srtlong.pdf |url-status=live }}</ref><ref>{{cite journal |url=https://ieeexplore.ieee.org/document/614875 |title=SRT Division Algorithms as Dynamical Systems |first1=Mark |last1=McCann |first2=Nicholas |last2=Pippenger |journal=SIAM Journal on Computing |volume=34 |issue=6 |pages=1279–1301 |year=2005 |doi=10.1137/S009753970444106X |hdl=2429/12179 |citeseerx=10.1.1.72.6993 |access-date=2022-08-24 |archive-date=2022-08-24 |archive-url=https://web.archive.org/web/20220824213238/https://ieeexplore.ieee.org/document/614875 |url-status=live }}</ref> The algorithm is named after D. W. Sweeney of [[IBM]], James E. Robertson of [[University of Illinois]], and [[K. D. Tocher]] of [[Imperial College London]]. They all developed the algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively).<ref>{{Citation |title=High speed arithmetic in a parallel device |last1=Cocke |first1=John |pages=20 |url=https://www.computerhistory.org/collections/catalog/102632302 |publication-date=11 February 1957 |last2=Sweeney |first2=D.W. |date=11 February 1957 |type=Company Memo |publication-place=IBM |access-date=24 August 2022 |archive-date=24 August 2022 |archive-url=https://web.archive.org/web/20220824212341/https://www.computerhistory.org/collections/catalog/102632302 |url-status=live }}</ref><ref>{{Cite journal |title=A New Class of Digital Division Methods |journal=IRE Transactions on Electronic Computers
SRT division is similar to non-restoring division, but it uses a [[lookup table]] based on the dividend and the divisor to determine each quotient digit.
Line 276:
The following computes the quotient of {{var|N}} and {{var|D}} with a precision of {{var|P}} binary places:
<div style="font-family: monospace, monospace;">
Express D as M × 2<sup>e</sup> where 1 ≤ M < 2 (standard floating point representation)<br>
D' := D / 2<sup>e+1</sup> ''// scale between 0.5 and 1, can be performed with bit shift / exponent subtraction''<br>
N' := N / 2<sup>e+1</sup><br>
X := 48/17 − 32/17 × D' ''// precompute constants with same precision as D''<br>
{{nowrap|'''repeat''' <math>\left \lceil \log_2 \frac{P + 1}{\log_2 17} \right \rceil \,</math> '''times'''}} ''// can be precomputed based on fixed P''<br>
'''end'''<br>
'''return''' N' × X<br>
</
For example, for a double-precision floating-point division, this method uses 10 multiplies, 9 adds, and 2 shifts.
Line 399:
It is not necessary to use specifically (1/''D''); any value (''X''/''Y'') that reduces to (1/''D'') may be used. For example, for division by 3, the factors 1/3, 2/6, 3/9, or 194/582 could be used. Consequently, if ''Y'' were a power of two the division step would reduce to a fast right bit shift. The effect of calculating ''N''/''D'' as (''N''·''X'')/''Y'' replaces a division with a multiply and a shift. Note that the parentheses are important, as ''N''·(''X''/''Y'') will evaluate to zero.
However, unless ''D'' itself is a power of two, there is no ''X'' and ''Y'' that satisfies the conditions above. Fortunately, (''N''·''X'')/''Y'' gives exactly the same result as ''N''/''D'' in integer arithmetic even when (''X''/''Y'') is not exactly equal to 1/''D'', but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.<ref>{{cite journal |title=Division by Invariant Integers using Multiplication |first1=Torbjörn |last1=Granlund |first2=Peter L. |last2=Montgomery |journal=SIGPLAN Notices |volume=29 |issue=6 |date=June 1994 |pages=61–72 |doi=10.1145/773473.178249 |url=http://gmplib.org/~tege/divcnst-pldi94.pdf |citeseerx=10.1.1.1.2556 |access-date=2015-12-08 |archive-date=2019-06-06 |archive-url=https://web.archive.org/web/20190606211506/https://gmplib.org/~tege/divcnst-pldi94.pdf |url-status=live }}</ref><ref>{{cite journal |title=Improved Division by Invariant Integers |first1=Niels |last1=Möller |first2=Torbjörn |last2=Granlund |journal=IEEE Transactions on Computers |date=February 2011 |volume=60 |issue=2 |pages=165–175 |doi=10.1109/TC.2010.143 |bibcode=2011ITCmp..60..165M |s2cid=13347152 |url=http://gmplib.org/~tege/division-paper.pdf |access-date=2015-12-08 |archive-date=2015-12-22 |archive-url=https://web.archive.org/web/20151222160554/https://gmplib.org/~tege/division-paper.pdf |url-status=live }}</ref><ref>ridiculous_fish.
[http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf "Labor of Division (Episode III): Faster Unsigned Division by Constants"] {{Webarchive|url=https://web.archive.org/web/20220108225258/http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf |date=2022-01-08 }}.
2011.</ref> [[Barrett reduction]] uses powers of 2 for the value of ''Y'' to make division by ''Y'' a simple right shift.{{efn|1=Modern [[compilers]] commonly perform this integer multiply-and-shift optimization; for a constant only known at run-time, however, the program must implement the optimization itself.<ref>{{cite web |last1=ridiculous_fish |title=libdivide, optimized integer division |url=https://libdivide.com/ |access-date=6 July 2021 |archive-date=23 November 2021 |archive-url=https://web.archive.org/web/20211123015446/https://libdivide.com/ |url-status=live }}</ref>}}
| |||