# Comparing co-primes

Suppose we have two numbers factorized into their primes, represented as lists of (p,d), where all p are prime, and d are the power of p.

Is there a way to compare such two numbers without converting them into long integers?

Comparing two numbers can be reduced to comparing two co-primes, but then it seems the luck runs out, and it seems I'd need to do some polynomial arithmetic, which is the same as converting into long integers.

• What kind of comparison have you got in mind? – Martin Berger Nov 8 '12 at 16:08
• trichotomy $\:$ – user6973 Nov 8 '12 at 20:26
• You could sum and compare the logrithms, with lazily computed precision. Unfortunately, I think in the worst case (numbers almost equal) you'll need enough precision that it's equivalent to just multiplying the numbers out anyway. This would let you detect widely different numbers much faster though. – Antimony Nov 9 '12 at 3:00
• @MartinBerger comparison as in ability to order them. For the purpose of my task, I can just add "deriving Ord", but that is not the numerical order. – Sassa Nov 13 '12 at 9:49
• @Antimony logarithms with lazily computed precision? do you mean, compute logarithm series, or something better? – Sassa Nov 13 '12 at 9:54

1. $\forall x.x < x+1$
2. $\forall xy. x < y \Rightarrow x+1 < y+1$.
What's relevant here is the base case (1). Translated into prime factorisation, it says that you need to know something about the factorisations of $x+1$ and $y+1$ from the factorisations of $x$ and $y$. However, as far as I'm aware the factorisations of $x$ and $x+1$ are essentially unrelated.