2100年春アニメ:ごちうさ-887.67期

背景

ごちうさは2014年と2015年にアニメ化されています.タイトルは,それぞれ

となっています.また,2020年にもアニメ化されることが決まっており,タイトルは2014年・2015年の例から考えて

となることが推察されます(正式には未定です).

ここで,西暦年を独立変数  x として考えると,クエスチョンマークの数(=アニメの期数)は  x の関数  f(x) で表せそうですね.というわけで, f(x) の具体的な形を考えてみようと思います.

補間

Lagrange 補間という多項式補間法があります.これを使えば, f(x)

 f(x) = \frac{(x-2015)(x-2020)}{(2014-2015)(2014-2020)} + \frac{(x-2014)(x-2020)}{(2015-2014)(2015-2020)} \times 2 + \frac{(x-2014)(x-2015)}{(2020-2014)(2020-2015)} \times 3

と書けます.頑張って計算することで,

 f(x) = -\frac{2}{15}x^2 + \frac{2691}{5}x - \frac{1629323}{3}

を得ます.

観察

具体的な  f(x) の表示が求まったので,性質を見ていこうと思います.

とりあえずプロットしてみた結果がこちらです.

f:id:villach:20190427123437p:plain

見ての通り下に凸で,最大値はおよそ 3.4になることが分かります. f(x) = 4は実解を持たないので,ごちうさ4期は放映されない公算が大きいです.また,2021年ごろに2期の再放送が,2022年ごろに1期の再放送がそれぞれ見込まれます.

展望

4期が放送されないというのが本当だとすると精神的にかなりつらいので,なんとかして単調増加性を前提した別の補間を見つけていきたいです.

高専生英語できない問題は本当なのか

はじめに

香風智乃すき(I am very love to kafuu chino.)

 

正確には「高専生英語できない問題」というより「高専生,高校生と比べて英語できない問題」について書いています.

本題

  • 高専生はそれなりの入試を経ているので,さっぱり英語ができないというわけでもない.
  • 進学予定の高校生は自主的に英語を学習するインセンティブがある.進学のためには高校の授業で用意されている時間は少なすぎるので,結果として授業外で学習することになる.
    対して,高専生は編入を目指さない限り単位を落とさない程度の学習で十分であり,それには授業時間のみの学習で事足りる.この辺が進学予定高校生との差に響いてきそう.
  • 一方,進学しない or 進学するけど英語の試験がない高校生というのもたくさん(大学進学率から考えて少なくとも5割以上)いて,彼らの英語学習に対するモチベは高専生と変わらない気もする.
  • 各種試験(英検,TOEICTOEFL,GTEC)の成績の違い(高専生は高校生よりかなり低い)がよく言われるけど,そもそもそういった試験を受ける高校生は平均を上回る程度には英語学習を積極的にやっているので,これだけを見て高専生の英語力を推し量るのは正しくない.

結論

高校生と比べてはちゃめちゃに英語できないというわけでもないけど,まあ平均レベルではあると思う.というか,そうであってほしい.

「美少女に支配されたい」?「美少女に服従したい」?

はじめに

美少女の靴を舐めたい

概要

「支配される」と「服従する」との差異はなんでしょう.単に受動態と能動態の違いだとも思われますが,本当にそうでしょうか?

これらの差異や政治学的な取り扱いについては,日本を代表する政治学者の丸山眞男が,『支配と服従』(『現代政治の思想と行動』および『政治の世界 他十篇』所収.現在は後者が最も入手しやすいと思われます)という論考で詳しく考察しています.

政治の世界 他十篇 (岩波文庫)

政治の世界 他十篇 (岩波文庫)

 

この記事では,『支配と服従』の内容をなるたけわかりやすくまとめてみようと思います.なお,記事中で扱う「支配」「服従」という語は別に価値判断を含んでいないことを付言しておきます.

1. 定義

