Wednesday, November 12, 2008

素数判定

ある数が素数かどうかを判定するときに、数をpとして、2からpの平方根までの数で割って確かめます。これだとpがおおきくなったときに時間がかかってしまいます。

ものの本を見ると、フェルマーの定理(小定理の方)で、pが素数の場合、
a^(p-1) = 1 (mod p)
であることを利用する。つまりいくつかのaを選び、この式に当てはめてみて、合格ならばpを素数の候補と考える、ということが書いてある。擬素数というのだそうです。なるほど、これはうまい手です。
pythonならば、

from random import randint

def is_pseudo_prime(p):
for i in xrange(0,10): #10個とって試してみる
a = randint(1, p-1)
if pow(a, p-1, p) != 1:
return False
return True

こんなもんです。大変簡単でよろしい。一方、ものの本の続きを見ると、Rabin Miller法というのが出ていて、これも似た考えのもの。GMPなどのライブラリにも入っています。

ところで、上の擬素数のコードをCで書いたら、非常に遅くてびっくりしました。ようするに

e = p-1;
a = randint(1, p-1);
r = 1;
while (e>0) {
r *=a;
r %= p;
e--;
}
return r;

といったことをしていたわけなのです。どうやら%=の処理が遅すぎる。というか多すぎる。pythonの組み込みのpowは便利で3項目のパラメタでmodの計算をしてくれているのです。じゃpythonはどうやってるのかとソースを見てみましたが、難しそうなことをやってます。

途方にくれていたのですが、wikiのページを見て、なるほどと思いました。上記のpow相当のwhileのところを、こう書くのです。

while (e > 0) {
if ((e & 1) == 1) r = (r * a) % p;
e >>= 1;
a = (a * a) % p;
}
return r;

詳しい説明はwikiの方を見てください。ようするにa同士を自乗の回数でかけるだけだから、もとのe回に比べてlog(e)に近いというわけです。これですばらしく速くなりました。

ただ、Cだと、変数を64bitにしても、かけ算が入るので、pはせいぜい32bitの範囲までしかできないのですよね。ちょっと残念です。
やっぱりGMPを使おうと思った次第です。

Monday, October 13, 2008

組み合わせを作るアルゴリズム#2

先日のエントリで集合の部分集合の表示にはbinary countingがあざやかにキマル、という話を書きました。これはすべての部分集合の表示でした。すべての部分集合は必要なく、エントリ数がk個のものだけで良い場合はどうすればよいでしょうか。

例えば{0,1,...,4}の集合の部分集合から要素数が3個のものだけを表示したい場合です。{0,1,2}, {0,1,3},...というのを表示したいとする場合。

この関係を使えば簡単とのことです。n個からk個を選ぶ組み合わせの記号を(n, k)と書くことにすると

(n, k) = (n-1, k) + (n-1, k-1)

右辺は、今の1個をパスして次以降でk取る組み合わせと、今の1個をとって後k-1個選ぶ組み合わせの和です。

これをプログラムで書くと以下のようになります。n,kは上のものと同じ、iは今の場所です。
def ksubset(n, k, i, ans):
if k == 0:
print ans
return
if n == 0:
return
ksubset(n-1, k-1, i+1, ans+[i])
ksubset(n-1, k, i+1, ans)

ksubset(5, 3, 0, [])として実行した結果が以下です。
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

お気づきの通り、このkの考慮をやめれば、部分集合全体となります。以下のように書き直しましょう。
def allsubset(n, i, ans):
if n == 0:
print ans
return
allsubset(n-1, i+1, ans+[i])
allsubset(n-1, i+1, ans)

allsubset(5, 0, [])として実行したのが以下です。長いので中略しました。
[0, 1, 2, 3, 4]
[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2]
;
;
[3, 4]
[3]
[4]
[]

これでもそんなに難しくはないですね。

pythonメモ 16進数

pythonで16進数を表示しようというとき、私は馬鹿の1つ覚えで以下のようにやっていました。
>>> a = 43
>>> print "%x" % a
2b
>>> print "%X" % a
2B

ところが、このような手頃な関数があるのでした。
>>> hex(a)
'0x2b'

さらに大文字で表示したいという場合には以下のような手段があるのでした。
>>> hex(a).upper()
'0X2B'

Xまで大文字となるのはご愛嬌ですね。

Tuesday, October 07, 2008

組み合わせを作るアルゴリズム

ちょっと家にいなければならない用があったので、例のごとくProject eulerであそんでいました。
いましがた気持ちよく一問解けたので今日はもうおしまい。

ところで集合の部分集合をすべてリストアップするにはどうすればよいでしょうか。
つまり要素がN個の集合{1,2,3,4,...,N}があるとして、この集合から要素数1からN個までの部分集合を全部書き出すのです。{1},...,{N},{1,2},{2,3},....,{N-1,N},{1,2,3},...,,,,...{1,....,N}てのを全部です。どうやるのがよいでしょうか。順列だの組み合わせだのってのは概念は簡単なのですが、あんがい面倒なものが多いですね。


今日やった問題、最初勘違いしていて、部分集合を作る問題かと思って、これを実装してしまってました。結局これは使わなかったのですが。いざやろうとすると迷いますね。

先日買った本(赤い方の本)で調べたのです。「辞書順」は意外に大変だよ、と書いてある、そうそう、それやったことある。大変だった。簡単な方法はbinary countingだよと書いてありました。部分集合の数は2^N個あるので、1から2^N-1までの数を生成する。その数を2進数で表して1の立った場所を{1,...,N}の位置から選んで部分集合の要素とするというもの。なかなかシンプルでよろしいですね。これなら実装も簡単です。

Monday, April 07, 2008

python メモ: sort関数

これは初歩的な問題なのでしょうね。
最初の要素でソート。


>>> l = [[1,2,3],[9,3,4],[5,6,7]]
>>> l.sort(lambda x,y: cmp(x[0],y[0]))
>>> l
[[1, 2, 3], [5, 6, 7], [9, 3, 4]]
>>>


今度使うぞ。

Tuesday, March 25, 2008

pythonメモ: 配列の初期化

これは間違い。

>>> c=[[0,0,0]]*3
>>> c
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> c[1][2]=3
>>> c
[[0, 0, 3], [0, 0, 3], [0, 0, 3]]
>>> 


[0,0,0]が示しているのが同じオブジェクトってことなんでしょうね。
以下だと思った通りの動きなのだが、一体、何が違うの、と言う感じ。

>>> d=[]
>>> d.append([0,0,0])
>>> d.append([0,0,0])
>>> d.append([0,0,0])
>>> d
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> d[1][2]=3
>>> d
[[0, 0, 0], [0, 0, 3], [0, 0, 0]]


Thursday, March 13, 2008

pythonメモ:リストのコピー

こういうのってどうなってるのかね。どっかに書いてあるのかな。
リストをコピーして加工するつもりで、元のものを保存しておきたいとする。もとをlと呼び、保存したのをrと呼ぼう。しかしr=lではコピーできていないね。参照だけがコピーされていて、中身は一つになっている。lを変更するとrも変更されてるもんね。

$ python
Python 2.5 (r25:51918, Sep 19 2006, 08:49:13) 
[GCC 4.0.1 (Apple Computer, Inc. build 5341)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> l=[1,2,3]
>>> r=l
>>> l
[1, 2, 3]
>>> r
[1, 2, 3]
>>> l.append(4)
>>> l
[1, 2, 3, 4]
>>> r
[1, 2, 3, 4]


中身をコピーするときにはどうするのかな。
-----
(追記)

コメントで教えて貰ったが、[:]で全体を指定するのであった。

$ python
Python 2.5 (r25:51918, Sep 19 2006, 08:49:13) 
[GCC 4.0.1 (Apple Computer, Inc. build 5341)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> l=[1,2,3]
>>> m=l[:]
>>> m
[1, 2, 3]
>>> l.append(4)
>>> l
[1, 2, 3, 4]
>>> m
[1, 2, 3]
>>> 


-----
(追記 9/29/2010)

二次元配列の場合、deepcopyを使います。
a[:][:]とやってもうまくゆきません。


>>> from copy import deepcopy
>>> a = [[ 0 for i in xrange(3)] for j in xrange(4)]
>>> a
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> b = deepcopy(a)
>>> c = a[:][:]
>>>
>>> a[1][1] = 3
>>> a
[[0, 0, 0], [0, 3, 0], [0, 0, 0], [0, 0, 0]]
>>> b
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]] #これはうまくできました
>>> c
[[0, 0, 0], [0, 3, 0], [0, 0, 0], [0, 0, 0]] #これはダメです
>>>

以下を参照。
http://docs.python.org/library/copy.html