実行速度の高速化（ｃ言語）

[こん にし]

ある問題があり、サンプル例として、いくつか値を入力することができるのですが、出力が遅くなってしまいます。
まず、今の自分のレベル、状態について書きます。

[1] 質問文
　[1.1] 自分が今行いたい事は何か・・・より速く、大きな数、サンプルなどの数の処理を早くしたいです。
　[1.2] どのように取り組んだか(プログラムコードがある場合記載)…コードは記載させてもらいました。
　[1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)・・・エラーはないです。
　[1.4] 今何がわからないのか、知りたいのか・・・long型などを試してもより遅くなったりしたので、自作関数を作れば早くなるのかもしれないと感じました。ただ、どうやってこの問題をかみ砕いて関数を作ればいいのか分かりません。知りたいことは、C言語における、高速化の方法です。

[2] 環境 　
　[2.1] OS ： Windows　vistaです。
　[2.2] コンパイラ名 ： 学習用Ｃ言語開発環境 Ver 0.0.9.0(苦しんで覚えるC言語というサイトで頒布されています。）
[3] その他
　・どの程度Ｃ言語を理解しているか・・・一通り勉強はしました。ただ、再帰の部分がまだ不完全で、勉強中です。

問題です。
ある計算機学者が電子空間に棲息する電子蝿という奇妙な生命体を見つけました。電子蝿の行動を観察し ているうちに、この空間の (x, y, z)地点にいる電子蝿は、次に以下の規則で示される (x', y', z')に移動すること が分かりました。
x'＝a1 x mod(m1)
y'=a2 y mod(m2)
z'=a3 z mod(m3)

ただし、a1, m1, a2, m2, a3, m3は電子蝿の個体ごとに定まる正の整数です。A mod B は正の整数Aを正の整数B で割ったときの余りです。

さらに観察をすると、ある種の電子蝿は(1,1,1)に置いてからしばらくすると、必ず(1,1,1)に戻ってくることがわ かりました。このような蝿を戻り蝿と名付けました1 。戻り蝿のデータを入力とし、(1,1,1)に戻ってくる最小の移動 回数(>0)を出力して終了するプログラムを作成してください。なお 1< a1, m1, a2, m2, a3, m3 < 215とします。

1 a1とm1, a2とm2, a3とm3がそれぞれ互いに素(公約数が 1)である時に戻ります。

Input
複数のデータセットが与えられます。各データセットは以下のとおり：

a1 m1 a2 m2 a3 m3
入力は６つの0を含む行で終わります。

Output
各データセットごとに、(1,1,1)に戻ってくる最小の移動回数(整数)を出力してください。

Sample Input
2 5 3 7 6 13・・・①
517 1024 746 6561 4303 3125・・・②
0 0 0 0 0 0
Output for the Sample Input
12
116640000

自分は次のように書きました。問題文通り、素直に書きました。また、高速化になるかもしれないと思い、いろいろなところで修正、削除しています。

コード:

#include<stdio.h>
int main(void)
{
	unsigned int a1,m1,a2,m2,a3,m3;
	unsigned int x,y,z;
	unsigned int m;
	while(1)
	{
		scanf("%d %d %d %d %d %d",&a1,&m1,&a2,&m2,&a3,&m3);
		if(a1==0)break;//1< a1, m1, a2, m2, a3, m3 < 215より、１つでも０なら必ず出力は終わります。
		x=1;
		y=1;
		z=1;
		m=0;
		for(;;)
		{
			x=a1*x%m1;
			y=a2*y%m2;
			z=a3*z%m3;
			m++;
			if(x==1&&y==1&&z==1)break;
		}
		printf("%d\n",m);
	}
	return 0;
}

今の自分の状態は、①の値なら瞬時に出ますが、②となると１秒近くかかります。

どのようにすれば高速化できるのでしょうか？
皆様のお力を貸していただきたいです。
よろしくお願いします。

[かずま]

x1、y1、z のそれぞれが 1 になるまでの回数の最小公倍数でいいのでは?

コード:

#include <stdio.h>

unsigned gcd(unsigned x, unsigned y)
{
    unsigned r;
    while (r = x % y) x = y, y = r;
    return y;
}

unsigned lcm(unsigned x, unsigned y)
{
    return x * y / gcd(x, y);
}

int main(void)
{
    unsigned a1, m1, a2, m2, a3, m3, x, y, z, k1, k2, k3;
    while (scanf("%d%d%d%d%d%d", &a1, &m1, &a2, &m2, &a3, &m3) == 6 &&
            a1 * m1 * a2 * m2 * a3 * m3) {
        x = y = z = 1;
        k1 = k2 = k3 = 0;
        do { x = a1 * x % m1; k1++; } while (x != 1);
        do { y = a2 * y % m2; k2++; } while (y != 1);
        do { z = a3 * z % m3; k3++; } while (z != 1);
        printf("%d\n", lcm(lcm(k1, k2), k3));
    }
    return 0;
}

すみません。オーバーフローはチェックしていません。

[かずま]

x1、y1、z のそれぞれが 1 になるまでの回数の最小公倍数でいいのでは?

x、ｙ、z です。

return x * y / gcd(x, y);　は、return x / gcd(x, y) * y; に、
scanf と printf の %d は、%u に、してください。

[こん にし]

おはようございます。

ご返事ありがとうございます。

自分なりにかずまさんのコードを解釈してみましたが、一つ分からないところがあります。

>printf("%u\n", lcm(lcm(k1, k2), k3));
の部分です。lcm(k1, k2)の部分は理解できました。ｋ１とｋ２の最小公倍数を求める。ｋ１はｘが１になるときの値、ｋ２はｙが１になるときの値。それが最小の値で一致するときの値を求めているのですね。
ポイントは、ｋ１、ｋ２の値がX==1＆＆ｙ＝＝１ではないと言う事だと思います。
ここで分からないのは、どうして最小公倍数を使う必要があるのでしょうか？
lcm(lcm(k1, k2), k3)というのは、つまりｘ、ｙ、ｚが１にあるときの値と解釈できますが、その場合、自分のかいた、
　　　　　x=a1*x%m1;
y=a2*y%m2;
z=a3*z%m3;
m++;
if(x==1&&y==1&&z==1)break;
}
printf("%d\n",m);
と違いが分からないのですが、どういう点で実行速度が早くなり、動作がことなるのでしょうか？
また、動作確認してみましたが、かなり早くなってびっくりです！
この解法をどうにかして理解したいと思っています。
お手数おかけしますが、よろしくお願いします。

[こん にし]

追記です。

自分の書いたコードでは、break;を使っているので、最小の値で回数を表示できると思いました。

たとえば、それで回数が変化するのなら、最小公倍数を使って、最小の値をもとめなければいけないと思うのですが、例の値を入れても同じ結果がでてくるので、どうしてだろう？と思いました。

[かずま]

>printf("%u\n", lcm(lcm(k1, k2), k3));
の部分です。lcm(k1, k2)の部分は理解できました。ｋ１とｋ２の最小公倍数を求める。
ｋ１はｘが１になるときの値、ｋ２はｙが１になるときの値。それが最小の値で一致するときの値を求めているのですね。
ポイントは、ｋ１、ｋ２の値がX==1＆＆ｙ＝＝１ではないと言う事だと思います。
ここで分からないのは、どうして最小公倍数を使う必要があるのでしょうか？

次のプログラムを実行して、2 5 3 7 6 13 を入力してみてください。

コード:

#include <stdio.h>

int main(void)
{
    unsigned a1, m1, a2, m2, a3, m3, x, y, z, k1;
    while (scanf("%u%u%u%u%u%u", &a1, &m1, &a2, &m2, &a3, &m3) == 6
            && a1 && m1 && a2 && m2 && a3 && m3) {
        x = y = z = 1;
        k1 = 0;
        do {
            x = a1 * x % m1;
            y = a2 * y % m2;
            z = a3 * z % m3;
            k1++;
            printf("%8u%8u%8u%8u\n", k1, x, y, z);
        } while (x != 1 || y != 1 || z != 1);
        printf("%u\n", k1);
    }
    return 0;
}

実行結果

コード:

2 5 3 7 6 13
       1       2       3       6
       2       4       2      10
       3       3       6       8
       4       1       4       9
       5       2       5       2
       6       4       1      12
       7       3       3       7
       8       1       2       3
       9       2       6       5
      10       4       4       4
      11       3       5      11
      12       1       1       1
12

x は、2 4 3 1 を繰り返しています。k1 = 4 です。
y は、3 2 6 4 5 1 を繰り返しています。k2 = 6 です。
k1 と k2 の最小公倍数は、12 です。
x は 4回ごとに 1 になります。
y は 6回ごとに 1 になります。
x と y がどちらも 1 になるのは、12回ごとです。
z は、k3 = 12 で、12回ごとに 1　になります。
k1, k2, k3 の最小公倍数は 12 です。
x と y と z が全部 1 になるのは 12回ごとです。
小学校の算数レベルの問題です。

lcm(lcm(k1, k2), k3)というのは、つまりｘ、ｙ、ｚが１にあるときの値と解釈できますが、その場合、自分のかいた、
　　　　　x=a1*x%m1;
y=a2*y%m2;
z=a3*z%m3;
m++;
if(x==1&&y==1&&z==1)break;
}
printf("%d\n",m);
と違いが分からないのですが、どういう点で実行速度が早くなり、動作がことなるのでしょうか？

