Come posso trasformare un numero in virgola mobile nella frazione più vicina rappresentato da un numeratore e il denominatore di byte?

Question

Come faccio a scrivere un algoritmo che, dato un numero in virgola mobile, e tenta di rappresentare è il più accuratamente possibile utilizzando un numeratore e un denominatore, sia limitato alla gamma di un byte Java?

La ragione di questo è che un dispositivo I2C vuole un numeratore e denominatore, mentre avrebbe senso per dare un galleggiante.

Per esempio, 3.1415926535... si tradurrebbe in 245/78, piuttosto che 314/100 o 22/7.

In termini di efficienza, questo sarebbe stato chiamato circa tre volte all'inizio del programma, ma dopo che non a tutti. Quindi un algoritmo lento non è anche male.

Answer 1

Ho scritto un po 'di codice (in Java, anche) per fare la cosa giusta che stai chiedendo. Nel mio caso, avevo bisogno di visualizzare un fattore di scala con una percentuale e un rapporto. L'esempio più familiare di questo è la finestra di zoom si vede in editor di immagini, come ad esempio il GIMP.

È possibile trovare il mio codice qui , nel metodo updateRatio () a partire da linea di 1161. si può semplicemente utilizzare esso, fino a quando la licenza LGPL funziona per voi. Quello che ho fatto essenzialmente segue ciò che è fatto in GIMP --- questa è una di quelle cose in cui non c'è praticamente un solo modo sensato efficace per farlo.

Answer 2

Ecco il codice che ho usato alla fine (basato sul codice di 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};
}

Grazie per coloro che hanno contribuito

Answer 3

Come preoccupato siete circa l'efficienza? Se non sei chiamare questa funzione di conversione 100s di volte al secondo o più, allora probabilmente non sarebbe così difficile forza bruta attraverso ogni possibile denominatore (solo molto probabilmente 255 di loro) e trovare uno che dà la più vicina approssimazione (calcolando il numeratore per andare con il denominatore è costante di tempo).

Answer 4

vorrei commentare, ma non ho ancora rep ...

La risposta di Eric sopra non prende in considerazione il caso in cui un risultato esatto è possibile. Ad esempio, se si utilizza 0,4 come input, allora la rappresentazione deve essere 2/5, nel qual caso si finisce con una divisione per zero nella terza iterazione del ciclo (r = 0 sul secondo anello => r = 1 / r errore sul terzo).

Così si vuole modificare il ciclo while per escludere questa possibilità:

while(true)

dovrebbe essere

while(r != 0)

Answer 5

Si dovrebbe guardare il Farey Sequence.
Dato un limite al denominatore d, il Farey sequenza è ogni frazione avente denominatore <= d.

Poi, si dovrebbe semplicemente prendere il galleggiante e confrontarlo con il valore risolto della frazione Farey. Questo vi permetterà di rappresentare il galleggiante in termini di reali ripetere-decimali.

Questa è una pagina sulla sua attuazione in java:
http://www.merriampark.com/fractions.htm

Ecco una buona dimostrazione del loro uso:
http://www.maths.surrey.ac .uk / ospitate siti / R.Knott / frazioni / fareySB.html

Answer 6

Cosa succede ad usare BigFraction di 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);
}