Created
February 13, 2011 17:16
-
-
Save mumumu/824848 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
/* | |
* param の num 乗を出力する関数(二進累乗法の実装) | |
* | |
* TODO: オーバーフロー/アンダーフローのチェックをしていない | |
* TODO: num が負の時に対応していない | |
*/ | |
static void power(double param, long long int num) | |
{ | |
double result = 1; | |
double power_base = param; | |
if (param == 0) { | |
printf("0\n"); | |
return; | |
} | |
if (num == 0) { | |
printf("1\n"); | |
return; | |
} | |
while (num != 0) { | |
// | |
// 乗数の最下位ビットをチェックし、1ならば | |
// 最終結果に今までの param^2x 分を掛ける | |
// これは以下の役割を果たす | |
// | |
// - num が奇数であった場合に、result の | |
// 初期状態をpower_base に等しくする | |
// (つまり、一回掛けた状態にする) | |
// - 最下位ビットが1の場合をとらえて、result | |
// に今までためてきた power_base^2x の値 | |
// を掛ける。この回数が少ないほど誤差が少なく | |
// なる。 | |
// | |
if ((num & 1) == 1) { | |
result *= power_base; | |
} | |
// | |
// 乗数を1ビットシフトし、 | |
// power_base^2 する。これにより、以下の | |
// ような形になる | |
// | |
// power_base^2 -> power_base^4 -> power_base^8 | |
// power_base^16 -> power_base^32 ... | |
// | |
// これにより、乗数のビット数 + 数回の掛け算により | |
// 大きな乗数でも値を計算できるようになる | |
// | |
num = num >> 1; | |
power_base *= power_base; | |
} | |
printf("%.20f\n", result); | |
} | |
int main(int argc, char *argv[]) | |
{ | |
double base = 0; | |
long long int num = 0; | |
// no error processing | |
printf("input base number:"); | |
scanf("%lf", &base); | |
printf("input multiplier:"); | |
scanf("%Ld", &num); | |
power(base, num); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment