8
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ What kind of comparison have you got in mind? $\endgroup$ – Martin Berger Nov 8 '12 at 16:08
  • $\begingroup$ trichotomy $\:$ $\endgroup$ – user6973 Nov 8 '12 at 20:26
  • 5
    $\begingroup$ 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. $\endgroup$ – Antimony Nov 9 '12 at 3:00
  • $\begingroup$ @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. $\endgroup$ – Sassa Nov 13 '12 at 9:49
  • $\begingroup$ @Antimony logarithms with lazily computed precision? do you mean, compute logarithm series, or something better? $\endgroup$ – Sassa Nov 13 '12 at 9:54
0
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$

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.