2010-05-27 11 views
9

Dato due numeri in virgola mobile, sto cercando un modo efficiente per verificare se hanno lo stesso segno, dato che se c'è ne dei due valori è zero (+0.0 o -0.0), dovrebbero essere considerati con lo stesso segno.Come confrontare in modo efficiente il segno di due valori in virgola mobile mentre si gestiscono gli zeri negativi

Per esempio,

  • SameSign (1.0, 2.0) dovrebbe restituire true
  • SameSign (-1,0, -2,0) deve restituire true
  • SameSign (-1,0, 2.0) dovrebbe restituire false
  • SameSign (0.0, 1.0) deve restituire true
  • SameSign (0.0, -1.0) deve restituire true
  • 01.235.164,106 mila
  • SameSign (-0.0, 1.0) deve restituire true
  • SameSign (-0.0, -1.0) deve restituire true

Un'implementazione naive ma corretta SameSign in C++ sarebbe:

bool SameSign(float a, float b) 
{ 
    if (fabs(a) == 0.0f || fabs(b) == 0.0f) 
     return true; 

    return (a >= 0.0f) == (b >= 0.0f); 
} 

Assumendo il modello IEEE in virgola mobile, ecco una variante di SameSign che compila codice branchless (almeno con Visual C++ 2008):

bool SameSign(float a, float b) 
{ 
    int ia = binary_cast<int>(a); 
    int ib = binary_cast<int>(b); 

    int az = (ia & 0x7FFFFFFF) == 0; 
    int bz = (ib & 0x7FFFFFFF) == 0; 
    int ab = (ia^ib) >= 0; 

    return (az | bz | ab) != 0; 
} 

con binary_cast definiti come segue:

template <typename Target, typename Source> 
inline Target binary_cast(Source s) 
{ 
    union 
    { 
     Source m_source; 
     Target m_target; 
    } u; 
    u.m_source = s; 
    return u.m_target; 
} 

Sto cercando due cose:

  1. Un più veloce, più efficace attuazione del SameSign, utilizzando trucchi bit, FPU trucchi o anche intrinseci SSE.

  2. Un'estensione efficiente di SameSign a tre valori.

Edit:

Ho fatto alcune misurazioni delle prestazioni sulle tre varianti di SameSign (le due varianti descritte nella domanda iniziale, più di uno) di Stephen. Ogni funzione è stata eseguita 200-400 volte, su tutte le coppie di valori consecutivi in ​​un array di 101 float riempiti a caso con -1.0, -0.0, +0.0 e +1.0. Ogni misura è stata ripetuta 2000 volte e il tempo minimo è stato mantenuto (per eliminare tutti gli effetti della cache e i rallentamenti indotti dal sistema). Il codice è stato compilato con Visual C++ 2008 SP1 con ottimizzazione massima e generazione di codice SSE2 abilitata. Le misurazioni sono state effettuate su un Core 2 Duo P8600 2.4 Ghz.

Ecco gli orari, senza contare il sovraccarico di recupero valori di input dalla matrice, chiamando la funzione e recuperare il risultato (che ammontano a 6-7 clockticks):

  • variante naive: 15 zecche
  • Bit variante magica: 13 zecche
  • variante di Stephens: 6 zecche
+0

Qualsiasi particolare linguaggio/piattaforma? –

+0

Ehi, grazie per la bella domanda :) Preferibilmente C/C++ su x86. –

+0

possibile duplicato di [confrontare due float per vedere se sono entrambi negativi, o entrambi positivi.] (Http://stackoverflow.com/questions/2013680/comparing-two-floats-to-see-if-theyre-oth -negativo-o-entrambi-positivo) – ChrisF

risposta

10

Se non è necessario per supportare infiniti, si può j ust use:

inline bool SameSign(float a, float b) { 
    return a*b >= 0.0f; 
} 

che è in realtà piuttosto veloce sulla maggior parte dei moderni hardware ed è completamente portatile. Tuttavia, non funziona correttamente nel caso (zero, infinito) poiché zero * infinito è NaN e il confronto restituirà false, indipendentemente dai segni. Dovrà inoltre verificarsi un problema di stallo su alcuni hardware quando a e b sono entrambi piccoli.

+0

In effetti, questo funziona bene per due valori e ha la semantica corretta. La mia unica preoccupazione è che richiede tre moltiplicazioni per il caso dei tre valori (a * b> = 0.0f && a * c> = 0.0f && b * c> = 0.0f). –

+0

@ François: sì, il caso dei tre valori è un puzzle interessante. Dovrò pensarci un po '. –

+0

È esatto? Per me, questa sarebbe la soluzione più ovvia, ma ho anche bisogno di avere un risultato esatto indipendentemente dagli errori di arrotondamento. Mi sembra che un * b possa essere arrotondato in su verso 0 e quindi questa funzione calcola il valore sbagliato. Non sono sicuro, però. – migle

3

forse qualcosa di simile:

inline bool same_sign(float a, float b) { 
    return copysignf(a,b) == a; 
} 

vedere la pagina man di copysign per ulteriori informazioni su ciò che fa (anche si consiglia di controllare che -0 = 0!)

o forse questo se si dispone di funzioni di C99

inline bool same_sign(float a, float b) { 
    return signbitf(a) == signbitf(b); 
} 

come nota a margine, su gcc almeno sia copysign e signbit sono funzioni interne in modo che dovrebbe essere veloce, se si vuole fare in modo integrato la versione è in uso si può fare __builtin_signbitf (a)

EDIT: questo dovrebbe anche essere facile da estendere al caso 3 valore come bene (in realtà entrambi questi dovrebbe ...)

inline bool same_sign(float a, float b, float c) { 
    return copysignf(a,b) == a && copysignf(a,c) == a; 
} 

// trust the compiler to do common sub-expression elimination 
inline bool same_sign(float a, float b, float c) { 
    return signbitf(a) == signbitf(b) && signbitf(a) == signbitf(c); 
} 

// the manpages do not say that signbit returns 1 for negative... however 
// if it does this should be good, (no branches for one thing...) 
inline bool same_sign(float a, float b, float c) { 
    int s = signbitf(a) + signbitf(b) + signbitf(c); 
    return !s || s==3; 
} 
0

Una piccola nota sulla signbit: La macro restituisce un int e la pagina man afferma che "Restituisce un valore diverso da zero se il valore di x ha il bit di segno impostato." Ciò significa che non è garantito che lo Spudd86 funzioni nel caso in cui signbit restituisca due diversi valori diversi da zero per due valori negativi diversi.

Casting al bool primo assicura un valore di ritorno corretto:

inline bool same_sign(float a, float b) { 
    return (bool)signbitf(a) == (bool)signbitf(b); 
}