実行速度を速くしたいです。

[いちこ]

前回のスレッドに答えてくださってありがとうございました。
前回のスレッドに関連した質問なので、こちら（↓）を見てくださるとうれしいです。省略してしまいすみません。
http://dixq.net/forum/viewtopic.php?f=3&t=14938

上のスレッドでは、漸化式Xn+1 = (a*Xn+c)modM a=1103515245、c=12345、M=2^31 を用いて乱数を計算していましたが、現在は
M=5^13,a=2^39として　Xn=a*Xn(mod M) という漸化式を用いてプログラムを作成しています。
それ以外に以前と違うのは、long long int型では桁が足らず、unsigned long long型を使用しているところです。

プログラムは実行することができたのですが、桁が多く、M回ループをまわすと、とても実行が終わりません。
プログラムを速くする方法はないでしょうか。

詳しい方がおられましたら、ご教示お願いします。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
int main(void){
  unsigned long long a=pow(5,13);
  unsigned long long Xn=1; //初期値
  unsigned long long M=pow(2, 39);
  unsigned long long n=0;
 
  while(1){
 
    Xn=(a*Xn) % M; //乱数の計算
    n++;
 
    if(n % 10000000 == 0)
      printf("%lld\t Xn=%lld\n",n,Xn); //10000000ごとに出力
 
    if(Xn==1) break; //1周期終えたら、ループを抜ける
 
  }
 
  // 結果出力
  printf("%lld\t Xn=%lld\n",n,Xn);
  printf("周期　%lld\n",n);
  return EXIT_SUCCESS;
}

実行環境
Ubuntu / gcc4.7.3
Windows7(cygwin) / gcc3.4.4

[いちこです。]

ログインしていませんが、スレッドを立てた者です。
補足、訂正です。
出力の部分は%lldでなく、%lluです。

[h2so5]

10000000ごとの出力処理を削って実行したところ、4分ぐらいで終わりました。
(ちなみに、同じマシンで前のスレッドのプログラムを実行すると4.5秒)

出力処理を削り、-O2オプションでコードの最適化を有効にすると高速化できますが、それでも結構時間はかかると思います。
gcc -o sample -O2 sample.c -lm

[softya（ソフト屋)]

マルチ・スレッドに分散できる処理でも無さそうですので驚異的な速度アップは難しいかと思います。【追記】
if(n % 10000000 == 0)を無くすことで効果があるようなら、無くしてみても良いかと。

[かずま]

+c がありませんが、これで一様乱数になるんでしょうか？
Xn は偶数になりませんよね。
次のプログラムによると、周期は 2^39 ではく、2^37 のようです。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
    unsigned long long a = pow(5, 13);
    unsigned long long Xn = 1;
    unsigned long long M = 0x7fffffffffLLU;  // pow(2, 39) - 1
    unsigned long long n;
    int i, j, k;

    for (i = 0; i < 1024; i++) {
        for (j = 0; j < 64*1024*1024; j++) {
            Xn = (a * Xn) & M; if (Xn == 1) { k = 1; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 2; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 3; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 4; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 5; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 6; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 7; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 8; goto PRINT; }
        }
        printf("%llu\t Xn=%llu\n", (i*64LLU*1024*1024 + j) * 8, Xn);
    }
PRINT: 
    n = (i*64LLU*1024*1024 + j) * 8 + k;
    printf("%llu\t Xn=%llu\n", n, Xn);
    printf("周期　%lld\n", n);
    return EXIT_SUCCESS;
}

[いちこ]

>>h2so5さん
返信ありがとうございます。
10000000ごとの出力処理を削り、-O2オプションを使ってみました。
10分前くらいに実行し始め、現在実行中です。
前のスレッドのプログラムの実行がだいたい3~5分くらいかかっていたので、かなりかかりそうです。

>>softya(ソフト屋)さん
返信ありがとうございます。
そうなんですか…参考になりました。
これ以上速くするには、計算機の性能によることになるのでしょうか。

>>かずまさん
返信ありがとうございます。

+c がありませんが、これで一様乱数になるんでしょうか？

これについてなんですが、上で示した漸化式は、たしかに一様乱数を求めるために作られている式ではないと思います。というのも、この漸化式の数値は、適当に決められたもので、これを解いてくるよう求められた課題なのです。
なので、かずまさんの言うとおり、実行結果は奇数しかありませんでした。

プログラムの提示、ありがとうございます。参考にさせていただきます。

[いちこ]

何度もすみません、今実行完了しました！
だいたい11~2分くらいかかりましたが、いままで1時間以上かけても終わらなかったのでうれしいです。ありがとうございます。

これに関連して質問があるのですが（新スレッドを立てたほうがよいでしょうか…）

上のプログラムにファイル出力（Unの値を出力する）を付けたいのですが、以前より重くなってしまうのではないかと思っています。

具体的には、Unの値がある一定値以下の場合(if文)、テキストファイルに出力する。という処理を行いたいです。
ですが、プログラムを組む段階で何度か実行結果を確認したいので、1時間2時間もかかるプログラムにするのはどうしても避けたいです。

これに関してなにかご指摘というか、アドバイス等を頂きたいです。
よろしくおねがいします。

[いちこ]

ほんとに何度もすみません。
ファイル出力処理を加えて作成してみたところ、15分くらいで実行できました。
これくらいなら許容範囲かなと思います。

みなさまのおかげで解決することができました。ありがとうございました。

[かずま]

途中経過を 10進にしてみました。
Windows 7/Cygwin/gcc 4.8.1 -O2/Core i5 2.53GHz/4GB mem
で 3分40秒でした。そちらではどれくらいでしょうか？

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
    unsigned long long a = pow(5, 13);
    unsigned long long Xn = 1;
    unsigned long long M = 0x7fffffffffLLU;  // pow(2, 39) - 1
    unsigned long long n;
    int i, j, k;

    for (i = 0; i < 1000; i++) {
        for (j = 0; j < 100*1000*1000; j++) {
            Xn = (a * Xn) & M; if (Xn == 1) { k = 1; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 2; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 3; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 4; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 5; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 6; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 7; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 8; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 9; goto PRINT; }
            Xn = (a * Xn) & M; if (Xn == 1) { k = 10; goto PRINT; }
        }
        printf("%llu\t Xn=%llu\n", (i+1)*100LLU*1000*1000*10, Xn);
    }
PRINT: 
    n = (i*100LLU*1000*1000 + j) * 10 + k;
    printf("%llu\t Xn=%llu\n", n, Xn);
    printf("周期　%llu\n", n);
    return EXIT_SUCCESS;
}

[いちこ]

>>かずまさん
返信ありがとうございます。
こんな方法があるんですね…！
私の計算機（Ubuntu/gcc4.7.3）では10分で実行が終わりました。（約2/3になりました！）
windowsではやっていませんが、前のプログラムが大体同じ速さで実行されたので、今回も同じくらいではないかなと思います。

此方の方が速いので、参考にさせて頂きます…！
また、わからないところがあったら質問させていただきます。
ありがとうございましたm(_ _)m