Dlaczego skrót nieskończoności Pythona ma cyfry π?

241

Hash nieskończoności w Pythonie ma cyfry pasujące do pi :

>>> inf = float('inf')
>>> hash(inf)
314159
>>> int(math.pi*1e5)
314159

Czy to tylko zbieg okoliczności, czy jest to celowe?

— wim
źródło

Nie jestem pewien, ale domyślam się, że jest to tak celowe, jak hash(float('nan'))bycie 0.

— cs95,

Hmm, nie ma o tym żadnej wzmianki sys.hash_info. Jajko wielkanocne?

— wim

123

Zapytaj Tima Petersa. Oto zatwierdzenie, w którym 19 lat temu wprowadził tę stałą: github.com/python/cpython/commit/… . Zachowałem te specjalne wartości, kiedy przerobiłem hash numeryczny w bugs.python.org/issue8188

— Mark Dickinson

@MarkDickinson Thanks. Wygląda na to, że Tim mógł pierwotnie użyć cyfr e dla skrótu -inf.

— wim

@ wim Ah tak, prawda. I najwyraźniej zmieniłem to na -314159. Zapomniałem o tym.

— Mark Dickinson

_PyHASH_INFjest zdefiniowany jako stała równa 314159.

Nie mogę znaleźć dyskusji na ten temat ani komentarzy podających powód. Myślę, że został wybrany mniej więcej arbitralnie. Wyobrażam sobie, że dopóki nie używają tej samej znaczącej wartości dla innych skrótów, nie powinno to mieć znaczenia.

— Patrick Haugh
źródło

Mały nitpick: z definicji jest prawie nieuniknione, że ta sama wartość będzie używana dla innych skrótów, np. W tym przypadku hash(314159)również 314159. Spróbuj także w Pythonie 3 hash(2305843009214008110) == 314159(to wejście jest 314159 + sys.hash_info.modulusitd.)

— ShreevatsaR

@ShreevatsaR Chodziło mi po prostu o to, że dopóki nie wybiorą tej wartości jako skrótu innych wartości z definicji, to wybranie znaczącej wartości takiej jak ta nie zwiększy prawdopodobieństwa kolizji skrótu

— Patrick Haugh

220

Podsumowanie: To nie przypadek; _PyHASH_INFjest zapisany na stałe jako 314159 w domyślnej implementacji CPython w Pythonie i został wybrany jako dowolna wartość (oczywiście z cyfr π) przez Tim Peters w 2000 roku .

Wartość hash(float('inf'))jest jednym z zależnych od systemu parametrów wbudowanej funkcji skrótu dla typów numerycznych i jest również dostępna jak sys.hash_info.infw Pythonie 3:

>>> import sys
>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> sys.hash_info.inf
314159

(Te same wyniki również w przypadku PyPy .)

Pod względem kodu hashjest wbudowaną funkcją. Nazywając go na obiekt typu float Python wywołuje funkcję, której wskaźnik jest przez tp_hashatrybut z wbudowanym typu float ( PyTypeObject PyFloat_Type), która jestfloat_hash funkcja, zdefiniowanego jako return _Py_HashDouble(v->ob_fval), co z kolei ma

    if (Py_IS_INFINITY(v))
        return v > 0 ? _PyHASH_INF : -_PyHASH_INF;

gdzie _PyHASH_INFjest zdefiniowany jako 314159:

#define _PyHASH_INF 314159

Jeśli chodzi o historię, pierwsza wzmianka o 314159tym kontekście w kodzie Pythona (można to znaleźć za pomocą git bisectlub git log -S 314159 -p) została dodana przez Tima Petersa w sierpniu 2000 r. W tym, co obecnie zatwierdza 39dce293 w cpythonrepozytorium git.

Komunikat zatwierdzenia mówi:

Poprawka dla http://sourceforge.net/bugs/?func=detailbug&bug_id=111866&group_id=5470 . To był błąd wprowadzający w błąd - prawdziwy „błąd” polegał hash(x)na zwróceniu błędu, gdy xwystępuje nieskończoność. Naprawiono to. Dodano nowe Py_IS_INFINITYmakro do pyport.h. Zmieniono kod, aby zmniejszyć rosnące powielanie liczb mieszanych i liczb zespolonych, co doprowadziło do logicznego zakończenia wcześniejszego dźgnięcia Trenta. Naprawiono niezwykle rzadki błąd, w którym haszowanie liczb zmiennoprzecinkowych mogło zwrócić -1, nawet jeśli nie wystąpił błąd (nie marnował czasu na próby zbudowania przypadku testowego, po prostu było oczywiste z kodu, że może się zdarzyć). Ulepszony złożony skrót, który hash(complex(x, y))nie jest już systematycznie równy hash(complex(y, x)).

