Re: Paper: dividing by seven

robin51@dodo.com.au writes:
>Might be useful to look at Hacker's Delight (H. S. Warren, Jr).


I looked at the first edition of this book for my paper
<https://www.complang.tuwien.ac.at/papers/ertl19kps.pdf>, but its
Chapter 10 only got an honourable mention at the end of my
Related-Work section; there is a second edition of this book, however.


In any case, I wrote at the start of my related-work section:


|If you read only one paper about the topic, my recommendation is
|Robison���s [Rob05].


@InProceedings{robison05,
    author = "Arch D. Robison",
    title = "{$N$}-Bit Unsigned Division Via {$N$}-Bit
Multiply-Add",
    OPTeditor = "Paolo Montuschi and Eric (Eric Mark) Schwarz",
    booktitle = "{Proceedings of the 17th IEEE Symposium on Computer
Arithmetic (ARITH-17)}",
    publisher = "IEEE Computer Society Press",
    ISBN = "0-7695-2366-8",
    ISBN-13 = "978-0-7695-2366-8",
    year = "2005",
    bibdate = "Wed Jun 22 07:02:55 2005",
    bibsource = "http://www.math.utah.edu/pub/tex/bib/fparith.bib",
    URL = "http://www.acsel-lab.com/arithmetic/arith17/papers/ARITH17_Robison.pdf",
    abstract = "Integer division on modern processors is expensive
compared to multiplication. Previous algorithms for
performing unsigned division by an invariant divisor,
via reciprocal approximation, suffer in the worst case
from a common requirement for $ n + 1 $ bit
multiplication, which typically must be synthesized
from $n$-bit multiplication and extra arithmetic
operations. This paper presents, and proves, a hybrid
of previous algorithms that replaces $ n + 1 $ bit
multiplication with a single fused multiply-add
operation on $n$-bit operands, thus reducing any
$n$-bit unsigned division to the upper $n$ bits of a
multiply-add, followed by a single right shift. An
additional benefit is that the prerequisite
calculations are simple and fast. On the Itanium 2
processor, the technique is advantageous for as few as
two quotients that share a common run-time divisor.",
    acknowledgement = "Nelson H. F. Beebe, University of Utah, Department
of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake
City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1
801 581 4148, e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|, \path|beebe@computer.org|
(Internet), URL:
\path|http://www.math.utah.edu/~beebe/|",
    keywords = "ARITH-17",
    pagecount = "9",
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.