ﾕﾕﾕﾕﾕ

webエンジニアです

C++ のコンパイル環境を変更した

C++

　vscode の devcontainer で debian コンテナを立てて、その上でコンパイルしていた。こうしていたのは単に <bits/stdc++.h> を楽に使いたかったからにすぎない。いろいろカスタマイズを頑張るより先に、手っ取り早くコンパイルできる環境を用意したかったのである。こうして作った環境を特に不自由なく利用していた。

　ではなぜいまになって見直したか？　ac-library の環境構築をするためである。かつてと同じように、さっさと動作する環境を手に入れたかったので、深く考えずに実施した。

　ローカルにライブラリをおいて、ローカルでコンパイルするようにした。 homebrew で gcc をインストールして、これを使うように設定しただけである。 docker イメージにライブラリを含めるとか、面倒かつ本質的でない作業に逸脱せずにさっさと済ませられて満足している。コンテナ定義は不要になったので捨てた。

Enable ac-library by sato11 · Pull Request #1 · sato11/atcoder

　一周回って、実直な環境構築に回帰したわけである。単にコンパイルするためだけのお膳立てなので、ただちに不便になるようなことはないだろう。

gcc のインクルードパスを確認する

C++ TIL

　C++ のライブラリをローカルの開発環境でインクルードできるようにしたい。また #include <aws/dynamodb> のように、相対パスではなく <> でインクルードしたい。

　正しいインクルードパスにヘッダファイルを配置してあげればいいはずだが、そのインクルードパスを忘れてしまった。過去に同じ作業をしたことはあるはずなので、マシン上のどこかにあるのは確かなのだが、どこにあるだろうか…。

　次のワンライナーが教えてくれる。

gcc -x c++ -v -E /dev/null

　出力はこうなる。 /usr/local/include が目的のパスであった。

Apple clang version 11.0.3 (clang-1103.0.32.62)
Target: x86_64-apple-darwin19.6.0
...
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/include
 /Library/Developer/CommandLineTools/usr/bin/../include/c++/v1
 /Library/Developer/CommandLineTools/usr/lib/clang/11.0.3/include
 /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include
 /Library/Developer/CommandLineTools/usr/include
 /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/System/Library/Frameworks (framework directory)
End of search list.
...

　蛇足。あとになって気づいたが、このパスは自分で環境変数として定義していたのだった。

export CPLUS_INCLUDE_PATH=/usr/local/include

2021年の生活規範

生活

　元日にあわてて立てた目標は決して根付かないだろうと信じるので、お試し期間の一週間に吟味し、決意しているところを掲示しておく。「○○をする」という形式はおのずと努力目標にならざるをえないだろう。強い制約として日常生活をしつけるために、「○○をしない」という禁止の形式で4箇条を定義することにした。

  1. 副業をしない
  2. 新刊本を買わない
  3. 新しい技術に踊らされない
  4. 食事中にビデオをみない

副業をしない

　副業を依頼されて嫌な気分はしない。「自分は名指しで依頼されるだけの実力の持ち主なのだ」といい気分にさせられる。しかしこれは単なる虚栄心である。

　仮に生活に困窮してしまったとして、そのときに副業というアディショナルな選択肢を持てるのは幸福なことである。ただしいまの僕はそれを求めない。自分なりに納得のいく金額で評価をもらえている現状、それを超えて金を求めるモチベーションはわかない。

　モチベーションとしては、稼働を増やす方向付けよりも、単価を上げる方が望ましい。少ない稼働で同じ収入を得られるのは魅力的に思う。とはいえこれは今年単年の目標にはなり得ないので、いまは考えないでおく。

新刊本を買わない

　スマホブームの揺り戻しなのだろうが、本を読むことすなわち教養というやや短絡的な逆張りが目立つ。「積読」という言葉を肯定的に捉え直してみたり、「巣篭もり需要」とかにかこつけて本を売ろうとする隠然たるマーケティングも多く感じた。

