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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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 3

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

Answer 4

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

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

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

while(true)

должно быть

while(r != 0)

Answer 5

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

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

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

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

Answer 6

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

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

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