È garantito che il seguente restituisca true per tutti i valori numerici e diversi da zero di x ?
bool IsRoundTrip(double x)
{
double y = 1 / (1 / x);
return x == y;
}
Quali condizioni potrebbero causare una discrepanza?
È garantito che il seguente restituisca true per tutti i valori numerici e diversi da zero di x ?
bool IsRoundTrip(double x)
{
double y = 1 / (1 / x);
return x == y;
}
Quali condizioni potrebbero causare una discrepanza?
Per semplificare le cose definendo un'implementazione concreta, assumerò (come altre risposte) che stiamo parlando di IEEE 754 a virgola mobile a 64 bit.
Ogni numero in virgola mobile ha tre parti: un segno, un esponente e una mantissa. (I dettagli tecnici sui bit nascosti sono irrilevanti per questa discussione).
La reciprocità non influisce sul segno
1 / (2**e * m) = (1 / 2**e) * (1 / m) = 2**-e * (1 / m) , quindi ci sono due modi in cui il doppio-alternativo può fallire nel fornire un punto fisso. Il facile è che l'esponente può essere un valore estremo tale da passare da un numero denormalizzato a uno che trabocca. Il secondo è che la mantissa può essere un non-punto fisso della doppia reciprocità.
Ho scritto un semplice programma per testare mantisse casuali:
import java.util.Random;
strictfp class RoundTrip
{
public static void main(String[] args)
{
long one = Double.doubleToLongBits(1.0);
Random rnd = new Random();
for (int i = 1; i < 1<<30; i++) {
long mantissa = rnd.nextLong() & 0xfffffffffffffL;
double x = Double.longBitsToDouble(one + mantissa);
double y = 1 / (1 / x);
if (x != y) {
System.out.println(Long.toHexString(one + mantissa));
System.out.println(x);
System.out.println(y);
break;
}
}
}
}
Ha dato rapidamente un po 'di output:
3ffeca41c09ebb2b
1.9243791126461456
1.9243791126461458
Ci si può aspettare che il programma trovi una risposta se falliscono solo 1 mantello su 2 ** 30. Con una leggera modifica, ho trovato che circa il 17,15% delle mantissine fallisce.
Analisi a portata di mano:
Ci sono 2 ** 52-1 mantissas che coprono l'intervallo aperto (1, 2) , e sono uniformemente distanziati.
Le stesse mantisse uniformemente distanziate coprono l'intervallo aperto (0.5, 1) , che contiene i reciproci. Notare che in questo intervallo un'unità nell'ultimo posto (1pulp), cioè la differenza tra valori consecutivi, ha un valore assoluto pari a metà dell'ulp nell'intervallo (1, 2) . Ma la reciprocazione non è un'operazione lineare, quindi in alcune parti dell'intervallo la densità dei valori richiesti è superiore a quella degli altri. Pertanto ci aspettiamo che la reciprocità non sia iniettiva.
Supponi valori x e x+dx , entrambi in (1, 2) , differiscono di 1ulp. Se si mappano sulla stessa reciproca mantissa, al massimo uno di loro può effettuare il round-trip. Qual è la probabilità di questa collisione?
x^-1 differenzia a -x^-2 , quindi la differenza tra 1/x e 1/(x+dx) è approssimativamente -dx/x^2 , o -2dx/x^2 ulps, quindi una differenza di un ulp prima della reciprocazione dà una differenza di -2/x^2 ulcere dopo la reciprocazione. Dato che la separazione tra due valori esattamente rappresentabili è 1ulp (per definizione), e assumendo (per semplificazione) nessun particolare allineamento tra mantisse e mantisse reciproca, possiamo stimare la probabilità di collisione come max(0, 1 - 2/x^2) , e possiamo approssimare la proporzione di collisioni come \int_1^2 max(0, 1 - 2/x^2) dx = \int_{\sqrt 2}^2 (1 - 2/x^2) dx = 3 - 2\sqrt 2 è circa 0,1716. Questo è in ottimo accordo con i miei risultati empirici per la proporzione di mantidi che non fanno il viaggio di andata e ritorno, quindi sembra ragionevole ipotizzare che una mantissa effettuerà un round trip a meno che il suo reciproco si scontrasse con quello di un'altra mantissa, nel qual caso solo uno dei due effettuerà il round-trip.
No. Come controesempio, 1/(1/49) funziona a 49,00000000000000710542735760100185871124267578125 sulla mia macchina.
Per un argomento più astratto, sia N il numero di numeri in virgola mobile rappresentabili nell'intervallo [1, 2). (In IEEE 754 a precisione doppia, N risulta essere 2 ^ 52) Esiste una banale corrispondenza uno-a-uno tra questo set ei numeri a virgola mobile nell'intervallo [1/2, 1): basta sottrarre 1 da l'esponente. Pertanto, ci sono anche N numeri in virgola mobile [1/2, 1).
All'interno di ogni intervallo [2 ^ k, 2 ^ (k + 1)), i numeri in virgola mobile sono equidistanti. Quindi:
I numeri in virgola mobile N / 2 nell'intervallo [3/2, 2) hanno reciproci nell'intervallo (1/2, 2/3). Ma ci sono solo ~ N / 3 numeri in virgola mobile disponibili in questo intervallo, quindi, secondo il principio del pigeonhole, esiste una coppia di numeri in virgola mobile distinti che hanno lo stesso reciproco a virgola mobile.
Oltre agli errori di arrotondamento con la prima o la seconda divisione, il virgola mobile IEEE ha + e - infinito e NaN (Not a Number), oltre a zero, che non funziona nemmeno con la formula per i numeri reali (che significa l'astrazione matematica, piuttosto che un formato di archiviazione del computer).
Senza entrare nei casi speciali dispari (zero, infinito, NaN), sembra probabile che l'unico modo per ottenere un risultato reale sia se ci sono due errori di arrotondamento che si verificano per cancellare o se il numero è esattamente rappresentabile nel punto mobile IEEE. Poiché esistono diversi schemi di arrotondamento per il virgola mobile IEEE e l'hardware potrebbe archiviare più bit rispetto alla rappresentazione per cercare di mantenere le cose accurate, la previsione di quando l'arrotondamento si annullerebbe sembra sia difficile che dipendente dall'hardware.
Questo non è il genere di cose con cui è stato inventato il floating point.
Regola empirica: se la lingua ha un tipo chiamato "double", probabilmente sarà falso per la maggior parte dei valori di x .
"Double" è in genere abbreviazione di "Double Precision Floating Point Number". Dicendo "Doppia precisione", implica "precisione finita", vale a dire l'arrotondamento avverrà ad un certo punto.
Alcune lingue supportano "Numeri di precisione arbitrari", che consentono di archiviare qualsiasi valore che abbia una rappresentazione finita e di solito può eseguire alcuni calcoli con questi numeri senza perdita di precisione. Questo ancora non copre tutte le opzioni, dato che alcuni numeri non hanno una rappresentazione finita - per esempio, 1/3 è vicino a 1.3333, ma non può essere scritto senza alcuni
Per gestire questo, alcune lingue supportano anche "Numeri simbolici", che in pratica significa che mantengono il numero come "1/3" e possono fare matematica con questo modulo.
L'uso di precisione arbitraria o numeri simbolici ha un costo elevato in termini di prestazioni, motivo per cui non è comune nelle lingue "mainstream". Anche le lingue che supportano queste forme hanno la tendenza a non essere tipizzate e si uniranno a tutti i tipi di numero sotto il nome "Numero" (ma questo non è affatto correlato al supporto dell'alta precisione).
Ho la maggior parte delle lingue che hanno un tipo "double", è identico (o al lease molto simile) a IEEE 754 Double Precision tipo.
Nota: il tuo codice potrebbe non fallire per x = 3, perché anche se il programma non può mantenere 1/3 con precisione, potrebbe anche fare un errore di arrotondamento simile quando si divide 1 da ciò che può contenere, e uscire con 3 ancora una volta.
Nota 2: troverai le librerie per la matematica arbitraria / simbolica per la maggior parte delle lingue che non le includono.
Esiste la possibilità che non siano uguali a causa della rappresentazione dei numeri in virgola mobile.
Informazioni sulla loro rappresentazione numerica possono essere trovate a ... link
La maggior parte delle volte, i numeri in virgola mobile sono normalizzati. Se il numero è un float denormalizzato, ci si può aspettare che l'algoritmo restituisca false. Se lo sarà o meno, dipenderà dal fatto che il compilatore scelga di riconoscere l'equivalenza matematica e ottimizzerà in base a ciò, o di implementare esattamente ciò che hai richiesto.
Potrebbero esserci altri casi in cui il tuo algoritmo potrebbe restituire false, ma questo è il primo che mi viene in mente.
Suppongo che ciò si verificherà in modo reale ogni volta che il compilatore ottimizza il calcolo. A parte questo, il controllo dell'eguaglianza è considerato un errore di programmazione in caso di doppio (a meno che la combinazione di compilatore / hardware non giustifichi il contrario). Questo non è limitato al tuo esempio, ma può verificarsi anche in altre situazioni. Come scrivere un doppio sul DB e leggerlo e confrontarlo con il valore originale che si può ancora avere in memoria.
No, non è sempre un viaggio di andata e ritorno. In matematica ( ie , il tipo che scrivi su carta con una matita), lo sarà, perché la matematica non avere un problema con una precisione limitata Ma in qualsiasi sistema di precisione finita ( per esempio , qualsiasi computer), ci saranno quantità della forma x != 1/(1/x) . È assolutamente banale dimostrare che quando x è 3, l'aritmetica decimale a precisione finita non può rendere 1/(1/3) uscire a 3. 1/3 = > 0.33333 ... e non importa quante cifre lo estenderai, sarai comunque errato. L'aritmetica binaria a precisione finita ha lo stesso problema con altri valori.
Leggi altre domande sui tag floating-point math