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

Question

Comment puis-je écrire un algorithme qui a donné un nombre à virgule flottante, et tente de représenter est aussi précisément que possible en utilisant un numérateur et un dénominateur, tous deux limités à la plage d'un octet Java?

La raison en est qu'un périphérique I2C veut un numérateur et un dénominateur, alors qu'il serait logique de lui donner un flottant.

Par exemple, 3.1415926535... entraînerait 245/78, plutôt que 314/100 ou 22/7. En termes d'efficacité, cela serait appelé environ trois fois au début du programme, mais pas du tout. Donc un algorithme lent n'est pas trop mauvais.

Answer 1

J'ai écrit du code (en Java, même) pour faire exactement ce que vous demandez. Dans mon cas, j'avais besoin d'afficher un facteur d'échelle comme un pourcentage et un ratio. L'exemple le plus familier de ceci est le dialogue de zoom que vous voyez dans les éditeurs d'image, tels que GIMP.

Vous pouvez trouver mon code here, dans la méthode updateRatio() à partir de la ligne 1161. Vous pouvez simplement l'utiliser, tant que la licence LGPL fonctionne pour vous. Ce que j'ai fait essentiellement suit ce qui est fait dans le GIMP --- c'est une de ces choses où il n'y a pratiquement qu'une manière efficace et sensée de le faire.

Answer 2

À quel point êtes-vous inquiet au sujet de l'efficacité? Si vous n'appelez pas cette fonction de conversion 100 fois par seconde ou plus, alors il ne sera probablement pas si difficile de forcer tous les dénominateurs possibles (probablement seulement 255) et de trouver celui qui donne le plus approximation (calculer le numérateur pour aller avec le dénominateur est le temps constant).

Answer 3

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 4

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

La réponse d'Eric ci-dessus ne considère pas le cas où un résultat exact est possible. Par exemple, si vous utilisez 0.4 en entrée, la représentation devrait être 2/5, auquel cas vous finissez 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 sur le troisième).

Vous souhaitez modifier la boucle while pour exclure cette option:

while(true) 

devrait être

while(r != 0) 

Answer 5

Vous devriez regarder la séquence Farey.
Étant donné une limite sur le dénominateur d, la séquence de Farey est chaque fraction ayant le dénominateur < = d. Ensuite, vous prendrez simplement votre flotteur et le comparerez avec la valeur résolue de la fraction Farey. Cela vous permettra de représenter votre flottant en termes de réels répétés-décimaux.

Voici une page sur son implémentation en Java:
http://www.merriampark.com/fractions.htm

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

Answer 6

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