Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Improved Division by Invariant Integers
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2011 (English)In: I.E.E.E. transactions on computers (Print), ISSN 0018-9340, E-ISSN 1557-9956, Vol. 60, no 2, 165-175 p.Article in journal (Refereed) Published
Abstract [en]

This paper considers the problem of dividing a two-word integer by a single-word integer, together with a few extensions and applications. Due to lack of efficient division instructions in current processors, the division is performed as a multiplication using a precomputed single-word approximation of the reciprocal of the divisor, followed by a couple of adjustment steps. There are three common types of unsigned multiplication instructions: we define full word multiplication (umul), which produces the two-word product of two single-word integers; low multiplication (umullo), which produces only the least significant word of the product; and high multiplication (umulhi), which produces only the most significant word. We describe an algorithm that produces a quotient and remainder using one umul and one umullo. This is an improvement over earlier methods, since the new method uses cheaper multiplication operations. It turns out that we also get some additional savings from simpler adjustment conditions. The algorithm has been implemented in version 4.3 of the GMP library. When applied to the problem of dividing a large integer by a single word, the new algorithm gives a speedup of roughly 30 percent, benchmarked on AMD and Intel processors in the x86_64 family.

Place, publisher, year, edition, pages
2011. Vol. 60, no 2, 165-175 p.
Keyword [en]
Computer arithmetic, multiple precision arithmetic, efficiency
National Category
Computer Science Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-29372DOI: 10.1109/TC.2010.143ISI: 000285599400004Scopus ID: 2-s2.0-78650984999OAI: oai:DiVA.org:kth-29372DiVA: diva2:394281
Note
QC 20110202Available from: 2011-02-02 Created: 2011-02-01 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Granlund, Torbjörn
By organisation
Theoretical Computer Science, TCS
In the same journal
I.E.E.E. transactions on computers (Print)
Computer ScienceOther Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf