Limitazioni di implementazione di float.as_integer_ratio()

Recentemente, un corrispondente menzionato float.as_integer_ratio(), nuovo in Python 2.6, osservando che le tipiche implementazioni in virgola mobile sono approssimazioni essenzialmente razionali dei numeri reali. Incuriosito, ho dovuto provare π:Limitazioni di implementazione di float.as_integer_ratio()

>>> float.as_integer_ratio(math.pi); 
(884279719003555L, 281474976710656L)

sono rimasto un po 'sorpreso di non vedere più accurate risultato a causa di Arima,:

(428224593349304L, 136308121570117L)

Ad esempio, questo codice:

#! /usr/bin/env python 
from decimal import * 
getcontext().prec = 36 
print "python: ",Decimal(884279719003555)/Decimal(281474976710656) 
print "Arima: ",Decimal(428224593349304)/Decimal(136308121570117) 
print "Wiki: 3.14159265358979323846264338327950288"

produce questa uscita:

 
python: 3.14159265358979311599796346854418516 
Arima: 3.14159265358979323846264338327569743 
Wiki: 3.14159265358979323846264338327950288

Certo, il risultato è corretto data la precisione offerta dai numeri a virgola mobile a 64 bit, ma mi porta a chiedere: come posso scoprire di più sui limiti di implementazione di as_integer_ratio()? Grazie per qualsiasi consiglio.

Link aggiuntivi: Stern-Brocot tree e Python source.

fonte

2010-01-16 trashgod

La risposta accettata è fuorviante. Il metodo 'as_integer_ratio' restituisce il numeratore e il denominatore di una frazione il cui valore _exactly_ corrisponde al valore del numero a virgola mobile passato ad esso. Se vuoi una rappresentazione perfettamente accurata del tuo float come frazione, usa 'as_integer_ratio'. Se vuoi una _approximation_ semplificata con denominatore e numeratore più piccoli, guarda in fractions.Fraction.limit_denominator'. IOW, 'math.pi' è un'approssimazione di π. Ma '884279719003555/281474976710656' è _non_ un'approssimazione a' math.pi'; è esattamente _ uguale a questo. –

@ Mark Dickinson: il tuo punto è ben preso; chiarisce questa [risposta correlata] (https://stackoverflow.com/a/2076903/230513). Anche se la [risposta accettata] (https://stackoverflow.com/a/2076296/230513) potrebbe richiedere un po 'di manutenzione, mi ha aiutato a vedere dove il mio pensiero era andato storto. – trashgod

L'algoritmo utilizzato da as_integer_ratio solo considers powers of 2 in the denominator. Ecco un (probabilmente) better algorithm.

fonte

2010-01-16 05:24:19

Aha, '281474976710656 = 2^48'. Ora vedo da dove vengono i valori. Interessante per confrontare le implementazioni: http: //svn.python.org/view/python/trunk/Objects/floatobject.c? revision = 77139 & view = markup – trashgod

Dire che l'algoritmo non è accurato è una spiegazione errata. 'float.as_integer_ratio()' restituisce semplicemente una coppia (numeratore, denominatore) che è * rigorosamente uguale * al numero in virgola mobile in questione (ecco perché il denominatore è un potere di due, poiché i numeri a virgola mobile standard hanno un base-2 esponente). La perdita di accuratezza deriva dalla stessa rappresentazione in virgola mobile, * not * da float.as_integer_ratio(), che in realtà è senza perdite. –

IIUC, l'algoritmo è sufficientemente preciso per una determinata precisione in virgola mobile. La genesi del denominatore è ciò che mi ha lasciato perplesso. L'algoritmo non produrrebbe mai il risultato unico di Arima e non ci sarebbe alcun punto dato la precisione richiesta. – trashgod

Passare attraverso il repository di origine per Python, scoprire chi ha commesso il codice di interesse e inviarlo via email.

fonte

2010-01-16 05:21:43

Posso consiglia gmpy s' attuazione del Stern-Brocot tree:

>>> import gmpy 
>>> import math 
>>> gmpy.mpq(math.pi) 
mpq(245850922,78256779) 
>>> x=_ 
>>> float(x) 
3.1415926535897931 
>>>

ancora una volta, il risultato è "corretta all'interno della precisione dei carri a 64 bit" (53-bit "i cosiddetti" mantisse; -), ma:

>>> 245850922 + 78256779 
324107701 
>>> 884279719003555 + 281474976710656 
1165754695714211L 
>>> 428224593349304L + 136308121570117 
564532714919421L

... precisione di gmpy si ottiene molto di più economico (in termini di somma dei valori numeratore e denominatore) di Arima di, e tanto meno di Python 2.6 -)

! 363.210

fonte

2010-01-16 05:28:26

Vedo il vantaggio. Ho già utilizzato GMP da Ada, quindi 'gmpy' sarà utile. http://code.google.com/p/adabindinggmpmpfr/ – trashgod

Si ottiene approssimazioni migliori usando

fractions.Fraction.from_float(math.pi).limit_denominator()

Le frazioni sono inclusi in quanto forse la versione 3.0. Tuttavia, math.pi non ha una precisione sufficiente a restituire un'approssimazione di 30 cifre.

fonte

2010-01-16 09:54:11 fesno

Limitazioni di implementazione di float.as_integer_ratio()

risposta

Problemi correlati