Comparación doble rápida

Ayer había un artículo sobre el análisis rápido de dobles, fui al blog de su autor y encontré otro truco interesante allí . Al comparar números de coma flotante, se debe prestar especial atención a NaN (hace ocho años escribí sobre ellos con más detalle); pero si los números que se comparan ciertamente no son NaN, ¡entonces se pueden comparar más rápido que el procesador!



Es muy fácil comparar dobles positivos: la normalización nos garantiza que de números con diferentes exponentes, cuanto mayor es aquel cuyo exponente es mayor, y de los números con el mismo exponente, mayor es aquel cuya mantisa es mayor. El estándar IEEE 754 ha colocado cuidadosamente el exponente en los bits de orden superior, por lo que los dobles positivos se pueden comparar simplemente como int64_t.







Los números negativos son un poco más complicados: se almacenan en código directo , mientras que int64_t se almacena en código complementario . Esto significa que para usar una comparación de enteros, los 63 bits inferiores de un doble deben invertirse (esto dará como resultado -0. <+0., Que no corresponde al estándar, pero en la práctica no presenta un problema ). La verificación explícita de bits de alto orden y la ramificación condicional destruirían todos los beneficios de saltar a la comparación de enteros; ¡Pero hay una manera más fácil!

inline int64_t to_int64(double x) {
	int64_t a = *(int64_t*)&x;
	uint64_t mask = (uint64_t)(a >> 63) >> 1;
	return a ^ mask;
}

inline bool is_smaller(double x1, double x2) {
	return to_int64(x1) < to_int64(x2);
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

a>>63



llena los 64 bits con copias del bit de signo y luego >>1



borra el bit más significativo.



El blog de Daniel Lemire tiene un código ligeramente diferente (de la misma complejidad computacional), pero mi versión conserva la propiedad útil de que to_int64(0.) == 0