7億ある配列を含んだ計算をしたいのですが、高校の一番良いコンピュータのc言語を使えば計算できますか？

7億ある配列を含んだ計算をしたいのですが、高校の一番良いコンピュータのc言語を使えば計算できますか？
ちなみにその配列は素数列なので計算もやや大変です

No.5 ベストアンサー 回答者： k-841 回答日時： 2017/11/10 14:38

＞ちなみにその配列は素数列なので計算もやや大変です

これって、2から始まって7億番目までの素数を配列に格納する、なんてことをしようと考えているのでしょうか？
もしそうだとすると、何番目かはわかりませんが、結構早い段階で32にビットの限界（符号なしで約42億）を超え、もしかすると64ビットの限界（約1800京）を超える数値になるかもしれません。このため、数値の表現をもっと拡張しないといけないと思います（何ビットが必要なのか想像もつきませんが）。

で、その前提で行くと、例えば各数値を128ビット（16バイト）で表現する場合、7億要素の配列1個のためだけで112億バイト（11.2ギガバイト）のメモリが必要になります。

また計算量については、原始的な方法だと、数値を2ずつ増やしていってこれまでに検出した素数で割り切れるかどうかを全部確認して、最後まで割り切れなかったら素数と認定、みたいなことになるんじゃないかと思いますが、もしそういった演算をするとなると途方もない計算量になります。もしかするともっと速いアルゴリズムがあるかもしれませんけど・・・

この回答へのお礼

このつもりでした。諦めます、ありがとうございます

お礼日時：2017/11/16 09:44

No.4 回答者： izayoimizuki 回答日時： 2017/11/04 12:55

7億要素あるような巨大な配列になりうるデータをファイルから読み込んで計算するという想定で回答します。

7億要素ある巨大な配列になりうるデータの演算を行うにはいくつかの問題を解決する必要が出てきます。

１．配列の大きさが大きすぎてメモリ上に展開できない
コンパイラによって異なるので何とも言えませんがC言語が想定している配列のサイズは精々数十MBです。
一方7億要素の単精度でも2.8GB程になるので、そのままメモリ上に展開はできません。
ですので、1項目ずつ読み込んで計算しては次の項目読み込むといったメモリ上に一度に展開しない工夫が必要になります。

２．演算結果が大きくなりすぎる
例えば1を7億回足しただけで7億になります。
一方でInt32型の最大値が2147483647なので簡単に超えてしまいます。
ですのでGNU Multi-Precision Libraryのような任意精度演算ライブラリが必要になります。

■GNU Multi-Precision Library
https://gmplib.org/

３．演算量が大きすぎる
２とも絡むのですが、ただ7億回足し算をするだけでCPUタイム、メモリからの読み込み、メモリへの書き戻しの時間、ディスクからの読み取り時間を加算するとSSDを使っても2～3分程度必要になります。
掛け算や割り算をすると更に時間がかかります。

加えて、任意精度の四則演算は内部的には多数のInt64型の四則演算と分岐に展開されるため、さらに時間がかかります。

計算結果がInt64型でオーバーフローしない演算についてはGPGPUを活用する、
計算結果がInt64型に収まらなくても計算順序の工夫で収まるようにしてGPGPUを活用するといった工夫をすれば、
最近のパソコンであれば10～20分程度で演算はできるのではないでしょうか。

コンピュータの性能次第という部分はありますが、技術的には可能です。
高速に実行しようとすると実装は大変だとはお思いますが。

No.3 回答者： Tacosan 回答日時： 2017/11/04 11:48

結論を言うと, #2 と同じく「わからない」としかいえない. どのような処理系でどのような計算をするかがわかって, 初めて「計算できるかどうか」が検討できる.

「C で扱える整数の上限」は決まっていませんよ＞#1. 「上限の最低値」なら
int型では 32767
だったり
long int型では 2147483647
だったりしますが, あくまで「最低値」でしかないのでもっと大きな値を扱えるかもしれません.

ちなみに「1個のオブジェクト」の大きさについても, 65535バイトを超えたら動かなくても文句は言えません.

No.2 回答者： don_go 回答日時： 2017/11/04 08:22

どういった「計算」をするかが分からないと回答不可。

配列の内容が素数列と決まっているなら、「計算」の内容
しだいで、配列にする必要が無いかも知れません。
＃高校の一番良いコンピュータ程度では、結果が出るまで
＃数日・数週間以上の時間がかかるかも？

数値の桁数に関しては、倍精度演算、四倍精度演算を利用
できれば問題無し。

No.1 回答者： tatsu99 回答日時： 2017/11/04 07:48

高校の一番良いコンピュータのスペックがどうなっているか不明なので何とも言えませんが、

それ以前にC言語で扱える整数の上限は、
int 型の場合、2,147,483,647
long long int型の場合、9,223,372,036,854,775,807
です。これ以上大きな整数を扱うことはできません。その点は大丈夫でしょうか。