かけ算に関してのアルゴリズム

アルゴリズムに関して全くの初心者なので、お力を貸してくれると幸いです。
タイトルにもありますが、かけ算を使ってのアルゴリズムですが、足し算なり、引き算なりを使ったほうが効率がいいのですが、どのようにすればいいのか悩んでおります。

x=a*b-c*c+bd
y=b*b-cc+a*d

と全部で６つののかけ算があります。
新しい変数（例えば、temp=c*c　のような）を作ってもかまいませんので、
かけ算の使用回数を３回までに押さえたいのです。

私が考えたのは、

x=b(a+d)-temp
y=b(b+a)-temp+a(d-b)

ほかに効率の良いアルゴリズムはありますでしょうか？
よろしくお願いします

No.10 ベストアンサー 回答者： goosyu 回答日時： 2009/09/14 18:42

式が途中で破綻しています。

訂正させて下さい。

数学の問題なのかな・・妄想してみます。

x=a*b-c*c+b*d
y=b*b-c*c+a*d

c*cを消してみる
y-x = b*b-c*c+a*d - (a*b-c*c+b*d)
y-x = b*b+a*d-a*b-b*d

何となく簡単にできそう・・・
y-x = (b-a)*(b-d)

y = x + (b-a)*(b-d) ...式１


x=a*b-c*c+b*dを簡単にすると

x = -c*c+b*(a+d) ...式２

式１に式２を代入すると

y = (-c*c+b*(a+d)) + (b-a)*(b-d)

積算回数3回 -c*c , b*(a+d), (b-a)*(b-d)

これはC言語云々ではないです・・・・

ここまで；；見直しは必要ですね。。すいません。

この回答へのお礼

ありがとうございました。上記のやり方を教授に見せたら、なんか知りませんが、ほめられました。きっと、教授の思ってたことと違うやり方だったみたいでしたが、考え方はあってたので、大丈夫みたいです。

お礼日時：2009/09/16 15:42

No.17 回答者： kamuycikap 回答日時： 2009/09/23 18:17

kamuycikapです。

計算スピードを早くするためのアルゴリズムでしょうか？
掛け算の回数を減らす目的と理由がわからないので、私の書き込みが的を得ていない可能性もあります。

コンパイラでプログラムをコンパイルする時に吐き出されるアセンブラコードを見ることをお勧めします。
結果として、掛け算のアセンブラが記述されている可能性が高いかもしれませんが、その場合は足し算命令を利用した掛け算のプログラムと、掛け算のアセンブラを利用したプログラムとの結果のスピードを測定してみてはどうでしょうか。
回答者(ralf124cさん)が書き込んで下さっているように、ビットシフトしてあれやこれやすることで掛け算を足し算で表現することが可能です。
※内容については勉強してくださいm(＿＿)m

経験上、カッコ付きで作成された複雑な計算式のプログラムが、結果的に遅くなっている事も多々あります。
1行に凝縮するプログラムではなくて、小学生でもわかるような計算式をツラツラと箇条書きのように書くプログラムのほうが早かったりするのです。
当然ながら、変数に格納される数値のビット数にも気を配る必要があります。
自分が走らせるプログラムがどんなハードウェア(CPU)なのかによっても変わってくると思います。
8bitレジスタのCPUなのか16bitレジスタのCPUなのか。

変数を多用(メモリ確保とアクセス)したとしても、スピードに関して問題がなければ無視しても良いと思いますし、ハードウェアアクセスの回数を減らすことにこだわるのであれば、利用するメモリを極力少なくし、利用する命令が極力少なくなるようなマシンコードを吐くソースを書かなければならないのではないでしょうか？

アルゴリズムを考え始めると・・・・結果的にコンパイル結果のアセンブラとにらめっこする事が多かったです^^;

No.16 回答者： ralf124c 回答日時： 2009/09/17 11:35

まさか、まさかとは思いますが乗数を２の倍数に分解してビットシフトを使ったりして・・・。

左へ１ビットシフトでブランク０にすれば２倍、２ビットシフトで４倍、３ビットシフトなら８倍とか、分解して残ったのが０なら何もしなくて１なら被乗数を最後に加える・・・
右なら割り算で・・・
いまどきそりゃ無いですね。失礼しました。

No.15 回答者： taloo 回答日時： 2009/09/16 10:10

No.4です。

> 展開の逆
Σ(￣△￣)おおぅ
因数分解でした。

> No.3
> No.10
なるほど、、、そういうことか。。。
(b-a)*(b-d)とか(b+c)*(b-c) のルールをすっかり忘れてますね。
もう一回勉強し直しだなあ。。。

