Comparando co-primos

Suponha que tenhamos dois números fatorados em seus primos, representados como listas de (p, d), onde todos os p são primos ed é a potência de p.

Existe uma maneira de comparar esses dois números sem convertê-los em números inteiros longos?

A comparação de dois números pode ser reduzida à comparação de dois primos, mas parece que a sorte acaba e parece que eu precisaria fazer uma aritmética polinomial, que é o mesmo que converter em números inteiros longos.

ds.algorithms nt.number-theory Sassa
fonte

Que tipo de comparação você tem em mente?

Martin Berger

tricotomia

$\:$

Você pode somar e comparar os logritmos, com precisão calculada preguiçosamente. Infelizmente, acho que no pior dos casos (números quase iguais) você precisará de precisão suficiente para que seja equivalente a multiplicar os números de qualquer maneira. Isso permitiria detectar números muito diferentes muito mais rapidamente.

Antimony

Comparação @MartinBerger quanto à capacidade de solicitá-los. Para o propósito da minha tarefa, posso apenas adicionar "Ord deriving", mas essa não é a ordem numérica.

Sassa

Logaritmos @Antimony com precisão computada preguiçosamente? você quer dizer, calcular séries de logaritmos, ou algo melhor?

Sassa

Respostas:

Esta é uma pergunta realmente interessante. Não consigo ver uma maneira de usar as fatorações primárias de números inteiros para acelerar a comparação wrt <, =,>.

Aqui está minha intuição sobre o porquê de ser difícil relacionar a fatoração com <, = e>: a fatoração primária é sobre a estrutura multiplicativa dos números inteiros, enquanto <e> são coisas aditivas. Talvez observar a definição de <na aritmética Peano torne isso mais claro: a definição de <é dada por (entre outras) as seguintes 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
fonte