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

Question

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

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

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

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

Answer 1

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

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};
}

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

Answer 2

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

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

Answer 3

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

Answer 4

Вы должны взглянуть на последовательность Фаре.
Учитывая ограничение на знаменатель d, последовательность Фареи - это каждая дробь, имеющая знаменатель <= d. <br>

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

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

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

Answer 5

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

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

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

while(true)

должно быть

while(r != 0)

Answer 6

Как насчет использования 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);
}