No.14 回答者： nda23 回答日時： 2009/09/15 14:09

#3です。

この問題を出した人はスゴく昔の人なんじゃないですかね？
私も孫が二人もいるジジイSEなんですが、20年ほど前までのCPUでは
掛け算にかかる時間は足し算の50倍以上でしたし、8ビット機では
掛け算自体がありませんでした。同じ結果をもたらす命令にしても
クロックの少ない命令で作ることが大きな命題だったんですよ。
割り算なんかに至っては150倍以上かかるので、無神経に商と剰余を
別々に求めるコード（機械語の除算は商と剰余が同時に得られる）を
見ると神経に障ったものです。今時、こういうこと言うと、「貧乏性
ですねぇ」と若手にバカにされますが・・・

ということで、掛け算の回数を減らすことはプログラムの実行速度を
向上させるのに大きな意味があったのです。特に繰り返し処理の中
では小さな積み重ねが大きな差になって現れるので、昔の師匠連中は
こういう所にはウルサかったですね。

この回答への補足

そうですね。確かに、この問題を出した教授はそこそこの年齢だと思います。

補足日時：2009/09/16 15:36

No.13 回答者： Tacosan 回答日時： 2009/09/15 12:38

う～ん, なんだろうなぁこの問題.

ここから Strassen のアルゴリズム (もしくは FFT) に発展するなら「全く無意味」とは言わんけど....

No.12 回答者： yama5140 回答日時： 2009/09/15 10:59

たくさん回答がつきましたね。

☆そもそも今回は、「アルゴリズムの課題」を騙って、教師に「試された」のではないでしょうか、数学力までを。

　元の式を見て、「パッと見」気付けよと・・（残念、年寄りには無理でした、「中学生の因数分解」なんて昔話）。
　または、No.10 さんのように少しは「妄想」してみろと・・（これが期待されているような）。

（お願い）
「結果」が出るまで当質問を「締め切り」することなく、出ましたら一番近い「回答」にコメント付けて頂けるのを楽しみにしています。

#include <stdio.h>

void main()
{
int a = 1, b = 2, c = 3, d = 4;
int x, y;
int p, q, r; // No.3 さん用
int e, f, g; // No10 さん用

x = a * b - c * c + b * d;
y = b * b - c * c + a * d;

printf( " org %d, %d\n", x, y );

p = ( b + c ) * ( b - c );
q = b * ( a + d - b );
r = a * d;

x = p + q;
y = p + r;

printf( "No.3 %d, %d\n", x, y );

e = -c * c;
f = b * ( a + d );
g = ( b - a ) * ( b - d );

x = e + f; // 式２
y = x + g; // 式１

printf( "No10 %d, %d\n", x, y );
}

この回答へのお礼

今日、教授に上記のやり方を見せたら、いいそうです。
でも、教授は違うことを考えてたみたいなんですが、それも気になります。

もし、教授の答えが提示されたら、また書き込みしますね。

お礼日時：2009/09/16 15:39

No.11 回答者： asuncion 回答日時： 2009/09/15 10:24

何だか、アルゴリズムというよりは、

数式のこねくり回しという感じがしてきました。

temp を求める際の乗算をカウントしないのであれば、
質問者さんが最初に提示された内容でじゅうぶんではないかと思います。

No.9 回答者： goosyu 回答日時： 2009/09/14 18:14

数学の問題なのかな・・妄想してみます。

（あってるのかな・・・）

x=a*b-c*c+b*d
y=b*b-c*c+a*d

c*cを消してみる
y-x = b*b-c*c+a*d - (a*b-c*c+b*d)
y-x = b*b+a*d-a*b-b*d

何となく簡単にできそう・・・
x-y = (b-a)*(b-d)

y = x - (b-a)*(b-d) ...式１

x=a*b-c*c+b*dを簡単にすると

x = -c*c+b*(a+d) ...式２

式１に式２を代入すると
y = (-c*c+b*(a+d)) - (b-a)*(b-d)

積算回数3回 -c*c , b*(a+d), (b-a)*(b-d)

これはアルゴリズムの問題としては・・・・・。

No.8 回答者： tatsu99 回答日時： 2009/09/14 16:51

>どの範囲で３回までなのかを確認しますが、私の判断からすると、

>x＝
>と
>y＝
>の右辺の式のなかのかけ算を３つまでに押さえたいということだと思います。

もしそうなら、極論になるが
temp1=a*b-c*c+b*d
temp2=b*b-c*c+a*d
x=temp1
y=temp2
は、かけ算０回なので、ＯＫということになる。
従って、トータルでのかけ算の回数のような気がする。