ニュートン法を使って、平方根を求めるアルゴリズムを書いてみよう

Goのプレイグラウンドで遊んでたら、フロー制御の章でニュートン法を使って平方根を求めましょう( A Tour of Go )と言われたので調べた。

 

ニュートン法とは?

ニュートン・ラフソン法(Newton-Raphson method)ともいう。

与えられた関数 f について f(x)=0 になる x の近似解を求める方法である。

例えば、 x^2-2=0 の解である \sqrt{2} 無理数(1.41421356...)である。有効桁数があるコンピューターは、この値を誤差なく持つことは不可能であるが、ニュートン法を用いて計算を繰り返すことで、型が持つ有効桁数の範囲で解に近い値を求めることができる。

 

やってみよう

 Goの問題は、引数として与えられる数( kとする)の平方根( xとする)を求めるアルゴリズム sqrt(k float64)(x float64) を書くというものである。ニュートン法を使って解いてみよう。

引数として与えられた k平方根 xを求めることから、

 k = x^2  より

 x^2 - k = 0 という方程式を解けば平方根が求まる。

 k = 2 のときを例に解法を説明する。以下は x^2 - 2 の曲線とその接線のグラフである。接線は解 x (  = \sqrt{ 2 } )よりも大きな値を適当にとり( \displaystyle x_0 とする)、引いた。

f:id:bambinya:20170124225900p:plain

 

上の図から分かるように、接線の x 切片 \displaystyle x_1 は、 {\displaystyle x_0} {\displaystyle \gt} {\displaystyle x_1} {\displaystyle \gt} x(= \sqrt{ 2 } ) という値をとる。この性質を使い、次は \displaystyle x_1 を元に曲線の接線を引き、 x 切片を求める。これを繰り返すことで、真の解に近づけていく。反復回数が多いほど精度が上がっていく。グラフでは下記のようになる。

 

f:id:bambinya:20170124231411p:plain

 

この反復処理は、 \displaystyle x_1  \displaystyle x_0 で表す漸化式を求めるとfor文で書ける。

 \displaystyle x_1  \displaystyle x_0 で表す式を求める。

接線の傾きは微分で求められる。

 f(x) = x^2 - k

 f'(x) = 2x

 \displaystyle x_0 の時の接線の傾きは 2\displaystyle x_0 であり、これはyの変化量をxの変化量で割ったものと等しい。下記を参照のこと。

 

f:id:bambinya:20170124223222p:plain

 

式にすると、

 2\displaystyle x_0 = \frac{\displaystyle x_0^2 - k} {\displaystyle x_0 - \displaystyle x_1}

両辺に {\displaystyle x_0 - \displaystyle x_1}をかけて整理すると、以下の式が得られる。

 \displaystyle x_1 = \frac{\displaystyle x_0^2 + k}{2\displaystyle x_0}

( \displaystyle x_1  \displaystyle x_0 で表す漸化式。 k is given.)

この漸化式を用いて、Goでfor文を書くと次のようになる。

 

