Optimal Size Integer Division Circuits

DOI10.1137/0219064zbMATH Open0711.68064OpenAlexW2093308874MaRDI QIDQ3495657FDOQ3495657

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

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

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)

Cited In (15)

• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Logarithmic Depth Circuits for Algebraic Functions

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)