Hier sollen kleine, effiziente Algorithmen der Numerik vorgestellt werden. Sollten Fehler in meinen Programmen entdeckt werden, so bitte ich diese mir unter meiner eMail-Adresse: andreas{dot}romeyke[at]web{dot}de zuzumailen. Ich bin auch an weiteren Algorithmen interessiert.
Die beschriebenen Programme können frei verwendet werden, Eine Kennzeichnung der Quelle wäre wünschenswert.
unsigned int egypt_mult (unsigned int a, unsigned int b) {
unsigned int tmp=0;
if ((a==0) || (b==0)) return (0);
do {
if ((a & 1)==1) /* Wenn a ungerade */
tmp=tmp+b;
b=b<<1; /* b=b*2 */
a=a>>1; /* a=a/2 */
} while (a>0); /* Wiederhole solange a>0 */
return (tmp);
}
Das Beispiel mit Integern ist hier langsamer als eine normale Multiplikation "a*b", das liegt an den Tests in der Schleife. Eine Optimierungsmöglichkeit, die bei großen Zahlen wirksam ist, ist zu prüfen, ob a>b, um dann a mit b zu tauschen, da ein kleineres a eher 0 wird.
unsigned int legendre_pow (unsigned int a, unsigned int b) {
unsigned int tmp=1;
if ((a==0)||(b==0)) return (1); /* je nach mathematischer Auffassung */
do {
if ((b & 1)==1) /* Wenn b ungerade */
tmp=tmp*a;
a=a*a;
b=b>>1; /* b=b/2 */
} while (b>0); /* Wiederhole solange b>0 */
return (tmp);
}
Diese Methode ist deutlich schneller als die Nutzung der auf den Datentyp double angepassten pow() Funktion der math.h. Sie ist auch deutlich schneller, als wenn man in einer Schleife a b-mal miteinander multipliziert. Auch hier gilt, der Effekt wird größer, je größer die Zahlen werden
unsigned float herons_squareroot (unsigned float a) {
unsigned float tmpx=1;
unsigned float tmpy;
if (a==0) return (0);
for (;;) {
tmpy=(tmpx+a/tmpx)/2;
if (abs(tmpx-tmpy)<0.00000000001f) /* gewuenschte Genauigkeit */
break;
tmpx=tmpy;
}
return(tmpx);
}
unsigned int euklids_ggt (unsigned int a, unsigned int b) {
int tmp;
if ((a==0)||(b==0)) return (0);
do {
if (a<b) { /* vertausche a,b */
tmp=a;
a=b;
b=tmp;
}
tmp=a-b;
a=b;
b=tmp;
} while (tmp>0); /* Wiederhole solange tmp>0 */
return (a);
}
unsigned float ta_ka_pi(unsigned float &a, unsigned float &b, unsigned float &c) {
unsigned float y=a;
unsigned float x=1;
a=(a+b)/2;
b=sqrt(b*y);
c=c-x*(a-y)*(a-y);
x=2*x;
};
Wobei die Funktion je nach gewünschter Genauigkeit wiederholt aufgerufen wird. Der Startaufruf lautet:
...
a=1;
b=1/sqrt(2);
c=0.25f;
for (...) {
ta_ka_pi(a, b, c);
}
pi=((a+b)*(a+b))/(4*c);
...
Was noch kommt? Mal sehen, ich werde demnächst noch schnelle Berechnung von Logarithmen vorstellen. Wer noch Ideen hat, was hier noch unbedingt reingehört, immer her damit!