　出版は掛け替えのない産業と思うし、本を売りたい気持ちもわかりたいと思う。しかし怪しいブロガーや起業家に書かせた安い本からヘイト本まで、売れそうとみるや恥も外聞もなく売りにかかる姿勢は堕落そのものである。

　話題先行であったり、明らかに広告が優位な出版物とは距離をおきたい。あらゆる新刊はプロモーションを伴うとして、新刊は一切買わない、と割り切ってしまうことにする。

　時間の審判に耐えた書籍だけを読む。そして読むと決めたものについては精読する。1年で10冊も読めればそれでいいと思う。その体験をどれだけ豊かにできるかは読み手の僕自身にかかっているというだけの話である。

新しい技術に目を奪われない

　トレンドは次々にやってくる。しかしそれらの宣伝をみても、正しく意義を理解できないことの方が多い。どんなパラダイムに属していて、どんな課題を解消する技術なのかがうまく飲み込めない。

　よくわからないまま踊り始めることを悪くは言わない。現に僕自身、そうして学んできたところは大きい。しかしいくらか成長してみて、踊っているつもりが実は踊らされているだけだったと知るのはあまり嬉しくない。

　まずは枯れたパラダイムを明晰に理解することが必要だ。 teachyourselfcs.com がよいコンパスとなる。その上で、乗るべきハイプを見極めて踊ることも必要だ。踊る人々を見て、単に冷笑して見せるだけというのは醜い。ある技術にベットするのは、張り間違えたとしてもそれが掛け替えのない学びとなるのであれば、そう悪くない。ギャンブルに見立てるならば、早いフェーズで乗るかそるかを決めてしまい、引くに引けなくなるのが最悪だということだけ注意を払っておけばよい。

食事中にビデオをみない

　一人で食事をするときに、 Netflix なり YouTube なりを再生しながら食事するのをやめること。これは単純な悪癖であるが、あまりに常態化してしまっている。「ながら食べ」は行儀が悪いと自分自身をしつけ直す。実際、そこまで慌てて消費なければならないコンテンツなどない。

　いっそ、これら動画プラットフォームと縁を切られれば人生の充実度は確実に高められるだろう。「YouTube は今後一切みないことにして、余暇には読書しかしない！」という目標を立てるのもよい。ただこうした抑圧は揺り戻しを伴うから、あえてそうまではしない。まずは最低限、食事中のマナーを正しくする。それができたら、段階的に引き締めていく。

AtCoder の茶色難度の過去問をコンプリートした

生活

　緑難度に取り組んでいると前に書いた。結果的にこれはハイプで、実際には difficulty 1000 前後の問題には歯が立たないことの方が多かった。

　徒手空拳でぶつかり続けてもただ自信をなくすばかり。まずはできるところからやらねば、という思いで、茶色難易度の過去問に取り組んでいた。そして今日、すべての過去問で AC するに至った。

f:id:jnsato:20210102092308p:plain

　解法の手がかりさえつかめないようなことはもはやない。茶色レベルであればそれなりにスラスラ解けるという自信は新たにできた。ただポカで WA することもまだ多いし、20問に1問くらい、着想に時間をかけてしまうことがある。これから緑色の過去問に取り組むうちに改善するだろうと期待したい。

　気付きとして、同じ茶色でも最近の問題の方が難易度が高いように思った。このごろレーティングが厳しくなっているという話に通じるのだろうか。昔であればスコアとしてはいまより容易に稼げたということなのかわからない。

　ただスコアはスコア、実力は実力である。数字を追いかけるよりもたしかな技術を身に着けるというアティチュードをもつのがよいのはたしかだ。間違えることを恐れるよりも、解けたときの気持ちよさを大切にして、またがんばってみよう。

ラップ・アップ・ニーマルニーマル

生活

1月

　ベルリンからブダペストまで鉄道旅行をした。大陸はどこまでもつながっている、という素朴な感動をえた。滞在したのは次の7都市。

滞在記は私的な日記にのみ書いた。この頃はまだブログを持っていなかったため。

2月

　アテネ・カイロ・ローマへ旅行した。まだコロナの存在感は薄かった頃のこと。いま思えば平和で幸福な旅行だった。

　旅行の前後では塩野七生の古代アテネ衰亡史を読んでいた。文明も民主主義もはかないものかという悲観と、いまある文明はきっともっとうまくやれるだろう、という楽観。そのどちらであろうと、僕ひとりが思い悩んだところで何も変わらないだろうという諸行無常の感覚。

3月

　外務省からドイツに滞在注意報が発令され、渦中のドイツから帰国した。帰国直前のデイリー感染者は200-300人。これが帰国後とんとん拍子に1000人、1万人と拡大してしまう。

　帰国後は秋田の実家に滞在していた。国内はいわずもがな、ヨーロッパ・アメリカの方からはいっそう陰惨なバッドニュースが伝えられ、気が滅入ってしまう。

　このころ Qiita を退会してブログを開設した。

4月

　松坂和夫『集合・位相入門』を読む。序盤の100ページほどのみ、わかるまで食らいつくような態度でじっくり読んだ。ある時までてんで読めなかった文章が、一瞬のひらめきによって単純明快そのものに変貌する。そんな体験が数度あった。どんな分野でも、専門書を読むのには教育と修行が必要であると知らされた。

『カラマーゾフの兄弟』、『燃え上がる緑の木』と大長編小説を立て続けに読んだ。

5月

　前年から少し触っていたC++を使って、 AtCoder に初挑戦した。 Ruby は使わない縛りを自分に課して、プログラミングの感覚をイチから鍛え直そうと努めた。過去問を解くのにも熱中していた。

　エージェント経由で業務委託の面談をうけた。すべての面談がオンライン化していて、楽ではあったが結果は出なかった。3社を受けていずれも落ちる。心の準備がまだできていないのだろうと諦めて、もうしばらく勉強期間を継続することにする。

6月

　1年ぶりに東京に戻る。このころは勉強内容をまとめたブログ記事を毎日投稿していた。記事を公開することに対する心理的障壁は劇的に下がった。

　以前より興味のあった Hanami フレームワークを試してみたり、『クリーン・アーキテクチャ』を再読してレイヤリングの考え方を再訪したりしていた。

7月

　縁あって以前お世話になっていた会社から業務委託案件を受注した。月初から稼働開始した。

jnsato.hateblo.jp

　Project Euler に初挑戦し、50問までトントン拍子に進められた。ここでも C++ だけを使う縛りを自分に与えていた。

jnsato.hateblo.jp

8月

　nand2tetris に取り組み始めた。

jnsato.hateblo.jp

　フィリップ・K・ディック作品をいくつか読んだ。『アンドロイドは電気羊の夢を見るか？』『高い城の男』そして『マイノリティー・リポート』。

9月

　森美術館にスタア展をみにいった。顧客体験としてよいとは思えなかった。作品というよりは、もっぱらオペレーションの問題である。広告費が大量投入された美術展は地雷と思うのが無難か。

　勤労・学習のどちらにおいても、モチベーションが低下してしまった時期であった。なんのために働くのだろう？　というようなことばかり考えていた。

jnsato.hateblo.jp

　ジム通いを再開した。人生初のパーソナルトレーニングも経験した。結局のところ、学習効率を高めるにはプロに教えを請うことである。生徒としてのアティチュードには注意している。自我は消し、トレーナーの言うことは神の啓示と思って取り組むのがよい。「コーチャビリティ」という概念はあとから知ったが、要はそういうことだろう。

『真田丸』を見るべくして、毎週ツタヤに通っていた。ストリーミング疲れした精神にとってツタヤはオアシスである。古典も駄作も、アイウエオ順にソートされてフラットに陳列されているのは荘厳である。推薦エンジンに馴致されるあまり、「自分の観たい映画は自分で決める」という最低限の主体性すら失ってはいまいか。ツタヤは救済である。

10月

　転職活動を開始した。労働、運動、企業研究に明け暮れた月だった。この上なく合理的な生活リズムだったが、振り返ってみると無味乾燥にならざるを得ない。

11月

　志望企業をふたつに絞り、月末には一社から内定を得た。

　勤労感謝の日が三連休にあたるので、大阪旅行を計画した。大阪らしい何かを読もうと思って、谷崎潤一郎をまとめて読んだ。『細雪』『卍』『少将滋幹の母』そして『吉野葛』と読破。大長編ながら読みやすい名作である『細雪』と、技巧を技巧と思わせない熟練味をたたえた『少将滋幹の母』がお気に入り。

　大阪では太陽の塔を見物した。異形の造形と突き抜けたスケール感で、人生ベスト級の芸術体験を味わった。並いる現代作家のなかで、どうして岡本太郎ただひとりがこれだけの仕事をできたのかはミステリーである。そしてそれがミステリーであるゆえに、これだけの成果を国内で再現することは永久に不可能だろうと思う。

　芦屋の谷崎記念館も訪ねた。直筆原稿、書簡のたぐいをみた。飼い猫のシャムに「タイ」と名付けていたということを知って、いいセンスだと思った。

　月末にはツイン・ピークスの旧シリーズを一気見した。

12月

　転職の意志を業務委託元に伝えた。ありがたいことに引き留めてもらうことになり、改めて自分の行く末を考える機会となった。いろんな人と話し、異なる観点からキャリアについてのアドバイスをもらえたのは財産である。自分の直感を信頼して、転職の道をとることに結論づけた。

　分散システムについての概論書である Designing Data-Intensive Applications の読書に取り掛かる。

jnsato.hateblo.jp

　図書館に通い、海外小説もいくつか読破した。話題作とはいえハードカバーは高価だからと敬遠していた中国産SFの『三体』も読んだ。結果、まんまとファンになってしまい、きっと第三部が出版されるときに、あらためて買い揃えることになりそう。

『ベン・ハー』『風と共に去りぬ』『サンセット大通り』と3本の古典映画もみる。名作と呼ばれるだけあって内容は大充実である。人海戦術と言っていいほどに潤沢なモブの使い方、圧倒的に配慮の行き渡った衣装や小物にセット、そしてそれらを「これでもか！」と惜しげなく披露してくれる俯瞰ショット。すべてが最高で大満足だった。平時に鑑賞するには重すぎるからこそ、年の瀬にまとめて味わえて幸福であった。

平方三角数

TIL

平方数でも三角数でもある最初の 2 つの数は 1 と 36 である。次に小さな例を見つけよう。できれば、その次の例も見つけよう。三角数でありかつ平方数でもある数を見つける有効な方法を見つけることはできるだろうか？　こうした性質をもつ数は無数にあると考えられるか？
-- ジョセフ・H・シルヴァーマン 著, 鈴木治郎 訳, 『はじめての数論』練習問題 1.1 より

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

　数論の本を読んでいる。コンピュータの使用について、節度を守って使うよう前書きで注意されていた。プログラムで答えを知るだけでは理解したとはいえない、という読者への警句である。

考えたこと

　で、冒頭の練習問題である。著者の指示を守って、コンピュータは使わずに計算するところから始めた。「次に小さな例」が 1225 であることは見つけられた。しかし結局「その次の例」には手計算では辿り着けず、プログラムを書いた。

1, 36, 1225, 41616, 1413721, 48024900, ...

　こういう数列をえられた。しかし、次の数を探索する「有効な方法」については、結局プログラムに頼るのが有効、ということしかいえなかった。そして、この数列が無限に続くかどうかには答えを見つけられなかった...。

答え合わせ

　wikipedia に 平方三角数 の項目があった。この呼称も初めて知った。

