<p>This is a really interesting question. I cannot see a way to use the prime
factorisations of integers to speed up comparison w.r.t. &lt;, =, >. </p>

<p>Here
is my intuition about why it should be difficult to relate
factorisation with &lt;, = and >: the prime factorisation is about the multiplicative 
structure of the integers, while &lt; and > are additive things. 
Maybe looking at the definition of &lt; in Peano arithmetic makes this clearer: the definition of &lt; is given by (among others) the following clauses.</p>

<ol>
<li><p>$\forall x.x &lt; x+1$ </p></li>
<li><p>$\forall xy. x &lt; y \Rightarrow x+1 &lt; y+1$.</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-11-14T17:07:29.153Z
2012-11-14T19:44:30.057Z
2012-11-14T19:44:30.057Z
Martin Berger
<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-11-08T16:08:50.693Z
What kind of comparison have you got in mind?
Martin Berger
CC BY-SA 3.0
2012-11-09T03:00:25.463Z
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
CC BY-SA 3.0
2012-11-13T09:49:47.917Z
@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
CC BY-SA 3.0
2012-11-13T09:54:05.580Z
@Antimony logarithms with lazily computed precision? do you mean, compute logarithm series, or something better?
Sassa
<ds.algorithms><nt.number-theory>
Comparing co-primes
Sassa
# Comparing co-primes

(Asked by: username_0 on 2012-11-08)

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.

**Tags:** ds.algorithms, nt.number-theory

> **Comments:**
> **username_1**: What kind of comparison have you got in mind?  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_0**: @username_2 logarithms with lazily computed precision? do you mean, compute logarithm series, or something better?  

---

## 1 answers

### Answer by username_1 on 2012-11-14. Score: 0 | Accepted answer

This is a really interesting question. I cannot see a way to use the prime
factorisations of integers to speed up comparison w.r.t. <, =, >.

Here
is my intuition about why it should be difficult to relate
factorisation with <, = and >: the prime factorisation is about the multiplicative
structure of the integers, while < and > are additive things.
Maybe looking at the definition of < in Peano arithmetic makes this clearer: the definition of < is given by (among others) the following clauses.

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.


---

