Перформантный алгоритм для рационализации поплавков

Question

Учитывая число с плавающей запятой, я ищу, чтобы получить String представление рационального числа, аппроксимирующего десятичное число (с точностью до заданного допуска ε хорошо). Мой текущий подход заключается в следующем:

String rationalize(double d)
{
    String s = Double.toString(d);
    s = s.substring(s.indexOf('.')+1, s.length());
    return s + " / " + ApintMath.pow(new Apint(10), s.length()).toString();
}

Если вы не знакомы с этим, ApintMath.pow будет работать даже с произвольно длинными числами, что хорошо, потому что я пытаюсь преобразовать десятичные дроби в тысячи десятичных знаков. Производительность моего алгоритма ужасна.

Я приписываю это двум вещам, но может быть больше:

1. Мой подход к получению дроби довольно наивен. Я уверен, что есть лучший способ.
2. Фракция не упрощена, поэтому любые последующие вычисления с использованием этой фракции, вероятно, будут тратить много времени.

Как бы вы это сделали? Есть другие области, о которых я не говорил, которые замедляют меня?

Answer 1

Здесь показана реализация дерева Штерна-Броко, но вам придется профилировать, чтобы увидеть, что лучше.

Приложение: у меня были хорошие результаты при использовании org.jscience.mathematics.number.Rational в линейных системах; org.apache.commons.math.fraction.BigFraction предлагает несколько конструкторов для double это может быть полезно. Все бросают подходящие исключения для неопределенных значений.