　一般項が与えられていたから、いちおう自分でも計算してみた。当たり前だが、きちんと答えが求められた。

　公式を導く手順については、手続きに組み込まれた「ペル方程式」をそもそも知らず、追いきれなかった。ただ、いまは少なくとも名前と形は認識したから、きっと近いうちに学ぶことになるだろう。いまはまだそこまでは踏み込んでいない。

　とはいえ、 \dfrac{n(n+1)}{2}=m^{2} の形で式を立てるところまでは、初見でも不足なかったはず。そもそも愚直に計算するプログラムを作るところで思考が止まっていて、立式してみるという発想を持てていなかった。思考がコンピュータに依存している傾向の現れであって、これに対してこそ著者は警鐘を鳴らしていたのだろう。つまり、「単にプログラムで答えを知ることで満足してはならない」という警告は、他ならない僕に向けられていたのだった。

終わりに

　こうした反省と自己批判の意識から、こうして記事に残しておく。これが記事公開にいたったひとつの動機付けである。

　もうひとつは、第三の平方三角数 1225 がちょうど今日の日付とかちあっていることに不思議を覚えたため、なんとなくの記念の気持ちで書いている。

1 + 2 + 3 + \cdots + 49 = 35^{2} = 1225

merry christmath!

合同式におけるモジュラ逆数 (mod_inv) の求め方

C++

　合同不定式 ax\equiv 1{\pmod {m}} を x について解く。

　 ax = 1 という不定方程式であれば、両辺に a の逆数 a^{-1} = \dfrac{1}{a} をかけて x = \dfrac{1}{a} としてあげればよい。

　同じように合同式 ax\equiv 1{\pmod {m}} においても両辺に a の逆数をかければ x が求められる。ただしこの文脈では、単に「 a の逆数」と言うよりも「 m を法とする a の逆数」と呼ぶのが正確である。単に「逆数」や「逆元」とだけ名指すことも可能とはいえ、合同式における逆数は拡張された概念であるため、単に分数のような計算を想像すると誤る。 wikipedia では「モジュラ逆数」という項目にまとまっているように、特殊な手続きを必要とする逆数であると認識しなければならない。とはいえ、例えば atcoder/ac-library においても modinv.hpp に inv() が定義され、この計算がまとめられていることから、多くのユースケースを伴う汎用的な概念であるのだろうと思っている。

　僕自身はそもそも合同式にすらさほど慣れ親しんでおらず、このあたりの概念についてはまだわからないことだらけである。だからこそ、まずはこうして学んだことを記録するところを第一歩とし、将来より高度な考察に至れるようにと願いを込めながら書く。

　以下はいくつかのソースから得た情報を僕なりに解釈したものとして読んでもらえればと思う。基本的に知識を持たないところにバラバラな資料を与えて理解を構築しているから、誤った論理もあると思う。誤謬は修正できるように未来の自分自身に期待するが、読者におかれては以上のような前提をもった上で読んでほしいと思う。

問題

　 ax\equiv 1{\pmod {m}} を x について解く。

問題文の読み替え

　問題文は次のように、 x についての合同式に変換できる。

ax\equiv 1{\pmod {m}} \Longleftrightarrow x \equiv a^{-1}\times 1{\pmod {m}}

　ここで現れる a のモジュラ逆数を x’ とおいて、さらに次のように式変換する。なお、 a と m は互いに素であるとする。

\begin{align} x’\equiv a^{-1} {\pmod {m}} &\Longleftrightarrow ax’ \equiv 1 {\pmod {m}}\\\ &\Longleftrightarrow ax’ \times my' \equiv 1 {\pmod {m}} \end{align}

　つまり一次不定式 ax’ + my’ = \gcd(a, m) を満たす任意の x’ を求めれば、それがそのまま a のモジュラ逆数 x’ のひとつの元となることにある。「ひとつの」と書いたのは、法を m とする合同式を満たす x’ は無限に存在し、ここで求めることのできる任意の x’ はその合同類のうちのひとつでしかないためである。とはいえ、解答する上では x’ は任意の一元で構わず、これは問題にならない。

一次不定式の特殊解を求める

　 ax’ + my’ = 1 を満たす任意の x’ を求めるには、適当な特殊解を見出せばよいのであって、一般解を導く必要はない。特殊解を求めるにあたって、例えば次の不定式を見てみよう。

4x + 5y = 1

これを見ると、 (x, y) = (-1, 1) と直感的にひとつの解を見出すことができるだろう。そしてこのときの x = -1 こそが、 4x \equiv 1 \pmod {5} における 4 のモジュラ逆数なのである。実際、明らかに 4 \times (-1) \equiv 1 \pmod{5} である。

　一次不定式の解法に戻ると、上のように係数が小さなケースでは単純な論理や推測で x を求めることができた。しかし、大きな二つの係数の最大公約数を解とする、次のような不定式はどうであろうか。

2021x + 1763y = \gcd(2021, 1763) = 43

これについて、直感ないし暗算で (x, y) のペアを見出すのは困難であろう。ではどうするか？

　実はここで、二つの係数 2021 と 1763 についてユークリッドの互除法を適用すると、ひとつの x, y の組み合わせが求められる。手続き的な計算手順としてはこうなる。

　まずは係数とその剰余を、剰余が発生しなくなるまで切り下げていく。これは一般的なユークリッドの互除法である。

\begin{align} 2021 &= 1763 \times 1 + 258\\\ 1763 &= 258 \times 6 + 215\\\ 258 &= 215 \times 1 + 43\\\ 215 &= 43 \times 5 \end{align}

　続いて今度は、上記のそれぞれの計算過程における剰余を根拠に、 2021x + 1763y = 43 の形を復元していく。つまり

\begin{align} 258 &= 2021 - 1763\\\ 215 &= 1763 - 258 \times 6\\\ & = 1763 - (2021 - 1763) \times 6\\\ & = -6 \times 2021 + 7 \times 1763\\\ 43 &= 258 - 215\\\ &= (2021 - 1763) - (-6 \times 2021 + 7 \times 1763)\\\ &= 7 \times 2021 - 8 \times 1763 \end{align}

　以上より 7 \times 2021 - 8 \times 1763 = 43 が求められる。つまり

\begin{align} 2021x &\equiv 1 &\pmod{1763}\\\ x &\equiv 1 \times 2021^{-1} &\pmod{1763}\\\ x &\equiv 7 &\pmod{1763} \end{align}

このように解くことができる。

アルゴリズム

　こうして確立することのできた手続きを、今度はアルゴリズムに実装していきたい。すでに材料は出そろっているから、あとはコードに置き換えていくだけ…と言いたいところだが、再帰を制御するやり方にまだしっくりきておらず、いまは写経したもので間に合わせておく。

　なお、モジュラ逆数が存在する必要十分条件は「 a と m が互いに素であること」であるが、ここでは a と m をそれぞれ \gcd(a, m) で除算してから演算を行うことで、 a と m は必ず互いに素 \Longleftrightarrow \gcd(a, m) = 1 であることが保証される。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }

  ll d = ext_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

ll mod(ll a, ll m)
{
  return (a % m + m) % m;
}

ll mod_inv(ll a, ll m)
{
  ll x, y;
  ll g = ext_gcd(a, m, x, y);
  return mod(x, m / g);
}

int main() {
  // 3x ≡ 1 mod 7
  cout << mod_inv(3, 7) << endl; // 5

  // 3x ≡ gcd(3, 11) = 1 mod 11
  cout << mod_inv(3, 11) << endl; // 4

  // 1071x ≡ gcd(1071, 1029) = 21 mod 1029
  cout << mod_inv(1071, 1029) << endl; // 25

  // 2021x = gcd(2021, 1763) = 43 mod 1763
  cout << mod_inv(2021, 1763) << endl; // 7

  return 0;
}