第５話 マルチスレッドにによる素数探索プログラム解説
解答例
#include<iostream>
#include<process.h>
#include<math.h>
using namespace std;
const int N=100000000; //定数の定義と初期化
int cn1,cn2,cn3,cn4,cn5,a1[N/10],a2[N/10],a3[N/10],a4[N/10];
/*
a1は5で割ると2余るタイプを収納するグローバル配列
a2は5で割ると4余るタイプを収納するグローバル配列
a3は5で割ると1余るタイプを収納するグローバル配列
a4は5で割ると3余るタイプを収納するグローバル配列
*/
void f1(void *a);
void f2(void *a);
void f3(void *a);
void f4(void *a);
char sh(int a);
int main(){
a1[0]=2;a4[0]=3; //a1は5で割ると2余るタイプの素数を収納するグローバル配列、a4はa1は3で割ると2余るタイプの素数を収納するグローバル配列
cn1=1;cn2=0;cn3=0;cn4=1; //a1は5で割ると2余るタイプの素数と3で割ると2余るタイプの素数はそれぞれ1カウントしている
_beginthread(f1, 0, NULL); //新たなスレッドを起動してそこに関数f1を展開する
_beginthread(f2, 0, NULL); //新たなスレッドを起動してそこに関数f2を展開する
_beginthread(f3, 0, NULL); //新たなスレッドを起動してそこに関数f3を展開する
_beginthread(f4, 0, NULL); //新たなスレッドを起動してそこに関数f4を展開する
int i;
cout<<"5で割ると余りが0のタイプ"<<endl;//この5だけは、スレッドで探索する5で割ると余るが出るタイプとは違う。
cout<<"5"<<endl;
cout<<endl;
cout<<"5で割ると余りが1のタイプ"<<endl;
for(i=0;i<cn3;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a3[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが2のタイプ"<<endl;
for(i=0;i<cn1;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a1[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが3のタイプ"<<endl;
for(i=0;i<cn4;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a4[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが4のタイプ"<<endl;
for(i=0;i<cn2;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a2[i]<<" ";
}
cout<<endl;
cout<<"素数が"<<cn1+cn2+cn3+cn4+1<<"個ありました。"<<endl;
}
void f1(void *a){ //5で割ると2余るタイプの素数の探索を任務とする関数
int i;
for(i=7;i<=N;i+=10){
if(sh(i)){
a1[cn1]=i;
cn1++;
}
}
}
void f2(void *a){ //5で割ると4余るタイプの素数の探索を任務とする関数
int i;
for(i=9;i<=N;i+=10){
if(sh(i)){
a2[cn2]=i;
cn2++;
}
}
}
void f3(void *a){ //5で割ると1余るタイプの素数の探索を任務とする関数
int i;
for(i=11;i<=N;i+=10){
if(sh(i)){
a3[cn3]=i;
cn3++;
}
}
}
void f4(void *a){ //5で割ると3余るタイプの素数の探索を任務とする関数
int i;
for(i=13;i<=N;i+=10){
if(sh(i)){
a4[cn4]=i;
cn4++;
}
}
}
char sh(int a){ //素数判定関数。素数のとき1を返し、素数でないとき0を返す。
int i;
for(i=3;i<=(int)sqrt((double)a);i+=2){
if(a%i==0)return(0);
}
return(1);
}
各スレッドから書き込むと、
スレッドは並列に働いていますので、
いろいろなタイプが書き込まれてしまいますので、
コンソールへの書き込みはすべてルートスレッドにしてあります。
でも皆さんこのコンソールへアウトプットは、
f1からf4がすべてが終わってからなされるのではなく、
それらが稼働中にも書き込みがおこなれています。
実は、ルートスレッドも含めれば５スレッドプログラミングです。
ルートから起動したスレッドが働いているときそれと並列にルートスレッドも働いています。
といっても
cout<<"5で割ると余りが1のタイプ"<<endl;
for(i=0;i<cn3;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a3[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが2のタイプ"<<endl;
for(i=0;i<cn1;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a1[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが3のタイプ"<<endl;
for(i=0;i<cn4;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a4[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"5で割ると余りが4のタイプ"<<endl;
for(i=0;i<cn2;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a2[i]<<" ";
}
の部分は直列に上から処理されていきますから、
５つが並列に働いているのは
for(i=0;i<cn3;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a3[i]<<" ";
}
とf1、f2、f3、f4です。
f3の処理より
for(i=0;i<cn3;i++){
if(i!=0 && i%10==0)cout<<endl;
cout<<a3[i]<<" ";
}
の方が早く処理されてしまうと、
5で割ると1余るタイプの素数は漏れてしまう可能性があります。
幸いなことに、実験の範囲内（１００００００まで実験）でもそれはありませんでした。
１から１００００００まで素数は６６４５７９個ですが、それを漏れなくカウントしています。
理由は、コンソールへの出力は時間がかかる処理なので、
f3の処理の方が遅れることはないからです。
素数探索大きくなるとかなり時間がかかる気がしますが、
コンソールへの出力はもっと時間が要するわけです。
CPU使用率は、１００００００ぐらいまでの探索ならプログラムを走らせて１００％に達した後すぐに
２５％程度に落ちてしまいます。
これはf1からf4までの処理が終わっていること示します。
f1からf4の4つによってすべての５の倍数を除く奇数が漏れなく重複なく探索されていることを
各関数が担当する奇数を羅列することによって確認してみましょう。
f1：７，１７，２７，３７，４７，５７，・・・
f2：９，１９，２９，３９，４９，５９，・・・
f3：１１，２１，３１，４１，５１，６１，・・・
f4：１３，２３，３３，４３，５３，６３，・・・
合わせると
７，９，１１，１３，１７，１９，２１，２３，２７，２９，３１，３３，３７，３９，４１，４３，・・・
５の倍数は５以外はすべて素数でないわけですから、
はじめから探索する必要はありません。
ですから５の倍数を除く奇数を探索すればよいのですが、
f1からf4の共同作業によって、すべて漏れなく重複なく5の倍数以外の素数が探索されています。
char sh(int a);
については解説済みです。
例えば、１１９が約数であるかはルート１１９以下の奇数すなわち９以下の奇数まで割っていって、
割り切れなければ素数、途中で割り切れてしまえば素数でないと判定すればよいのです。
素数ときは１を返し、素数以外では０を返しますから
if(sh(i)){
a3[cn3]=i;
cn3++;
}
等は素数のときだけ実施されます。
皆さんは
if(sh(i)==1){
a3[cn3]=i;
cn3++;
}
ではないかとお思いになると思いでしょう。
もちろん、これでもよいのです。
では何故、
if(sh(i)){
a3[cn3]=i;
cn3++;
}
でも正常に動くのでしょうか。
実は、sh(i)==1という式は値を持っています。
真のときは１で、偽のときは０です。
素数なら1が返ってきますので、
if(sh(i)){
a3[cn3]=i;
cn3++;
}
は実行され、素数でないときは０が返ってきますから実行されません。
というわけで
if(sh(i)){
a3[cn3]=i;
cn3++;
}
は
if(sh(i)==1){
a3[cn3]=i;
cn3++;
}
と同じになるのです。
皆さん、今回_beginthread(f1, 0, NULL);のピンクのところはお呪いということにしてありましたが、
実はのNULLところで引数を渡すことができます。
ただし、その引数は
void *型です。
_beginthread(f, 0,(void *)1);
_beginthread(f, 0,(void *)2);
などとしてやれば関数を4つも用意することはありません。
例えば、
void f(void *a){ //5で割ると2余るタイプの素数の探索を任務とする関数
int i;
if(a==(void *)1){
for(i=7;i<=N;i+=10){
if(sh(i)){
a1[cn1]=i;
cn1++;
}
}
}
if(a==(void *)2){
for(i=9;i<=N;i+=10){
if(sh(i)){
a1[cn1]=i;
cn1++;
}
}
}
・
・
・
}
としてやればよいのです。皆さん引数を利用して関数を1つにしてみましょう。
第４話へ 第６話へ
