エラトステネスのふるい 速度比較

C言語版を以下のように書き直して、perl と速度比較してみる。

#include "stdafx.h"
#include <stdlib.h>
#include <stdbool.h>

int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long int prime_max = 100000000;
bool *prime;
unsigned long long int i, j;


/* 配列の領域を確保 & 初期化 */
prime = (bool *)malloc(sizeof(bool) * (prime_max + 1));
for (unsigned long long i = 0; i <= prime_max; ++i)
prime[i] = true;

/* さて、始めるよ！ */
for (i = 2; i <= prime_max/2 ; ++i){
if (!prime[i])
continue; /* 素数で無いなら次へ */

/* 素数の倍数 (=素数で無い) に false を代入 */
for (j = 2; prime_max >= i * j; ++j)
prime[i*j] = false;
}

return 0;
}

# perl

use strict;
use warnings;
use Benchmark qw/timethese cmpthese/;

# エラトステネスの篩 (Sieve of Eratosthenes)
my $MAX = 10000000;

my $results = timethese( 1,{
Erat_pl =>
sub {
my $x = $MAX;
my @Prime = ();
for (my $i = 2 ; $i <= sqrt($x) ; $i++){
# マークが付いていたら (=素数でなかったら) 次へ
if (defined($Prime[$i])){next;}

# 素数の倍数にマークを付ける
for (my $j = 2 ; $x >= ($i * $j) ; ++$j ){
$Prime[$i * $j] = 1;
}
}
},
Erat_clx64 =>
sub {
system('C:/～～～/Eratosthenes_cl.exe');
},

Erat_IDEx86 =>
sub {
system('C:/～～～/Eratosthenes_IDE.exe');
}

});

cmpthese $results;

統合環境でコンパイル 32bit版
　→　110秒
コマンドラインでコンパイル 64bit版 /Ot /arch:AVX2 /GL
　→　62秒
Perl スクリプト
　→　130秒

64bit の威力！

C言語だとメモリ 3GB 手前ぐらいで 2999999929 まで求められました。

エラトステネスのふるい その2

MS Visual Studio Express 2013 for Windows Desktop とかってのを見つけたのでダウンロードしてみた。
しかしすることが無い。
ということで、C でエラトステネスの篩を書いてみた。

引数に求めたい素数の最大値を指定。
C:>Eratosthenes.exe 1000
1000 までの素数は大きい方から
997
991
983
977
971
967
953
947
941
C:>
と、でかい方から 10個表示する。

#include "stdafx.h"
#include &lt;limits.h>
#include &lt;stdlib.h>
#include &lt;wchar.h>
#include &lt;tchar.h>
#include &lt;stdbool.h>

int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long int prime_max;
bool *prime;
unsigned long long int i, j;

if (argc != 2){
puts("素数を求める最大値を 1つ指定して下さい");
return -1;
}
/* 引数を数値に変換 LLONG_MAX まで */
prime_max = _tstoi64(argv[1]);
printf("%llu までの素数は大きい方から\n", prime_max);
if (prime_max > LLONG_MAX || prime_max == 0){
puts("1以上の数値を 1つ指定して下さい。");
return -1;
}
/*
printf("LONG_MAX : %ld\n", LONG_MAX);
printf("ULONG_MAX : %lu\n", ULONG_MAX);
printf("LLONG_MAX : %lld\n", LLONG_MAX);
printf("ULLONG_MAX: %llu\n", ULLONG_MAX);
*/

/* 配列の領域を確保 & 初期化 */
prime = (bool *)malloc(sizeof(bool) * (prime_max + 1));
for (unsigned long long i = 0; i <= prime_max; ++i)
prime[i] = true;

/* さて、始めるよ！ */
for (i = 2; i <= prime_max / 2; ++i){
if (!prime[i])
continue; /* 素数で無いなら次へ */

/* 素数の倍数 (=素数で無い) に false を代入 */
for (j = 2; prime_max >= i * j; ++j)
prime[i*j] = false;
}

/* 表示ルーチン
* 大きい方から j = 10 個表示 */
for (i = prime_max, j = 10; i > 1 && j > 1; --i){
if (!prime[i]) continue;
printf("%lld\n", i);
--j;
}
return 0;
}

若干ごみが残ってますが、こんな感じ。ヘッダーが大量に要りますねぇ(^^;
不思議なのは IDE からコンパイルするのと開発者コマンドプロンプトの cl でコンパ
イルするのではできた実行ファイルのサイズが倍以上違う。何故？

MS Visual Studio Express 2013 for Windows Desktop の統合環境版でコンパイル
　→ 32,256バイト

開発者コマンドプロンプト for VS 2013　でコンパイル
　→ 68,608バイト