Discussion :

[ToTo13]

Bonjour,

je calcule une valeur gaussienne de la manière suivante :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
private double gaussian(double x, double y, double sig)
	{
	return Math.exp(-(x*x+y*y)/(2*sig*sig)) / (2.0*Math.PI*sig*sig) ;
	}

Seulement cette fonction est appelées des millions de fois, donc je souhaiterai savoir s'il n'y a pas un moyen plus rapide de faire le calcul. Bon à vrai dire je serai surpris que oui.

J'avais pensé à :
- pré-calculer des valeurs, mais les paramètres x, y et sig sont TRES variables.
- faire des approximations car si x et y sont grands, le résultat est quasi nul.

Merci par avance...


PS : quelle est la complexité de la fonction Math.exp() ?
En gros, est elle très gourmande en terme de CPU ?

[Nebulix]

La fonction est calculée par le FPU du processeur et doit prendre le temps de quelques multiplications. Mon PC en calcule 20 millions en environ 2sec.

[pseudocode]

On peut approximer exp() en utilisant des hack sur la représentation en flottant, si les valeurs sont assez petites.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
public static double exp(double val) {
	long hack = (long) (1512775 * val) + 1072632447;
	return Double.longBitsToDouble(hack << 32);
}

On peut aussi utiliser interpoler une table de valeurs précalculées.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
static double[] EXPNEGTABLE = new double[1000];
static {
	for(int i=0;i<1000;i++)
		EXPNEGTABLE[i]=Math.exp((double)-i/32);
}
 
public static double exp(double val) {
	if (val>0) throw new ArithmeticException(); 
	int i=(int)(-val*32);
	if (i>=999) return 0.0;
	double a=(-val*32)-i;
	return EXPNEGTABLE[i]+a*(EXPNEGTABLE[i+1]-EXPNEGTABLE[i]);
}

Hormis faire des approximations, je ne pense pas qu'on puisse accélérer les calculs. La méthode Math.exp() en Java est un appel natif, alors ca va être difficile de faire mieux.

[FR119492]

Salut!
Tout d'abord, il est inutile de calculer deux fois 2.0*sig*sig. Si ça n'est pas assez efficace, pourquoi ne pas passer à un langage plus efficace, comme le C, le Fortran ou même Matlab?
Jean-Marc Blanc

[Nebulix]

Pour ma curiosité personnelle, combien de temps mets ton ordi à calculer une exponentielle ? Et quel système utilises-tu ?

[ToTo13]

Bonsoir,

On peut approximer exp() en utilisant des hack sur la représentation en flottant, si les valeurs sont assez petites.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
public static double exp(double val) {
	long hack = (long) (1512775 * val) + 1072632447;
	return Double.longBitsToDouble(hack << 32);
}

On peut aussi utiliser interpoler une table de valeurs précalculées.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
static double[] EXPNEGTABLE = new double[1000];
static {
	for(int i=0;i<1000;i++)
		EXPNEGTABLE[i]=Math.exp((double)-i/32);
}
 
public static double exp(double val) {
	if (val>0) throw new ArithmeticException(); 
	int i=(int)(-val*32);
	if (i>=999) return 0.0;
	double a=(-val*32)-i;
	return EXPNEGTABLE[i]+a*(EXPNEGTABLE[i+1]-EXPNEGTABLE[i]);
}

Hormis faire des approximations, je ne pense pas qu'on puisse accélérer les calculs. La méthode Math.exp() en Java est un appel natif, alors ca va être difficile de faire mieux.

- 1 - je ne suis pas fan du hack.
- 2 - en gros il me faut pré-calculer les valeurs de l'exponentielle pour gagner du temps. Mais est ce réellement significatif d'après toi ? Comme tu le dis toi même, c'est du natif derrière.
Deuxième question : pourquoi diviser par 32 et faire ensuite ce calcul bizarre ?

Salut!
Tout d'abord, il est inutile de calculer deux fois 2.0*sig*sig. Si ça n'est pas assez efficace, pourquoi ne pas passer à un langage plus efficace, comme le C, le Fortran ou même Matlab?

J'avais déjà corrigé le double calcul.
Je souhaite optimiser ce calcul qui tourne pour une application en java.

Pour ma curiosité personnelle, combien de temps mets ton ordi à calculer une exponentielle ? Et quel système utilises-tu ?

Je n'ai pas fait de test :-(
Je suis sous Mac OS X.

[pseudocode]

- 2 - en gros il me faut pré-calculer les valeurs de l'exponentielle pour gagner du temps. Mais est ce réellement significatif d'après toi ? Comme tu le dis toi même, c'est du natif derrière.
Deuxième question : pourquoi diviser par 32 et faire ensuite ce calcul bizarre ?

Avec la table de précalcul tu gagnes un facteur 10 à 15 sur ma machine (Java 6-u21 64bits) . C'est pas négligeable tout de même.

La division par 32, c'est juste la fréquence d'échantillonnage de la gaussienne.

table[0] = exp(-0)
table[1] = exp(-1/32)
table[2] = exp(-2/32)
...
table[1000] = exp(-1000/32)