一方の人間(あるいは人間集団.以下同じとします)が他方の人間に対して継続して優越的地位にあり,それにより後者の行動様式が継続的に規定される場合,客観的にみて従属関係が生じます.支配あるいは服従という関係は,かかる従属関係の特別なパターンとして捉えることができます.

定義というか辞書的説明としてはこれだけの話で,割と簡明なのですが,これでは考察を掘り下げようもありません.もう少し具体的な説明が欲しいところです.とはいえ,ある従属関係を取ったとき,それが支配・服従関係に妥当するのかどうかを明確に線引きするのは非常に難しいので,とりあえず例を挙げて考えてみることにします.

2. 教師と学生,主人と奴隷

学生が教師に「服従」しているというのは,あまり違和感なく受け取れる事実だと思います(先述したとおり,「服従」という語には価値判断を含んでいないことに留意してください).

一方,教師が学生を「支配」していると言い切れるかというと,これは微妙になってきます.ここで重要なのは,支配関係の有無に関わらず権力関係が発生していることです.教師は学生に何かを命じたり,何かを禁じたりすることができます(し,現にしています.勉強せよ,放蕩するべからず!). さらにまた,学生の違背に対して罰を以て報いることも可能です(叱責,留年,退学……).こうした権力関係は自然に(先験的に)教育と密着していますが,しかし支配関係は発生していません.

では,支配関係が発生している事例にはどのようなものがあるでしょうか.パッと思いつくのは,古代の奴隷制ですね.この場合は明白に支配が成立しています.

教師と学生の関係・主人と奴隷の関係の差異はなんでしょうか? 丸山は,利益志向の同一性と対立性をその差異として挙げています.

教師と学生の求めているものは本質的に同じです.学生は教育を受けることで人格的ないし学問的な向上を目指しており,教師もまた学生の人間的完成を志向しています.教師が学生に加える罰も,かかる志向のもとでのみ成立します.ここにあって,教師は権威となり,学生は権威に服従するのです.

一方,主人と奴隷はその目標とするところが完全に異なります.主人は奴隷を最大限使役すること,奴隷は主人の使役から最大限逃れることを目指しています.奴隷は主人を範とすることなく,ただ物理的強制力のために労働することになります.ここで,主人から奴隷への一方的な支配関係が成立します.

こうして,記事タイトルに掲げた問いへの答えがとりあえず出てきそうです.屈服プレイにも種々様々ありますから一概に支配であるとか服従であるとかは言えませんが,ぼくは美少女に服従したい方ですね.美少女に服従するということについて詳しく語るとキモくなるので避けますが.

ここからは歴史的・政治制度的な話になります.

3. 支配と服従の歴史

一般に,古代社会は服従によって成り立っていました.族長という権威への同方向的な服従がコミュニティを支えていました.一方,社会が近代化するにつれ,支配集団と被支配集団との目的は別々の方向を向いてゆきます.人間の歴史は,極めて大ざっぱに述べて,服従関係から支配関係への転換の歴史ということになります.

さてここで,パラドキシカルですが,政治的支配が純粋な支配関係のみでは成立しないという問題が発生します.奴隷制的支配にあっては,奴隷が主人に自発的服従を以て仕えることはなく,形式的な「服従という事実」のみが生じ得ます.名前忘れたけどなんか偉い人が「奴隷労働は最も非効率的な労働形態である」と述べたのはそのためです.政治的にもそうであって,純粋な支配によって成り立つ支配機構は,抑圧のためにいたずらに巨大な装置を用意する必要に追われます.

したがって,支配者は多かれ少なかれデモクラティックな制度を立ち上げ,被支配者に譲歩し,同時に被支配者との同一化を図ることになります.ここに至って,デモクラシーという仕組みは,支配の事実を「隠蔽」して被支配者の協力を得るための偽装装置と相成ります.もちろん,かかるシステムが支配集団によって意識的に偽装として運用されるかと言えば,決してそうでもありません.現代に至るまで,徐々に支配集団がその自覚性を増してきたというあたりが本当だと思われます.

現代にあっては,この「偽装装置」であるデモクラシーを,いかにして制度的な,真に表現的なものと変えていくかが問題となります.ここで思い出すべきは,支配と(自発的)服従との差異が,両集団の利益志向同一性の有無にあったことです.社会を利益共同的な集団とし,価値の寡占を防ぐことが一種の処方箋たりうるのではないか,と考えられます.

おわりに

勢いで書いたものの,頭から読み返してみたら長いし晦渋でわけわからんですね.

3節は端折った部分が多いので,もう少し支配と服従についてちゃんと考えたい人は丸山の著書を買ってみてください.

新年度になった

4年生になりました.月日が経つのははやいものですね.

今年度は編入試験に向けて全力を注がなければならないシーズンになります.甘えることなく精進していきたいと思います.

部活動(プロコン含む)にはあまり関われそうにないです.競技部門のルールをちょっと読みましたが,昨年の大会から大幅に変わったわけではないので,もしかしたら後輩のチームに少し協力することになるかもしれません.

時間割を見ての感想ですが,全体として授業時間数が減っていてうれしいです.生じた剰余時間を有効活用していきたいですね.水曜日は90分授業3コマ分も数学の講義が入っています.うれしいような,しんどいような気持ちです.

そういえば,今年2月に受験した TOEIC IP の点数が返ってきました.完全に無対策の状況で受けたので点は良くないだろうと想像していたんですが,それにしても酷い点数でした.次回受験でリベンジできるよう対策を積んでいきたいと思います.

今年度もよろしくお願いします.

高速な素因数分解アルゴリズム(Lenstra の楕円曲線法)を実装する

はじめに

春休みに入ってからというもの,腰痛が悪化する一方です.

TL; DR

Lenstra の楕円曲線法とは?

素因数分解アルゴリズムの一種で,現時点で見つかっているアルゴリズムの中では3番目に高速だと言われています.Hendrik Lenstra によって考案されたらしいです.

この記事では,Lenstra の楕円曲線法(以下 ECM と略称します)について,アルゴリズムや実行結果,原理などを簡単にまとめていこうと思います.

前提

くどくならない程度に前提となる数学的基礎を紹介しておきます.興味のない人は読み飛ばした方がいいかもしれません.

方程式  y^2 = x^3 + ax + b *1 の体  K における解全体がなす集合,すなわち
 E' = \{ (x, y) \in K \times K ; y^2 = x^3 + ax + b\}
に,無限遠点としての役割を持つ点*2  O を追加して得られる集合,
 E(K) = E' \cup O
は,Abel 群をなします.「点同士の足し算」として加法が突っ込まれた群です.この群を  K 上の楕円曲線と呼びます.足し算の構成法や Abel 群をなすことの証明に関しては,インターネットや書籍に優れた説明があるので,そちらを参照していただければと思います.

さらにまた,同じ点同士を繰り返し足すことでスカラー倍算も導入できます.すなわち,ある点 P \in E(K)に対し,
 nP = \underbrace{P + P + \cdots + P}_{n \: times}
という計算も定まります.

実数体上で考えた楕円曲線のグラフの一例を以下に示しておきます.

f:id:villach:20190317205727p:plain

ECM の手順

ECM は以下のような手順で構成されています.以下, n を実際に素因数分解したい合成数とします.以下の手順は  n の自明でない約数を求めるものなので,完全に素因数分解するには素数判定をはさみつつ再帰的に手順を実行する必要があります.

  1. 楕円曲線  E(\mathbb{Z}/n\mathbb{Z}) を適当に決め,その上の点  P をランダムに一つ定める.
  2. 適当に  k を決める.
  3.  P k 倍点である  kP を計算する. kP を計算する過程で無限遠 O に飛んでしまったら,そこから  n の非自明な約数が求まる(原理は後述).もし  kP が普通に計算できたら,1. か 2. に戻ってパラメータを選び直し,再試行する.

要は  kP を計算しているだけです. kP の計算過程で  n の非自明な約数が求まるまで,神様に祈りつつ試行を繰り返します.楕円曲線ガチャみたいなものですね.

また, k としては極めて大きな数が使用されるので,この計算にあたっては繰り返し2乗法*3などを用います.

実行結果

大きな数の取り扱いが大変だったので,Python 3 を用いて実装しました.ソースコードはチラ裏レベルのひどい代物なので,実行結果だけの記述とさせてください.

以下が実行結果の一例です.ちょっと出力がシンプルすぎる気もしますね.

f:id:villach:20190317211714p:plain

実際,29130502385925287 = 96600277 * 301557131 です.このくらいの数なら総当たりでも計算可能かもしれませんが,以下の場合はどうでしょう.

f:id:villach:20190317212029p:plain

このくらいの桁数になると,総当たりで計算するのは(少なくとも PC 使用かつ短時間では)不可能でしょう.

計算時間については,手元の PC でだいたい以下のような結果が得られています.入力に使った2つの合成数は,大きな素数2つの積で書かれる,いわば「タチの悪い」ものです.

  • 25227563887000340779(20桁)……約2秒
  • 119798122324797418809504766589(30桁)……約44秒

もっとも,ECM がかなり運ゲー色の強いアルゴリズムであること, k の選択についてあまり最適化をしていないことを考えると,もっと速くなる余地は十分あると思います.逆に,実行状況によってはもっと遅くなることも考えられます.

