math compiler2017年05月15日 16:41

math compiler


C言語で、完全数を求めるプログラムを動かしたことは、既に書いた。

(速さは正義)
http://kfujito2.asablo.jp/blog/2017/05/10/8552087

しかし、これでは満足できない。

(8インチも1703へ)
http://kfujito2.asablo.jp/blog/2017/05/12/8555194

「完全数を求めるのに、エラトステネスのふるいを応用して、高速に計算するプログラムを見つけた。
(完全数)
http://www.saoyagi2.net/integer/perfect.html

このソースを読めない。

勉強不足だ。

で、とりあえず、エラトステネスのふるいを実装しているプログラムを探す。

(第 06 章 配列と文字列)
http://www.is.titech.ac.jp/compview/clang/chap6.html

このプログラム(つーか、演習問題)では、どうしてもwhileの外に出られなかったし、jとか怪しかったので、独自に書き直す。

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

int main() {
int i, j, n;
n = 1000;
/* 各整数が素数かどうかを記録する配列
0~nまでの値を管理するためn+1の要素の配列を定義している */
int flag[n + 1];

/* 最初はすべて素数とみなす
(フラグの値で)1は素数 0は素数でないと定義する */
for (i = 0; i <= n; i = i + 1) {
flag[i] = 1;
}

/* 0, 1は素数ではない */
flag[0] = 0;
flag[1] = 0;
/*ふるいはnの平方根まで*/
for (i = 0; i <= sqrt(n); i = i + 1) {
/* 1になっている最初の値を探す */
if (flag[i] == 1) {
/* iは素数のため素数の倍数の値をすべて0にする */
for (j = 2; (i * j) <= n; j = j + 1){
flag[i * j] = 0;
}
}
}

/* この時点で1となっている要素は素数である */
for (i = 0; i <= n; i = i + 1) {
if (flag[i] == 1){
printf("%d ", i);
}
}
printf("\n");

return 0;
}

突っ込みどころはあるんだろうが、とりあえず動くところまで持ってきた。

出力の整形とかは、全く考えていない。

問題だったのはコンパイルだ。

gcc -o hoge hoge.c

これだと、sqrtの引数に変数を入れるとコンパイルエラーになる。

自然数を引数にするとエラーを吐くとか、いろいろ調べたが、どうやらmathを読み込んでくる時にlmというオプションを付ける必要があるということが分かった。

しかもだ、ウブンツの場合(バージョンにもよるようですが)、末尾に付ける必要がある。

gcc -o hoge hoge.c -lm

これで、ようやく探索範囲の最大値を変数にぶち込んで、ふるいを掛けることが出来るようになった。

(C言語のコンパイルについて)
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12108453907

「試してみました。
ubuntu
$ cc -v
gcc バージョン 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
×cc -lm hoge.c
○cc hoge.c -lm」

ちなみに、浮沈子のBUWの現在の環境では、gccのバージョンは5.4.0、ウブンツは16.04.4になっている。

Cのコード自体のミスもあって、見つけ出すのに苦労したが、なんとかmath使ってコンパイラーを通すことに成功した。

マスかいて、疲労こんぱい(らー)・・・。

子供は、分かんなくていいです!。

まあ、どうでもいいんですが。

さて、この先は、いよいよ本丸の完全数の探索に、この仕掛けを応用するという話になる。

先が思いやられるな・・・。

Gの威力2017年05月15日 20:29

Gの威力
Gの威力


ブログで字下げのやり方が分からず、レストランで作ったエラトステネスのふるいを、自宅に帰ってきてからブログのページからBUWにコピペする。

当然、字下げとかされない。

で、うまいやり方があったはずだと、ネットをググると、こんなページが・・・。

([vim] 自動インデント 自動整頓)
http://blog.majide.com/2006/01/vim-auto-indent/

「先頭へ移動し、
=G
「:」は不要。」

うーん、神だ・・・。

これがホントの神業だな。

構文解析しながら、1行ずつタブキー押してたのは、一体何だったのか?。

人間に出来ることは、間違いなく機械でも可能だ。

少なくとも、浮沈子よりは確かだな。

今日は、さんざん苦労したsqrt関数を使わずに平方根を求めるプログラムを探す。

自分で考えて書くんじゃない。

人様の知恵をお借りして、勉強させていただく。

まあ、パクリともいうがな。

(平方根のアルゴリズム)
https://cpplover.blogspot.jp/2010/11/blog-post_20.html

パクろうとしたんだが、C++なのでめげる。

アルゴリズムとか、さっぱりだな。

コードをパクって、動かすのがせいぜいだ。

ぱっと、コピペできるコードが見当たらない。

仕方ないので、このページのエクセルによる計算を試みる。

(√2 の話:その20:バビロニアの平方根)
http://yamada-kuebiko.cocolog-nifty.com/blog/2015/02/post-ed0c.html

「この際、誰でも気軽に試してみられるようにエクセルのセルに式を書き込むやり方で実験してみましょう。」

ビンボーな浮沈子はエクセルなど買えないので、オープンオフィスのカルクを開く。

書かれたとおりに計算させると、意外に早く収束する。

なんとか、Cで実装したいな・・・。