Comparar co-primos

Supongamos que tenemos dos números factorizados en sus números primos, representados como listas de (p, d), donde todos los p son primos yd son la potencia de p.

¿Hay alguna manera de comparar esos dos números sin convertirlos en enteros largos?

La comparación de dos números se puede reducir a la comparación de dos números primos, pero luego parece que la suerte se agota, y parece que necesito hacer algo de aritmética polinómica, que es lo mismo que convertir en enteros largos.

ds.algorithms nt.number-theory Sassa
fuente

¿Qué tipo de comparación tienes en mente?

Martin Berger

tricotomía

$\:$

Podrías sumar y comparar los logritmos, con precisión calculada perezosamente. Desafortunadamente, creo que en el peor de los casos (números casi iguales) necesitará suficiente precisión para que sea equivalente a simplemente multiplicar los números de todos modos. Sin embargo, esto le permitiría detectar números muy diferentes mucho más rápido.

Antimonio

Comparación @MartinBerger en cuanto a la capacidad de ordenarlos. Para el propósito de mi tarea, solo puedo agregar "derivar Ord", pero ese no es el orden numérico.

Sassa

@ ¿Logaritmos de antimonio con precisión calculada perezosamente? ¿te refieres a calcular series de logaritmos o algo mejor?

Sassa

Respuestas:

Esta es una pregunta realmente interesante. No puedo ver una manera de usar las factorizaciones primas de los enteros para acelerar la comparación wrt <, =,>.

Aquí está mi intuición sobre por qué debería ser difícil relacionar la factorización con <, = y>: la factorización prima se trata de la estructura multiplicativa de los enteros, mientras que <y> son cosas aditivas. Quizás mirar la definición de <en la aritmética de Peano aclara esto: la definición de <viene dada por (entre otras) las siguientes cláusulas.

$\forall x.x < x+1$
$\forall xy. x < y \Rightarrow x+1 < y+1$

$x+1$ $y+1$ $x$ $y$ $x$ $x+1$

Martin Berger
fuente