проверить, достаточно ли десятичное число близко к рациональному числу - PullRequest
Новая
       62

проверить, достаточно ли десятичное число близко к рациональному числу

1 голос
/ 14 октября 2010

Учитывая десятичное число x, я хочу проверить, находится ли x в пределах 10 ^ -12 от рационального числа со знаменателем 9999 или меньше. Очевидно, я мог бы сделать это, посмотрев на x, 2x, 3x и т. Д. И выяснив, достаточно ли одно из них близко к целому. Но есть ли более эффективный алгоритм?

Ответы [ 3 ]

5 голосов
/ 14 октября 2010

Существует алгоритм, называемый алгоритм продолженной дроби , который даст вам «наилучшие» рациональные приближения в определенном смысле.Вы можете остановиться, когда ваш знаменатель превысит 9999, а затем вернуться к предыдущему конвергенту и сравнить, достаточно ли он близок.Конечно, если десятичное число является достаточно малым рациональным числом, алгоритм завершится рано.

2 голосов
/ 14 октября 2010

Итак, пара вещей:

Я предполагаю, что под десятичным знаком x вы имеете в виду некоторое представление с плавающей запятой x.То есть вы намереваетесь реализовать это в каком-то формате, который на самом деле не может точно представлять .1 или 1/3 и т. Д. Если вы делаете это вручную или что-то еще, что имеет свой собственный способ представления десятичных дробей, это победит 't применяются.

Во-вторых, вы привязаны к этим конкретным знаменателям и допускам?Я спрашиваю, потому что, если вы в порядке со степенями 2 (например, знаменатель до 8192 с допуском 2 ^ -35), вы можете легко воспользоваться тем фактом, что все числа с плавающей запятой в стиле IEEE-754 являются рациональными числами.Используйте показатель степени, чтобы определить, какая цифра в мантиссе соответствует 2 ^ -13, затем убедитесь, что следующие 22 цифры мантиссы равны 0 (или не более 22, если точность не достаточно высока, чтобы включить 22 после этой точки).Если это так, у вас это есть.

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

1 голос
/ 14 октября 2010

Я вижу, что вы уже приняли ответ, но я все равно буду звонить.

Метод грубой силы не должен проверять каждый знаменатель.Если вы работаете в обратном направлении, вы можете исключить не только число, которое вы только что проверили, но и каждый его фактор.Например, после того как вы проверили 9999, вам не нужно проверять 3333, 1111, 909, 303, 101, 99, 33, 11, 9, 3 или 1;если число может быть выражено как дробь одного из них, оно также может быть выражено как дробь 9999. Оказывается, что каждое число до 5000 является фактором, по меньшей мере, одного числа от 5000 до 9999, поэтому вы сократилиВаше пространство поиска пополам.

Редактировать: Я нашел эту проблему достаточно интересной, чтобы кодировать решение на Python. 

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def simplify(fraction_tuple):
    divisor = gcd(fraction_tuple[0], fraction_tuple[1])
    return fraction_tuple[0] / divisor, fraction_tuple[1] / divisor

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False):
    best_error, best_result = abs(value), (0,1)
    for denominator in range(max_denominator/2+1, max_denominator+1):
        numerator = round(value * denominator)
        error = abs(value - (numerator / denominator))
        if error < best_error:
            best_error = error
            best_result = int(numerator), denominator
            if error <= tolerance:
                break
    if enforce_tolerance and best_error > tolerance:
        return None
    return simplify(best_result)
...