Optimal Size Integer Division Circuits

DOI10.1137/0219064zbMath0711.68064OpenAlexW2093308874MaRDI QIDQ3495657

Stephen R. Tate, John H. 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 complexitysize complexityalgebraic computationpolynomial multiplicationinteger division

Mathematics Subject Classification ID

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

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Complexity of computation in finite fields ⋮ Oblivious sampling with applications to two-party \(k\)-means clustering ⋮ A parametric error analysis of Goldschmidt's division algorithm ⋮ On the complexity of Fibonacci coding