パンの木を植えて

主として数学の話をするブログ

トップ > シルヴァーマン『はじめての数論』 > 整数論のために計算機環境を整備する- Exercise 6.3(b)

整数論のために計算機環境を整備する- Exercise 6.3(b)

シルヴァーマン『はじめての数論』
\[ %%% 黒板太字 %%% \newcommand{\A}{\mathbb{A}} %アフィン空間 \newcommand{\C}{\mathbb{C}} %複素数 \newcommand{\F}{\mathbb{F}} %有限体 \newcommand{\N}{\mathbb{N}} %自然数 \newcommand{\Q}{\mathbb{Q}} %有理数 \newcommand{\R}{\mathbb{R}} %実数 \newcommand{\Z}{\mathbb{Z}} %整数 %%% 2項演算 %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \]

-Silverman『はじめての数論』の演習問題を解いていたところ，計算機を動かすことを要求されました．

はじめての数論 原著第4版

はじめての数論 原著第4版

Amazon

上のアルゴリズムを好みのコンピュータ言語を使ってコンピュータ上に実現せよ． シルヴァーマン『はじめての数論』第4版 問6.3(b)

上のアルゴリズムというのは，前回やったEuclidの互除法アルゴリズムのことなんですけど．


なんだか楽しそうなのでやってみることにします．何から始めたらいいのかわからないんですけど，まあ多分やればできるでしょう．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]


環境構築したい

プログラミングはやったことがないので，なにもかも手探りです．TeX の類推でいうなら，とりあえず最初に環境構築をしないといけないはずです．このときに

  1. ローカルに構築するか

  2. クラウドサービスを使うか

2つの選択肢があります．

テキストエディタとしてよく VSCode を使っているので，とりあえず VSCode を使ってローカルにやれないかちょっと調べてみましたが，どうやら TeX と同じで結構面倒なようですね．できれば Web 上でやってしまいたいものです．

VSCode で python 周りの拡張機能を調べていると jupyter Notebook なるものをよく目にします．jupyter……なんかおしゃれな名前！なんなのか調べてみることに．

とりあえず jupyter notebook の公式サイトに飛び，try と書いてあったのでクリック．

なんだか楽しげな画面になりました．いいね．

気分だけはいろいろできそうでルンルンです．プログラミング言語知らないから出来やしないけどね！


jupyter notebook をいじる

なんだか楽し気な画面が出てきてしまったので，何にもわからないけどちょっと試してみようかと思います．

新規でなんぞ書くにはここを押したらええか．

それっぽい雰囲気がムンムン出てるのでとりあえずクリック．


コードを打ってほしそうな画面になったので，お望み通りコードをうっちゃります．なんとなく print とか打ったら出力するやろという偏見がプログラミング言語に対してあるので，print(x) と打ってみたら正解でした．

いけるじゃん．

なんだかよくわからないけど，もうこれでEuclidの互除法書けるんじゃないのか．（謎の自信）


互除法を書いてみる

というわけで環境構築すっとばして，もう互除法書いちゃおうかと思います．

改めて，今回 python コードにしたい疑似コードはこちら．

f:id:seasawher:20220215000432j:plain

まあ行列は成分ごとに書き直せば大丈夫でしょう．

とりあえずコメントアウトの記号を調べておかないと．調べたら# でした．なるほど．

あと，整数の割り算が実行できないといけない．商と余りを取得しないと．調べたら，// が商で % が余りだそうで．

とりあえずここまで書いた．

# Euclidの互除法
a = 
b = 
###
x = 1
g = a 
v = 0
w = b 
while w != 0:
    q = g // w
    x = v
    g = w
    v = x - q*v
    w = g - w*q
y = (g - a*x)//b
return g

$a$ と $b$ に適当な具体的な数値を入れて run させてみると，エラーになってしまいました．どうやら return という命令に問題があるらしいです．

直してみました．

# Euclidの互除法
a = 24
b = 32
###
x = 1
g = a 
v = 0
w = b 
while w != 0:
    q = g // w
    x = v
    g = w
    v = x - q*v
    w = g - w*q
y = (g - a*x)//b
print(g,x,y)

でもダメだったんですよ．

なんでダメなんだろうなぁと考えた結果，変数を代入してる順序がまずいんだなということに気づきました．

適当に仮変数に値を入れて保存しておいて，代入しても値が変わらないようにしておかないといけないっぽいです．それはまあそうか．

というわけで修正した結果がこれ．

# Euclidの互除法
a = 
b = 
###
x = 1
g = a 
v = 0
w = b 
while w != 0:
    q = g // w
    t = g % w
    s = x - q*v 
    x = v
    v = s
    g = w
    w = t
y = (g - a*x)//b
print(g,x,y)

まあうまくいきましたが，ちょっと見づらいコードですね．

疑似コードでやってたみたいに変数を行列で管理して，一斉に代入したりできないのかなぁ？後で調べてみます．


感想とまとめ

環境構築くらいはやってしまうつもりだったんですが，なんもしてないのに目標の課題が終わってしまいました．したがってこの記事もいったんここで終わりです．

シルヴァーマンの本の演習問題にはまだまだ続きがあるので，いったん仕切り直してまたやっていきたいと思います．いちおう注意しますが，python の環境構築はかなり雑にやってます．あんまり真似しない方がいいかもしれません．


追記: 第2回の記事はこちら．