¿Por qué el hash del infinito de Python tiene los dígitos de π?

7 minutos de lectura

avatar de usuario
ingenio

El hash del infinito en Python tiene dígitos que coinciden Pi:

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

¿Es solo una coincidencia o es intencional?

  • No estoy seguro, pero supongo que es tan deliberado como hash(float('nan')) siendo 0.

    – cs95

    20 mayo 2019 a las 20:04

  • Hmm, no se menciona eso en sys.hash_info. ¿El huevo de Pascua?

    – Wim

    20 mayo 2019 a las 20:09

  • Pregúntale a Tim Peters. Aquí está el compromiso donde introdujo esta constante, hace 19 años: github.com/python/cpython/commit/…. Mantuve esos valores especiales cuando modifiqué el hash numérico en bugs.python.org/issue8188

    –Mark Dickinson

    20 mayo 2019 a las 20:38


  • @MarkDickinson Gracias. Parece que Tim también pudo haber usado los dígitos de mi para hash de -inf originalmente.

    – Wim

    20 mayo 2019 a las 20:42


  • @wim Ah, sí, cierto. Y aparentemente cambié eso a -314159. Me había olvidado de eso.

    –Mark Dickinson

    20 mayo 2019 a las 20:44

avatar de usuario
ShreevatsaR

Resumen: No es una coincidencia; _PyHASH_INF está codificado como 314159 en la implementación predeterminada de CPython de Python, y se eligió como un valor arbitrario (obviamente de los dígitos de π) por Tim Peters en 2000.


El valor de hash(float('inf')) es uno de los parámetros dependientes del sistema de la función hash incorporada para tipos numéricos, y también está disponible como sys.hash_info.inf en Python 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

(Los mismos resultados con PyPy también.)


En términos de código, hash es una función incorporada. Llamarlo en un objeto flotante de Python invoca la función cuyo puntero está dado por el tp_hash atributo del tipo de flotador incorporado (PyTypeObject PyFloat_Type), cual es la float_hash función, definido como return _Py_HashDouble(v->ob_fval)que a su vez posee

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

dónde _PyHASH_INF es definido como 314159:

#define _PyHASH_INF 314159

En términos de historia, la primera mención de 314159 en este contexto en el código de Python (puede encontrar esto con git bisect o git log -S 314159 -p) fue añadido por tim peters en agosto de 2000, en lo que ahora se comete 39dce293 en el cpython repositorio git.

El mensaje de confirmación dice:

Arreglo para http://sourceforge.net/bugs/?func=detailbug&bug_id=111866&group_id=5470. Este fue un error engañoso: el verdadero “error” fue que hash(x) dio un retorno de error cuando x es un infinito. Arreglado eso. Agregado nuevo Py_IS_INFINITY macro a
pyport.h. Se reorganizó el código para reducir la creciente duplicación en el hash de números flotantes y complejos, lo que llevó la puñalada anterior de Trent a una conclusión lógica. Se corrigió un error extremadamente raro en el que el hashing de flotantes podía devolver -1 incluso si no había un error (no perdió el tiempo tratando de construir un caso de prueba, era simplemente obvio por el código que pudo suceder). Hash complejo mejorado para que
hash(complex(x, y)) no es sistemáticamente igual hash(complex(y, x)) más.

En particular, en este compromiso arrancó el código de static long float_hash(PyFloatObject *v) en Objects/floatobject.c y lo hizo justo return _Py_HashDouble(v->ob_fval);y en la definición de long _Py_HashDouble(double v) en Objects/object.c añadió las líneas:

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

Entonces, como se mencionó, fue una elección arbitraria. Tenga en cuenta que 271828 se forma a partir de los primeros dígitos decimales de mi.

Confirmaciones posteriores relacionadas:

  • La elección de -271828 para -Inf elimina cualquier duda de que la asociación pi fue accidental.

    –Russell Borogove

    21 de mayo de 2019 a las 4:30

  • @RussellBorogove No, pero lo hace un millón de veces menos probable;)

    – tubería

    21 de mayo de 2019 a las 15:01

  • @cmaster: consulte la parte anterior donde dice mayo de 2010, es decir, la sección de documentación sobre hashing de tipos numéricos y número 8188 — la idea es que queremos hash(42.0) ser igual que hash(42)también lo mismo que hash(Decimal(42)) y hash(complex(42)) y hash(Fraction(42, 1)). La solución (de Mark Dickinson) es elegante en mi opinión: definir una función matemática que funcione para cualquier número racional y usar el hecho de que los números de coma flotante también son números racionales.

    – ShreevatsaR

    22 de mayo de 2019 a las 13:22

  • @ShreevatsaR Ah, gracias. Si bien no me hubiera importado garantizar estas igualdades, es bueno saber que existe una explicación buena, sólida y lógica para el código aparentemente complejo 🙂

    – cmaster – reincorporar a monica

    22 mayo 2019 a las 14:00

  • @cmaster La función hash para enteros es simplemente hash(n) = n % M donde M = (2^61 – 1). Esto se generaliza para racional n a hash(p/q) = (p/q) mod M con la división siendo interpretada módulo M (en otras palabras: hash(p/q) = (p * inverse(q, M)) % M). La razón por la que queremos esto: si en un dict d nosotros ponemos d[x] = foo y luego tenemos x==y (por ejemplo, 42.0==42) pero d[y] no es lo mismo que d[x], entonces tendríamos un problema. La mayor parte del código aparentemente complejo proviene de la naturaleza del formato de punto flotante en sí mismo, para recuperar la fracción correctamente y necesita casos especiales para valores inf y NaN.

    – ShreevatsaR

    22 mayo 2019 a las 23:22

avatar de usuario
patricio haugh

_PyHASH_INF es definido como una constante igual a 314159.

No puedo encontrar ninguna discusión sobre esto, o comentarios dando una razón. Creo que fue elegido más o menos arbitrariamente. Me imagino que mientras no usen el mismo valor significativo para otros hashes, no debería importar.

  • Pequeño detalle: es casi inevitable, por definición, que se utilice el mismo valor para otros hashes, por ejemplo, en este caso hash(314159) es también 314159. También intente, en Python 3, hash(2305843009214008110) == 314159 (esta entrada es 314159 + sys.hash_info.modulus) etc.

    – ShreevatsaR

    21 de mayo de 2019 a las 11:43

  • @ShreevatsaR Solo quise decir que, siempre que no elijan este valor como el hash de otros valores por definición, elegir un valor significativo como este no aumenta la posibilidad de colisiones de hash

    –Patrick Haugh

    21 de mayo de 2019 a las 13:37

avatar de usuario
alec

Por cierto,

sys.hash_info.inf

devoluciones 314159. El valor no se genera, está integrado en el código fuente. En realidad,

hash(float('-inf'))

devoluciones -271828o aproximadamente -e, en python 2 (es -314159 ahora).

El hecho de que los dos números irracionales más famosos de todos los tiempos se utilicen como valores hash hace que sea muy poco probable que sea una coincidencia.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad