Timeline for Algorithm to decide whether two constructible numbers are equal?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2020 at 10:20 | vote | accept | J Fabian Meier | ||
| Nov 23, 2020 at 9:30 | comment | added | katago | a similar problem is how to decide a fix constructible numbers is in a fix algebraic extension of $\mathbb{Q}$. | |
| Nov 23, 2020 at 9:06 | answer | added | Anders Kaseorg | timeline score: 7 | |
| Mar 16, 2017 at 21:08 | comment | added | Gro-Tsen | See, for example, Henri Cohen, A Course in Computational Algebraic Number Theory (Springer 1993 / GTM 138), specifically §4.2. But this is merely one possible reference among many: the subject is really quite standard, and googling "algorithm exact algebraic arithmetic" returns various relevant results (which probably themselves point to other references). More abstractly, Rabin's theorem on the algebraic closure can also be relevant. | |
| Mar 16, 2017 at 20:22 | comment | added | J Fabian Meier | @Gro-Tsen Thank you. Do you have a reference that explains your "basic idea" more thoroughly? That would be great. | |
| Mar 16, 2017 at 19:41 | comment | added | Gro-Tsen | Furthermore, I should add that such algorithms are not purely theoretical: they are implemented, e.g., in Sage, which is capable of handling exact algebraics (although, to be fair, complexity becomes quickly awful whenever you do something not too trivial). | |
| Mar 16, 2017 at 19:39 | comment | added | Gro-Tsen | There exist algorithms to deal with algebraic numbers in $\mathbb{C}$ (i.e., compute their sums, differences, products and inverses, solve algebraic equations on them, take their real and imaginary parts, and compare them for equality and, when they are real, for order). This solves your problem and much more. The basic idea is to represent an algebraic by a polynomial in $\mathbb{Q}[t]$ of which it is a root, and an interval (in real and imaginary parts if necessary) in which it is the only root. | |
| Mar 16, 2017 at 19:37 | comment | added | J Fabian Meier | A constructible number would be defined by a finite sequence of $+,-,*,/, \sqrt_\pm{}$ and complex conjugation applied to rational numbers, where $\sqrt_\pm{}$ would be one of the possible square roots of the given number. | |
| Mar 16, 2017 at 19:34 | comment | added | Joseph O'Rourke | In what form would the two constructible numbers be presented to the algorithm? | |
| Mar 16, 2017 at 19:25 | history | asked | J Fabian Meier | CC BY-SA 3.0 |