原理

 n が非自明な素因数  p を持っているとし,位数(要素数 p の体  \mathbb{F}_p 上の楕円曲線  E(\mathbb{F}_p) について考えます.

いま,ステップ 2. で選んだ  k が,幸運にも  E(\mathbb{F}_p) の位数の倍数となっていたとしましょう.このとき, E(\mathbb{F}_p) 上の任意の点  P は, k 倍したら必ず無限遠 O になります*4

 kP無限遠点であるということは, kP を求める式で登場する分母(仮に  d_k とします)が  \mathbb{F}_p 上で  0 となることに他なりません.いいかえると, p d_k を割り切ります.よって, p \mathrm{gcd} (d_k, n) を割り切り,わずかな例外を除いて  n の自明でない約数が得られます.

また,「 k E(\mathbb{F}_p) の位数の倍数である」という条件を満たすためにどうすればよいかを考えると, k をどう選べぶべきかもおぼろげにわかってきます.すなわち, k は約数をたくさん持つように選べばよいのです.これについては流儀が複数あるようです.

 

上述した内容からわかる通り,ECM E(\mathbb{F}_p) の構造に依拠しています.実は,ECM の前身(?)として,Pollard の  p - 1 法が存在します. p-1 法では, (\mathbb{Z}/p\mathbb{Z})^{*} の構造を利用していました.これは  p によって完全に固定されてしまうため, n の因数が「都合よく」なければ,その時点で諦めて試合終了でした.ECM は,代わりに楕円曲線  E(\mathbb{F}_p) を用いることで,仮に試行に失敗しても, E を取り換えて再チャレンジできるようにしています.これが ECM の偉大な進歩なんだそうです.

ECM では, E(\mathbb{F}_p) の位数が重要になってきますが,これについては Hasse の定理 なる定理が存在して, |\#E(\mathbb{F}_p) - p + 1| \le 2\sqrt{p} となることがわかっています.つまり,位数が  p + 1 を中心として  4\sqrt{p} の範囲に散らばっているということです.さらにまた,この「散らばり具合」に関しても 佐藤-Tate 予想という予想*5があって,そこまで偏らずいい感じに散らばっているらしいと信じられています.したがって, E(\mathbb{F}_p) の位数に望みを託す賭けも,そこまで分の悪い勝負ではないということが分かります.

今後の方針

まず,単純に実行速度を追求したいと思います.具体的には,パラメータの選択手法を洗練したり, kP の計算方法を見直したり*6といった手段が考えられます.

また,背景にある数学的理論をより深く知り,見通しの明確化を図るのも一つの目標です.

ECM の実装や理論面の学習は半分くらい高専の授業の枠内で行っているので,授業で得る知見や教員からのアドバイスも活かしていきたいですね.

参考文献

*1:Weierstrass 標準形と呼ばれます.

*2:厳密には射影幾何学を使って考えます.

*3:競プロ界隈の人にはおなじみだと思います.

*4:この辺は認識が曖昧なのですが,Lagrange の定理からしたがうそうです

*5:2019/04/30 追記:指導教員いわく,10年ほど前に証明されたそうです.勉強不足でした.

*6:繰り返し2乗法の他にも,移動窓法や符号つきm進展開法といった手法が存在するようです.

女子小学生でもわかる剰余環の定義

はじめに

この記事きじんで,数学すうがく興味きょうみをもったおんなは,ぼくへ連絡れんらくしてください.個人こじんレッスンをしてあげます.

 

大人の方へ:

厳密性の話はしないでもらえるとありがたいです.

加算・減算・乗算の3つの演算を行える集合を,と呼びます.たとえば,整数全体は環です(整数同士の和差積は全て整数になります.一方,整数同士の商は整数になるとは限りません.たとえば,1/2 は整数ではありません).

同値関係

以下では R を環とします.
R の要素2つ (a, b) を引数として取り,TRUE/FALSE のどちらかを返す関数 f(a, b) を考えます.たとえば,R が整数集合なら,a < b のとき TRUE を返し,a ≧ b のとき FALSE を返す,といった関数などを挙げられますね.
こうした関数を,特別に2項関係と呼びます.また,2項関係は,関数の形で書く代わりに,適当な記号(たとえば ~ とか)を取り,a ~ b と書いたりします.a < b,a > b,a != b なんかは全て2項関係です.

ここで,以下の3条件を満たす2項関係 ~ を特に同値関係と呼びます.

  1. R に含まれる全ての要素 x について,x ~ x
  2. x ~ y かつ y ~ z なら,x ~ z
  3. x ~ y なら y ~ x

たとえば,整数集合での関係 = (等しい)は,明らかに同値関係です.整数 n, m, l について,n = n ですし,n = m かつ m = l なら n = l ですし,n = m なら m = n です.

また,ある整数 k を決め打ちして,「x と y は,それぞれ k で割った余りが等しい」ことを x ≡ y (mod k) と書きますが,これも同値関係です.

剰余環

さて,同値関係を導入すると,「同値な要素は全部ひとまとめにして考える」ということができますね.

たとえば,先ほどの「k で割った余り」について考えます.k = 3 とすると,整数は全て

  • 3 で割った余りが 0 になるやつ
  • 3 で割った余りが 1 になるやつ
  • 3 で割った余りが 2 になるやつ

に分類されます.すなわち,{ …, -6, -3, 0, 3, 6, … },{ …, -5, -2, 1, 4, 7, … },{ …, -4, -1, 2, 5, 8, … } の3分類ができますね.

ここで,それぞれの分類のうち,代表者を一つずつ選出します.別になんでもいいんですが,簡単さのために 0, 1, 2 を取り出しましょう.つまり,

  • 3 で割った余りが 0 になるやつの代表 → 0
  • 3 で割った余りが 1 になるやつの代表 → 1
  • 3 で割った余りが 2 になるやつの代表 → 2

みたいに考えます.

さて,こうすることで,代表者のみを集めた集合を作れます.{0, 1, 2} ですね.この集合を剰余環と呼びます.要するに国会みたいな感じですね.いまは例として 3 で割った余りのことばかり考えていましたが,同値関係として別のものを取れば,いろんな剰余環を作れます.

うれしさ

剰余環では,同値な要素を「ひとまとめ」にして,代表者だけを集めて考えることができます.
これによるうれしさは,間接民主主義を導入するうれしさと一部共通すると思います.古代ギリシャのポリスみたいに,みんなが顔見知りであるほど人数が少なければ,全員の意志を考える直接民主主義が可能ですね.しかし,現代国家のように,人数が爆発しているところでは,代表者を選出し,直接的にはそうした代表者の意志を考える間接民主主義が必要になってきます.

ましてや数学では,集合の要素が無限に存在することがたくさんあります.ここで,手に負えるサイズまで集合を「圧縮」し,しかもその集合をきちんと有意義に扱える(剰余環も環なので,演算ができます!),というのは大変うれしいことです.

特に現代では,有限な演算しかできないコンピュータにたくさんの処理をさせることが多いので,剰余環の効用はかなりありがたいです.先ほど考えた「3で割った余りについての剰余環」とかはかなり使われています.もっとも,こいつは環じゃなくて体になっちゃうんですが.環のままじゃイカン!ってことなんでしょうか.

第26回コンピュータフェスティバル競技部門に参加しました

宇部高専で開催された第26回コンピュータフェスティバルの競技部門に参加し,なんと優勝を勝ち取ることができたので,嬉しさが残ってるうちに記事をしたためておこうと思います.

参加記事は誰かが部のブログに書いてくれると思うので,主に技術的なことを残しておきます.

基本的な気持ち

最良優先探索(priority_queue を使った探索)で5ターン分先読みし,各状態について評価し,もっとも評価値の高かったものを採用するようにしました.

探索結果は保持せず,ターンが進むごとに一から探索しています.

評価関数

以下の5つを評価用のメトリクスとして採用しました.

  1. タイル点による利得
  2. 自チームで領域を形成することによる利得
  3. 相手チームの領域を破壊することによる利得
  4. 自チーム両エージェント間の距離
  5. 移動先での自由度

1. 2. 3. は特に説明しなくても大丈夫だと思います.付け加えるとすれば,領域点よりタイル点の方に多少加重しました.これは理論的な根拠があるわけではなく,テストプレイを積み重ねての実感に依拠しています.領域点を重視すると,いきおい「大風呂敷」を広げがちになり,安定した得点を得られなくなります.

4. についてですが,エージェントがくっついてもいいことはない(とりうる行動が制限される,相手が遠くで策動しているのを防げない,などの弱点ばかりが目立つ)ため導入しました.5. は,自チームのタイルがあらかた置いてあったり,隅っこだったりするところにあまり行かないようにするため設定しました.
これらのメトリクスは,マップのタイル得点の状況に依存しない数値なので,重みを固定した場合,全体として高得点なマップにおいては 1. 2. 3. との不均等が生じてしまいます.そこで,マップのタイル得点の平均値を計算し,それに応じて 4. 5. の重みを動かすようにしました.

また,体感として,タイルによって得点の上下が激しいマップほど領域点が大事になる気がしたので,タイル得点の標準偏差を求め,それがしきい値を超えた場合に 1. の重みを増やすようにしています.

対戦前の時点で,ぼくとソルバで対戦した場合は9割方ソルバが勝つ,くらいの強さまで持っていけていたはず……です.

対戦の結果

1戦目が一番大変でした.与えられたマップが線対称性を前提しておらず,読み込みの時点でエージェント座標をバグらせてしまいました.また,この混乱により,最初の2ターンはロスしました.最終ターンでなんとか逆転して僅差の勝利です.

以降は,上記の不具合も修正し,ソルバも順調に動いたので,基本的にうまく戦えたと思います.たまに,人間からすれば不合理に思える手(-99点のタイルを占領しにいく,序盤10ターンの間ひたすら前進するなど)もありましたが,ソルバを信頼するように努めていました(こう書くと美しいですが,実際には人力モードへの切り替えを導入していなかっただけです).また,コリジョンが連発することもあり,特に決勝では10ターンくらい睨み合っていましたが,この辺も柔軟に対応できるようシステムを作っていなかったので,我を通しつづけた感じです.

所感

この辺の考察を昨年9月の段階でやっておきたかったですね.

基本的なアルゴリズム自体はプロコン本選のものと一緒なんですが,当時は実装力が弱かった(今が強いというわけでもありませんが)ので,かなりひどいコードでした.冬休みの期間にその方面のコードを読み込み,いい感じのプラクティスを吸収できたのが活きてきたんだと思います.