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

質問

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

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.17

kamuycikap

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

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

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

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

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

回答No.16

ralf124c

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

回答No.15

神崎 渉瑠（@taloo）

No.4です。

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

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

回答No.14

nda23

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

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

補足

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

回答No.13

Tacosan

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

回答No.12

yama5140

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

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

　元の式を見て、「パッと見」気付けよと・・（残念、年寄りには無理でした、「中学生の因数分解」なんて昔話）。
　または、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 );
}

お礼

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

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

回答No.11

asuncion

何だか、アルゴリズムというよりは、
数式のこねくり回しという感じがしてきました。

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

回答No.9

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

何となく簡単にできそう・・・
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

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

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

回答No.7

AKARI0418

全部足し算にしたいのであれば、
たとえば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"）と置き換えてしまう。最近の言語処理系ではほとんど必ず行われる。