Division algorithm
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Variants of these algorithms allow using fast multiplication algorithms. It results that, for large integers, the computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used. Discussion will refer to the form , where is the input, and is the output.
- Comment
- enA division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Variants of these algorithms allow using fast multiplication algorithms. It results that, for large integers, the computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used. Discussion will refer to the form , where is the input, and is the output.
- Date
- enJune 2015
- Has abstract
- enA division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include , non-performing restoring, , and division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. and algorithms fall into this category. Variants of these algorithms allow using fast multiplication algorithms. It results that, for large integers, the computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used. Discussion will refer to the form , where * N = numerator (dividend) * D = denominator (divisor) is the input, and * Q = quotient * R = remainder is the output.
- Is primary topic of
- Division algorithm
- Label
- enDivision algorithm
- Link from a Wikipage to an external page
- www.quadibloc.com/comp/cp0202.htm
- web.archive.org/web/20180703001722/http:/www.quadibloc.com/comp/cp0202.htm
- Link from a Wikipage to another Wikipage
- Algorithm
- AMD
- Approximation
- Barrett reduction
- Binomial theorem
- Burnikel-Ziegler division
- Category:Articles with example pseudocode
- Category:Binary arithmetic
- Category:Computer arithmetic
- Category:Computer arithmetic algorithms
- Category:Division (mathematics)
- Chebyshev polynomial
- Chunking (division)
- Compiler
- Compilers
- Computational complexity
- Cryptography
- Double precision
- Equioscillation theorem
- Euclid's Elements
- Euclidean division
- Extended precision
- Fixed point arithmetic
- Fixed-point arithmetic
- Floating-point
- Fused multiply–add
- Galley division
- Greatest common divisor
- Hexadecimal
- IBM
- Imperial College London
- Integer (computer science)
- K. D. Tocher
- Karatsuba algorithm
- Long division
- Lookup table
- Microprocessor
- Modular arithmetic
- Montgomery reduction
- Multiplication algorithm
- Multiplicative inverse
- Newton's method
- OEIS
- One's complement
- Original Intel Pentium (P5 microarchitecture)
- Output-sensitive algorithm
- Pentium FDIV bug
- Power of two
- Precision (computer science)
- Quotient
- Radix
- Rate of convergence
- Relative error
- Remainder
- Remez algorithm
- Round-off error
- Schönhage–Strassen algorithm
- Short division
- Single precision
- Toom–Cook multiplication
- Two's complement
- University of Illinois
- Reason
- enBarrett reduction is usually understood to be the algorithm for computing the remainder that one gets from having precomputed the inverse of the denominator. Rather than providing a solution to the problem of division, it requires that a separate solution is already available!
- SameAs
- 3FVZG
- Division algorithm
- m.096h2k
- Q3526714
- Алгоритм деления
- الگوریتم تقسیم
- 除法器
- 除算 (デジタル)
- SeeAlso
- Binary number
- Subject
- Category:Articles with example pseudocode
- Category:Binary arithmetic
- Category:Computer arithmetic
- Category:Computer arithmetic algorithms
- Category:Division (mathematics)
- WasDerivedFrom
- Division algorithm?oldid=1119822964&ns=0
- WikiPageLength
- 35118
- Wikipage page ID
- 3336479
- Wikipage revision ID
- 1119822964
- WikiPageUsesTemplate
- Template:About
- Template:Anchor
- Template:Citation needed
- Template:Cite web
- Template:Efn
- Template:Expand section
- Template:Further
- Template:Main
- Template:Notelist
- Template:Number-theoretic algorithms
- Template:OEIS link
- Template:Reflist
- Template:Rp
- Template:See also
- Template:Sfrac
- Template:Short description
- Template:Snd
- Template:Var
- Template:Verification needed