efficace, mais toujours précis, multiple exposant

Question

J'ai besoin de calculer efficacement un ensemble de quelque chose comme f(i,a) = exp(-0.5 * (i-1) * i * a) pour tous i in (0..n), avec n jusqu'à 20.000 et a une valeur positive très proche de 0.

Pour éviter le calcul du exp n fois, j'ai utilisé une approche progressive telle que (l'écriture en scala):

def fInc(n: Int, a: Double) 
    val expA = Math.exp(-a) 
    var u = 1.0 
    var v = 1.0 

    var i = 1 
    while(i < n){ 
    u *= expA 
    v *= u // in practice I store that value in an array, for all i 
    i += 1 
    } 
} 

// reference by calling exp directly 
def fRef(n: Int, a: Double) = Math.exp(-0.5 * (i-1) * i * a) 

Ceci est mathématiquement correct, mais la différence avec calcul exp directe est trop grand. Voici quelques résultats:

n  a   v    Math.exp    diff 
1000 1E-6 0.6068340008761639 0.6068340008714599 4.704014955336788E-12 
1000 1E-9 0.9995006247427483 0.9995006247293567 1.339151E-11 
1000 1E-12 0.9999995005111699 0.9999995005001248 1.1045164782785832E-11 
1000 1E-15 0.9999999995008992 0.9999999995005  3.992361996552063E-13 
10000 1E-6 1.938417748402E-22 1.938417746809E-22 1.5929953847004499E-31 
10000 1E-9 0.9512341819777599 0.9512341806597269 1.3180330160622589E-9 
10000 1E-12 0.9999500073554776 0.9999500062497292 1.1057483817467073E-9 
10000 1E-15 0.9999999500449599 0.9999999500050013 3.995859199079632E-11 

Comme vous pouvez le voir, pour certaines valeurs, la différence va jusqu'à 1E-9, alors que je peux accepter peut-être 1e-13

Alors question:

• Y at-il un moyen d'obtenir une meilleure approximation avec un algorithme qui est encore beaucoup plus efficace que d'appeler exp sur tous les i?

Notes:

1. J'utilise apache FastMath exp, ce qui donne à peu près les mêmes résultats que exp standard java.
2. La algorith réelle est plus complexe, avec d'autres comme exp incrémental (non quadratique bien)

Answer 1

Voici la meilleure solution que je trouve:

L'erreur étant incrémentée (sorte de) linéairement avec chaque multiplication par le "exp unitary (a)". Nous pouvons penser à l'erreur comme une fonction similaire à err(i) ~= i*i*err0 pour certains err0. Le point est que l'erreur de v est quadratique w.r.t i.

Le meilleur I trouvé est:

1. réinitialiser le volume à la valeur correcte à une certaine fréquence choisie (chaque k itération)
2. améliorer l'exactitude de u à chaque itération k, en utilisant le calcul d'exp incrémentale

.

val k = 100 
val expA = Math.exp(-a) 
val expAk = Math.exp(-k*a) 
var u = 1.0 
var uk = 1.0 
var v = 1.0 

var i = 1 
while(i < n){ 
    if(i%k==0){ 
    uk *= expAk 
    u = uk 
    v = Math.exp(- 0.5*(i+1)*i * a) 
    } else{ 
    u *= expA 
    v *= u 
    } 
    i += 1 
} 

Cette méthode nécessite n/k + 2 appel à exp, mais pas tout à fait satifying le meilleur que j'ai pour l'instant. Il peut probablement être amélioré en choisissant le meilleur paramètre de fréquence k.