複天一流:どんな手を使ってでも問題解決を図るブログ

宮本武蔵の五輪書の教えに従い、どんな手を使ってでも問題解決を図るブログです(特に、科学、数学、工学の問題についてですが)

東大数学2024問題6 (part 2): 素数のデータファイルを読み込む

前回のあらすじ

前回の記事では、東大2024数学入試問題6を解き始めた。この問題では素数を扱うため、素数データベースを利用して問題探究を数値的に行うことにした。pythonでデータファイルを読み込む方法を知らなかったので、今回は配列に似た概念を用いてそれを実装する計画である。

二次元の配列に似たもの

どうやら、pythonでは「配列」という用語は使わないようである。代わりに「リスト」という概念を採用している。今回利用するのは、CやFORTRANでいう「2次元配列」なのであるが、pythonでは「ネストされたリスト」というらしい。面倒臭いので、pythonでも「二次元配列」と言い続けることにする。

The PrimePagesからダウンロードした素数のデータファイルは、1000行の素数データを含み、1行中には10個の素数が書かれている。プログラム中では、n行目の素数データ列にあるm番目の素数のことをprime_data[n][m]と表すことにする。ただし、n,mは0から数え始めることにする。このような「二次元配列」(つまりネストされたリスト)は、プログラムの先頭で次のように宣言して、メモリを確保することになっているらしい。

prime_data = [  [0.0 for n in range(10)] for m in range(1000)]

括弧の置き方を見ると「ネスト」状になっているから、これを「ネストされたリスト」と呼ぶのであろう。0.0という数値は初期値である。メモリでの連続性を確かめると、nについて連続になっていることがわかる。これは後で確かめてみることにする。

コードを書く

さっそくコードを書いてみた。

Nx = 10
Ny = 1000
prime_data = [[0.0 for i in range(Nx)] for j in range(Ny)]

icount = 0
while True:
    prime_dummy = input().split()
    if len(prime_dummy) == Nx:
        prime_data[icount] = prime_dummy
        icount += 1
    if len(prime_dummy) == 1 and prime_dummy[0] == "end.":
        break

2つのif文は、素数のデータファイルの冒頭と終わりにある、説明書きなどを読み飛ばしたり、ファイルの終わり(EOF)を検知するための処理である。自分でデータファイルを修正してこれらの部分を消去してしまえば、このような条件文は不要となるであろうが、try-except EOFError構文をはめ込む必要が出てきて、結局は同じ手間がかかることになってしまうだろう。

1行ずつ一時的な変数prime_dummyに読み込んで、それを配列に収めていく形式である。読み込みが終わった後も、prime_data[n][m]の形式でアクセスすることができる。

これで、エラトステネスの篩を自分で実装した場合のチェック用データをプログラムに組み込む準備ができた。

次回はエラトステネスの篩のアルゴリズムを見てみたい。このアルゴリズムは有名なもので、当然ながら古代ギリシア時代から知られる有名なものであり、高校数学の教科書でも紹介されている。しかし、現代の暗号資産や電子マネーの照合で利用される巨大な素数を計算するには不向きなアルゴリズムであることも知られている。どんな利点と問題があるのか、調べてみたいと思う。

東大数学2024問題6: 素数と因数分解

「今年最難」と噂の問題6へ

ネットでの評価をざっと見た感じでは、本年度の東大入試問題においては問題6が「一番難しかった」との評価のようである。問題1もそれなりに難しかったと思うのだが、あれが「ウォーミングアップ」程度だとすると、やはり東大に合格する学生たちはそれなりに頑張っているのだな、と思う。とはいえ、数学を満点で合格する人と、半分以下の出来で合格する人との差は結構あるだろう。

ちなみに、問題6の前半(1)はかなり簡単である。設問(1)は、ある意味で具体例の計算である。したがって、(1)のやり方を一般化すれば(2)も簡単に解けそうな気がする。ただ、一般化する時はそれなりの注意深さが必要で、面倒臭い例外処理というのもある(場合分?)から、油断は禁物である。

もし問題6が「最難」だとすると、今年の入試問題は「簡単な部類」ということになって、どの学生も高得点しないと厳しく、競争は激しいだろう。こういうときは、ケアレスミスみたいな減点が影響するので、真の意味での知性は入試で測れないような気がする。今回の入試に失敗した諸君も、白紙で手も足も出なかったというのであればダメだが、解き方はわかっていたが、ところどころで計算ミスしてしまった、という場合には、わざわざ東大まで通う必要はない。自信を持って別の大学で、存分にその知性の高さ(注意深さの高さではない)を発揮したらよいと思う。

問題の概略

素数因数分解できない正の整数である。ただし1だけは除く」というのが、素数の大雑把な定義である。問題6のテーマは、数学用語の定義や数学の概念をきちんと日頃から気にする姿勢をもっているかというものであろう。これは意外に大事であって、たとえば、解析の場合、代数関数、初等関数、多項式関数など様々な用語を使って関数を分類する。それぞれの意味がわかっていないと問題を正しく解くことができない(正直、私もこれらの関数の定義について奥底まで理解したとは到底言えないので、恥じるべきであるとは感じている)。

今回の問題文には、素数の定義がわざわざ書かれているので、それが大きなヒントになっている。 考察するのは多項式 \begin{equation} f(x)=x^3 + 10x^2 +20x \end{equation} なのであるが、実数$x$を整数$n$に「投影」した際に、その「影」$f(n)$が素数になる場合があるかどうか考えよ、という問題になっている。実数空間内で$f(x)$は明らかに因数分解できる形をすでに持ち合わせていて、 \begin{equation} f(x) = x (x^2 + 10x +20) \end{equation} である。したがって、$x\rightarrow n$としたときに$f(n)$が素数になれるとすれば、「2つの場合」しかあり得ない。それは$n=1$か、$n^2+10n+20=1$の場合である(後でみるが、実はあともう2つ、考えるべきケースがあるのだが、それを見落としてしまうかもしれないというのが、この問題の「落とし穴」である)。因数が1であれば、それは素数の例外規定に適用されるので、上の形式であっても許されるのである。

実際計算してみると、$n=1$は問題に適合するケースであり、答えの一つとなる。一方$n^2+10n+20=1$の場合は不適合となる($n$が整数にとれない)。ここで解答をやめると、おそらく「不合格」となるであろう。

「落とし穴」と私が呼ぶ、残り2つのケースは、$n<0, n^2+10n+20<0$の場合である。「素数」といったら正数しかないが、「整数」ならば負数もあり得る。2つの因子の両方が負であれば、その積は正となるので、依然として問題として考察すべきケースになりうるのである。したがって、残り2つのケースというのは、$n=-1$の場合と、$n^2+10n+20=-1$の場合である。しかし、注意すべきは相棒の因子も負にならないといけない、という条件である。

$n=-1$の場合、$n^2+10n+20 \rightarrow 11 >0$なので条件に合致しない。一方で、$n^2+10n+20=-1$の場合は、$(n+3)(n+7)=0$となるので$n=-3,-7$である。これは条件に合致する。したがって、$n=-3,-7$も答えに属する。

以上より、$n=-7, -3,1$の3つが解答の全体である。ここまでかなり簡単である。多分10分、うまくいけば5分程度で解ける。

天一流の流儀で解く

しかし、我々は複天一流である。上のような解き方では予備校の解説とあまり違わないし、学ぶべきことが少なすぎて、勉強にならない(東大合格には近づくかもしれないが、仮に合格しても4月からの学業生活で困難を極めるであろう)。そこで、今回も計算機を使って、この問題に取り組んでみることにする。

正解は3つだけである。しかも絶対値にして10よりも小さな整数だけ。「人間のすばらしさは、必要最低限の思考で、最大の効果をあげることができることだ」と予備校の先生なら叫ぶかもしれない。しかし、現代はAIの時代である。将棋AIが人間を凌駕し始めたのは、人間では考えが及ばないような一手を、コンピュータがしらみつぶしに調べるようになったあたりからである。人間の観点からは「無駄な一手」に見えても、実は有効な一手になっている場合が存在し、それをAIは「見つける」ことができるのである。AIは「無駄」ということは考えないので、つまらないことでも、すばらしいことでも、平等にすべてを計算するので、馬鹿であり、かつ同時に利口なのである。

今回の設問(1)も、とにかく片っ端から整数を順番に入れて行って、問題の条件にあるものが出てくるまで探し続ければよいのである。一見間抜けに見えるこのアルゴリズムは、意外な点において重要さを見せてくれるかもしれない。とにかくやってみよう。

 素数のデータベース

この問題を数値的に解くに当たり、まずは素数のデータベースをつくらねばならない。

ネット上には、これまでに誰かが計算してくれたデータが上がっているはずで、それを読み込めばよい。とはいえ、一応自分でもある程度の整数生成はやった方が勉強になるであろう。古典的に有名な素数探索アルゴリズムはエラトステネスの篩(ふるい)と呼ばれる。まずはこれを使って、素数を1万個程度、自分で探してみよう。

とはいえ、このアルゴリズムが正しく機能するかどうかのチェックには、古人が既に見つけてくれた素数のデータベースを利用することにする。権威の軍門に下るのか!、という叱責の声が聞こえてきそうであるが、間違えてしまってはどうしようもない。特にプログラミングというのはバグがつきものである(古代ローマ人は、Erarre humanum estと言った!)。この際、権威に媚びつつも、ただデータベースを読むだけに終わらず、プログラミングの技能向上のために自分自身でもコーディングしてみたいと思う。

どうやら、もっとも有名なデータベースはテネシー大学のThe PrimePagesのようである(他にもあるとは思うが、まず最初に見つかったのがこれなのである)。素数の専門家は「最大の素数」探しに躍起になっているので、2から始まる最初1万個程度の素数にはあまり興味がないようである。データベースをつかって、「初等的な素数」を探そうと思ったが、意外に苦労した。やっと見つけたのがこちらである。

t5k.org

ということで、まず目標とするのは、このデータベースにある「小さな素数、最初の1万個」を再現することである。データベースからダウンロードしたデータの一部を以下に掲載する。

                       The First 10,000 Primes
                        (the 10,000th is 104,729)
         For more information on primes see https://t5k.org/

      2      3      5      7     11     13     17     19     23     29 
     31     37     41     43     47     53     59     61     67     71 
     73     79     83     89     97    101    103    107    109    113 
    127    131    137    139    149    151    157    163    167    173 
    179    181    191    193    197    199    211    223    227    229 
    233    239    241    251    257    263    269    271    277    281 
    283    293    307    311    313    317    331    337    347    349 
    353    359    367    373    379    383    389    397    401    409 
    419    421    431    433    439    443    449    457    461    463 
    467    479    487    491    499    503    509    521    523    541 
    547    557    563    569    571    577    587    593    599    601 
    607    613    617    619    631    641    643    647    653    659 
    661    673    677    683    691    701    709    719    727    733 
    739    743    751    757    761    769    773    787    797    809 
    811    821    823    827    829    839    853    857    859    863 
    877    881    883    887    907    911    919    929    937    941 
    947    953    967    971    977    983    991    997   1009   1013 
   1019   1021   1031   1033   1039   1049   1051   1061   1063   1069 
   1087   1091   1093   1097   1103   1109   1117   1123   1129   1151 
   1153   1163   1171   1181   1187   1193   1201   1213   1217   1223 
   1229   1231   1237   1249   1259   1277   1279   1283   1289   1291 
   1297   1301   1303   1307   1319   1321   1327   1361   1367   1373 
   1381   1399   1409   1423   1427   1429   1433   1439   1447   1451 
   1453   1459   1471   1481   1483   1487   1489   1493   1499   1511 
   1523   1531   1543   1549   1553   1559   1567   1571   1579   1583 
   1597   1601   1607   1609   1613   1619   1621   1627   1637   1657 
   1663   1667   1669   1693   1697   1699   1709   1721   1723   1733 
....
103889 103903 103913 103919 103951 103963 103967 103969 103979 103981 
 103991 103993 103997 104003 104009 104021 104033 104047 104053 104059 
 104087 104089 104107 104113 104119 104123 104147 104149 104161 104173 
 104179 104183 104207 104231 104233 104239 104243 104281 104287 104297 
 104309 104311 104323 104327 104347 104369 104381 104383 104393 104399 
 104417 104459 104471 104473 104479 104491 104513 104527 104537 104543 
 104549 104551 104561 104579 104593 104597 104623 104639 104651 104659 
 104677 104681 104683 104693 104701 104707 104711 104717 104723 104729 
end.

最初の1万個の素数を見つけるには、11万までの整数を調べなくてはならないということだ。とはいえ、偶数が考察から除外されることはすぐにわかる(エラトステネスの篩の一部でもある)。ということで、我々のプログラムは、11万の半分の5万5千個の整数を調べ、そこに素数がいくつ入っているのか確かめることになるであろう。

最初のコード

このデータベースはtxt形式のファイルとしてダウンロードできる。まずは、このデータベースを読み込む部分をプログラムで書いてみよう。整数の区切りは「空白」であるから、pythonのsplit()関数がもってこいであろう。

ファイルの最初4行は説明文なので、これを飛ばして次の行からデータとして読み込みを始め、最後の"end."が読み込まれたときに、プログラムを終了させよう。1行に10個のデータが書いてある構造を利用すると、次のような感じのプログラムで狙いの機能を実現することができた。

#!/opt/homebrew/bin/python3                                                            
while True:
    prime_data = input().split()
    if len(prime_data) == 10:
        for i in range(10):
            print(prime_data[i]+" ",end="")
        print()
    if len(prime_data) == 1 and prime_data[0] == "end.":
        break

実行はパイプを用いて、次のようにする。

python3 prime_read.py < 10000.txt

ちなみに、上のプログラムは"prime_read.py"とした。

しかしながら、この読み方だと、1行処理が終わった途端にメモリからデータ内容が破棄されてしまい、保持されない。 やはり、データは、パイプではなく、ファイルを開いて読み込み、プログラムがアクセスできるメモリに一度マウントすべきであろう。そのやり方は現在調査中である。

東大数学2024問題1(part 4): 境界の方程式を数値的に求める

前回のあらすじ

前回では「スクラッチカードシミュレーション」の結果を分析し、条件を満たす領域の境界を抜き出す作業を数値的に行なった。その結果、滑らかな曲線とおぼしき境界線が出てきた。これがどんな方程式によって作り出されているのか、今回は数値的に求めてみたい。

境界曲線の特徴

パッとみた感じは、$x=0$の頂点を持つ放物線のように見える。しかし、$(x,y)=(1,1)$の近傍で傾きが無限大、つまり垂直な直線が曲線の接線になっているように見えるので、これは放物線ではないことがわかる。放物線も、接線の傾きは原点から離れるにつれどんどん大きくなるのだが、無限大の傾きを持つのは$x=\infty$のところであって、$x=1$のような有限な位置ではない。

とはいえ、$x\simeq 0$で放物線のように「見える」のは確かである。これは原点周辺に限っていえば、放物線で近似できるという意味である。すなわち、2次のテイラー展開である。原点周りで、境界を表す曲線がテイラー展開によって \begin{equation} y = c_0 + c_2x^2 \end{equation} と表せると仮定しよう。線形項がないのは、点Aがyz平面にあることによる対称性(xの符号反転に対する系の対称性)のおかげである。角度の条件はyz平面の右と左で違いはない。

クラッチカードシミュレーションで得た、原点近傍の数値データを2つ使うと、この2点は上の放物近似曲線を(近似の精度の範囲で)満たすから、$y_1=c_0+c_2x_1^2, y_2=c_0+c_2x_2^2$となる。これを行列を使って表すと \begin{equation} \left(\begin{array}{c} y_1 \\ y_2 \end{array}\right) =\left(\begin{array}{cc}1 & x_1^2 \\ 1 & x_2^2\end{array}\right) \left(\begin{array}{c}c_0 \\ c_2\end{array}\right) \end{equation} となる。逆行列によって係数$c_0, c_2$を求めることができる。すなわち、 \begin{equation} \left(\begin{array}{c} c_0 \\ c_2\end{array}\right) =\left(\begin{array}{cc}1 & x_1^2 \\ 1 & x_2^2\end{array}\right)^{-1} \left(\begin{array}{c} y_1 \\ y_2\end{array}\right) \end{equation} 逆行列の存在条件はその行列式が非零値をとることであるが、異なる二点であれば(Vandermonde行列式によく似た)この行列式は明らかにその条件を満たす。2x2行列の逆行列はかつては高校数学で暗記させられたものであるが、それに従えば \begin{equation} \left(\begin{array}{cc}1 & x_1^2 \\ 1 & x_2^2\end{array}\right)^{-1} =\frac{1}{(x_2^2-x_1^2)}\left(\begin{array}{cc}x_2^2 & -x_1^2 \\ -1 & 1\end{array}\right)^{-1} \end{equation}

抽出した境界線データのうち、もっとも$x=0$に近い値を持っている2つの点を選び、上の逆行列を計算してみる。

2次のテイラー展開数値計算

クラッチカードシミュレーションのプログラムで

Nmax = 10000

と置いた。以前計算した時はNmax=100だったので、かなり細かく計算点を取ってみた。これはテイラー展開の精度を上げるためである。計算点は細かいけれど、必要なのは二点だけなので、うまく計算を実行すればあっという間に欲しい数字が手に入る。まあ、現代のコンピュータならどんなに非力でも数分も我慢すれば全部計算してくれるとは思うが。

計算の結果次の2つの点の数値が手に入った。

x1 = 0.028317651829966893
y1 = 2.731353210515776

x2 = 0.008582817011423207
y2 = 2.731986518131477

答えを知っていれば、y1とy2が$\sqrt{3}+1$でよく近似されているのがわかるだろう。また、もちろんx1もx2も0に近い値である。

逆行列の計算は非常に単純である。

x1 = 0.028317651829966893
y1 = 2.731353210515776

x2 = 0.008582817011423207
y2 = 2.731986518131477

dt = (x2+x1)*(x2-x1)

c0 =  (y1*x2**2 - y2*x1**2)/dt
c2 =  (y2 - y1)/dt

print(c1,c2)

これだけである。結果は、

c0=2.7320505813918388, c2=-0.8696596707381011

となった。この数字を用いた放物線とシミュレーションで得た境界線を、gnuplotで重ねて表示してみる。

境界線をテイラー展開による近似表現で表す
$x\simeq 0.4$くらいまでは、かなり良い精度で近似できていることがわかる。しかし(予想通り)$x$の値が大きくなるにつれて、テイラー展開による近似の精度は悪くなっている。

境界線を表す曲線が放物線でないとするならば、高校数学の範疇ならば、消去法で楕円か双曲線しかない(ちなみに、これらの曲線はすべて円錐曲線というグループに属する2次曲線である)。シミュレーションの結果をパッとみた感じでは、これを楕円(の一部)だと考えて、まずは解析してみるべき、と思うだろう。それで良いのである。もし、予想通りに行かなければ、その時は双曲線でやってみればよいだけのことである(双曲線でうまくいかなければ4次曲線に進めばよい!)。

楕円の方程式とテイラー展開の関係

この問題が持っている対称性により、今回考える楕円の方程式は3つのパラメータ$a,b,c$で表される。 \begin{equation} \frac{x^2}{a^2} + \frac{(y-c)^2}{b^2} =1 \end{equation}

この式を変形して$y$について解いてみると、 \begin{equation} y=b\sqrt{1-\frac{x^2}{a^2}}+c \end{equation} である。2次までのTaylor展開を行えば、上式は次のように近似できる。 \begin{equation} y\simeq b \left(1-\frac{x^2}{2a^2}\right)+c \end{equation} すなわち、先ほど計算して得た数値計算とは次の関係をもつことがわかる。 \begin{equation} c_0 = b+c, \quad c_2 = - \frac{b}{2a^2} \end{equation} $b,c$を$a$で表すと \begin{equation} b = -2c_2a^2, \quad c=c_0+2c_2a^2 \end{equation} となる。これで3つのパラメータのうち2つが消えて、残りは$a$だけとなった。

シミュレーションの結果を心眼でみる

$a$を求めるにはもう一つ条件式が必要である。これまでは$x\simeq 0$の領域で分析してきたので、$x\simeq 1$の領域を今度は利用する。ここで、シミュレーション結果をよく「みる」ことにする。すると$(x,y)=(1,1)$が境界線に乗っているように見える。 たとえ近似であっても、この性質は利用しない手はない。なんといっても、このブログの精神は「複天一流」なのである!使えるものはなんでも使うのである。

今度は近似式ではなく、厳密な楕円の方程式を利用する(実はこれには理由があるが、後述とする)。もちろん、境界曲線が楕円かどうかはまだ不明である。仮定した上で計算を進め、後でシミュレーションの結果をよく再現しているかどうかをみてから、この仮定が妥当かどうかを判断するのである。

$x\sim 1$でもテイラー展開する方が、手法の一貫性の観点から良さそうな気がする。しかし実際にやってみるとテイラー展開がうまく機能しないことがわかる。それは、この領域で境界曲線がほぼ垂直に突っ立った形状になっているからである。微分が無限大になっているという意味である。テイラー展開微分が定義できる場所でしか利用することができない(定義からそうなっている)。そこで、楕円曲線を仮定してしまい、もしかしたら違っているかもしれないとは思いつつ、やってみてうまくいったらそのまま突破してしまおう、というアプローチを選択したのである。こういうのを「試行錯誤法」といってもいいだろう。物理学では「変分法」というタイプに属する手法である(今の問題の場合は多少複雑だが、微分ができないタイプの曲線の集合に対して変分法を当てはめた、といえるだろう)。

$(1,1)$を代入して得られる条件式は \begin{equation} \frac{1}{a^2} + \frac{(1-c)^2}{b^2}=1 \end{equation} である。ここに、テイラー展開で得られた結果を代入し$c,b$を消去すると,$a$についての2次方程式が手に入る。 \begin{equation} 4c_2(c_0+c_2-1)a^2 + (1-c_0)^2 = 0 \end{equation} 数値計算の結果は$c_0\sim 2.7, c_2\sim -0.9$であったから、$c_0+c_2-1 \sim 2.7-0.9-1 > 0$となり、$a$が実数解を持つことができることが確認できる。すなわち、 \begin{equation} a = \frac{c_0-1}{2\sqrt{-c_2(c_0+c_2-1)}} \end{equation} という形で計算できる。

数値計算の結果を用いてa2, b2, cを計算すると、

a^2 = 1.0000176119391624,  b^2= 3.025338332967406,  c=0.9927006071292104

を得る。この数値結果を$a^2=1, b^2 =3, c=1$と解釈し、楕円の方程式を \begin{equation} x^2 + \frac{(y-1)^2}{3} =1 \end{equation} とみなして、シミュレーションの結果と重ねて表示してみると、次のようになった。

黄の◯:シミュレーション結果、黒の実線:予想した楕円の方程式、緑の実線:テイラー展開による近似

まとめ

「心眼でみる」とか気取ったことを書いてみたが、結局は答えを知っていたから、そう書いただけにすぎない。解析的にやっても、この問題は簡単にとける(とはいえ、20分くらいはかかるだろう)。そこで楕円と直線の組み合わせになることを知ってしまえば、あとは「シミュレーションの練習」くらいなもので、簡単にここまで辿り着ける。しかし、このやり方を練習しておけば、答えがわからないときに、シミュレーションで何をすれば良いか、なんとなく察することができると思う。そのような問題はかならずこの先現れるであろう。

東大数学2024問題1(part 3): 境界を抽出する

前回のあらすじ

前回の記事では、2つの不等式を満たす$(x,y)$をしミューレションによって数値的に見つけ出し、その結果をgnuplotで描画した。大体の感じはわかったが、その境界の方程式を算出するところには至らなかった。

今回は不等式を満たす領域の境界を表す方程式を計算して求めるところまでやりたい。

境界を抜き出す

ある領域の境界を抜き出すという作業は、デジタル画像データの処理でよく利用される。画像の輪郭を抜き出して、個人認証に利用したり、ロボットやAIが作業する物体の識別に利用したりするからだ。今回のプログラムはそこまで大げさなものではないが、基本的な考え方は同じであると思われるので、いづれ役に立つ日もくるのではないだろうか?(補償なしの、安っぽい希望で申し訳ない)

前回書いたプログラムをscratch-card.pyと名づけることにすると、このプログラムの出力で6つ目の数字(整数)が1となっている座標(データの3つ目と4つ目の浮動小数の数字)が不等式の条件を満たす点である。この領域の「境界」だけを抜き出すためには、極座標で計算したループの構造を利用することになる。

ループでは動径$r$を与えてから、角度$\alpha$を動かした。したがって、与えられた$r$のうち、$\alpha$の値が最も小さい点に対応するデータが、境界点を与えることになる。この観点からpythonでプログラムを書いてみた。

i=1
while True:
    try:
        data_seq = input().split()
        if int(data_seq[1]) == i and int(data_seq[5]) == 1:
            i += 1
            print(data_seq[0],data_seq[1],data_seq[2], data_seq[3],data_seq[5])

    except EOFError:
        break

このプログラムはread-data.pyと呼ぶことにする。 以下では、このプログラムを部分分解して、ポイントを確認してみる。

データの読み込み

読み込むデータはscratch-card.pyで作ったデータである。したがって、次の二つの方法で読み込むことができる。

[1] 外部データに一度scratch-card.pyの結果を保存するやり方
% python3 scratch-card.py > tmp.dat
% python3 read-data.py < tmp.dat > result.dat

[2]パイプを使ってデータをプログラム間でやりとりするやり方
% scratch-card.py | read-data.py > result.dat

実際の計算では、1つ目の方法を採用することが多いだろう。 2つ目の方法では、プログラムを実行形式にした場合を想定している。

今回のデータ読み取り方法の利点は、データの型を気にしなくていいという点である。それはPythonがもっているinput()関数のおかげである。この関数はデータを「文字列」と解釈して取り込み、「文字列」として出力する。

以前、赤玉計算の問題を解いたときはC言語を使ったのでscanf()を利用したが、今回は同じような処理をpythonのinput()を使って行っている。すでに上述したとおり、scanfの場合には読み込むデータの型を指定する必要があったのに対し、inputの場合にはどんなデータでも「文字列」と決めつけて読み込むので、変数型について気にする必要がない。その分だけプログラムは簡略化されるが、その後の計算では好みのデータ型へ変換する点について気をつけねばならない。

またinputで読み込んだデータは「区切り」というものがない。scratch-card.pyでは「空白」を用いて複数の数値データを区切っていたが、inputで読み込んでしまうと空白も文字列の一部と見做される。

したがって、たとえば、

@@XOOO,XOOX@

というデータがあるとする(赤玉の時に使った記号である)。2つの記号シーケンスがカンマ(,)で区切られているというデータ構造である。これはいわゆるcsvファイルである(comma separated values)。

このデータを次のようにしてpythonで読み取ったとする。

dseq = input()

するとdseq[0]=@ dseq[1]=@ dseq[2]=X dseq[3]=O .... dseq[6]=, dseq[7]=X ... dseq[11]=@となる。 またlen(dseq)は12という値を返す。データの区切りのつもりでつかったカンマ(,)もデータの一部として取り込まれてしまう。

データが2つのシーケンスからなることをプログラムにわからせるために利用するのがsplit()関数である。今、csv形式でデータを区切っているので次のようにプログラムしてデータを2つに分割する。

dseq = input().split(',')

すると, len(dseq)は2となり、dseq[0]=@@XOOO dseq[1]=XOOX@となって、人間が意図した構造にデータが分割された。

splitのデフォルトの区切り文字は「空白」なので、scratch-card.pyのデータを読み込むときはsplit()をそのまま使用することになる。

最後に、scratch-card.pyが出力するデータ行は100である。予め行数がわかっているので、その分だけ読み込むようにプログラムすることは可能だが、C言語のようにEOFを利用し、任意の長さのデータを読み込めるようにしたいときもあるだろう。今回のread-data.pyでは後者を採用している。そこで利用するのがtry... except EOFError...の構文である。コードを見れば使い方はすぐにわかるだろう。

以上で、データの読み込み部分についての説明はおしまいである。

動径と角度でグループ化されたデータ構造を利用して境界を抽出する

さて、プログラムのメインである境界抽出のアルゴリズム(のようなもの)についてみていこう。「アルゴリズム」と呼ぶのがちょっとおこがましい感じもするくらい、今回のプログラムでは簡単に処理できる。

まず、動径$r$と角度$\alpha$によってデータはまとめられており、まずは$r$を固定した上で、$\alpha$を動かしている。つまり、与えられた$r$に対して最も小さな$\alpha$の値をとる点が「境界点」となる。ある$r$で境界点を見つけたら、次の$r$に移り、そこでまた境界点を見つける、といった作業を($r$の最大値になるまで)繰り返せばよい。

条件を満たす点かどうかは6番目の整数値data_seq[5]で判定できる(1なら条件を満たす点、0なら条件を満たさない点)。

整数の変数iが、着目している動径$r$の値に対応するラベルである。最初に合致したら、すぐに次の値i+1になってしまうため、領域内部の座標は表示されずスルーしていくだけである。データが進んでdata_seq[1]の値が変化したタイミングこそが境界点であり、そのときは座標が表示される....これをデータの終わりまで繰り返す、という感じである。

東大の問題を自力で解けばわかるように、動径が小さいところ$(r\le \sqrt{2})$では境界は$y=x$で表される。この部分はデータを「見る」だけで人間でも判定できる。問題は、動径が大きくなって境界の方程式が楕円のそれに切り替わる領域である。答えは \begin{equation} x^2 + \frac{(y-1)^2}{3} = 1 \end{equation} つまり、 \begin{equation} y=\sqrt{3(1-x^2)}+1 \end{equation} であるのだが、これをシミュレーションで計算するにはどうすればよいかである。

境界を抽出する

まずはscratch-card.pyで得たシミュレーション結果を分析して、領域の境界を抽出しよう。すでに書いた通り、その結果はresult.datに出力されている。これをgnuplotで描画すると次のようになった。

「スクラッチカード」シミュレーションで得た領域の境界の抽出
シミュレーションの結果に、正解となるはずの関数を重ねてみたが、ほぼ一致しているのがわかる。つまり、シミュレーションは正しい答えに肉薄しているらしいことが推測できる。

しかし、答えがわかっているものを分析できる機会はそうはない(笑)。どうやったら、シミュレーションをつかって正解をえられるのだろうか?

Rosettaの底力 (part-2): iPhotoも動いた

Catalinaで見捨てられたiPhoto

Mojaveを長らく利用し続けた理由の一つがiPhotoにある(より正確にはiPhoto.app?)。長いこと(Powerbookの頃から)デジタル写真の管理はiPhotoでやってきたので、いきなり「写真.app」でやりますよ、と言われても強い抵抗があったのだ。しかも、iPhoneの写真管理と同じように、スワイプを念頭にした写真整理はどうも違和感があって馴染めない。やはり、ディレクトリのような「箱」に収まってないと整理した気にならないし、写真を探すときに探しにくさを感じるのである。

コロナウイルスのせいでオンライン講義が始まったとき、ビデオ会議でMojaveを酷使しすぎてあやうくシステムが壊れる寸前にまで追い詰められた。仕方なく、Intel core i5の安い(というより「安め?」の)macbook proを購入し、Catalinaの洗礼を受けたというわけである。そのCatalinaも知らないうちに慣れていったが、iPhotoだけはゆずれない一線であった。

iPhotoやそのプロフェッショナル版であるApertureの使い勝手の良さはよく知られている。しかし、(CanonSONYのデジカメではなく)iPhoneで写真を撮る時代になり、iPhotoのような写真管理ではなく、iOSと同じやり方で写真管理したくなるのはある意味当然なのかもしれない。しかし、多数派だけが世の中の全てではない。必ずいつの時代にも少数派は存在し、少数派の方がインパクトのある結果を出すことも少なくないのである!

またiPhotoで管理してきた10年近くに及ぶ大量の画像データを、「写真.app」型のデータに変換するのは馬鹿らしい作業でもある(一度試したことがあるが、気が遠くなって途中でやめた)。また、個人的にはiPhoneで写真を撮ることはまずない(目の前で地震によって建物が崩れたと言ったような、よっぽどの緊急的な事態でない限り)。写真を撮るときは、一眼レフを準備してから撮影に向かう、という感じである。こういうタイプの撮影をする限り、iPhotoの方が圧倒的に使いやすいと感じる。

Catalinaを買ったとき、iPhotoをCatalinaで使い続けるための方法について調べた。そこで見つけたのがRetroactiveというソフトウェアであった。試してみるとあっさりうまくいったので、なんのメモも取らずにそのままにしてしまった。

あれからさらに数年が経過し、ついにまたiPhotoの引っ越しが必要になったのである。しかし、今回はCPUのアーキテクチャの変更が伴う「大事業」になりそうな予感である。果たして、Catalinaのときと同じように、M1-MBPのmontereyでもうまく移行できるだろうか?

Retroactiveはまだ存在するか?

MojaveからCatalinaへ移行するときだけに必要とされたRetroactiveであるから、あれから数年が経過した今、ほとんどのユーザーが写真.appに慣れ親しんでいるとするならば、わざわざM1-macbook proRetroactiveを使ってiPhotoを持ち込もうとする人はほぼ皆無ではなかろうか?ユーザーが存在しないとアプリは死んでしまう、というのがAtomエディターの件で感じたことである。

おそるおそる調べてみると、なんと生き残っていた!しかもM1への移行も可能だという。どうも世界にはiPhotoユーザーが根強く生き延びていると思われる。彼らの要望はかなり強いらしい。

現在はgithhubでオープンソースとして公開されている。ソースからのコンパイルも可能だろうが、今回はiPhotoの生き残りの方が優先事項なので、バイナリファイルをダウンロードしてさっそく作戦開始である。移行手続きの詳細に関しては、下のリンクにあるREADME.mdを参照すべきである。

github.com

Retroactiveで「M1の岸を渡った」iPhoto

Retroactiveのアプリは(rosettaのおかげか)無事に起動し、機能し、そしてiPhotoの改造も無事に終了した。M1-macbook proにもiPhotoがやってきたのである!これでまた10年近くはiPhotoで画像データを管理できるし、これまでのデータも継続して管理することができる!10年に一度程度しか使わないアプリであるが、Retroactiveは非常に素晴らしいアプリである。

Retroactiveを起動したところ(iTuneに馴染みがある人もRetroactiveは救ってくれる)

RetroactiveによってiPhotoの改良が終わったところ

M1-macbook proのMontereyで起動したiPhoto.app

ちなみに、インストールしたiPhotoのバイナリファイルを調べるとx86_64である(Catalinaからコピーしただけなので当然)。やはり、Rosettaはいい仕事をしているといえる。

$ file iPhoto 
iPhoto: Mach-O 64-bit executable x86_64

Rosettaの底力: Nanosaurは動いた

Rosettaの限界と底力

先日はcrispy-doomコンパイルにおいてRosettaの限界を感じたのだが、今回はRosettaの底力を感じたので、それを書いておこう。

試したのは、このあいだ、MojaveでコンパイルしたNanosaurとNanosaur2である。SDL2ライブラリを利用した現代風の改良が加えられた、この2つのゲームソフトは、現在githubソースコードが公開され、オープンソフトウェアとして生き返った。ちょっと苦労した点もあったが、私もソースコードコンパイルに成功し、このクラシックなゲームをMojaveやCatalinaで再び楽しめるようになった。

先日から、メインマシンをIntel-mac(mojave)からM1-mac(monterey)に移行する作業を実施しているが、MojaveでコンパイルしたNanosaurが果たしてRosettaによってM1-macbook proそのまま起動できるか試してみた。その結果は、NanosaurもNanosaur2も両方とも(なんの修正もやり直しも不要で)問題なく起動し作動したということになった!コードは当然ながらx86_64のはずである。これがarm64で動いたというのだから、Rosettaの底力を見せつけられた、ということになるだろう。

しかし、crispy-doomはダメで、NanosaurはOKというのはどういうことなんだろうか?どうも、Rosettaが力を発揮するのは、アプリ名がXXX.appとなっているタイプのアプリケーション、つまりXcodeのプロジェクトとして完成したアプリだけのようである。crispy-doomはmakeによって実行ファイル単体に全てが固められてしまったが、NanosaurはNanosaur.appというディレクトリがその正体であり、その中には設定ファイル*.plistやその他のデータがバイナリとともに配置されている。

そういえば、Mojaveからコピーして持ってきたAtom editorもM1-MBPで動いているが、その正体はAtom.appである。ディレクトリの中に入ってみるとContentsというディレクトリがあり、その中にInfo.plistなどさまざまなファイルが収められている。実行ファイルの本体は、MacOS/Atomであり、そのファイル形式を調べると、予想通りx86_64であった。

$ cd Atom.app/Contents/MacOS
$ file Atom

Atom: Mach-O 64-bit executable x86_64

Apple M1-macbook proでcrispy-doomをコンパイルする:Rosettaの限界

intel-macからM1-macへの引っ越しは終了

intel-macbook(Mojave)からM1-macbook(Monterey)へ、仕事用のファイルの転送やメールの設定なども終わり、これでひととおりシステム移行は終了である。なんとか問題なくこれまでは来ている。

そこでcrispy-doomコンパイルしてみることにした。

crispy-doomをM1-macbookコンパイル

引越しの際、githubからダウンロードしたcrispy-doomのソースファイルもM1-macbookに転送した。

Rosettaがあれば、Intel x86-64のバイナリコードもM1-macbookで動かせるのだろう」と思ったのだが、そうは問屋が下さなかった。

まずひっかかったのが、homebrewのファイル構成の変更である。最新のhomebrewと10年前のhomebrewとでは、ディレクトリ構造が異なっていても不思議ではない。たとえば、libSD2-2.0.0.dylibの位置が、Intel-macのMojaveでは/usr/local/opt/sdl2/lib/に置かれていたのだが、M1-macのMontereyでは、/opt/homebrew/libに置かれている。この程度の差異なら、リンクを貼り直すことでなんとかなるので、

sudo mkdir /usr/local/opt
sudo mkdir /usr/local/opt/sdl2
sudo ln -s /opt/homebrew/lib /usr/local/opt/sdl2/lib

として再度起動してみた。すると今度は次のエラーである。

dyld[15015]: Library not loaded: /usr/local/opt/sdl2/lib/libSDL2-2.0.0.dylib
....
Reason: tried: '/usr/local/opt/sdl2/lib/libSDL2-2.0.0.dylib' (mach-o file, but is an incompatible architecture (have 'arm64', need 'x86_64')

さっきhomebrewを使ってインストールしたばかりのSDL2のライブラリは、当然ながらarm64のバイナリファイルである。それをintel-macコンパイルしたx86_64のcrispy-doomは利用できないのは、普通に考えれば「当然」であるが、このM1-macbookマシンには「天下のRosetta」がインストールされているのではなかったか?!「こういう不一致を解析して、intel-macのバイナリファイルも動かしてしまうのがRosettaの役割じゃなかったのか?」と詰問したくなるが、そんな独り言を言っても無駄である。要は、自分でコンパイルしたバイナリファイルについては、Rosettaは動作を保証してくれないのである。(intel-macからもってきたatomエディターがRosettaを用いてM1-macで動いたのは、ライブラリの部分も一切合切、atomの実行ファイルの中にまとめてあるからなんだろうか?)

ということで、単なるディレクトリ構造の違いだけでは済まない、大きな壁があることが、crispy-doomコンパイルを通じて初めて体験できた。これはこれで大きな収穫だ。

M1-chipでARM64コードにコンパイルし直す

そこで、make cleanして、最初からM1-macbookコンパイルし直すことにした。sdl2に関する幾つかのファイルをインストールし忘れていたので、brew search sdl*を使ってリストアップし、端からインストールした。

% brew search sdl2
==> Formulae
sdl2 ✔              sdl2_image ✔        sdl2_net ✔          sdl2_ttf ✔
sdl2_gfx            sdl2_mixer ✔        sdl2_sound ✔

sdl2_gfxはグラフィックス処理関係の関数がまとめてあるライブラリだと思うが、crispy-doomでは使ってないようだ(インストールしてないのは気まぐれ)。

makeを繰り返すと、libsamplerateがない、という苦情がきたのでbrew install libsamplerateでインストールする。そういえば、makeもintel-mac用に生成されたものである。autogen.shを起動してMakefileを作り直した。再再度makeする。

今度はpython3のバイナリがx86_64になっていて動かない、という苦情がくる。よくよくみると、venvとしてローカルにインストールしたpython3がシステム移行の際に$HOME/binに紛れ込んでいたのが原因であった。このファイルを消去し、/opt/homebrew/bin/python3を使ってインストールさせる。このpython3は紛れもなくARM64のバイナリファイルである。

ということで、この後のmakeが最後となって、やっとのことでcrispy-doom (arm64版)が完成したのである!

しかし、crispy-doomとコマンドを打ったとき、最後の最後でまたもやerrorが発生した。一瞬愕然としたが、エラーメッセージを読んで苦笑した。wadファイルが指定されてない、というのである。wadファイルはディレクトリの上の階層に置いてあったので、crispy-doom -iwad ../doom1.wadと打つと見事にDOOMが起動したのであった!