compare co-primes

[sassa_nf]

есть разложения двух целых чисел на простые множители.

можно ли сравнить эти целые числа, не превращая их разложения в BigInteger?

(а чо subject про co-primes: понятно, что a / b > 1 - один из способов; в таком случае задача сравнения a и b упрощается до сравнения co-primes)

Comments

[antilamer.livejournal.com]

Можно попробовать рассматривать логарифмы.

Но я почти уверен, что в худшем случае всё равно придётся перемножать.

Лучше всего спросить на cstheory.stackexchange.com :)

[sassa-nf.livejournal.com]

да вот же ж, уже есть разложение на простые, [(Int, Int)], т.е. [(prime, power)], так что, почти логарифм. Но поскольку a и b - co-prime, они состоят из списков пар (p, d) с уникальными p. Значит, нужно уметь делить p_a на p_b с остатком, а значит, уметь обращаться с q_a, r_a, умноженными на следующее p_a, и вот тут-то начинается котовасия, похожая по сложности на просто длинное умножение по одному фиксированному модулю.

Да, спасибо, поспрашиваю на stackexchange

[sassa-nf.livejournal.com]

На cstheory тоже предлагают логарифмы.

Но вообще-то здесь есть рациональное зерно. Для сравнения чисел ведь не нужно расчитывать весь логарифм, нужно посчитать только первый член ряда Тейлора. Да, там будет приведение к общему знаменателю, т.е. всё равно длинное умножение понадобится, но размер чисел будет значительно меньшим.

[antilamer.livejournal.com]

Худший случай будет, если логарифмы так близки, что вычисление их с достаточной для сравнения точностью эквивалентно вычислению самого числа.

[sassa-nf.livejournal.com]

неее, я не так мыслю.

∀prime p, ln(p)= -ln(1/p) = -ln(1-(p-1)/p) = Σ(((p-1)/p)^n)/n


Далее, поскольку нам нужно лишь сравнить числа, то мы можем ограничиться сравнением первого слагаемого этого ряда; остача ряда будет относиться к остаче ряда для другого числа точно так же.

Мне кажется, должно выполняться также условие ∀ n > 1, Σ(x_i)^n-1 > Σ(y_i)^n-1 ⇔ Σ(x_i)ⁿ > Σ(y_i)ⁿ. Если это так, то в этом случае мы суммируем первый член ряда для всех простых чисел в разложении первого числа и сравниваем с суммой первых членов рядов всех простых чисел из разложения второго числа. Да, для суммирования нужно привести к общему знаменателю, но в среднем это будет меньшее число, чем изначальные.

[antilamer.livejournal.com]

> Далее, поскольку нам нужно лишь сравнить числа, то мы можем ограничиться сравнением первого слагаемого этого ряда; остача ряда будет относиться к остаче ряда для другого числа точно так же.
Что-то не понял. Первое слагаемое этого ряда - (p-1)/p. Ты предлагаешь, например, для чисел вида p^a * q^b вместо a*ln(p) + b*ln(q) рассматривать a*(p-1)/p + b*(q-1)/q и утверждаешь, что это будет всегда верно?

[sassa-nf.livejournal.com]

Да, я думаю, что это будет верно всегда. Множители a и b можно игнорировать, ибо общий вид Σ((p_i)-1)/p_i.

[antilamer.livejournal.com]

Характер монотонности у a*(p-1)/p + b*(q-1)/q - как у a*q + b*p. Оно не монотонно a*p + b*q; подобрать примеры тривиально. Или я чего-то не понимаю?

[sassa-nf.livejournal.com]

да я вот тоже засомневался. 2+2 > 3, 2^2+2^2 < 3^2.

Может, тогда по двум точкам прикинуть, кто из них растёт быстрее?

[sassa-nf.livejournal.com]

мда... это тоже что-то не то. таки в итоге нужно убедиться, какой предел, а это значит, вычисление с неизвестной точностью.

[sassa-nf.livejournal.com]

как всё просто:

http://cstheory.stackexchange.com/questions/14250/comparing-co-primes

т.е. никак низзя сравнить быстрее.