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

質問

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

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 · ベストアンサー

式が途中で破綻しています。訂正させて下さい。

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

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言語云々ではないです・・・・

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

お礼

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

回答No.6

tatsu99

>アルゴリズムの課題として６回のかけ算を３回にとどめるということなのです。
>言葉足らずでもうしわけありません。
ということは、足し算なら何回やってもよいのですか？
そうであれば、かけ算を足し算に変えられるので、かけ算の回数＝０を実現できます。・・・が、このようなものは、望んではいないのでしょうか。

回答No.5

asuncion

そもそも、すなおに６回かけ算を使うのでなく、どうして
３回にとどめたいか、その理由を教えていただけますか？

その演算を何億回も繰り返すのでない限り、
演算にかかる全体時間にはそれほどの違いはないと思います。

補足

アルゴリズムの課題として６回のかけ算を３回にとどめるということなのです。

言葉足らずでもうしわけありません。

回答No.4

神崎 渉瑠（@taloo）

アルゴリズム以前に、数学の問題では？
（展開の逆ってなんて言うんでしたっけ。）

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

これがどうなってこうなるのかわかりません。。。

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

+a*b-a*bが増えて複雑化してるだけのような気がしますが。

補足

仮に

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

という条件で、このままだとコストが高いから、足し算なり、引き算を付け加えてコストを下げようと言う考えてでいきたいのですが、上記の変換ではよけいにコストがあがってしまいますか？

回答No.3

nda23

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

x = p + q → b*b - c*c + a*b + b*d - b*b → a*b - c*c + b*d
y = p + r → b*b - c*c + a*d

中学生の因数分解みたいですね。

回答No.2

asuncion

＞かけ算の使用回数を３回までに押さえたいのです。

どの範囲で３回ですか？

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

tempを求める式でのかけ算を含めると、
お考えになった上記の方法では４回必要です。

補足

どの範囲で３回までなのかを確認しますが、私の判断からすると、
x＝
と
y＝
の右辺の式のなかのかけ算を３つまでに押さえたいということだと思います。

回答No.1

AKARI0418

http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96

このあたりをじっくり読んでみてください。

ソースは基本的に、視認性を最重視したほうがよいのではないでしょうか？

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

今回は変数名が短いため、今のままでも十分見やすいですしこのままでも十分では？

変数が長くてみずらいのであれば、
int multipul_ab
int multipul_cc
int multipul_bd

multipul_ab= a*b
multipul_cc= c*c
multipul_bd= b*d

//算術の途中経過が正しいかを確認できる。

x=multipul_ab - multipul_cc + multipul_bd

などと記述する意味が出てきます。