Diskuze: Float jako poměr celých čísel

hanpari

Člen

hanpari:27.7.2014 18:34

Ahoj všichni,

náhodou jsem zabrousil k metodám typu float a narazil jsem na zvláštní jev:

>>> f=2/5
>>> f.as_integer_ratio()
**(3602879701896397, 9007199254740992)**

Dokázal bych pochopit ledasco, ale toto mi uniká. Neví někdo, proč ta funkce nevrací inteligentnější hodnotu? A k čemu vlastně je takový poměr?

Odpovědět

27.7.2014 18:34

coells

Tvůrce

coells:27.7.2014 19:06

Jak si představuješ inteligentní hodnotu? Z mého pohledu a z hlediska matematiky je nejinteligentnější hodnota ta, která je nejblíže zadání. Takže hledáme racionální číslo r=p/q, které bude nejblíže vstupu:

from math import log10

def as_integer_ratio_by_coells(f):
    g = f
    while log10(g * 2) < 15: g *= 2
    return int(g * f * 10), int(g * 10)

p,q = as_integer_ratio_by_coells(2/5)
print(p, q)
print(p / q)

Nahoru Odpovědět

27.7.2014 19:06

hanpari

Člen

hanpari:27.7.2014 19:25

Nu, sice jsi mi toho moc nevysvětlil, ale prozradím ti sladké tajemství: Inteligentní hodnota (z mého pohledu) je poměr nejmenších možných celých čísel, v tomhle konkrétním případě 2 a 5.

A nedělej, že jsi to nepochopil

Abych ale přeložil tvou mystickou odpověď pro případné čtenáře, nejspíš jsi chtěl říct, že je to způsobené implementací konkrétního algoritmu, který nevrací vždy to, co bychom my, základní školou políbení, očekávali.
A dřív než se začneš čílit, že tohle jsi napsat nechtěl, tak ti rovnou odpovím, že si nemáš hrát na tajemnou Sibylu

Nahoru Odpovědět

27.7.2014 19:25

gcx11

Tvůrce

gcx11:27.7.2014 19:38

Ahoj. Můžeš zkusit jednodušší cestu.

>>> a = 2/7
>>> from fractions import Fraction
>>> a = Fraction(a)
>>> a
Fraction(2573485501354569, 9007199254740992)
>>> a.limit_denominator(10)
Fraction(2, 7)

Metoda as_integer_ratio() se snaží porovnávat přesně. Jenže v paměti se hodnota neuloží přesně, a tak dojde k nepřesnosti. Metoda limit_ratio vrací nejbližší přesný zlomek pro počet čísel v jmenovateli (?).
Odkaz:
https://docs.python.org/…actions.html?…

Nahoru Odpovědět

27.7.2014 19:38

hanpari

Člen

hanpari:27.7.2014 19:38

Abys neumřel hloupý

http://cs.wikipedia.org/wiki/Sibyla

Mimochodem, proč zrovna 15?

while log10(g * 2) < 15: g *= 2

Nahoru Odpovědět

27.7.2014 19:38

coells

Tvůrce

coells:27.7.2014 19:50

Budeš se možná divit, ale opravdu jsem to nepochopil. On je to totiž nesmysl a mě to nenapadlo, dokud jsi to nenapsal :-P

Takže budeme mluvit mojí řečí, abych nebyl tak tajemný.

Máme číslo f vyjádřené ve tvaru:

f = SUM(fx(i) \* (2 \*\* i)), pro i = [-1 .. -32], kde fx(i) = {0,1}

Chceme f vyjádřit ve tvaru p/q, kde platí:

p = SUM(px(i) \* (2 \*\* i)), pro i = [0 .. 31], kde px(i) = {0,1}
q = SUM(qx(i) \* (2 \*\* i)), pro i = [0 .. 31], kde qx(i) = {0,1}

Takže máme rovnici ve tvaru:

f = p / q
0 = f - p / q