最小公倍数を使ったプログラムのほうで、k1、k2、k3 を表示させると、
517 1024 746 6561 4303 3125
に対して、k1 = 256、k2 = 1458、k3 = 2500 となります。
そして、それらの最小公倍数は 116640000。

そのプログラムでループを回る回数は、
256 + 1458 + 2500 = 4214 回です。

こんさんのプログラムでループを回る回数は 11664000回。
しかも、1回のループで、x、y、z の計算をしているので、
時間は さらに 3倍かかります。遅いのは当然ですね。

[こん にし]

なｔるほど！
確かにそうなりますね。
どうにか解決できました。何回プールしたかによってこんなにも実行速度が変わるんですね。
とても勉強になりました。
ありがとうございます！

[みけCAT]

ループが何回回るかというのは、競技プログラミングにおいて実行時間を見積もるための基本です。
例えば、ループがだいたい10,000,000回以内なら1秒以内に実行が終わりそう、と見積もります。
(もちろん、ループが回る回数だけで実行時間が決まるわけではありません)

[こん にし]

なふほどですね。

どのように実行するのか、完璧に動きを追うのは難しいですが、ここで何をしているのかなど考え、解いていこうと思います。今回はループの回数という問題でしたが、そのことも意識しながら、今後もプログラミングをやっていこうと思います。また、どうしても分からない問題があり、質問させてもらうかもしれませんが、その時はどうかよろしくお願いします。
今回はありがとうございました。

