random

田舎の人に春が来て嬉しいのは、雪がもう降らないってのがある。それとオイラー的には 楽しみにしてる、ふきのとう が食べられる事。

去年までは、散歩の途中にある耕作放棄地で採取出来たんだけど、今年は無理。 重機が入って、雪をかき分け、地面を掘り返し、そのうちに家の土台の型が作られ、 セメントが流し込まれちゃったから。

地面も凍るような厳寒期にセメントなんて打って大丈夫か? 高野豆腐や寒中寒天みたいに 水分が凍って、スカスカのセメントにならないのか? まてまて、セメントは硬化する時 自家発熱するから大丈夫でしょう。まあ、オイラーにとっては、菜園を破壊したにっくき 施工主と思ってるから、どうでもいいけどね。

そんなある日、その工事現場の近くで測量をやってるおじさん2人組に出会った。また、別棟 でも建てるのか。そんなに新築したって入る人居るんか? 町の広報で、空き家バンクの 案内が有ったけど、誰も借り手がいないようだぞ。新築するって事は、景気が良い証拠なんです かね?

で、測量って一口で言うけど、どんな事やるの? 測量計を使ってるおじさんに聞いてみた。 カメラのお化けみたいなのに、キーパッドが付いていた。遠くの方では、相方が細い棒を 持って左右に動いてた。なんでも、距離を測っているとの事。後は、内蔵コンピュータで 答え一発らしい。

あれ? カメラの頭にアンテナが付いているぞ。このアンテナってトランシーバーで相手方と 話でもするんですかって聞いてみたぞ。そしたら、一人で測量が出来るように、リモート コントロール出来るようになってるとか。遠方で動いているおじさんが、コントロールする んだな。凄い進歩だ事。

勿論、レーザー距離計だから、遠方のおじさんは、鏡を持ってうろうろするんだな。ああ、鏡 じゃなくて、プリズムか。昔、アポロが月面に置いてきたプリズムと一緒で、どんな角度で 光が入射しても、同方向へ反射するって、あれだな。

で、この測量計って幾らするのってゲスな質問をしてみた。軽くクラウンが買えますよとの 事。あのおじさんの年代は、高い車イコール、クラウンなのね。決してレクサスではあり ませんでした。

家に帰って、測量の事を少々調べてみた。

三角測量

それから、現場で使われていた測量器もメーカー名を記憶してたんで、簡単に同定出来た。

イメージングステーション IS3

なかなか面白いな。

random

前回は、パスワードの発生をunixのコマンドだけで実行出来ないかってやった。

その為には、どうしても乱数の発生が必要。再現性のある乱数列って事でこだわったら ああいう形なった。普通rubyとかpythonを使って書くでしょ、その方がずっと自由度も あるし楽だからね。

まあ、それはそうなんだけど、特定言語に縛られたく無いってのが根本にある。でも、 そんな原始的な生活を捨てて、近代的になったら。

って事で、pythonかな。 記者が試したディープラーニング、当然だが甘くはないでも、絶賛してるしね。でも、pythonコードを書くと言うと ちょいと構えちゃうな。いい加減に書くと直ぐに怒り出すんだもん。

それに、パイプに組み込む部品としては、ちと面倒なしきたりが必要。標準入力から読み込む にも、何やらをimportしなきゃならん。 標準入力から文字列を取得したい とか、 ファイルを読むみたいにね。

で、問題は、再現性のある乱数だな。種を与えればいいんだな。その種を秘密の数値に すればおk。

In [1]: import random

In [2]: random.   ## TABで補完した
         random.betavariate     random.normalvariate   random.setstate
         random.BPF             random.NV_MAGICCONST   random.SG_MAGICCONST
         random.choice          random.paretovariate   random.shuffle
         random.expovariate     random.randint         random.SystemRandom
         random.gammavariate    random.Random          random.triangular
         random.gauss           random.random          random.TWOPI
         random.getrandbits     random.randrange       random.uniform
         random.getstate        random.RECIP_BPF       random.vonmisesvariate
         random.LOG4            random.sample          random.weibullvariate
         random.lognormvariate  random.seed

randomと一口に言っても、色々あるなあ。取り合えず種だな。そして一番凡庸なrandom() でいいのかな。

In [2]: random.seed(2469634)

In [3]: random.random()
Out[3]: 0.5151391486984227

うん、取り合えず良かったみたい。種は語呂合わせで、西向く武蔵を選んでみた。 こういう語呂合わせのストックをたくさん持ってると、重宝するぞ。

『からまん棒』とかの名前を発明した方が書いた、ネーミング全史という本が面白かった。 勿論、語呂合わせの極意なんかも出て来てた。名前重要のmatzさんご推薦かな。

random.sampleって、サンプルを提供してくれると思っていたら、サンプリングなのね。 消費者を惑わす名前付けは、いかがなものかと。正しい使い方を例示しとく。

In [1]: import random

In [2]: random.sample("abcdefghijk", 4)
Out[2]: ['c', 'd', 'g', 'k']

In [3]: random.sample("abcdefghijk", 4)
Out[3]: ['j', 'f', 'd', 'a']

こういう便利な物が有ると、つい使ってみたくなる。そこで、前回出てきた、パスワード発生器を、書いてみた。ちょいと悩んだのが、記号に何を使ったら良いかって事。

さくらさんとこや、 YAHOOさんやら、 どうせ記号を混ぜるならとかを参考にする。使える記号を限定するのは、エスケープをさぼりたいって 要求よりも、サポセンに文句を言われたくないためらしい。 悩ましい問題だな。取り合えず、開陳しとく。

from string import ascii_lowercase, ascii_uppercase, digits
import random
import sys

random.seed(int(sys.argv[1]))
sel = random.sample(digits, 4) + \
      random.sample('@.,_#%+=;:~', 4) + \
      random.sample(ascii_uppercase, 4) + \
      random.sample(ascii_lowercase, 4)
random.shuffle(sel)
print(''.join(sel[:10]))

下記は使用例。

sakae@debian:~/r$ python pg.py 123
@#+MefkRr4
sakae@debian:~/r$ python pg.py 123
@#+MefkRr4
sakae@debian:~/r$ python pg.py 456
D@ow7YP.K;

Pythonの乱数発生器の元は、メルセンヌ乱数発生器らしい。どんなものかちょい見してみる。

Mersenne Twist pseudorandom number generator

Mersenne Twister Home Page

あなたの使っている乱数、大丈夫?

間違いだらけの疑似乱数選び

HDLによる乱数発生回路 メルセンヌ・ツイスタの設計と実装

Rubyで使用されている乱数の均等分布について(メルセンヌ・ツイスタ)

C言語による乱数生成

この発生器の特徴として、乱数列の発生周期が非常に長いというのがある。上の説明でも 言及されたけど、2の19937乗とか。それって、どんだけーーー? 真面目に桁数を 調べてみた。

In [4]: len(str(2**19937))
Out[4]: 6002
sakae@debian:/tmp$ echo '2^19937' | bc | head -n 1
43154247973881626480552355163379198390539350432267115051652505414033\

4の下に0が6000個も続く巨大数。どんなに高速なコンピュータを使っても、1周したねって 確認は出来ない。桁数は確かに、こうやって出て来るけど、到達は絶対に無理。こんなのを 考えちゃうんだから、大したものだな。

ruby

で、Pythonの次はrubyだな。 何の積りかOpenBSDに入っていたので、勇気256倍。さっそうと乱数事情を調査。

[ob: 2.3]$ ruby -v
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-openbsd]

そろそろ賞味期限切れかな。自前でコンパイルすると時間がかかるからなあ。まあいいや、 マニュアルを見ておく。

class Random

module SecureRandom

再現性のある乱数と無い乱数が有るとな。再現性の有る乱数列は、やはりメルセンヌ乱数を採用してた。暗号に使うには再現性の無いやつを使わないと いけないという事で、ライブラリィーも分かれている。安全な方のソースをlibの下に 潜って見る。

module SecureRandom
  if defined?(OpenSSL::Random) && /mswin|mingw/ !~ RUBY_PLATFORM
    def self.gen_random(n)
      @pid = 0 unless defined?(@pid)
      pid = $$
      unless @pid == pid
        now = Process.clock_gettime(Process::CLOCK_REALTIME, :nanosecond)
        ary = [now, @pid, pid]
        OpenSSL::Random.random_add(ary.join("").to_s, 0.0)
        seed = Random.raw_seed(16)
        if (seed)
          OpenSSL::Random.random_add(seed, 16)
        end
        @pid = pid
      end
      return OpenSSL::Random.random_bytes(n)
    end

元ねたは、やっぱりOpenSSLに求めているんだな。前回やったオイラーの見立ては正しかった って事だ。ほっとしたぞ。

つらつらとソースを見てると、自前のbase64が定義されてて、再発明の言い訳が書いてあったぞ。と、書いていて、いくら何でもrubyの人達が勝手な定義をするはずは無い。世界規格が有るはず。

世界規格と言えば、いわずと知れたRFC。BASE64でサーチしたら、BASE16,BASE32,BASE64を世界に向けて提案してる、RFC4648が引っかかってきた。ここにURL安全なBASE64が定義されてた。s#+/#-_# ですってさ。

  # By default, padding is not generated because "=" may be used as a URL delim\
iter.
  #
  # The result may contain A-Z, a-z, 0-9, "-" and "_".
  # "=" is also used if _padding_ is true.

BASE64ってのは、3バイトを単位として、それを4文字の英数字と記号に置き換える方法。置き換えた時に、4バイトに満たない場合は、= を適当に入れて、4文字の塊にする。

   BASE64("") = ""
   BASE64("f") = "Zg=="
   BASE64("fo") = "Zm8="
   BASE64("foo") = "Zm9v"
   BASE64("foob") = "Zm9vYg=="

ふむふむ、記号に意味を込めるってのは、古くはemacsの時代から、インターネット時代では、 イコールが大事な用途に使われるんで、それを避ける。URL安全で記号を変えるとな。 勝手に=が省略されちゃった場合、察してくださいって言う方針なんだな。今や、メールも Webに置き換えられちゃった現実があるから、当たり前に察しないといけないんだな。 メールの文字エンコードもutf-8が、当たり前になっちゃったからなあ。時代は変わる。

やや、web繋がりで、uuidなんてのも有るな。これもJavaの時代(こう書くと、既にJavaは オワンコを実感出来る)に、パッケージ名のユニークさを出すために、サイト名を逆に綴ると いう発明があった。

今は、ネット上でユニークと言うと、uuid使えか。RFC4122になってるとコメントして あった。こういうのに出会うから、ソースは覗いてみるものだな。

RFC4122 日本語訳

rubyを見ててついでにpythonってのは、混ぜるな危険という内なる警告を聞く思いだけど、 21.20. uuid — RFC 4122 に準拠した UUID オブジェクト(Python)説明が有った。それから、勿論pythonにもopensslのパッケージは有るよ。pipで入れるのかな。rubyでは標準と言う事からすると、ちょっとスタンスが違うな。

uuid何処かで見たな。

[sakae@fedora ~]$ cat /etc/fstab
  :
UUID=16fbc26b-bb64-4a17-b5d6-8bb0d25aaf57 /boot    ext4    defaults     1 2

これって、世界に一つだけのdiskって主張なんだな。

octave

最近使っていたoctaveの乱数発生器はどうかな?

'rand' is a built-in function from the file libinterp/corefcn/rand.cc

 -- Built-in Function:  rand (N)
 -- Built-in Function:  rand (M, N, ...)
 -- Built-in Function:  rand ([M N ...])
 -- Built-in Function: V = rand ("state")
 -- Built-in Function:  rand ("state", V)
 -- Built-in Function:  rand ("state", "reset")
 -- Built-in Function: V = rand ("seed")
 -- Built-in Function:  rand ("seed", V)
 -- Built-in Function:  rand ("seed", "reset")
 -- Built-in Function:  rand (..., "single")
 -- Built-in Function:  rand (..., "double")
     Return a matrix with random elements uniformly distributed on the
     interval (0, 1).

     To compute the pseudo-random sequence, `rand' uses the Mersenne
     Twister with a period of 2^19937-1 (See M. Matsumoto and T.
     Nishimura, `Mersenne Twister: A 623-dimensionally equidistributed
     uniform pseudorandom number generator', ACM Trans. on Modeling and
     Computer Simulation Vol. 8, No. 1, pp. 3-30, January 1998,

なる程、初期値の設定とか出来るようになってて、趣味レーションにどうぞってスタンスか。

gauche

FreeBSDに入れていた。説明書によるとやはり使われていた。これを核にしてポータブルな ランダムモジュール srfi-27を提供してるんで、普段はそちらを使ってくださいとの事。

12.25 math.mt-random - Mersenne Twister乱数発生器

ちょっと試運転。発生器を作る時に、種で初期化出来るのね。また、任意の時点で Function: mt-random-set-seed! mt seed を使って初期化出来るとな。 更に嬉しいのは、途中で発生器の状態を保存しておいて、後でそれをリストア出来るとな。 これって、継続だな。

gosh> (use math.mt-random)
gosh> (define m (make <mersenne-twister> :seed (sys-time)))
m
gosh> (mt-random-real m)
0.18355394150994875
gosh> (mt-random-real m)
0.12102872145633181

ソースは、Gauche-0.9.5/ext/mt-random/ に、gauche化されたC語のソースと、取り巻きの scmファイルが置いてある。

/* initializes mt[N] with a seed */
void Scm_MTInitByUI(ScmMersenneTwister *mt, unsigned long s)
{
    int mti;
    mt->mt[0]= s & 0xffffffffUL;
    for (mti=1; mti<N; mti++) {
        mt->mt[mti] =
            (1812433253UL * (mt->mt[mti-1] ^ (mt->mt[mti-1] >> 30)) + mti);
        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
        /* In the previous versions, MSBs of the seed affect   */
        /* only MSBs of the array mt[].                        */
        /* 2002/01/09 modified by Makoto Matsumoto             */
        mt->mt[mti] &= 0xffffffffUL;
        /* for >32 bit machines */
    }
    mt->mti = mti;
}

使うメモリエリア(Nは624)を、種のsを元に初期化してる。種はどんなに大きな数値を与えても、下位の32Bitが使われる。初期化と言っても、Knuth先生の乱数発生器で、疑似乱数を 書いている。よって、幾ら長い周期の乱数を発生出来ると言っても、列の種類は、2の32乗 になる。

それでは困ると言う人向けに、Knuth先生を無視して、自前の乱数を初期値とメモリーエリアを 埋められるようになってるぞ。

scheme

sakae@debian:/tmp$ scheme
Chez Scheme Version 9.4
Copyright 1984-2016 Cisco Systems, Inc.

--------------------------------------------------------------------------------
random       random-seed
--------------------------------------------------------------------------------
> (random-seed 4649893)
> (random 1000)
382
> (random 1.0)
0.9751775769274795

やはりrandomで補完してみた。こちらは、すっきりしてますねぇ。種と発生しかない。上限を整数か浮動小数点かで指定 するんだな。この方が目移りしなくていいかも。 引数無しで、random-seed を呼ぶと、現在の種値を返してくる。こういう仕様もスマートだな。

所で、種に選んだ数値。京都の病院のドンが 口走ったとか、しないとか。(そんなの堂々と医療倫理って言えばよい)8930184ってはっきり 言うのが法治国家の住民の務めです。権力は決して放置しないぞと、ニュースになる訳だ。 ああ、そうそう、線路内に入って写真を撮ってた(元)アイドルが挙げられましたなあ。 これ幸いとばかり、広告されてましたよ。権力は無料で広告を打った訳だ。内部では、経費 節約したでしょうって事で、表彰状が出てたりして。

で、このschemeはどんな乱数発生器が組み込まれているのだろう? ソースが残っている はずなんで、探ってみるか。

ChezScheme-9.4/c/prim5.cに出てた。ちょいと心配な方式だな。(偉そうに言うな)

/* the random formula is based on Knuth.  It returns a random fixnum
 * between 0 and n-1.
 */

static ptr s_flrandom(x) ptr x; {
    ptr tc = get_thread_context();
    U32 t1, t2, t3, t4;

    t1 = RANDOMSEED(tc) = RANDOMSEED(tc) * 72931 + 90763387;
    t2 = RANDOMSEED(tc) = RANDOMSEED(tc) * 72931 + 90763387;
    t3 = RANDOMSEED(tc) = RANDOMSEED(tc) * 72931 + 90763387;
    t4 = RANDOMSEED(tc) = RANDOMSEED(tc) * 72931 + 90763387;
    return Sflonum(S_random_double(t1, t2, t3, t4, FLODAT(x)));
}

static void s_set_random_seed(x) U32 x; {
    ptr tc = get_thread_context();
    RANDOMSEED(tc) = x;
}

もう一つ定義されてたけど、すっきり版の方を載せてみた。

go

最近、余り出番が無いけど、goでぐぐる様の御意向を伺ってみるかな。乱数ルーチンは src/math/rand/に有るようだ。 使い方の例がexmpleとして有ったぞ。


func Example_rand() {
        // Create and seed the generator.
        // Typically a non-fixed seed should be used, such as time.Now().UnixNano().
        // Using a fixed seed will produce the same output on every run.
        r := rand.New(rand.NewSource(99))

        // The tabwriter here helps us generate aligned output.
        w := tabwriter.NewWriter(os.Stdout, 1, 1, 1, ' ', 0)
        defer w.Flush()
        show := func(name string, v1, v2, v3 interface{}) {
                fmt.Fprintf(w, "%s\t%v\t%v\t%v\n", name, v1, v2, v3)
        }

        // Float32 and Float64 values are in [0, 1).
        show("Float32", r.Float32(), r.Float32(), r.Float32())
        show("Float64", r.Float64(), r.Float64(), r.Float64())

複数の乱数発生器を簡単に定義して使えるとな。ドキュメントには、乱数発生方式が明記 して無かったぞ。って事は、将来的に、乱数発生器はぐぐる様から提供頂くように変更 されても、文句を言えない。

だから、この手のものは、安全じゃない。上で見たように、pythonもrubyもメルセンヌ乱数を 使っているけど、ずっと使い続ける保証は無い。

よって、オイラーがお試しで書いたパスワード発生器は、実用しちゃだめだぞ。 せいぜい使っていいのは、機械学習でパソコン(GPU)を唸らせるぐらいにしておけ。

111の入力に対して、@#+MefkRr4 が得られました。456の入力に対して、D@ow7YP.K; が 得られました。こういうのを教師付き機械学習させたら、893って入力に対して予想出来るはず。 (賢ければね)

ああ、馬鹿な事を考えちゃった。取り合えず現在のgoの乱数発生はどうやってるか、調べて みると、 rng.go が、ねた元みたいだ。特に発生器の名前は無いようだ。(だれか、かっこいい名前を つけてやれ。それで、世間に認知されるんだから、って、ネーミング本に書いてあった)

漸化式が、ちらっとコメントに有った。

// seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1)

これを使って、鍛えたテーブルを元に、読み出し・更新していくんだな。

Card

面白い記事が出てたので、掲載しておく。

架空のdカード プリペイドを作成してみよう!(帰納編)

架空のdカード プリペイドを作成してみよう!(演繹編)

番号の付け方って、Macアドレスのそれと酷似してるじゃん。 ベンダー番号が上位6桁、最下位の桁はチェックデジット。真ん中の9桁がシリアル番号。 ああ、マックアドレスにチェックデジットは無いか。

シリアル番号は止めて、コリジョンが発生しない、ダイジェストにすれば良かったのにね。

Vender No

知れば納得!クレジットカード番号が表す意味とは!?