Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #3729

Re: Paper: dividing by seven

Show all headers | View raw

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/

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

Paper: dividing by seven John R Levine <johnl@taugh.com> - 2026-04-10 12:04 -0400
  Re: Paper: dividing by seven anton@mips.complang.tuwien.ac.at - 2026-04-13 05:48 +0000
  Re: Paper: dividing by seven robin51@dodo.com.au - 2026-04-19 00:19 +1000
    Re: Paper: dividing by seven anton@mips.complang.tuwien.ac.at - 2026-04-19 14:30 +0000

csiph-web