W szczególności w tym zatwierdzeniu rozerwał kod static long float_hash(PyFloatObject *v)in Objects/floatobject.ci uczynił go sprawiedliwym return _Py_HashDouble(v->ob_fval);, aw definicji long _Py_HashDouble(double v)in Objects/object.cdodał linie:

        if (Py_IS_INFINITY(intpart))
            /* can't convert to long int -- arbitrary */
            v = v < 0 ? -271828.0 : 314159.0;

Jak wspomniano, był to arbitralny wybór. Zauważ, że 271828 jest utworzony z pierwszych kilku cyfr dziesiętnych e .

Powiązane później zatwierdza:

Autor: Mark Dickinson w kwietniu 2010 r. ( Także ), dzięki czemu ten Decimaltyp zachowuje się podobnie
Autor: Mark Dickinson w kwietniu 2010 r. ( Także ), przenosząc tę kontrolę na górę i dodając przypadki testowe
Autor: Mark Dickinson w maju 2010 jako numer 8188 , całkowicie przepisując funkcję haszującą do jej obecnej implementacji , ale zachowując ten specjalny przypadek, nadając stałej nazwę _PyHASH_INF(usuwając również 271828, dlatego hash(float('-inf'))powraca w Pythonie 3, -314159a nie -271828jak w Pythonie 2)
Autor: Raymond Hettinger w styczniu 2011 r. , Dodając wyraźny przykład w „Co nowego” dla Python 3.2 sys.hash_infopokazujący powyższą wartość. (Zobacz tutaj .)
Autor: Stefan Krah w marcu 2012 r. Modyfikujący moduł dziesiętny, ale zachowujący ten skrót.
Christian Heimes w listopadzie 2013 roku , przeniósł się do definicji _PyHASH_INFz Include/pyport.hcelu Include/pyhash.h, gdzie obecnie mieszka.

— ShreevatsaR
źródło

Wybór -271828 dla -Inf eliminuje wszelkie wątpliwości, że skojarzenie pi było przypadkowe.

— Russell Borogove

@RussellBorogove Nie, ale sprawia, że jest to około milion razy mniej prawdopodobne;)

— fajka

@cmaster: Patrz część wyżej, gdzie jest napisane: maj 2010, mianowicie część dokumentacji na mieszaja typów liczbowych i numerze 8188 - chodzi o to, że chcemy hash(42.0)być taka sama, jak hash(42)również takie same, jak hash(Decimal(42))i hash(complex(42))i hash(Fraction(42, 1)). Rozwiązanie (autorstwa Marka Dickinsona) jest eleganckie IMO: zdefiniowanie funkcji matematycznej, która działa dla dowolnej liczby wymiernej, i wykorzystanie faktu, że liczby zmiennoprzecinkowe są również liczbami wymiernymi.

— ShreevatsaR

@ShreevatsaR Ach, dziękuję. Chociaż nie chciałbym zagwarantować tych równości, dobrze jest wiedzieć, że istnieje dobre, solidne i logiczne wyjaśnienie pozornie złożonego kodu :-)

— cmaster - przywróć monikę

@cmaster Funkcja skrótu dla liczb całkowitych jest po prostu hash(n) = n % Mtam, gdzie M = (2 ^ 61 - 1). Uogólnia się to dla liczby wymiernej od do hash(p/q) = (p/q) mod Mz interpretowanym podziałem modulo M (innymi słowy:) hash(p/q) = (p * inverse(q, M)) % M. Powód, dla którego tego chcemy: jeśli dumieścimy w nagraniu , d[x] = fooa następnie będziemy mieli x==y(np. 42,0 == 42), ale d[y]to nie to samo, co d[x], będziemy mieli problem. Większość pozornie złożonego kodu pochodzi z samej natury formatu zmiennoprzecinkowego, aby właściwie odzyskać ułamek i potrzebować specjalnych przypadków dla wartości inf i NaN.

— ShreevatsaR

W rzeczy samej,

sys.hash_info.inf

zwraca 314159. Wartość nie jest generowana, jest wbudowana w kod źródłowy. W rzeczywistości,

hash(float('-inf'))

zwraca -271828, lub w przybliżeniu -e, w python 2 ( teraz jest -314159 ).

Fakt, że dwie najbardziej znane nieracjonalne liczby wszechczasów są używane jako wartości skrótu, sprawia, że jest bardzo mało prawdopodobne, aby był to zbieg okoliczności.

— Alec Alameddine
źródło