関数とループを使った簡単な練習として、 ニュートン法 を使った平方根の計算を実装してみましょう。( ...

 

おしまい。

 

Rubyのオブジェクトモデルを紹介しました。

speakerdeck.com

zshellを導入したときのメモ

ログインシェルをbashから、zshellに変更した。

brewzshをインストール。

$ brew install zsh
... 🍺 ...

$ which zsh
/usr/local/bin/zsh

システムで有効なログインシェルの一覧を、/etc/shellsで見ることができる。
ログインシェルとは、ユーザーがシェルにログインしたときに、最初に起動するシェルのこと。
Mac OS Xだと、bash以外に csh ksh sh tcsh zsh が入っている。

$ cat /etc/shells
# List of acceptable shells for chpass(1).
# Ftpd will not allow users to connect who are not using
# one of these shells.

/bin/bash
/bin/csh
/bin/ksh
/bin/sh
/bin/tcsh
/bin/zsh

システムにプリインストールされていたzshと、brewでインストールしたzshのバージョンを比較する。
brewからインストールしたzshの方が新しい。

$ /bin/zsh --version
zsh 5.0.5 (x86_64-apple-darwin14.0)

$ /usr/local/bin/zsh --version
zsh 5.2 (x86_64-apple-darwin14.5.0)

/etc/shellsに、/usr/local/bin/zshを追記する。

$ sudo bash -c 'echo /usr/local/bin/zsh >> /etc/shells'
Password:

catで追加されたことを確認し、change shellコマンドのchshを実行する。

$ cat /etc/shells
# List of acceptable shells for chpass(1).
# Ftpd will not allow users to connect who are not using
# one of these shells.

/bin/bash
/bin/csh
/bin/ksh
/bin/sh
/bin/tcsh
/bin/zsh
/usr/local/bin/zsh

$ chsh -s /usr/local/bin/zsh
Password for Bambi:


設定は、~/.zshrcに書く。なければ作成する。
~/.bashrcと~/.bash_profileから、エイリアス環境変数を移せば、完了です〜 😋

ターミナルからgemを使うときにバージョン指定する

忘れちゃうのでメモ。

$ rails _5.0.0.beta3_ new AppName

$ pry _0.9.12.2_

pryのバージョンを確認したいとき

f:id:bambinya:20160508111134p:plain

でできます。

 

RubyのClassクラスについてとか、クラスを知るためのメソッドとか、あれこれ(メモ)

Ruby

MyClass.class            # => Class

MyClass.class.class   # => Class

という結果に Σ(・∀・;) となったので調べた。

 (.classはオブジェクトが定義されたクラス名を返す。)

 

まとめ

Rubyでは、定義されたクラスは全て、Classクラスのインスタンスとなる。

Rubyでは、扱われる全ての要素はオブジェクトで(何らかのクラスのインスタンスで)、Objectクラスのインスタンスメソッドを継承している。(Object#classとか)

どうやら、MyClass.classで返る"Class"も、クラスであり、オブジェクトであり、Classクラスのインスタンスとして扱われるため、その結果、MyClass.class.class #=> Class が返るらしい。(難しいなぁ。考え方合ってるのかなぁ。。)

 

やってみよう!

f:id:bambinya:20160110135338p:plain

StringやArrayなどの組み込みクラスも、自分で定義したMyClassも、.classを実行するとClassが返ってくる。

Rubyで扱う全ての値はオブジェクトなので、Objectクラスが持つインスタンスメソッドを継承している。あるクラスが持つインスタンスメソッドを見たいときは、instance_methodsを使う。(↓こんな感じ。)

f:id:bambinya:20160110142407p:plain

 

MyClass.classが返すのは、Classクラスというオブジェクトである。

f:id:bambinya:20160110150442p:plain

Classクラスは"クラス"の一つなので、オブジェクトであり、また、Classクラスのインスタンスであることから、MyClass.class.class #=> Class という結果になるみたい。

 

ちなみに、あるクラスがどんなクラスやモジュールを継承したりインクルードしているかを見るにはancestorsを使う。

出力結果の、配列の順番は、[クラス自身、親クラス、親の親クラス..]となる。クラス名の間にインクルードしているモジュール名がちょこちょこ入ってくる。

実行結果。

Rubyで扱う全ての値はオブジェクトなので、ClassクラスもObjectクラスを継承していることがわかる。)

f:id:bambinya:20160110145829p:plain

 

おしまい。m(__)m

 

emacs key bindingメモ

キーバインドのデフォルトで

C-h がHELPの設定になっていたので、 ~/.emacs.d/init.el ファイルに下記マクロを追加。シンタックスemacs lisp.

(keyboard-translate ?\C-h ?\C-?)

Function: keyboard-translate from to
この関数は、文字コードfromを文字コードtoに変換するように keyboard-translate-tableを変更する。 必要ならばキーボード変換表を作成する。

*1

 

画面操作(ファイル開閉、emacsプロセスの開閉、画面分割と移動、画面削除、ミニバッファから離れる)

  • C-x C-c KILL TASK
  • C-z SUSPEND TASK (fg → foreground)
  • C-x C-f OPEN FILE
  • C-x C-s SAVE FILE
  • C-x 2 split-window-below
  • C-x 3 split-window-right
  • C-x o SELECT ANOTHER WINDOW
  • C-x 0 DELETE SELECTED WINDOW
  • C-] KILL MINIBUFFER

エディタの移動(上下左右の移動)

  • C-p UP
  • C-n DOWN
  • C-b BACK
  • C-f FORWARD
  • C-a GO TO BEGINNING OF LINE
  • C-e GO TO END OF LINE
  • C-o OPEN LINE
  • M-v PAGEUP
  • C-v PAGEDOWN
  • M->(Shift + .) Move to the END of the buffer
  • M-<(Shift + ,) Move to the TOP of the buffer

エディタの操作(文字の削除、行の削除、選択範囲の削除、やり直し)

  • C-h BACKSPACE
  • C-d KILL FORWARD CHARACTER
  • C-k KILL LINE
  • C-w KILL THE REGION(バッファに保存される)
  • C-_ UNDO

 

コピペしたいときのステップ

  1. C+space key(Mark Set)
  2. M+w(copy)
  3. C+y(paste)

 

検索

  • C-r SEARCH

 

置換

  1. M+%(Shift+5)
  2. 置換したいテキスト入力、RET
  3. 新しいテキスト入力、RET
  4. !  (to replace all remaining occurrences without asking again.)

GNU Emacs Manual: Query Replace

 

一括インデント

  1. C+space keyで範囲選択
  2. CM+\

 

一括コメントアウト

  1. C+space keyで範囲選択
  2. M+;

 

操作の解除

  • C+g 実行中の全ての操作をキャンセル

おわり

JavaScript 関数のカリー化と部分適用

引数を複数とる関数から、いくつかの引数を固定値で束縛した新たな関数を生成する。これにより、関数を使うたびに同じ値の引数を入力する手間が省け、見た目も簡潔なプログラムになる。

 

カリー化とは、複数の引数を取る関数を、1つの引数のみを取る関数のチェーンに変換する処理のこと。

みてみよう!

js curry function

 

部分適用とは、複数の引数を取る関数を、それより少ない数の引数を取る関数に変換し、除外された引数には最初から値を指定しておく、という処理のこと。

関数に対して複数の引数を部分的に適用し、残りの引数で構成される関数を新たに作成する。

みてみよう!

js bind method

※bind()メソッドは呼び出されたときに新しい関数を生成する。第一引数は新しい関数のthisキーワードにセットされる。第二引数以降は、ターゲット関数の引数として、第一引数から順に与えられる。