Comparação dupla rápida

Ontem saiu um artigo sobre análise rápida de duplas, fui ao blog de seu autor e encontrei outro truque interessante lá . Ao comparar números de ponto flutuante, atenção especial deve ser dada a NaN (oito anos atrás eu escrevi sobre eles com mais detalhes); mas se os números comparados certamente não forem NaN, eles podem ser comparados mais rápido do que o processador!



É muito fácil comparar duplos positivos: a normalização garante-nos que dos números com expoentes diferentes, quanto maior for aquele cujo expoente é maior, e dos números com o mesmo expoente, maior será aquele cuja mantissa é maior. O padrão IEEE 754 colocou cuidadosamente o expoente nos bits de ordem superior, portanto, os duplos positivos podem ser comparados simplesmente como int64_t.







Os números negativos são um pouco mais complicados: eles são armazenados em código direto , enquanto int64_t é armazenado em código complementar . Isso significa que, para usar uma comparação inteira, os 63 bits inferiores de um duplo devem ser invertidos (isso resultará em -0. <+0., O que não corresponde ao padrão, mas na prática não apresenta um problema ) A verificação explícita de bits de alta ordem e a ramificação condicional destruiriam todos os benefícios de pular para a comparação de inteiros; mas existe uma maneira mais 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



preenche todos os 64 bits com cópias do bit de sinal e, em seguida, >>1



limpa o bit mais significativo.



O blog de Daniel Lemire tem um código ligeiramente diferente (da mesma complexidade computacional), mas minha versão mantém a propriedade útil de to_int64(0.) == 0