消除乘法運算
我們已經成功的將乘法的次數減少了一半,還有沒有可能進一步降低運算量呢?還要從計算式入手。
第一次循環時,tan(45)=1,所以第一次循環實際上是不需要乘法運算的。第二次運算呢?
Tan(22.5)=0.4142135623731,很不幸,第二次循環乘數是個很不整的小數。是否能對其改造一下呢?答案是肯定的。第二次選擇22.5度是因為二分查找法的查找效率最高。如果選用個在22.5到45度之間的值,查找的效率會降低一些。如果稍微降低一點查找的效率能讓我們有效的減少乘法的次數,使最終的計算速度提高了,那么這種改進就是值得的。
我們發現tan(26.565051177078)=0.5,如果我們第二次旋轉采用26.565051177078度,那么乘數變為0.5,如果我們采用定點數運算的話(沒有浮點協處理器時為了加速計算我們會大量的采用定點數算法)乘以0.5就相當于將乘數右移一位。右移運算是很快的,這樣第二次循環中的乘法運算也被消除了。
類似的方法,第三次循環中不用11.25度,而采用 14.0362434679265 度。
Tan(14.0362434679265)= 1/4
乘數右移兩位就可以了。剩下的都以此類推。
tan(45)= 1
tan(26.565051177078)= 1/2
tan(14.0362434679265)= 1/4
tan(7.1250163489018)= 1/8
tan(3.57633437499735)= 1/16
tan(1.78991060824607)= 1/32
tan(0.8951737102111)= 1/64
tan(0.4476141708606)= 1/128
tan(0.2238105003685)= 1/256
還是給出C語言的實現代碼,我們采用循序漸進的方法,先給出浮點數的實現(因為用到了浮點數,所以并沒有減少乘法運算量,查找的效率也比二分查找法要低,理論上說這個算法實現很低效。不過這個代碼的目的在于給出算法實現的示意性說明,還是有意義的)。
double my_atan4(double x, double y)
{
const double tangent[] = {1.0, 1 / 2.0, 1 / 4.0, 1 / 8.0, 1 / 16.0,
1 / 32.0, 1 / 64.0, 1 / 128.0, 1 / 256.0, 1 / 512.0,
1 / 1024.0, 1 / 2048.0, 1 / 4096.0, 1 / 8192.0, 1 / 16384.0
};
const double angle[] = {45.0, 26.565051177078, 14.0362434679265, 7.1250163489018, 3.57633437499735,
1.78991060824607, 0.8951737102111, 0.4476141708606, 0.2238105003685, 0.1119056770662,
0.0559528918938, 0.027976452617, 0.01398822714227, 0.006994113675353, 0.003497056850704
};
int i = 0;
double x_new, y_new;
double angleSum = 0.0;
for(i = 0; i < 15; i++)
{
if(y > 0)
{
x_new = x + y * tangent[i];
y_new = y - x * tangent[i];
x = x_new;
y = y_new;
angleSum += angle[i];
}
else
{
x_new = x - y * tangent[i];
y_new = y + x * tangent[i];
x = x_new;
y = y_new;
angleSum -= angle[i];
}
printf("Debug: i = %d angleSum = %f, angle = %f, ρ = %f\n", i, angleSum, angle[i], hypot(x, y));
}
return angleSum;
}
程序運行的輸出結果如下:
Debug: i = 0 angleSum = 45.000000, angle = 45.000000, ρ = 316.227766
Debug: i = 1 angleSum = 71.565051, angle = 26.565051, ρ = 353.553391
Debug: i = 2 angleSum = 57.528808, angle = 14.036243, ρ = 364.434493
Debug: i = 3 angleSum = 64.653824, angle = 7.125016, ρ = 367.270602
Debug: i = 4 angleSum = 61.077490, angle = 3.576334, ρ = 367.987229
Debug: i = 5 angleSum = 62.867400, angle = 1.789911, ρ = 368.166866
Debug: i = 6 angleSum = 63.762574, angle = 0.895174, ρ = 368.211805
Debug: i = 7 angleSum = 63.314960, angle = 0.447614, ρ = 368.223042
Debug: i = 8 angleSum = 63.538770, angle = 0.223811, ρ = 368.225852
Debug: i = 9 angleSum = 63.426865, angle = 0.111906, ρ = 368.226554
Debug: i = 10 angleSum = 63.482818, angle = 0.055953, ρ = 368.226729
Debug: i = 11 angleSum = 63.454841, angle = 0.027976, ρ = 368.226773
Debug: i = 12 angleSum = 63.440853, angle = 0.013988, ρ = 368.226784
Debug: i = 13 angleSum = 63.433859, angle = 0.006994, ρ = 368.226787
Debug: i = 14 angleSum = 63.437356, angle = 0.003497, ρ = 368.226788
z = 63.437356
評論
查看更多