重複なしの乱数発生 を修正し、100〜200までの値を発生する等、初期値を指定した乱数を発生させる例題です（初期値100、個数100での乱数発生）。
エクセルや既存のサイトのCGI等でそのようなことは可能かもしれませんが、5000個、10000個ともなってくるとスクリプトや従来の重複なしの方法では相当に時間がかかってしまうので、コマンドラインツールとして利用することが主な目的になります。
また、Javascript・Perl版も用意しています。
10000個の乱数発生では、Cで作成した場合には0.1秒、Perlで作成した場合には5秒近くと速度は圧倒的に違いますが、CGI等で利用するための参考として。
randtable.cpp
実行結果
Javascript
randtable.pl / Perl
2017年6月17日土曜日
2011年5月14日土曜日
クイックソートによるソート
Ｃ言語の標準関数である qsort() 関数を用いずにクイックソートを行う例です。
入力データは乱数を用いています。
ソートされた結果は0から乱数の最大数までの昇順の数になります。
実行結果
入力データは乱数を用いています。
ソートされた結果は0から乱数の最大数までの昇順の数になります。
実行結果
2011年5月4日水曜日
乱数発生に関する考察
乱数発生に関する考察です。
Numerical Recipes in C, Second Edition (1992)(7. Random Numbers) に記載されていた、乱数を発生するアルゴリズムに若干の疑念を覚えたので検証するための例題を用意しました。
以下の例題では、上記 random() 関数と、srand/rand 関数による乱数発生のアルゴリズムによる乱数発生の比較を行っています。
乱数発生を繰り返し行い、ヒストグラムを作成し、それに要する時間と平均値、標準偏差を計算しています。
実行結果
例題では、0から99までの乱数を発生する計算を 100×1000 回行っていますが、平均値は双方のアルゴリズム共に 1000 となっています。
その標準偏差を比較すると、random() 関数では srand/rand 関数のアルゴリズムよりも標準偏差が大きく、バラつきが多くなっています。
また、計算時間も srand/rand 関数の方が短くなっています。
ヒストグラムは下記のグラフのようになっています。
グラフでは、私が使っていたアルゴリズムの方（青線）が、最小値／最大値の発生率が低く、そのせいでバラつきが大きい結果になっていることが分かります。
これまで普通に使ってきましたが、標準関数を利用するようにしていかないといけないですね。
Numerical Recipes in C, Second Edition (1992)(7. Random Numbers) に記載されていた、乱数を発生するアルゴリズムに若干の疑念を覚えたので検証するための例題を用意しました。
以下の例題では、上記 random() 関数と、srand/rand 関数による乱数発生のアルゴリズムによる乱数発生の比較を行っています。
乱数発生を繰り返し行い、ヒストグラムを作成し、それに要する時間と平均値、標準偏差を計算しています。
実行結果
例題では、0から99までの乱数を発生する計算を 100×1000 回行っていますが、平均値は双方のアルゴリズム共に 1000 となっています。
その標準偏差を比較すると、random() 関数では srand/rand 関数のアルゴリズムよりも標準偏差が大きく、バラつきが多くなっています。
また、計算時間も srand/rand 関数の方が短くなっています。
ヒストグラムは下記のグラフのようになっています。
グラフでは、私が使っていたアルゴリズムの方（青線）が、最小値／最大値の発生率が低く、そのせいでバラつきが大きい結果になっていることが分かります。
これまで普通に使ってきましたが、標準関数を利用するようにしていかないといけないですね。
以下、同様に Numerical Recipes in C に掲載されていた乱数発生の例です。
上記と同様にヒストグラムを作成した結果、最大最小値の発生率が低くバラつきが大きい結果になりますので、標準関数を利用した方が良い結果になります。
2011年4月9日土曜日
四面体の体積を求める／指定した点が四面体の中に含まれるかを確認する
三次元空間内の４点 Pi (i=1,2,3,4) を頂点とする四面体の体積を求める例題です。
また、指定した点 Q がその四面体の中に存在するかを確認する方法についても考えています。
まず、四面体の体積に関する計算方法ですが、
CASIO の keisan の HP : http://keisan.casio.jp/
が役に立ちました。
トップページから空間幾何のリンクへ飛び、その中に四面体の体積の計算方法が記載されています。
点 A,B,C,P に対し、
また、空間幾何のページを参考に、点（P）と平面（三角形ABC）の距離を求め、
両者の計算が一致することを確認しています。
四面体の中に点 Q が存在するかどうかに関しては、
文章だけでは確認しずらいと思いますので、実際に図を書いてみて確認して頂ければと思います。
ソース等をまとめたもの：DL
3dvector.h
3dvector.cpp
tetrahedron.cpp 実行結果
また、指定した点 Q がその四面体の中に存在するかを確認する方法についても考えています。
まず、四面体の体積に関する計算方法ですが、
CASIO の keisan の HP : http://keisan.casio.jp/
が役に立ちました。
トップページから空間幾何のリンクへ飛び、その中に四面体の体積の計算方法が記載されています。
点 A,B,C,P に対し、
A→B : b ベクトルという形で計算されます。
A→C : c ベクトル
A→P : p ベクトル
というベクトルを定義し、
体積 V = (p・(b×c))/6 （・は内積、×は外積）
また、空間幾何のページを参考に、点（P）と平面（三角形ABC）の距離を求め、
体積 V = (底面積×高さ)/3により計算しています。
により計算しています。
底面積（三角形ABCの面積）は、ヘロンの公式により、
B→C : a ベクトル
C→A : b ベクトル
A→B : c ベクトル
s = (|a|+|b|+|c|) / 2
底面積 S = sqrt(s*(s-a)*(s-b)*(s-c))
両者の計算が一致することを確認しています。
四面体の中に点 Q が存在するかどうかに関しては、
1. 点 Q と他4つの点 Pi を頂点とする4つの四面体の体積を求めるという確認方法をとっています。
2. 元の四面体の体積と4つの四面体の体積が一致すれば、点 Q が四面体の内部に存在することになる
文章だけでは確認しずらいと思いますので、実際に図を書いてみて確認して頂ければと思います。
ソース等をまとめたもの：DL
3dvector.h
3dvector.cpp
tetrahedron.cpp 実行結果
2011年4月6日水曜日
重複なしの乱数発生（クラス化）
重複なしの乱数を発生するための例題です。
前回は、配列に乱数を格納するというものでしたが、今回は乱数を発生するための仕組みをクラス化し、必要に応じて１つ１つの乱数を取得するというものに変更しています。
必要な乱数の数以上の乱数を要求した場合には、-1 が返されるようになっています。
実行結果
前回は、配列に乱数を格納するというものでしたが、今回は乱数を発生するための仕組みをクラス化し、必要に応じて１つ１つの乱数を取得するというものに変更しています。
必要な乱数の数以上の乱数を要求した場合には、-1 が返されるようになっています。
実行結果
重複なしの乱数発生
重複なしの乱数を発生するための例題です。
重複なしの乱数発生について、本来ならば一度発生した乱数を配列に登録していき、すでに登録されている乱数が発生されればその乱数は破棄する等の手順をとりますが、そうすると、必要な乱数の数よりも多い計算回数を必要とします。
そこで、乱数発生の数を必要な数と同じにし、判定の手順も必要としないアルゴリズムを考えてみました。
下記の例題にて、
int round_tbl[RAND_N]; // 変換テーブル
は、発生した乱数を使われていない値に変換するためのテーブルであり、必要な乱数の数(RAND_N)を次第に減らしていくために利用しています。
全ての値が発生すれば、必要な乱数の数は 0 になります。
このアルゴリズムでは、変換テーブル用の配列の準備が必要となります（その分のメモリが必要）。
乱数を発生する数は、必要な乱数の数と同じであり、不必要な乱数を破棄することはありませんので、高速なアルゴリズムになります。
例題では、通常のアルゴリズムと比較した時間も表示しています。
10000 の数を発生する際には16倍程度高速になっています。 図解begin
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜２｜３｜・・｜ｎ−１｜ → n個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n の乱数を発生 val=2 → 配列から 2番目の値を抜き出し、抜けた分を詰める
＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜３｜４｜・｜ｎ−１｜ → n-1個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n-1 の乱数を発生し、上記と同じように発した値の配列を抜き出し、抜けた分を詰める
以下、配列がなくなるまで繰り返す
図解end
重複なしの乱数発生について、本来ならば一度発生した乱数を配列に登録していき、すでに登録されている乱数が発生されればその乱数は破棄する等の手順をとりますが、そうすると、必要な乱数の数よりも多い計算回数を必要とします。
そこで、乱数発生の数を必要な数と同じにし、判定の手順も必要としないアルゴリズムを考えてみました。
下記の例題にて、
int round_tbl[RAND_N]; // 変換テーブル
は、発生した乱数を使われていない値に変換するためのテーブルであり、必要な乱数の数(RAND_N)を次第に減らしていくために利用しています。
全ての値が発生すれば、必要な乱数の数は 0 になります。
このアルゴリズムでは、変換テーブル用の配列の準備が必要となります（その分のメモリが必要）。
乱数を発生する数は、必要な乱数の数と同じであり、不必要な乱数を破棄することはありませんので、高速なアルゴリズムになります。
例題では、通常のアルゴリズムと比較した時間も表示しています。
10000 の数を発生する際には16倍程度高速になっています。 図解begin
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜２｜３｜・・｜ｎ−１｜ → n個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n の乱数を発生 val=2 → 配列から 2番目の値を抜き出し、抜けた分を詰める
＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜３｜４｜・｜ｎ−１｜ → n-1個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n-1 の乱数を発生し、上記と同じように発した値の配列を抜き出し、抜けた分を詰める
以下、配列がなくなるまで繰り返す
図解end
クラス化し、必要な値だけ取り出すように変更した例は こちら
実行結果
2011年3月22日火曜日
CRC の計算
ランダムに生成された数値データに対し、誤りチェックのためのCRCを計算する例題です。
CRCでは、
（１）送信すべきビット列を２進数とみなし、
（２）検査用の２進数ビット列で割り算し、
（３）最後はあまりを出す。
という手順を取ります。
相手側には、送信すべきビット列と余りを送ります。
受信側でも同じ割り算を行い、余りが一致すれば正しく受信できたことになります。
（割り算と言っても「桁借り」の無い特殊な割り算です）
多項式：２進ビット列のビットは上に行くほど桁の重みが大きい。
そこで、重みを考慮した多項式表示（足し算の形）で表現します。
生成多項式：検査用のビット列（割る数）も同じように多項式の形で表します。
（余りを生成するもとの式という意味で）生成多項式と呼びます。
例題では、多項式を用い直接計算する方式と（calculateCRC16）と、余剰テーブルを用いて高速化を図った方式（calculateCRC16t/calculateCRC32t）の２種類の計算を行っていますが、それぞれの結果は同じです。
配列のサイズが大きくなると計算量も大きくなるため、このような工夫が取られています。
また、検査用ビット数を16/32ビットとした計算の２種類用意しています。
生成された配列にCRCを付与した配列に対し、再度CRCを計算（CRCデータも含め）するとCRCが0になることを確認することにより、CRCの計算結果が正しいことが確認できます。
CRCを配列に格納する場合のバイトオーダーは、ビッグエンディアンで格納する必要があります。
ネットワークでやり取りされるデータは、通常ビッグエンディアンになりますので、ホスト内のバイトオーダーとは異なる点に注意が必要です。
例題では、htons/htonl 関数により、16/32 ビットのデータをビッグエンディアンに変更し格納しています。
ソース等をまとめたもの：DL
crc.h
crc.cpp
crcTest.cpp
実行結果
CRCでは、
（１）送信すべきビット列を２進数とみなし、
（２）検査用の２進数ビット列で割り算し、
（３）最後はあまりを出す。
という手順を取ります。
相手側には、送信すべきビット列と余りを送ります。
受信側でも同じ割り算を行い、余りが一致すれば正しく受信できたことになります。
（割り算と言っても「桁借り」の無い特殊な割り算です）
多項式：２進ビット列のビットは上に行くほど桁の重みが大きい。
そこで、重みを考慮した多項式表示（足し算の形）で表現します。
（例）１０１１１００１１１００１０１１ (16bit)これが（送信すべきビット列の）多項式です。
最上位は2^15、最下位は2^0=1です。
すると上のビット列は
x^15 + x^13 + x^12 + x^11 + x^8 + x^7 + x^6 + x^3 + x + 1 (x=2)
で表せます。
生成多項式：検査用のビット列（割る数）も同じように多項式の形で表します。
（余りを生成するもとの式という意味で）生成多項式と呼びます。
例題では、多項式を用い直接計算する方式と（calculateCRC16）と、余剰テーブルを用いて高速化を図った方式（calculateCRC16t/calculateCRC32t）の２種類の計算を行っていますが、それぞれの結果は同じです。
配列のサイズが大きくなると計算量も大きくなるため、このような工夫が取られています。
また、検査用ビット数を16/32ビットとした計算の２種類用意しています。
生成された配列にCRCを付与した配列に対し、再度CRCを計算（CRCデータも含め）するとCRCが0になることを確認することにより、CRCの計算結果が正しいことが確認できます。
CRCを配列に格納する場合のバイトオーダーは、ビッグエンディアンで格納する必要があります。
ネットワークでやり取りされるデータは、通常ビッグエンディアンになりますので、ホスト内のバイトオーダーとは異なる点に注意が必要です。
例題では、htons/htonl 関数により、16/32 ビットのデータをビッグエンディアンに変更し格納しています。
ソース等をまとめたもの：DL
crc.h
crc.cpp
crcTest.cpp
実行結果
2011年3月21日月曜日
XOR和によるチェックサムの計算
データを送受信する際の誤り検出方法の一つであるチェックサムを計算し、配列に格納する例題です。
誤り検出の方法としては、他にもCRCやMD5等があります（SHA-1）。
今回のチェックサムではXOR和を用いており、単純な加算・減算方式、パリティ方式、CRC方式等々、様々な方法があります。
送信側、受信側のアルゴリズムが一致しないと、正しいデータ転送を行えませんので、どの方式が利用されているか確認の上、ご利用下さい。
例題では、ランダムに発生した数値データに対し、チェックサムを計算し、その値を格納後、通信の終りを示す EOT(0x04)/0 を配列に格納しています。
（このような形はあくまで例題であり、私が使っていた通信機器のデータ格納方式がそうだったというだけです。汎用な形式ではありません。）
実行結果
誤り検出の方法としては、他にもCRCやMD5等があります（SHA-1）。
今回のチェックサムではXOR和を用いており、単純な加算・減算方式、パリティ方式、CRC方式等々、様々な方法があります。
送信側、受信側のアルゴリズムが一致しないと、正しいデータ転送を行えませんので、どの方式が利用されているか確認の上、ご利用下さい。
例題では、ランダムに発生した数値データに対し、チェックサムを計算し、その値を格納後、通信の終りを示す EOT(0x04)/0 を配列に格納しています。
（このような形はあくまで例題であり、私が使っていた通信機器のデータ格納方式がそうだったというだけです。汎用な形式ではありません。）
実行結果
2011年3月20日日曜日
2011年3月13日日曜日
乱数発生例
乱数を発生する例題です。
[0..max] の実数値を発生しています。
実数における一様乱数として最もよく用いられるのは 0..1 の範囲の一様乱数ですが、その乱数に max の値を掛ければ 0..max の区間の実数値を得ることができます。
rand() 関数は、0..RAND_MAX（コンパイラ等により異なる）の範囲の整数を発生するため、RAND_MAX 個の乱数を max の範囲に分散させることになり、乱数ごとの間隔は max/RAND_MAX になります。
OSX/gcc の RAND_MAX は以下の実行例のように、2147483647 となっています。
乱数を発生させるためにはシード値を設定しなければなりませんが、同じシード値を利用すると毎回同じ乱数列が取得されます（ソース上では、idum 変数）。
実行結果
[0..max] の実数値を発生しています。
実数における一様乱数として最もよく用いられるのは 0..1 の範囲の一様乱数ですが、その乱数に max の値を掛ければ 0..max の区間の実数値を得ることができます。
rand() 関数は、0..RAND_MAX（コンパイラ等により異なる）の範囲の整数を発生するため、RAND_MAX 個の乱数を max の範囲に分散させることになり、乱数ごとの間隔は max/RAND_MAX になります。
OSX/gcc の RAND_MAX は以下の実行例のように、2147483647 となっています。
乱数を発生させるためにはシード値を設定しなければなりませんが、同じシード値を利用すると毎回同じ乱数列が取得されます（ソース上では、idum 変数）。
実行結果
登録:
投稿 (Atom)
投稿
