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

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

6 голосов
/ 02 апреля 2012

Учитывая число с плавающей запятой, я ищу, чтобы получить 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. Фракция не упрощена, поэтому любые последующие вычисления с использованием этой фракции, вероятно, будут тратить много времени.

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

1 Ответ

3 голосов
/ 02 апреля 2012

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

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

...