An algorithm for exact division
Division of long integers is a frequently performed task in computer algebra. The common algorithms used for that purpose rely on computing quotient and remainder (IQR), even when it is known in advance that the latter one is zero. The author proposes to exploit the fact that the division is exact and gives a time-saving algorithm (EDIV) starting from the least significant digits of the operands, which is particulary efficient when the radix is a prime number or a power of 2. The speed-up may be quite significant, when the length of the result is much smaller than the lengths of the operands. Moreover the proposed algorithm is specially suited for systolic parallelization in pipelining least- significant-digits-first. The algorithm can be applied to integer GCD computation and to division modulo a power of 2. Benchmarks show that the ratio of CPU-times between EDIV and IQR is between 70\% and 30\% depending on the relation of the lengths of the operands. In computing the modular inverse the savings may even be better giving speed-ups between 23 and 28 depending on the input length.
- A DIVISION ALGORITHM
- A multiple-precision division algorithm
- scientific article; zbMATH DE number 4009638
- Constant-division algorithms
- A division algorithm for residue numbers
- scientific article; zbMATH DE number 3879184
- scientific article; zbMATH DE number 566342
- Division algorithm and Kronecker's approximation theorem
- A modular reduction for GCD computation.
- Common factors in fraction-free matrix decompositions
- New algorithms for the division's quotient
- Bidirectional exact integer division
- scientific article; zbMATH DE number 3843505 (Why is no real title available?)
- A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes
- scientific article; zbMATH DE number 4009638 (Why is no real title available?)
- scientific article; zbMATH DE number 566342 (Why is no real title available?)
- What Happens When the Division Algorithm “Almost” Works
- Integer Division in Linear Time with Bounded Fan-In
- A division algorithm without number comparison
- A DIVISION ALGORITHM
- The Euclidean algorithm as a sequence of modular inverse switching formulas
- libwignernj: a reusable C/C++/Fortran/Python library for exact Wigner symbols and related coefficients
This page was built for publication: An algorithm for exact division
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260759)