Учитывая и ,
Мои вопросы:
Учитывая
- Предполагая, что мы можем решить в , есть ли способ решить без предварительного умножения (или деления), и . Или есть какое-то доказательство того, что нет пути.
- Существует ли более быстрый способ сравнения рациональных чисел, чем умножение знаменателей.
algorithms
integers
Реал Слав
источник
источник
Ответы:
Мое текущее исследование:
Начальная попытка некоторых общих правил
Можно попытаться составить несколько общих правил для решения рационального сравнения:
Предполагая все положительные :a,b,c,d
Еще одно правило:
С этого момента мы будем предполагать, что , потому что в противном случае мы можем либо решить его с помощью приведенных выше правил, либо изменить вопрос на , и мы все получим это условие.a<c∧b<d cd<?ab
Правила : This Правило в основном гласит, что вы всегда можете вычесть числители из знаменателей и установить результаты в качестве числителей, чтобы получить эквивалентную задачу. Я опущу доказательства.
Это правило позволяет вычесть левый числитель и знаменатель из правого числителя и знаменателя для эквивалентной задачи.
И конечно же есть масштабирование:
Используя эти правила, вы можете поиграть с вещами, применять их многократно, в умных комбинациях, но есть случаи, когда числа близки и патологичны.
Применяя предыдущие правила, вы можете уменьшить все эти проблемы до:
Иногда вы можете решить это прямо сейчас, иногда нет. Патологические случаи обычно имеют вид:
Затем вы переворачиваете это, и в результате получаете то же самое, только с немного меньшим. Каждое применение правил + флип уменьшает его на цифру / бит. AFAICT, вы не можете быстро решить ее, если не примените правила раз (один раз для каждой цифры / бита) в патологическом случае, сводя на нет их кажущееся преимущество.O(n)
Открытая проблема ??
Я понял, что эта проблема, кажется, сложнее, чем некоторые текущие открытые проблемы.
Еще более слабая проблема заключается в определении:
И еще слабее
Это открытая проблема проверки умножения . Это слабее, потому что, если у вас был способ определения , тогда можно легко определить , дважды протестировав алгоритм, , . Если и то, и другое верно, вы знаете, что .ad<?bc a d ? < b c b c ? < a d a d ≠ b cad=?bc ad<?bc bc<?ad ad≠bc
Теперь была открытой проблемой, по крайней мере, в 1986 году:ad=?c
Очень интересно, что он также упомянул вопрос о проверке умножения матриц :
С тех пор это было решено, и действительно можно проверить в время с помощью рандомизированного алгоритма (с являющимся размером входных матриц, так что это в основном линейное время в размер входа). Интересно, возможно ли свести целочисленное умножение к умножению матриц, особенно с их сходствами, учитывая сходство целочисленного умножения Карацубы с алгоритмами умножения матриц, которые последовали. Тогда, возможно, каким-то образом мы можем использовать алгоритм проверки матричного умножения для целочисленного умножения.n × nO(n2) n×n
Во всяком случае, поскольку, насколько мне известно, это все еще открытая проблема, более серьезная проблема обязательно открыт. Мне любопытно, будет ли решение проблемы проверки равенства иметь какое-либо отношение к проблеме проверки неравенства сравнения.ad<?cd
Небольшое изменение нашей проблемы будет, если дроби гарантированно будут сокращены до самых низких сроков; в этом случае легко сказать, если . Может ли это иметь какое-либо отношение к проверке сравнения для сокращенных фракций?ab=?cd
Еще более тонкий вопрос: что если бы у нас был способ протестировать , будет ли это распространяться на тестирование ? Я не понимаю, как вы можете использовать этот "оба пути", как мы использовали для .ad<?c ad=?c ad<?cd
Связанный:
Приблизительное распознавание нерегулярных языков конечными автоматами
Они делают некоторую работу по приблизительному умножению и рандомизированной проверке, которую я не полностью понимаю.
источник
Вот очень частичная попытка опровержения. Предположим, что мы можем использовать только (постоянное количество) сложений и вычитаний в нашем решении, а также постоянное число заранее определенным числам. Другими словами, мы можем сделать постоянное число , и т. Д. В нашем решателе. Тогда единственные величины, которые мы можем вычислить, имеют вид где - это предопределенные константы. Обратите внимание, что может быть вычислено за время .mod mod 2 mod 3 q=k1a+k2b+k3c+k4d=∑kia k q O(∑|a|)
Отредактированный Этот решающий элемент предназначен для определения бита если . Подумайте о том, чтобы взять качестве точек в . Бит определяется его положением относительно поверхности которая представляет собой гиперболоид в четырех измерениях. Если у нас есть точка во входном пространстве, вышеприведенное решение может вычислить точки на ограниченном расстоянии от этой входной точки, то есть эти точки т. д. Это определяет кубоид в 4-мерном пространстве.a d > b c a , b , c , d R 4 B a d = b c ( a , b , c , d ) q : | q - a | = k 1 ,B:B=1 ad>bc a,b,c,d R4 B ad=bc (a,b,c,d) q:|q−a|=k1,
(Как это сделать более точно?) Расстояние от кубоида до поверхности, как правило, не ограничено, и, следовательно, поверхность не может быть вычислена решающим устройством.
источник
Хороший вопрос. Вы бы приняли уровень доверия?
Возможно сделать приблизительное деление. Т.е.
Чтобы вычислить ограничивающие приблизительные коэффициенты a / b, сдвиньте вправо a на ceil (log_2 (b)), а также на этаж (log_2 (b)). Тогда мы знаем, что точное отношение находится между этими двумя значениями.
Затем, в зависимости от относительных размеров четырех целых чисел, можно исключить определенные случаи и получить 100% достоверность.
Можно повторить процедуру для radix, отличную от 2, и путем последовательности таких операций повысить уровень достоверности, пока не будет каким-либо образом наблюдаться смена знака / тай-брейка?
Это мой первый набросок метода.
источник
Конечно.
Идея: сравнить десятичное расширение по крупицам.
Единственный неприятный момент заключается в том, что мы должны сначала исключить равенство, потому что в противном случае мы не можем завершиться.
Полезно сначала сравнить целочисленные части, потому что это легко.
Учти это:
Обратите внимание, что
do-while
цикл должен завершиться, так как числа неравны. Мы не знаем, как долго это продолжается, хотя; если цифры очень близки, это может занять некоторое время.Очевидно, что нет дорогостоящих умножений; единственное, что нам нужно, это умножить номинаторы на . В частности, мы явно избегаем вычисления и .а д с б10 ad cb
Это быстро? Возможно нет. Есть много целочисленных делений, модулей и
gdc
s для вычисления, и у нас есть цикл, число итераций которого обратно пропорционально расстоянию между числами, которые мы сравниваем.Вспомогательный метод:
источник