流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【Python】5000×5000直交行列の対角化【線形代数】

巨大なランダム直交行列

各成分が[-1/2,1/2]の一様乱数で決定される5000×5000行列を近似的に対角化してみた。

手法

規格化したベクトルを用意し、各成分がe^{i\theta}という位相だけを持つとして、\thetaモンテカルロ法により最適化し、対角化を行った。

プログラム

github.com

gistc1a016e8bd86d10e898655f2ac6a979f

結果

行列が大きくなると、適当に作った固有ベクトルでも、偶然固有ベクトルに一致する個数の期待値が上がる。そのため、今回のようなかなり雑な近似でも良い結果が得られる。

固有ベクトルの誤差の期待値は、\frac{|Av/||Av||-v|}{5000}\approx 0.0181で、平均の直交すべきベクトルの内積の値は、5.0967\times10^{-6}であった。肝心の計算時間は、対角化自体は12秒。誤差のチェックに1分40秒、直交性のチェックに5分25秒で、残りの下準備の計算時間も合わせて、合計7分48秒となった。

 

【Python】確率的素数生成プログラム【改良版】

バグがありました

sky-time-math.hatenablog.jp

素数が見つからないときは、取り合えず2を足す作戦に変更

ついでに、sympy.isprime()で素数判定する作戦に変更。プログラムは以下においてあります。

github.com

進捗バー表示は以下のサイトを参考にした。

qiita.com

素数2,3,5だけから始めて、200個の素数を生成するテスト。prodの積の最大値は5、その各場合につき、乱数は1つの素数につき、100パターン取っている。

gist02db7518e164c1786a5adcb24fbc4f05

ある素数の次の素数を見つける確率99.01%。素数を見つける確率99.51%。

素数2,3,5だけから始めて、1万個の素数を生成するテスト。prodの積の最大値は10、その各場合につき、乱数は1つの素数につき、100パターン取っている。

gist6a1bd58014cb3df8b65e40ad4578de35

ある素数の次の素数を見つける確率99.02%。素数を見つける確率99.99%。しかし、28分もかかってしまった。

次にすべきこと

上記のプログラムでは素数生成時に、それまでに生成した素数全てを用いている。それを減らして、例えば100個の素数から生成し直した場合どうなるかなど調べた。1万個の素数を生成するテスト。prodの積の最大値は10、その各場合につき、乱数は1つの素数につき、100パターン取っている。この計算には、1分50秒で済んだ。

gist40988ad27e18a3c3148b3d71601ab7f0

ある素数の次の素数を見つける確率98.97%。素数を見つける確率99.99%とかなりの好成績を収めてくれた。

まとめ

確率的素数生成プログラムとしては、ある程度の水準のものができたように思う。これ以上改良するには、最初に用意する素数を増やすなどの手を打つ必要があるだろう。どれくらいの大きさの素数に対して、いくつ素数を事前に用意すればよいか、素数を選ぶ重みづけなど、いくつか課題は残っている。

 

 

 

 

 

 

【Python】二重ループが一部同期するバグ【バグ】

n×n行列の配列を

A=[[0]*n]*n

で初期化した後、

for i in range(n):

    for j in range(n):

          A[i][j]=(i,j)

等で、値を代入すると、A=[[(n,0),(n,1),…],[(n,0),(n,1),…],…]となるバグが発生した。

解決策は、

import numpy as np

A=np.zeros((n,n))

とした後、同じようにループを作ればいい。内包表記が複雑になり過ぎる場合、for文を使わざるをえないので、このようなバグには注意しましょう。

【素数】確率的素数生成【Python】

n番目の素数p_nが与えられた時、n+1番目の素数p_{n+1}を予測する。

アルゴリズムのアイデアは前回の記事と同様なので、それを貼り付けておく。

 

sky-time-math.hatenablog.jp

コード

パラメータの調整でどこまで成功確率が上がるかわからないが、ひとまず素数2,3,5を出発点として、確率的に100個素数を生成して、どれくらい正しい素数が含まれていて、次の素数を正しく計算できる確率を算出してみた。

確率的アルゴリズムのため、比較的うまくいった結果をとりあえず載せてみる。

github.com

gist6e61390f695c422cab264792f36581d4

このように約41%の確率で素数判定に成功しを、素数から次の素数を見つける確率は約40%である。最高で、49%付近までいったこともあるが、うまくいかないときは、35%程度である。

素数2~29を出発点として、確率的に素数を生成した場合の結果は次のように、いい時で50%付近まで改善された。元になる素数の情報が多いので当然の結果である。

gist5c4b2d564f917487dbb11a65163ed002

 

 

 

【素数判定】分解に基づく素数判定の劇的改良(99.58%)【Python】

前回の反省点

前回の記事では、判定成功率55%程度とあまりぱっとしなかった。

 

sky-time-math.hatenablog.jp

 

そこで、少し悩んだ結果、明らかに2,3,5,7などで割れるのは合成数だという情報を使っていなかったことに気づいた。また、プログラムのフローに問題があったので修正した。

修正版

github.com

gist388a80711e815a542ee7cb6bd9525809

1~1万までの自然数に対して試した結果、なんと判定成功率99.58%となった。素数だけの判定成功率は脅威の100%だった。なお、乱数による分割は書く自然数に対して、100回ずつ行っている。

f:id:FoxQ:20210919084320p:plain

自然数の素因数の種類数

追記

2,3,5,7の倍数をサンプルから除いた場合の素数判定成功率も調べた。

gist1610dbf28d8e1fe3b3016b3561d329d4

2,3,5,7の倍数をサンプルから除いた場合の判定成功率は約99%で、素数を正しく素数と判定できる確率は100%であった。

 

【素数判定】自然数の分解に基づく素数判定遊び【Python】

事始め

上記のひさぴょんさんの素数判定法が面白かったので、インスピレーションが湧いた。

397の素数判定式

397は一つの都合のいい素数の和差積であらわすことができないことが考えられているそうだ。ツイート内の引RT内の文献参照のこと。

そこで、2つの素数の和差積で表すことにして、実際成功した。

インスピレーションを受けて

今回の手法のポイントは2つの和か差の数に分けて、各数が多くの素数の積になっていて、なおかつそれら2数が互いに素であるということである。つまり、ツイートにまとめたように、

のように見積もれることになる。

 

実装

乱数で素数判定の式を2つに分けて、素因数の種類はなるべく大きくなるように更新すると、以下のようなプログラムになる。

github.com

2~10までの素数判定および素因数の種類数を既知として、10~1000までの素数判定を行った結果が次のものである。

gistf734d8d9838e28e061a878ce13489e0c

 

合成数素数の判定成功率は約47%で、素数だけで判定成功確率を見ると約55%となっている。また、素因数の種類の推測値も同時にプロットされている。図では、値が1のところが正しく判定できている。

今回のケースは、1~1000までに素数は、168個あり、その内90個の判定に成功している。

1~1万までの数を対象に素数判定しても、合成数素数の判定成功率は約49%で、素数だけで判定成功確率を見ると約56%となり、数の大きさの増加に対してある程度安定性があることがわかった。

このケースは、1~1万までに素数は、1229個あり、その内680個の判定に成功している。

f:id:FoxQ:20210919071818p:plain

素数判定結果

f:id:FoxQ:20210919071951p:plain

素因数の種類数の推測

まとめ

今回の推論モデルは、素因数の種類を確率的に見積もることで、そこから素数判定を行うものだった。成功確率は安定して55%付近となっており、素数の個数が減ってきても判定にはさほど影響を及ぼさないことが分かった。

 

【Python】Pythonが認識またはダウンロードされないエラー【anaconda3】

問題

Pythonの新しいバージョンを使いたかったので、pythonとanacondaを全て一度アンインストールし、もう一度インストールしようとしたらつまづいた。使用したインストーラーは、Anaconda3-2021.05-Windows-x84_64.exeです。

解決

github.com

このサイトを参考に、

conda install -c conda-forge opencv

を実行後、(一応PATHも通した)、

conda install jupyter

conda activate

としたらver3.8.11までは使えるようになった。後は、condaプロンプトをデフォルトにしました。

 

ver3.9.0以降はエラーが出てアップデートできなかったので、anaconda3のバージョンの問題かと思ってconda自体をアップデートしたがこれもダメ。ひとまず、ver3.8.11が使えるようになったので、我慢していますが、解決策知っている人がいたら教えてください。

よろしくお願いします。