označíme E jako chybu E = f - p / q

E = SUM(fx(i) \* (2 \*\* i)) - SUM(px(j) \* (2 \*\* j)) / SUM(qx(k) \* (2 \*\* k))

Úkolem je najít řešení naší rovnice tak, abychom minimalizovali chybu E.
Jedná se tedy o optimalizační úlohu, kde se vyskytuje 64 proměnných px(i),qx(i) a podmínka min(E).
Tuhle úlohu není až tak těžké vyřešit, ale těžké je dokázat, že vyjádření px a qx vede k minimální chybě E.

Teď proč je nesmysl, aby se vrátilo 2 a 5?

Počítač využívá binární reprezentaci desetinných čísel, takže pokud zapíšeš 2/5, musí najít f ve formě výše uvedené sumy, tedy fx(i) * (2 ** -i). V tu chvíli není možné zjistit, jaká byla originální hodnota, protože máme pouze přibližnou reprezentaci. V závislosti na hardwarové implementaci bude například platit, že 2/5 = (2*(10**32)+1) / (5*(10**32)+1).

Editováno 27.7.2014 19:51

Nahoru Odpovědět

27.7.2014 19:50

coells

Tvůrce

coells:27.7.2014 20:00

Zmínka o Sibyle je celkem trefná. Počítač má v sobě (většinou) deterministické CPU, nikoliv křišťálovou kouli. Neumí tedy uhádnout výsledek, který vyžaduješ, protože sis to spletl s příkladem ze základní školy :-)

Nahoru Odpovědět

27.7.2014 20:00

hanpari

Člen

hanpari:27.7.2014 20:14

Potíž je, že i když já něco takového tušil, není to tak samozřejmé, jak si nejspíš myslíš.
Pokud jsi opravdu nepochopil, oč mi jde (tomu se ale opravdu dá těžko uvěřit!), pak máš významný problém
3602879701896397/9007199254740992 vs. 2/5

Z hlediska počítače jasně, ale z pohledu základní školy?

Nahoru Odpovědět

27.7.2014 20:14

hanpari

Člen

hanpari:27.7.2014 20:22

Copak ty jsi také počítač, abys nechápal, proč mi to přijde divné?

Nahoru Odpovědět

27.7.2014 20:22

hanpari

Člen

hanpari:27.7.2014 22:02

Python se chlubí tím, že je high-level, čili že programátora chrání před problémy low-level jazyků jako c. Ve skutečnosti selhává na plné čáře, když si nedokáže problémy s binárním počítáním pohlídat, nebo to nepovažuje za důležité.
K čemu je typ Decimal? Decimal, i když pomalejší, by měl být standardní, a float se svými problémy volitelný. Koho zajímají problémy počítače s desetinou čárkou? V céčku možná, v pythonu? Určitě ne!
Stejně tak i index polí, který začíná od 0. 0,1,2... To je tedy u vysokoúrovňového programování průšvih. Každé dítě počítá od jedné.

Nahoru Odpovědět

27.7.2014 22:02

hanpari

Člen

hanpari:28.7.2014 9:16

Zkusil jsem to takto, samořejmě to platí jen pro čísla s ukončeným desetinným rozvojem.

def as_integer_ratio_by_han(f):
    retez = str(f)
    delka = 10 ** (len(retez) - retez.index(".") - 1)
    return (int(retez.replace(".", "")), delka)


assert as_integer_ratio_by_han(0.4)  == (4, 10)
assert as_integer_ratio_by_han(0.55) == (55, 100)
assert as_integer_ratio_by_han(1.234) == (1234, 1000)
print(as_integer_ratio_by_han(1/3)) # Tohle je ještě správně
# >>> (3333333333333333, 10000000000000000)
print(as_integer_ratio_by_han(20/3)) # Tohle už samozřejmě ne
# >>> (6666666666666667, 1000000000000000)

Nahoru Odpovědět

28.7.2014 9:16