Optimal Size Integer Division Circuits

DOI10.1137/0219064MaRDI QIDQ3495657zbMATH OpenOpenAlexFDO

Authors Stephen R. Tate, J. Reif

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://libres.uncg.edu/ir/uncg/f/S_Tate_Optimal_1990.pdf

zbMATH Keywords

Turing machinecircuit complexityalgebraic computationsize complexitypolynomial multiplicationinteger division

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Log Depth Circuits for Division and Related Problems
• Fast Parallel Arithmetic via Modular Representation
• Logarithmic Depth Circuits for Algebraic Functions
• Division in logspace-uniform NC
• Integer Division in Linear Time with Bounded Fan-In

Cited in

(15)

• Logarithmic Depth Circuits for Algebraic Functions
• Division using a logarithmic-exponential transform to form a short reciprocal
• Integer Division in Linear Time with Bounded Fan-In
• Easy multiple-precision divisors and word-RAM constants
• Oblivious sampling with applications to two-party k-means clustering
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• A Minimum Table Size Result for Higher Radix Nonrestoring Division
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• scientific article; zbMATH DE number 1254004 (Why is no real title available?)
• A parametric error analysis of Goldschmidt's division algorithm
• On the complexity of Fibonacci coding
• Log Depth Circuits for Division and Related Problems
• Complexity of computation in finite fields
• Fast Parallel Arithmetic via Modular Representation
• scientific article; zbMATH DE number 3960996 (Why is no real title available?)

This page was built for publication: Optimal Size Integer Division Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495657)