[きゃりーわんわん]

既に解決済みですが。

今回はループの回数という問題でしたが、そのことも意識しながら、今後もプログラミングをやっていこうと思います。

今回の問題というよりは、高速化についてコメントさせていただきます。

高速化したい場合、
考える流れは以下となると思っています。
①：アルゴリズムとデータ構造は適切か？
②：不要な処理はないか？
③：他に何かすることはないか？

大抵の場合、
適切なアルゴリズムとデータ構造を使用すれば
十分高速になります。

それでも速度を求める場合に②を考えます。
例えばループ内の不要な処理をループ外に移すとかです。

それをしてもまだ速度を求める人は
③を考えます。
例えば以下のようなことをします。
・マルチプロセス/マルチスレッドを使用する
・問題に応じてチューニングする
　→ 例えば、数値に厳密性を求めない(誤差が気にならない)問題であれば
　　　浮動小数点を使わずに整数を使うこともありです。
　　　# 実は現状のCPU/コンパイラが優秀で
　　　# 浮動小数点と整数の計算に差はなくなっているのかもしれません。
　　　# 昔は明らかな差がありましたので・・・

　　　他には、整数Aと整数Bが入力として与えられ、
　　　A / Bを返しなさいという問題があるとします。
　　　このBに0が来ないことが保証されているのであれば
　　　除算するさいに分母(B)が0かどうかのチェックはする必要がないため、
　　　条件分岐をなくすことができます。
　　　

③の行くつく先はコンパイラが吐くアセンブリコードを眺めるところですかね・・・

高速化は結果が伴うため、
やっていて楽しいと思います。
頑張ってください。

[こん にし]

適切なアルゴリズムを考えることが大事ですね。


なるほど、確かに条件の文が減れば、そこでの動作がなくなるので早くなりますね。

答えを出すだけでなく、早さも重要なので、とても参考になりました＾＾

ありがとうございます。

またわからないところがあり、お世話になるかもしれませんが、その時はよろしくお願いします！