Calcul d'un logaritme népérien(ln) [résolu]

Calcul d'un logaritme népérien(ln) [résolu] - Algo - Programmation

Marsh Posté le 11-07-2005 à 15:33:40    

Salut, je cherche à calculer (informatiquement) un logarithme népérien (base e) d'un nombre quelconque (positif tout de même) et je cheche un lien ou une formule qui pourrait m'aider:
 
pour le moment j'ai trouvé sur google:
 

Code :
  1. ln(1 + x) = sum[n=1 -> +inf]( ((-1)^(n+1) / n) * x^n ) pour abs(x) < 1


 
donc si je ne dis pas de betises ca limite les possibilités en:
 
ln(a) avec a dans ]0, 2[
 
Je suppose donc qu'il y a possibilitée de "decouper" un logarithme népérien d'un nombre quelconque en plusieurs morceaux qui pourrait etre calculés via la formule ci dessus mais je n'ai rien trouvé.
 
Quelqu'un peut il m'aider ?


Message édité par chicotruss le 27-07-2005 à 19:46:02
Reply

Marsh Posté le 11-07-2005 à 15:33:40   

Reply

Marsh Posté le 12-07-2005 à 00:01:35    

chicotruss a écrit :

Salut, je cherche à calculer (informatiquement) un logarithme népérien (base e) d'un nombre quelconque (positif tout de même) et je cheche un lien ou une formule qui pourrait m'aider:
 
pour le moment j'ai trouvé sur google:
 

Code :
  1. ln(1 + x) = sum[n=1 -> +inf]( ((-1)^(n+1) / n) * x^n ) pour abs(x) < 1


 
donc si je ne dis pas de betises ca limite les possibilités en:
 
ln(a) avec a dans ]0, 2[
 
Je suppose donc qu'il y a possibilitée de "decouper" un logarithme népérien d'un nombre quelconque en plusieurs morceaux qui pourrait etre calculés via la formule ci dessus mais je n'ai rien trouvé.
 
Quelqu'un peut il m'aider ?


 
Je ne connais pas l'algorithme réel utilisé par les langages courants, ce n'est probablement pas ce que je vais dire ici.
 
En fait, la série en question a effectivement un rayon de convergence égal à 1, mais elle converge très lentement si |x| est proche de 1.
 
Aussi, si j'étais toi, je calculerais à l'avance les nombres 1.1^n pour n=-7250 à 7250, par exemple, pour faire varier le résultat entre 10^-300 et 10^300, ordre de grandeur de ce que permet le format IEEE, et je stockerais ces résultats dans un tableau. Et je calculerai log(1.1) avec la série ci-dessus.
 
En découvrant la valeur a dont je dois calculer le logarithme, je chercherais dans le tableau quelle puissance n de 1.1 est telle que 1.1^n <= a < 1.1^(n+1)
 
Ensuite, je calculerais b=a/1.1^n. b serait alors nécessairement compris entre 1 et 1.1. Il serait alors facile de calculer log(b) par ta série.
 
a=1.1^n * b
 
donc :
 
log(a)=n * log(1.1) + log(b)
 
Il convient bien sûr de calculer log(b), et surtout log(1.1) avec une grande précision.
 
La plupart des algorithmes de calcul de fonctions utilisent des expressions super sophistiquées, avec des séries rapidement convergentes de derrière les fagots, séries elles mêmes approximées par des développements en fractions continues, etc... Ici, rien de tel ; tout simplement parce que je ne connais pas les détails de ces calculs. Par conséquent, il y a fort à parier que le temps de calcul sera plus important avec cette méthode que le temps nécessité par ces méthodes très compliquées et très rapides, codées qui plus est en assembleur... Mais sur le plan de la précision, je pense que cela sera presque aussi bon...

Reply

Marsh Posté le 21-07-2005 à 14:35:03    

On peut utiliser ln(x) = -ln(1/x), de là on se ramène a quelque chose compris entre 0 et 1 à tous les coups, et tu n'as plus qu'à utiliser x - x²/2 + x^3/3 - ...

Reply

Marsh Posté le 21-07-2005 à 17:26:57    

leneuf22 a écrit :

On peut utiliser ln(x) = -ln(1/x), de là on se ramène a quelque chose compris entre 0 et 1 à tous les coups, et tu n'as plus qu'à utiliser x - x²/2 + x^3/3 - ...


Je n'ai pas dit que la série ne convergeait pas. Bien sûr qu'elle converge : mais elle converge lentement. C'est une série alternée telle que deux valeurs successives encadrent la limite. Pour calculer ln(100) en évaluant 1000 termes, la largeur de l'encadrement serait x^1000/1000 soit 0,99^1000/1000 soit 0.000000043. Pour un calcul de 1000 termes, c'est une précision très médiocre ! Ça converge, d'accord ; mais faut pas être pressé !

Reply

Marsh Posté le 21-07-2005 à 22:54:29    

Je ne suis pas du tout un fin matheux, mais est-ce que la vitesse de convergence serait meilleure si on utilisait le développement en série de ln(x) au voisinage de 1/2 ?
 
Celui ci doit valoir -ln(2) + 2(x-1/2) - 2(x-1/2)² + 8/3(x-1/2)^3 - 4(x-1/2)^4 ... ( (-1)^(n+1) * 2^n/n * (x-1/2)^n )
 
Pour 1000 termes j'obtiens une fourchette de 2e-12 environ (avec x=0.99), ce qui est déjà mieux, sans être terrible c'est vrai...

Reply

Marsh Posté le 22-07-2005 à 11:35:58    

www.google.fr !!!
 
Est ce que ce document ne contiendrait pas de meilleures information ? (rechercher le mot logarithme
 
http://www.librecours.org/documents/7/785.pdf

Reply

Marsh Posté le 24-07-2005 à 01:01:09    

leneuf22 a écrit :

Je ne suis pas du tout un fin matheux, mais est-ce que la vitesse de convergence serait meilleure si on utilisait le développement en série de ln(x) au voisinage de 1/2 ?
 
Celui ci doit valoir -ln(2) + 2(x-1/2) - 2(x-1/2)² + 8/3(x-1/2)^3 - 4(x-1/2)^4 ... ( (-1)^(n+1) * 2^n/n * (x-1/2)^n )
 
Pour 1000 termes j'obtiens une fourchette de 2e-12 environ (avec x=0.99), ce qui est déjà mieux, sans être terrible c'est vrai...


 
Si x=0.99 dans ton exemple, cela veut dire que tu cherches log(0.99). Dans ce cas ta première série converge très très vite puisque les termes successifs sont :
 
0,01  O,0001/2 0,000001/3 0,0000000/4 etc...
 
alors que cette dernière série que tu proposes peut s'analyser comme suit :
 
si tu poses x=1-e :
 
ln(x)=-ln(2)+...+(1-2e)^n/n
 
qui converge beaucoup moins vite que ta série de départ quand e est proche de 0. Mais justement, ta série de départ converge très vite lorsque x est proche de 1, lentement lorsque x est proche de 0. Or, lorsque la valeur pour laquelle tu cherches le logarithme est proche de 0, dans ta série :
-ln(2) + 2(x-1/2) - 2(x-1/2)² + 8/3(x-1/2)^3 - 4(x-1/2)^4 ... ( (-1)^(n+1) * 2^n/n * (x-1/2)^n )
x-1/2 est NEGATIF ce qui fait que tous les termes sont négatifs et que la série n'est plus alternée. Par conséquent tu as un autre problème : tu ne sais pas quand tu dois t'arrêter. Enfin, tu peux chercher, mais disons que c'est un inconvénient supplémentaire. En outre, si tu poses x=e,
 
ln(x)=-ln(2)-...-(1-2e)^n/n
 
Au millième terme tu obtiens bien 10^-12, ce qui n'est pas extraordinaire, mais surtout tu ne sais pas jusqu'où il te faudra aller car la série n'est plus alternée...
 
Par exemple, si tu vas jusqu'à n=1000, pour e=0.01 ton dernier terme est 1.6 * 10^-12. Si la série avait été alternée, tu pourrais dire que l'erreur que tu fais en n'allant pas plus loin est inférieure à ce dernier terme. Mais puisqu'elle n'est pas alternée, le calcul montre, en majorant le reste de la série par une série géométrique, que l'erreur que tu fais en n'allant pas plus loin est inférieure à environ 50 fois ce dernier terme, soit 8. 10^-11 !
 
Donc, globalement, je crois que l'idée est à rejeter...

Reply

Marsh Posté le 25-07-2005 à 13:45:23    

que cherches tu a faire exactement?
un algo pur et dur genre developpement limité ou calcul d'une valeur approchée comme le fait une calculatrice?
si c'est la 2eme option, tu peux regarer ici:
http://www.jacques-laporte.org/LeS [...] ithmes.htm
 
j'ai codé cet algo en c++ a la va vite. il marche pour les nombres dans ]0;10[ les autres etant faciles a obtenir avec l'algo ( ln A*10^p=lnA + pln10)
on part avec des constantes de log connues et on calcule les autres( voir le lien )

Code :
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <vector>
  4. using namespace std;
  8. double ln(double n)
  9. {
  11. vector < double > logs(8);
  12. vector < double > nbre(8);
  13. vector < int > somme(8,0);
  15. logs[0]=2.302585092994045; //ln 10
  16. logs[1]=0.693147180559945; //ln 2
  17. logs[2]=0.095310179804325; //ln 1.1
  18. logs[3]=0.009950330853168; //ln 1.01
  19. logs[4]=0.000999500333084; //ln 1.001
  20. logs[5]=0.000099995000333; //ln 1.0001
  21. logs[6]=0.000009999950000; //ln 1.00001
  22. logs[7]=0.000000999999500; //ln 1.000001
  24. nbre[0]=0;
  25. nbre[1]=2;
  26. nbre[2]=1.1;
  27. nbre[3]=1.01;
  28. nbre[4]=1.001;
  29. nbre[5]=1.0001;
  30. nbre[6]=1.00001;
  31. nbre[7]=1.000001;
  34. double temp=n;
  35. cout<<temp<<endl;
  36. int i=1;
  37. int j=1;
  38. double c;
  39. while (j<11)
  40. {
  41. c=temp*nbre[i];
  42. if (c<10) {temp=c;
  43.            j++; 
  44.            somme[i]++;                     
  45.           } else i++;
  47. }
  48. temp=((10-temp)/10);
  49. c=0;
  50. for (int k=1;k<9;k++) c+=somme[k]*logs[k];
  51. c=logs[0]-c;
  52. return (c-temp);
  53. }
  55. int main(int argc, char *argv[])
  56. {
  57. cout<<"entrez le nombre"<<endl;
  58. double nbre;
  59.   cin>>nbre;
  60. nbre=ln(nbre);
  61. int l;
  62. l=(int) (nbre*100000000);  //pour voir les chiffres apres la virgule
  63. cout<<l;
  64.   system("PAUSE" );
  65.   return 0;
  66. }

Reply

Marsh Posté le 27-07-2005 à 19:45:26    

OK j'ai réussi, merci tout le monde pour vos solutions.
 
J'ai finalement opté pour la méthode calculatrice (http://www.jacques-laporte.org/LeS [...] ithmes.htm) que j'ai implémentée en Java pour l'API J2ME (qui ne dispose pas de cette fonction dans la classe Math).
 
En utilisant que des flottants 32 bits j'arrive à obtenir une précision de 10^-3 en 10 itérations (suffisant pour mon utilisation)
Niveau performance, compilé en J2SE 1.5 je ne suis que 2 fois plus lent (en moyenne) que la méthode native de la classe Math (mais je n'ai pas la même précision).
 
Mon code:
 

Code :
  1. public final class H264Functions {
  3. /**
  4.  * The number of iteration in neperian logarithm approximation.
  5.  */
  6. public final static int LN_DEFAULT_PASS = 10;
  8. /**
  9.  * Constants needed to compute <code>ln(float)</code>.
  10.  */
  11. private final static float[][] LN_CONSTANTS = {
  12.  {10.0f, 2.0f, 1.1f, 1.01f, 1.001f, 1.0001f, 1.00001f, 1.000001f, 1.0000001f, 1.00000001f},
  13.  {
  14.   2.30258509299404568402f, // ln(10)
  15.   0.69314718055994530942f, // ln(2)
  16.   0.09531017980432486004f, // ln(1.1)
  17.   0.00995033085316808285f, // ln(1.01)
  18.   0.00099950033308353317f, // ln(1.001)
  19.   0.00009999500033308335f, // ln(1.0001)
  20.   0.00000999995000033333f, // ln(1.00001)
  21.   0.00000099999950000033f, // ln(1.000001)
  22.   0.00000009999999500000f, // ln(1.0000001)
  23.   0.00000000999999995000f  // ln(1.00000001)
  24.  }
  25. };
  27. /**
  28.  * Compute Neperian logarithm of <code>f</code> with precision of 10^-3.
  29.  * @param f, the value you want Neperian logarithm.
  30.  * @return the Neperian logarithm of <code>f</code> at 10^-3 precision.
  31.  * @throws IllegalArgumentException, if <code>f < 0.0f</code>.
  32.  */
  33. public static float ln(float f) throws IllegalArgumentException {
  34.  if(f > 0.0f) {
  35.   // ln(1) = 0 ; ln(e) = 1 ; ln(ab) = ln(a) + ln(b) ; ln(a/b) = ln(a) - ln(b) ;
  36.   // ln(a^b) = b * ln(a) ; e = 2.7182818284590452354
  38.   boolean infOne;
  39.   if(infOne = (f < 1.0f)) {
  40.    f = 1 / f;
  41.   }
  43.   //here: limit = 10.0f
  44.   float limit = LN_CONSTANTS[0][0];
  46.   //init at ln(limit)
  47.   float result = LN_CONSTANTS[1][0];
  49.   //forward to convenient case
  50.   float pow = 0.0f;
  51.   while(f >= limit) {
  52.    f /= limit;
  53.    pow++;
  54.   }
  55.   float complement = pow * LN_CONSTANTS[1][0];
  57.   //compute convenient case: 1 <= f <= 10
  58.   float temp;
  59.   float acc = f;
  60.   int constantsIndex = 1;
  61.   int nbPass = LN_DEFAULT_PASS;
  62.   while(nbPass-- != 0) {
  63.    if((temp = LN_CONSTANTS[0][constantsIndex] * acc) < limit) {
  64.     acc = temp;
  65.     result -= LN_CONSTANTS[1][constantsIndex];
  66.    } else {
  67.     constantsIndex++;
  68.     nbPass++;
  69.    }
  70.   }
  72.   //adjustment + complement
  73.   result += complement - (limit - acc) / limit;
  75.   return(infOne ? -result : result);
  76.  } else {
  77.   throw(new IllegalArgumentException("Can only compute logarithm with value > 0" ));
  78.  }
  79. }
  81. }

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed