読者です 読者をやめる 読者になる 読者になる

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

math.prime

【注意書き】よく考えたらHEADだからドキュメントとかもないのはある意味当然で、最新のリリースバージョンの0.9.3.3にはmath.primeは存在しないです。今日の段階(2013/07/35)のHEADの情報ということで。。

Gaucheにそんなものがあったなんて知らなかった。。。
(それもそのはず?7ヶ月前に作られたばかり(ばかりっていうのかな)らしくドキュメントもまだないぽい?)

Project Eulerとかやっていると、素数はなにかと入用なので、速さ的にも自分で実装するより圧倒的に良いので、ある程度以上は積極的に使っていきたいかもしれない…?
とりあえず、ソースコードを読んで何が使えるのか分かったので、簡単にメモりメモる。

primes

中身読んでもあまり理解できないけど、無限の素数列を生成する手続きぽい。引数なしなので(primes)で呼び出せる。(けど、無限なのでREPLとかで無闇にやるもんじゃなさそう)

*primes*

手続きprimesを定数として定義している。普通はこっち使う方が良さそう。

(take *primes* 10) ;; => (2 3 5 7 11 13 17 19 23 29)

reset-primes

*primes*にprimes手続きを代入。なんか間違って*primes*を再定義しちゃったときとかに使えそう。引数はなし。

small-prime?

これ、実装がすげーって思った。findの使い方が参考になった。
341550071728321以下までの素数判定に使えるのかな。341550071728321より大きいと#fが返ってくる。
素数判定なので当然引数はある数nひとつだけですね。100以上の数に関してはミラーラビン素数判定法を採用しているぽい。

*small-prime-bound*

これは素数が「小さい素数」かという境界値の定数らしい。341550071728321が境界らしい。

miller-rabin-prime?

ミラーラビン素数判定法を使って素数かを判定する。これも引数はひとつ。

bpsw-prime?

bpsw testという素数判定法を使って素数かどうかを判定する。(bpswって初めて聞いた)
The Baillie-PSW primality test

naive-factorize

素朴な素因数分解。割と素直な(?)素因数分解。結果はリストで返ってくる感じ。

(naive-factorize 100) ;; => (2 2 5 5)

mc-factorize

モンテカルロ法を使った素因数分解。ある程度の大きさまではnaive-factorizeを内部的に使っているみたい。

jacobi

ヤコビ記号(jacobi symbol)を求めるらしい。*1
(jacobi a n)でa,nは非負の整数で特にnは奇数でなければならない。

totient

オイラーのトーシェント関数の実装。

(totient 100) ;; => 40


ということでさらっとソースコードを読んで、メモった!
コード読みやすいなーっと思った。あと知らない手続きとかマクロとか沢山あったので、ちょこちょこ調べる。

*1:というのもヤコビ記号って何に使うのかさっぱり分からないので…

広告を非表示にする