平方根の計算アルゴリズム
今日聞いた、平方根を計算アルゴリズム。
日本では教えているんじゃないの？と言われたけど、知らなかった！
そしてググっても見当たらないのでメモ。
以下、例として を求める。
(25, 5) というペアからスタートする *1。 なら (5n, 5) という形。
(左の数) >= (右の数) のときは、(左の数) - (右の数) を新しい左の数、(右の数) + 10 を新しい右の数とする。
25 - 5 = 20、5 + 10 = 15 なので、ここでは (20, 15) となる。この操作を A と名付けよう。
このペアも (左の数) >= (右の数) なので、再び操作 A を適用する。20 - 15 = 5、15 + 10 = 25 なので、新しいペアは (5, 25)
(左の数) < (右の数) のときは、(左の数) * 100 を新しい左の数、(右の数) は一の位と十の位の間に 0 を入れる。
5 * 100 = 500、25 → 205 なので、ここでは (500, 205) となる。この操作を B と名付けよう。
これらを好きなだけ繰り返す。
(25, 5) →A (20, 15) →A (5, 25) →B (500, 205)
→A (295, 215) →A (80, 225) →B (8000, 2205)
→A (5795, 2215) →A (3580, 2225) →A (1355, 2235) →B (135500, 22305)
→A ...
さて、操作 B の間にある A の数を数えてみよう。
2 2 3 ...
となっている。さらに調べていくと、
2 2 3 6 0 6 7 9 ...
となるはずだ。2.2360679...
これは ...！
教えてくれた方の話によると、近似ではなく、延々求めていくと延々近くなるそうです。
開平法ぐらいしか知らないのですが、習ったことがある！という方が居たら教えて下さい :-)
*1:本当は縦書きのほうが分かりやすい
2010年
何となく、今年を振り返る。
ほとんど日記を書いていないのに、ここで振り返っても仕方ない気もするけれど…。
- 1 月 - 3 月:
- ぎりぎりの精神状態で論文提出。
- なぜか accept (条件付き) される。読み直したら、ひどかった… !
- 発表時にはそこそこ動く実装が出来ていたのは、我ながら不思議。
- 4 月
- 学会参加。
- 火山の影響があったな !
- 5 月
- 学振などの書類作成に腐心。
- 自分の研究を見つめ直す、いい機会だったんじゃないかな (遠い目)
- 6 月・7 月
- 修論書きとか。
- 8 月
- 韓国に行ったり、
- 名古屋に行ったり。
- OCaml Meeting や Coq 庵は楽しかった :-)
- 9 月
- 研究室合宿
- 修了
- 10 月 - 12 月
- 入学
- Agda2 と戯れたり、
- 京都に行ったり、
- お客さまが来たり、
- 韓国に行ったり。
とくに今月は忙しかった…。
こう振り返ると、10 月から殆ど何もしていない気がしてくる (研究で)。
真面目にやらないと駄目な理由が出来たので、来年はもっと eager に、かつ楽しみながら、色々なことに取り組みたい。
今年はネットの情報に助けられたこともあり、読める文章を書いておく意義も感じつつあるから … 来年はもう少し日記も書こうかな。
来年の目標は、来年書く。
面接
終わり。
珍しく緊張しなかったけど、どうなることやら。
人事を尽くして天命を待つ。
Agda
Agda のインストール for Mac OS X (Leopard & Snow Leopard) が成功したので、メモ。
- haskell-platform を入れる。
MacPorts から入るのは古いらしいので、本家から。
http://hackage.haskell.org/platform/mac.html
- cabal 実行
cabal update
cabal install Agda-executable
- .emacs 編集
(load-file "/Users/hoge/.cabal/share/Agda-2.2.8/emacs-mode/agda2.el")
# hoge のところは変更。
- 標準ライブラリを持ってくる
http://wiki.portal.chalmers.se/agda/pmwiki.php?n=Libraries.StandardLibrary
から Version 0.4 をダウンロード・展開。
- emacs を立ち上げる
M-x agda2-mode
で agda-mode になる。(M は esc キー)
M-x customize-mode
を実行すると、編集画面になる。
- Agda2 Include Dirs の右の Show Value ボタンをクリック。
- INS だけの行の INS をクリック (一番上の INS DEL の行は変更しない)
- 新しく出て来たボックスにダウンロードしたライブラリへのパスを入力
とか。
# hoge のところは変更。
入力したら、上のほうにある Save for Future Sessions のボタンをクリック。
これで Agda で遊べる :)
ABCD
ABCD (A Basic Course in Dvorak) 終わり。
http://www.kototone.jp/typex/index.html
qwerty より打ちやすそうな「気」はする。
あとは練習 ?
セットアップ
修理に出していた Mac が帰って来たので、セットアップ。
- XCode Tools
- Carbon Emacs
のインストールまで済んでいたので、
ののちに、
sudo port selfupdate
sudo port install ocaml +doc +labltk
sudo port install proofgeneral
sudo port install wget
sudo port install ledit
sudo port install nkf
sudo port install w3m
sudo port install psutils
sudo port install lha
sudo port install ghostscript
sudo port install ghostscript-fonts-hiragino
sudo port install gv
sudo port install ptex +nox11
sudo port install mpage +mediaA4
sudo port install msmtp
sudo port install subversion
sudo port install ispell
Coq は
を見て入れた。
しかし、この方法だと coqide は相変わらず動かない;
coqtop は入ったので、記念に証明。また遊びたい。
まだ入れていないもの
- a2ps (文字化け)
- ghc
- smlnj
- DrScheme
