Как я могу превратить число с плавающей запятой в ближайшую дробь, представленную числителем и знаменателем байтов?

Как я могу написать алгоритм, который задает число с плавающей запятой и пытается представить его как можно точнее, используя числитель и знаменатель, оба из которых ограничены диапазоном байта Java?

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

Например, 3.1415926535... приведет к 245/78, а не 314/100 или 22/7.

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


java algorithm floating-point math fractions
person Eric    schedule 01.11.2009    source источник
comment
245/78 является лучшим приближением к PI с числителем и знаменателем размером в байт.   -  person pavium    schedule 01.11.2009
comment
Обратите внимание, что байты Java подписаны, поэтому 245 не является значением байта в Java.   -  person starblue    schedule 01.11.2009
comment
Вероятно, это должно быть помечено как математика. Я бы сделал это сам, но у меня пока нет достаточной репутации.   -  person uckelman    schedule 01.11.2009
comment
Обратите внимание, что байты Java подписаны, поэтому 245 не является значением байта в Java - упс. Думаю, я хотел беззнаковые байты   -  person Eric    schedule 01.11.2009
comment
Проверьте код rosetta, он реализован на разных языках rosettacode.org/wiki/Convert_decimal_number_to_rational   -  person jcubic    schedule 26.03.2020

Ответы (6)


arrow_upward
3
arrow_downward

Я написал некоторый код (даже на Java), чтобы сделать именно то, о чем вы просите. В моем случае мне нужно было отобразить коэффициент масштабирования как в процентах, так и в соотношении. Наиболее знакомым примером этого является диалоговое окно масштабирования, которое вы видите в графических редакторах, таких как GIMP.

Вы можете найти мой код здесь, в методе updateRatio(), начиная со строки 1161. Вы можете просто использовать его, если лицензия LGPL работает на вас. То, что я сделал, в основном следует тому, что сделано в GIMP — это одна из тех вещей, где есть практически только один эффективный и разумный способ сделать это.

person uckelman    schedule 01.11.2009

arrow_upward
4
arrow_downward

Вот код, который я использовал в конце (на основе кода Укельмана)

public static int[] GetFraction(double input)
{
    int p0 = 1;
    int q0 = 0;
    int p1 = (int) Math.floor(input);
    int q1 = 1;
    int p2;
    int q2;

    double r = input - p1;
    double next_cf;
    while(true)
    {
        r = 1.0 / r;
        next_cf = Math.floor(r);
        p2 = (int) (next_cf * p1 + p0);
        q2 = (int) (next_cf * q1 + q0);

        // Limit the numerator and denominator to be 256 or less
        if(p2 > 256 || q2 > 256)
            break;

        // remember the last two fractions
        p0 = p1;
        p1 = p2;
        q0 = q1;
        q1 = q2;

        r -= next_cf;
    }

    input = (double) p1 / q1;
    // hard upper and lower bounds for ratio
    if(input > 256.0)
    {
        p1 = 256;
        q1 = 1;
    }
    else if(input < 1.0 / 256.0)
    {
        p1 = 1;
        q1 = 256;
    }
    return new int[] {p1, q1};
}

Спасибо тем, кто помог

person Eric    schedule 01.11.2009
comment
т.е. вы используете подходящие дроби цепных дробей. en.wikipedia.org/wiki/ Это дает некоторое приближение, но почему оно должно быть оптимальный в заданном диапазоне числителей/знаменателей? - person Echsecutor; 06.10.2017

arrow_upward
3
arrow_downward

Насколько вы беспокоитесь об эффективности? Если вы не вызываете эту функцию преобразования 100 раз в секунду или более, то, вероятно, будет не так уж сложно перебрать все возможные знаменатели (скорее всего, только 255 из них) и найти, какой из них дает самое близкое значение. аппроксимация (вычисление числителя вместе со знаменателем происходит за постоянное время).

person Amber    schedule 01.11.2009
comment
Эффективность на самом деле не проблема. Однако я надеялся (и смутно припоминаю), что есть метод более эффективный, чем грубая сила. - person Eric; 01.11.2009
comment
Нет, вы не Йоханнес - учитывая конкретный знаменатель, вы можете напрямую вычислить ближайший числитель - поскольку вы хотите, чтобы A и B были такими, что A / B = C, вы просто вычисляете B * C и округляете до ближайшего целого числа, и это ваш числитель. - person Amber; 01.11.2009
comment
Это лучше, чем метод непрерывной дроби, поскольку вы ограничены значениями байтов. - person Thorbjørn Ravn Andersen; 01.11.2009

arrow_upward
1
arrow_downward

Я бы прокомментировал, но у меня пока нет представителя...

Ответ Эрика выше не рассматривает случай, когда возможен точный результат. Например, если вы используете 0,4 в качестве входных данных, то представление должно быть 2/5, и в этом случае вы получите деление на ноль на третьей итерации цикла (r=0 на втором цикле => r = 1/ r ошибка на третьем).

Итак, вы хотите изменить цикл while, чтобы исключить эту опцию:

while(true)

должно быть

while(r != 0)
person LZM    schedule 16.12.2009

arrow_upward
1
arrow_downward

Вам следует взглянуть на последовательность Фари.
Учитывая ограничение на знаменатель d, последовательность Фари состоит из каждой дроби со знаменателем ‹= d.

Затем вы просто берете поплавок и сравниваете его с разрешенным значением дроби Фари. Это позволит вам представить поплавок в виде повторяющихся десятичных чисел.

Вот страница о его реализации в Java:
http://www.merriampark.com/fractions.htm

Вот хорошая демонстрация их использования:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/fareySB.html

person Matthew    schedule 08.11.2011
comment
Первая ссылка (merriampark.com/fractions.htm) не работает. - person Jim; 12.10.2019

arrow_upward
0
arrow_downward

Как насчет использования Apache BigFraction:

import org.apache.commons.math3.fraction.BigFraction;

public static BigFraction GetBigFraction(double input)
{
    int precision = 1000000000;
    return new BigFraction((int)(input * (double)precision), precision);
}
person YOKA    schedule 04.01.2013