Arithmetic with real algebraic numbers is in NC

Bud Mishra; Paul Pedersen

doi:10.1145/96877.96909

Arithmetic with real algebraic numbers is in NC

Bud Mishra, Paul Pedersen

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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(log³ 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(log⁷ 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].

Original language	English (US)
Title of host publication	ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation
Publisher	Publ by ACM
Pages	120-126
Number of pages	7
ISBN (Print)	0201548925, 9780201548921
DOIs	https://doi.org/10.1145/96877.96909
State	Published - 1990
Event	ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation - Tokyo, Jpn Duration: Aug 20 1990 → Aug 24 1990

Publication series

Name	ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation

Other

Other	ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation
City	Tokyo, Jpn
Period	8/20/90 → 8/24/90

ASJC Scopus subject areas

Engineering(all)

Access to Document

10.1145/96877.96909

Cite this

Arithmetic with real algebraic numbers is in NC. / Mishra, Bud; Pedersen, Paul.

ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation. Publ by ACM, 1990. p. 120-126 (ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mishra, B & Pedersen, P 1990, Arithmetic with real algebraic numbers is in NC. in ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation. ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation, Publ by ACM, pp. 120-126, ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation, Tokyo, Jpn, 8/20/90. https://doi.org/10.1145/96877.96909

@inproceedings{8e1ace9172c5430792d8882bead1adf5,

title = "Arithmetic with real algebraic numbers is in NC",

abstract = "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].",

author = "Bud Mishra and Paul Pedersen",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation ; Conference date: 20-08-1990 Through 24-08-1990",

year = "1990",

doi = "10.1145/96877.96909",

language = "English (US)",

isbn = "0201548925",

series = "ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation",

publisher = "Publ by ACM",

pages = "120--126",

booktitle = "ISSAC '90 Proceedings of International Symposium on Symbolic and Algebraic Computation",

}

TY - GEN

T1 - Arithmetic with real algebraic numbers is in NC

AU - Mishra, Bud

AU - Pedersen, Paul

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 -

Arithmetic with real algebraic numbers is in NC

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this