Comment puis-je transformer un nombre à virgule flottante dans la fraction la plus proche représentée par un numérateur et le dénominateur d'octets?

Question

Comment puis-je écrire un algorithme qui donne un nombre à virgule flottante, et tente de représenter est aussi précisément que possible à l'aide d'un numérateur et un dénominateur, à la fois limitée à la portée d'un octet Java?

La raison est qu'un dispositif I2C veut un numérateur et le dénominateur, alors qu'il serait judicieux de donner un flotteur.

Par exemple, 3.1415926535... entraînerait 245/78, plutôt que 314/100 ou 22/7.

En termes d'efficacité, ce serait appelé environ trois fois au début du programme, mais après que pas du tout. Donc, un algorithme lent est pas aussi mauvais.

Answer 1

J'ai écrit un code (en Java, même) de faire exactement la chose que vous demandez. Dans mon cas, je avais besoin d'afficher un facteur d'échelle à la fois comme un pourcentage et un rapport. L'exemple le plus connu de c'est la boîte de dialogue de zoom que vous voyez dans les éditeurs d'image, tels que GIMP.

Vous pouvez trouver mon code ici , dans le updateRatio () à partir de la ligne 1161. vous pouvez simplement l'utiliser, tant que la licence LGPL fonctionne pour vous. Ce que je l'ai fait suite essentiellement ce qui se fait dans le GIMP --- c'est une de ces choses où il y a à peu près une seule efficace, façon sensée de le faire.

Answer 2

Voici le code je à la fin (basé sur le code de uckelman)

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

Merci pour ceux qui ont aidé

Answer 3

Comment êtes-vous inquiet au sujet de l'efficacité? Si vous n'êtes pas appeler cette fonction de conversion 100s de fois par seconde ou plus, il ne serait probablement pas si difficile à force brute par chaque dénominateur possible (très probablement seulement 255 d'entre eux) et trouver celui qui donne le plus proche approximation (calcul du numérateur pour aller avec le dénominateur est la constante de temps).

Answer 4

Je commentaires, mais je n'ai pas encore rep ...

La réponse de Eric ne considère pas au-dessus du cas où un résultat exact est possible. Par exemple, si vous utilisez 0.4 en entrée, la représentation doit être 2/5, auquel cas vous vous retrouvez avec une division par zéro dans la troisième itération de la boucle (r = 0 sur la deuxième boucle => r = 1 / erreur de r sur la troisième).

Vous voulez modifier la boucle while pour exclure cette option:

while(true)

doit être

while(r != 0)

Answer 5

Vous devriez regarder la séquence Farey.
Compte tenu d'une limite sur le dénominateur D, la séquence est Farey chaque fraction ayant le dénominateur <= d.

Alors, vous simplement prendre votre flotteur et le comparer à la valeur résolue de la fraction Farey. Cela vous permettra de représenter votre flotteur en termes de nombres réels répéter décimales.

Voici une page sur sa mise en œuvre en java:
http://www.merriampark.com/fractions.htm

Voici une bonne démonstration de leur utilisation:
http://www.maths.surrey.ac .uk / hébergés-sites / R.Knott / fractions / fareySB.html

Answer 6

Qu'en est-il de l'utilisation 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);
}