TY - GEN
T1 - Arithmetic with real algebraic numbers is in NC
AU - Mishra, Bud
AU - Pedersen, Paul
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1990
Y1 - 1990
N2 - We describe NC algorithms for doing exact arithmetic with real algebraic numbers in the signcoded representation introduced by Coste and Roy [CoR 1988]. We present polynomial sized circuits of depth O(log3 N) for the monadic operations -α, 1/α, as well as α + r, α · r, and sgn (α - r), where r is rational and α is real algebraic. We also present polynomial sized circuits of depth O(log7 N) for the dyadic operations α+β, α·β, and sgn(α-β), where α and β are both real algebraic. Our algorithms employ a strengthened form of the NC polynomial-consistency algorithm of Ben-Or, Kozen, and Reif [BKR 1986].
AB - We describe NC algorithms for doing exact arithmetic with real algebraic numbers in the signcoded representation introduced by Coste and Roy [CoR 1988]. We present polynomial sized circuits of depth O(log3 N) for the monadic operations -α, 1/α, as well as α + r, α · r, and sgn (α - r), where r is rational and α is real algebraic. We also present polynomial sized circuits of depth O(log7 N) for the dyadic operations α+β, α·β, and sgn(α-β), where α and β are both real algebraic. Our algorithms employ a strengthened form of the NC polynomial-consistency algorithm of Ben-Or, Kozen, and Reif [BKR 1986].
UR - http://www.scopus.com/inward/record.url?scp=0025559994&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025559994&partnerID=8YFLogxK
U2 - 10.1145/96877.96909
DO - 10.1145/96877.96909
M3 - Conference contribution
AN - SCOPUS:0025559994
SN - 0201548925
SN - 9780201548921
T3 - ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation
SP - 120
EP - 126
BT - ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation
PB - Publ by ACM
T2 - ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation
Y2 - 20 August 1990 through 24 August 1990
ER -