C言語関係掲示板

過去ログ

No.236.2進アルゴリズム


No.1439

2進アルゴリズム
投稿者---yusuke(2002/04/20 00:46:50)


皆様お久しぶりです。といっても誰も覚えていらっしゃらないでしょうけど・・・。
今、2進アルゴリズムについて学んでいます。
2進アルゴリズムの定義は

x^2=(x^m)^2


x^2m+1=(x^m)^2*x

であり、計算回数を減らすことができると学びましたが、これが、どのようにプログラムの中で生きてくるのか、ということを質問したくて参りました。
よろしくお願いします。

No.1442

Re:2進アルゴリズム
投稿者---かずま(2002/04/21 11:18:22)


>2進アルゴリズムの定義は
>x^2=(x^m)^2
>x^2m+1=(x^m)^2*x
>であり、計算回数を減らすことができると学びましたが、

なんか杜撰な定義ですね。
^ は、Cでは、ビット単位の排他OR演算子だということはご存知ですか。
ここでは、べき乗の意味だと解釈することにしておきましょう。さらに、

 x^(2*m) = (x^m)^2
 x^(2*m + 1) = (x^m)^2 * x

として、話を進めます。

計算回数を減らすというのは、べき乗の計算回数のことでしょうか。

単純に考えると、x^n を計算するのに、掛け算を (n-1)回しないといけない。
例えば、x^100 だったら、99回の掛け算が必要。でも、x^50 が求まったら、
それを2乗すればよいのだから、50回の掛け算で済みむことがわかります。
x^50 を求めるのにも、もっと少ない回数の掛け算でいいはず。そこで、次の
ようなプログラムを書いてみると、x^100 はなんと 8回の掛け算で出来て
しまいます。
double power(double x, int n)  /* n = 1, 2, ... */
{
    double t;

    if (n == 1)
        return x;
    if (n & 1) {
        t = power(x, (n-1)>>1);   /* n が奇数の場合 */
        return t * t * x;
    }
    t = power(x, n>>1);           /* n が偶数の場合 */
    return t * t;
}
でも、これは、最小の掛け算回数のアルゴリズムではありません。

例えば、x^15 は、このプログラムだと 6回の掛け算になります。

 x2 = x * x
 x3 = x2 * x
 x6 = x3 * x3
 x7 = x6 * x
 x14 = x7 * x7
 x15 = x14 * x

実際には、次のように 5回の掛け算で答えを求める方法があります。

 x2 = x * x
 x3 = x2 * x
 x6 = x3 * x3
 x9 = x6 * x3
 x15 = x9 * x6



No.1443

Re:2進アルゴリズム
投稿者---yusuke(2002/04/21 12:15:01)


どうもありがとうございます。
これを元に、もう少し自分で考えてみようと思います。
ありがとうございました。


No.1444

Re:2進アルゴリズム
投稿者---かずま(2002/04/21 16:48:50)


>double power(double x, int n)  /* n = 1, 2, ... */
>{
>    double t;
>
>    if (n == 1)
>        return x;
>    if (n & 1) {
>        t = power(x, (n-1)>>1);   /* n が奇数の場合 */
>        return t * t * x;
>    }
>    t = power(x, n>>1);           /* n が偶数の場合 */
>    return t * t;
>}
このプログラムですが、再起呼出しを使わないようにすると、
double power(double x, int n)
{
    double t = x;
    int    m = n;

    while (m & m-1)
        m &= m-1;
    while (m >>= 1) {
        t *= t;
        if (n & m)
            t *= x;
    }
    return t;
}


戻る


「初心者のためのポイント学習C言語」 Last modified:2002.06.22
Copyright(c) 2000-2002 TOMOJI All Rights Reserved