[C] Valore assoluto di un numero + velocemente possibile

[Mr. X]

Ciao Ragazzi,

sapete dirmi qul'è secondo voi il modo più veloce per ottenere il valore assoluto di un numero siccome lo devo calcolare tante volte? Io pensavo alla seguente funzione:

int abs(int x)
{
return (x > 0) ? x : -x;
}

che ne dite?

[marko.fatto]

unsigned int

[Mr. X]

Originariamente inviato da marko.fatto

unsigned int

In uscita voglio che sia dello stesso tipo che in ingresso. Poi è ovvio che sarà positivo.

[kk3z]

#define ABS(x) ((x) > 0) ? (x) : -(x);

[shinya]

Non va bene.

Considera (è in java, ma non cambia):

class twocompl {
  public static void main(String[] args) {
    int x = -2147483648;

    System.out.println(myAbs(x));
  }

  private static int myAbs(int x) {
    return (x > 0) ? x : -x;
  }
}

c:\> java twocompl
-2147483648  <-- OMG!!1

In pratica, fallisce con il minor numero rappresentabile. Ma è la logica del complemento a due.
Il tuo problema è più accentuato perchè stai lavorando in C, quindi la dimensione dell'int varia da macchina a macchina.

Fatti due conti.

[cionci]

Credo che il più veloce sia questo:

unsigned int iabs(int a)
{
  return ~a + 1;
}

La condizione inline mette sempre in gioco il branch predictor, sicuramente un branch è veloce, ma l'altro no

[Mr. X]

Originariamente inviato da cionci

Credo che il più veloce sia questo:

unsigned int iabs(int a)
{
  return ~a + 1;
}

La condizione inline mette sempre in gioco il branch predictor, sicuramente un branch è veloce, ma l'altro no

Ma sei sicuro che la tua funzione non faccia solamente un cambio di segno? cioè se a = 5 => ritorno = -5 e se a = -8 => ritorno = 8

[cionci]

Sì che testa

[Mr. X]

Originariamente inviato da cionci

Sì che testa

Di nulla figurati

Mi sa che la più veloce è la mia... Ho provato con il quadrato al posto del valore assoluto e ho avuto un miglioramento di circa il 25% sulla velocità totale dell'algoritmo. Però dai un modo più veloce ci deve essere

[kk3z]

hai provato la macro?

[cionci]

Con il quadrato però perdi parte dello spazio degli interi.

[wingman87]

Ma com'è codificato in bit un numero positivo e uno negativo? Lo avevo fatto alle superiori ma non me lo ricordo più...

[Mr. X]

Originariamente inviato da wingman87

Ma com'è codificato in bit un numero positivo e uno negativo? Lo avevo fatto alle superiori ma non me lo ricordo più...

Se il primo bit partendo da destra è uguale a 0 allora è positivo altrimenti è negativo. Ricorda però il complemento a 1.

[Mr. X]

Originariamente inviato da cionci

Con il quadrato però perdi parte dello spazio degli interi.

Purtroppo lo so ed è per questo che non lo voglio usare. Era per fare una prova di quanto succhia l'if.

[Mr. X]

Originariamente inviato da kk3z

hai provato la macro?

La macro da gli stessi risultati della mia funzione.

[Mr. X]

Ho provato a costruirmi un Look Up Table e sono passato dai 19ms con la mia funzione a 13ms.
Peccato però che debba usare quella LUT che è abbastanzza grande.

[wingman87]

Originariamente inviato da Mr. X

Se il primo bit partendo da destra è uguale a 0 allora è positivo altrimenti è negativo. Ricorda però il complemento a 1.

Ah ecco, grazie! Solo una cosa, non si guardava il primo bit da sinistra?

[^TiGeRShArK^]

...ovviamente hai effettuato un profiling per verificare incontrovertibilmente che ottimizzando quella funzione otterresti *sensibili* vantaggi in esecuzione spero...
Altrimenti hai solo perso tempo sottraendolo alla scrittura di codice utile....

[gugoXX]

Se si tratta di studiare il problema sono d'accordo con TigerShark. E' sempre bene usare un profiling se si tratta di ottimizzare qualcosa.
E prima di ottimizzare con il profiling la maggior parte delle volte e' quasi sempre un problema di modello dati inadeguato.
Una volta aggiustato il modello dati la situazione migliora da sola.

Comunque non penso che questo caso sia effettivamente migliorabile, mantenendo la leggibilita' e l'universalita', rispetto a quanto ottenibile con la macro.

Se invece si tratta di una gara, poiche' sono l'unico ad essere rimasto in ufficio durante la pausa pranzo, e poiche' da solo mi rompo abbastanza, io provo con questo:

int __inline absasm(int x)
{	
     __asm{
          mov eax,x
          cdq
          xor eax,edx
          sub eax,edx
     }		
}

Senza salti.
Ovviamente e' ben poco universale. Molto poco.
Se si prova a compilare con le __inline function si guadagna un 10% rispetto alla versione Macro (che penso sia comunque la preferibile e universale).

[MFSPO=DBGPOF]

prova così:

int abs(int x)

{
	int b=0x80000000,c=30;

	return (x*(((x&b)>>c)+1));
}