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

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

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.7 回答者： AKARI0418 回答日時： 2009/09/14 15:38

全部足し算にしたいのであれば、

たとえばa*bを
int i;
for (i = 0; i < b; i++)
{
a += a;
}
で全て足し算にできます。

でもコストが高くなります。

私が提示したwikiを呼んでください。
コンパイラがコードを最適化している文法についても取り上げられています。

コストが高い低いはコンパイラの動作に習うのが最もよいと思いますよ。

たとえば、
共通式削除（common sub-expression elimination）
"(a+b)-(a+b)/4" という式があったとき、"(a+b)" が2回出現する共通式である。共通式削除では、"(a+b)" がこの間に変化しないと判断し、1回だけ計算するよう最適化する。
定数畳み込み（constant folding）と定数伝播（constant propagation）
定数からなる式（例えば、"3 + 5"）をコンパイル時に計算結果（"8"）と置き換えてしまう。最近の言語処理系ではほとんど必ず行われる。

No.6 回答者： tatsu99 回答日時： 2009/09/14 14:50

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

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

No.5 回答者： asuncion 回答日時： 2009/09/14 14:00

そもそも、すなおに６回かけ算を使うのでなく、どうして

３回にとどめたいか、その理由を教えていただけますか？

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

この回答への補足

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

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

補足日時：2009/09/14 14:21

No.4 回答者： taloo 回答日時： 2009/09/14 13:48

アルゴリズム以前に、数学の問題では？

（展開の逆ってなんて言うんでしたっけ。）

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

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

補足日時：2009/09/14 14:23

No.3 回答者： nda23 回答日時： 2009/09/14 13:45

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 回答日時： 2009/09/14 13:27

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

どの範囲で３回ですか？

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

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

この回答への補足

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

補足日時：2009/09/14 14:26

No.1 回答者： AKARI0418 回答日時： 2009/09/14 12:48

http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3% …

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

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

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

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