5
$\begingroup$

I'm working on a simple CAS and I have run into the issue of number representation, or more specifically, number comparison.

while programming with integers, the CPU compares them by checking if their bits have the same values and the same order.

Now given these integers, you can create a data structure (a number representation), such as a fraction, and ensure that each possible value that it can represent will only ever be represented in one way. For a fraction, we do this by removing all factors shared by the numerator and the denominator. This means that we can just compare each element of the fraction individually, and we never need to worry about accidentally comparing 12/4 with 3/1.

We also have the ability, however, to do the simplification at the time of the comparison. Again with the fraction example, we can also find the common denominator of the two and scale them so that we can compare them (or something like that).

Now how can we create some sort of list-based data structure (or rather number notation) that allows us to compare algebraic numbers with either of these methods? This might be asking too much because this is all under the assumption that we will still be able to perform operations.

$\endgroup$
14
  • 1
    $\begingroup$ Algebraic numbers, you mean $n$th roots, or arbitrary roots of polynomials $\in \mathbb{Z}[x]$ ? $\endgroup$
    – reuns
    Apr 23 '17 at 19:08
  • 1
    $\begingroup$ arbitrary roots of polynomials $\endgroup$
    – Evan
    Apr 23 '17 at 19:10
  • 3
    $\begingroup$ Interesting question. Googling data structure for algebraic numbers turns up links that might help. cs.nyu.edu/mishra/PUBLICATIONS/90.Mishra-NC.pdf, reduce-algebra.com/docs/arnum.pdf, ... $\endgroup$ Apr 23 '17 at 19:14
  • 3
    $\begingroup$ I'm not sure what is wrong with the answer I gave (which was deleted!). Please enlighten me. We specify an algebraic number by giving three pieces of data - its (normalised) minimal polynomial $p(x)$, a bounding box $B$ in the complex plane, and its multiplicity. We arrange matters so that bounding boxes are computed deterministically from $p(x)$ and that boxes for distinct roots are disjoint. $\endgroup$
    – Sam Nead
    Feb 6 at 9:20
  • 4
    $\begingroup$ @SamNead Your answer was deleted with the comment "This does not provide an answer to the question." That comment is wrong, but I've seen the same incorrect comment on a number of other answers --- it's just something that happens occasionally here. It would, however, be better if you put some more details into your answer, to help people who don't immediately see why it's right. $\endgroup$ Feb 6 at 15:34
6
$\begingroup$

I am not an expert here. So please take this with a grain of salt or, even better, point out I should fix things. Now, with the apology out of the way:

If we are focussed on the equality test (which is what the bulk of the OP was about) then we can proceed as follows. We specify an algebraic number $\alpha$ by giving two pieces of data

  • the minimal polynomial $P(x)$ of $\alpha$ (monic by definition) and
  • a bounding box $B$ about $\alpha$ in the complex plane.

We arrange matters so that

  • bounding boxes are computed deterministically from $P$ and
  • boxes for distinct roots of $P$ are disjoint.

Given algebraic $\alpha$ and $\beta$ in this way, it is easy to decide if they are equal. (It is also easy to decide if $\alpha$ is real.) It should not be too painful to compute $-\alpha$ and $1/\beta$, as well.

However, given algebraic $\alpha$ and $\beta$ in this way, it is quite a bit of work to compute representations for $\alpha + \beta$ or $\alpha \cdot \beta$ (or, if both are real, to decide if $\alpha < \beta$). In addition to computing new minimal polynomials we will have to shrink the given boxes.

There is another method with different trade-offs. To specify $\alpha$ we find a number field $K$, equipped with a place, that contains $\alpha$. We think of $K$ as a $\mathbb{Q}$-vector space and "represent" $\alpha$ as a rational vector. Of course, the place has to be given to sufficient precision to separate $\alpha$ from its Galois conjugates. If $\beta$ also lives in $K$ then arithmetic is much faster. (Comparisons as real numbers is still expensive.) However, if $\beta$ lives in a different number field $L$ then we cannot ask about equality until we find a third number field that contains both, and so on. So the faster arithmetic is paid for by a slower equality test.

(I guess that any representation will have to have trade-offs of this kind. However, lower bounds in complexity theory are famously difficult, so please don't ask me to prove my guess is correct.)

ADDED: After writing the answer, I looked around a bit and found the paper "Thom's Lemma, the Coding of Real Algebraic Numbers and the Computation of the Topology of Semi-algebraic Sets" by Coste and Roy. They reduce the size of the representation of $\alpha$ (assumed real) considerably (but the simpler representation appears to be harder to compute).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.