通大指定教材:Free Pascal のダウンロード/インストールに付いて

通大生に次のような質問を受けたんですよ。

今コンピュータの過去問を解くに当たってpascalをダウンロードしようと思ったのですが、もともとパソコンに弱い上に、玉川大学が指定しているダウンロードページがすべて英語なのでよくわかりません。
どのようにダウンロードしたらよいのか教えていただけないでしょうか？？

とか訊かれて。
反射的に口を突いて出そうになったのは次の一言です。

バッカじゃねえの???

と。
いや、この質問者に思ったんじゃないですよ。そうじゃなくって通大が、です。アホちゃうか???と思った。
以下に通大数学コースコンピュータの教授陣が如何にバカタレなのかその理由を書いていきます。
いや、俺はホントに怒ってるんだぞ(怒)。

1. 通大数学コースコンピュータの教授陣がバカタレな理由:Free Pascal は本当に Pascalなのか?

   
   まず、亀田はFree Pascalの存在は知っていました。
   と言うか、現状で、マトモと呼べるフリーのPascalコンパイラと言えば、次の二種類しか思い浮かばなかったのです。
   
   
   
   • GNU Pascal
   
   
   • Free Pascal
   
   
   
   この二つのうち、前者はWindowsで使用するのは極めて難しいです。まず、Windowsに簡単にインストールして動かせるいわゆる.exeファイルが提供されていない、んですよね。LinuxやFreeBSD等のオープンソースのOS上ならいざ知らず(あるいはMac OS Xでも良いですが)、Windowsでこれを動かすのは至難の技です。
   一方、後者は確かにWindows用の実行ファイルも提供されていますし、比較的敷居が低いです。それは間違いありません。
   だったら。
   どうして亀田がFree Pascalの存在を匂わせなかったのか。その理由は以下の通りです。
   

   
   Free Pascal が本当にPascalコンパイラと呼んで良いのか自信が持てなかったから。
   

   
   これに尽きます。
   
   詳しい話はWikipedia辺りを参照して欲しいんですが、こんな事が書いてありますね。
   

   
   

   概説

   
   言語仕様はボーランドの Pascal （Turbo Pascal及びDelphi）に準拠しており、いくつか MacPascal の仕様も採用している。
   
   

   言語仕様

   
   FPC は Pascal の方言のうちで、デファクトスタンダードとなっているボーランドのものを採用している（1.0.xのFPCではBorland Pascal 7とDelphi 2、2.0.xでは Delphi 6または7）。
   

   
   
   以前、Delphiの話を書きましたが、今現在、DelphiはPascalではない、んです。全く別の独自の言語と言って良いです。
   と言うことは、Free Pascalの実装方針、Delphi互換を目指してる、んだったらFree Pascalは事実上Delphiですよ。ホントにそれでイイのか?亀田はそこが不安に感じたので敢えてFree Pascalには触れなかったのです。
   
   名前にPascalが入ってりゃエエ、って問題じゃないんです。Pascal、と名乗るには、本来だったらISO(国際標準化機構)で制定された標準Pascalの言語仕様に準じてないといけません。
   
   通大数学コースの教授陣、ホントにFree Pascalの仕様確かめたんだろうな?どーも通大数学コースコンピュータの選択見ると、
   

   
   まあ、動けばイイや。
   

   
   と言うド素人と変わらない基準で選んでいる感じがしてとても不安です。十進BASICの配布もそうですが、本当に標準仕様に準じて実装しているのかどうか怪しい言語を選んでたりしますし。
   本来、プログラミング教育を名乗る以上、
   

   
   標準仕様に準じている以上、問題無く動作するコードが書ける
   

   
   実装を指定するべきでしょう。反面、通大の選択だとマトモな情報工学系大学の教員だったら絶対に行わないような事ばっかりやってるように見えます。
   (あるいは通大数学コースはマトモじゃねえのか。そうかもな。これじゃあそう取られてもしょーがない。)
   
   動けば良い、んだったらプログラミング言語なんて使わずにMicrosoft Excelでも教えてりゃイイんですよ(笑)。その方がよっぽど役に立ちますって。
   



2. 通大数学コースコンピュータの教授陣がバカタレな理由:Free Pascal Compiler をダウンロードしたからと言ってどーにもならない

   
   第二がこれです。ダウンロードサイトを指し示したところでどーにもならない、と言う事です。
   
   英語ページに挑んで、無事Free Pascalのダウンロード/インストールに成功したとしましょう。
   

   
   「さて、Free Pascalを立ち上げようか」
   

   
   とFree Pascal IDEなるアイコンをダブルクリックすると結果はコレです。
   
   
   
   

   図1

   
   2chのアスキーアート状態です。
   この時点で通大生はPCの前でこんな顔↓してますよ。
   
   
   
   実際、ダウンロードした通大生から次のような事を言われました。
   

   
   実際にダウンロードしたpascalを開いてみるとバグ？？のような感じになってしまっていて何もできませんでした。
   

   
   実はこれバグじゃないんですけどね。この状態でも使える事は使えます。
   平たく言うと、Windowsのコマンドプロンプト(DOS窓)の文字コードとFree Pascalの文字コードが合ってない為、こう言う「文字化けした」ような画面になるんです(良く見ると、FPCって書いてる事が分かるんですが)。
   いや、実際、LinuxでのUTF-8の世界に住んでいるとこーゆーのは滅多に起こらないんですが、Windowsで久々にこう言う「バカ現象」に遭遇しました(笑)。初め「バグ？？のような感じ」とか言われて想像付かなかったんですけど(笑)。
   本来、Free Pascalの提供元はこう言う形で表示させたいんです。
   
   
   
   

   図2

   
   
   分かりますかね?
   
   本来だったら、こーゆー「文字コードの問題」なんかも学生に説明しておかなければならない、んです。相手はコンピュータ素人の学生だろ、っての。ボケ。
   十中八九、「プログラミングをやった事が無い」学生だったら図1の状態を見て、
   

   
   インストールに失敗した
   

   
   って思うはずです。「何で?何で?何で?」と頭の中に疑問符の嵐、でしょう。
   かつ、最悪な事に、現代ではPascal自体が大して人気のある言語じゃありません(ハッキリ言えば、例えばSchemeのコミュニティを探す方が遥に簡単です)。誰かに質問しようと思っても答えてくれる場所さえ無い、のです。
   
   ところが、質問者の話を聞く限り、通大の指定は、
   

   
   ダウンロードサイトだけ書いてある
   

   
   らしく、それ以外の事は何も書いてない模様です。
   

   
   そんなのアリか?(怒)
   

   
   こう言う「バグモドキ現象」なんて一回でもダウンロードして実行してみれば分かる筈なんですけど。加えて、通大側で図1の状態から図2の状態への持って行き方を学生に説明するのってそんなに大変な事か???
   あるいは、そんな現象がある、とも全く確かめてない?
   だとしたら通大数学コースコンピュータの教授陣は
   

   
   ボンクラ
   

   
   の集まりです。一体何やってんだ、と小一時間問い詰めたいですね。
   

以上により、通大数学コース・コンピュータの教授陣は大馬鹿野郎であることが証明されました。

Q.E.D.

もう一回繰り返しておきますが、対象学生は「プログラミング」なんてやった事ない輩が殆ど、なんですよ。何も説明せずにダウンロードサイトだけ教えておけば何とかなるだろ、なんて考えていても何とかなるわけねーだろが(怒)。バカモノどもが。
通大数学コースのコンピュータの教授陣に次のように言っておきたいですね。

べらぼーめ、豆腐の角に頭ぶつけて死んでしまえ

てやんでえ、こちとら江戸っ子よ。寿司喰いねえ(謎)。

Free Pascalのインストール/設定の方法

とまあ、悪態吐いたトコで本題入りましょうか。

註:悪態、とか書いてますけど、当たり前の事を指摘してるに過ぎませんけどね。

一応、苦肉の策(どー考えても苦肉の策)で通大がFree Pascalを公式指定している以上、そのインストール方法と設定の方法をここで解説しておきます。
繰り返しますが、こんなの一般人に解説させたら本当はダメなんですよ。通大自ら率先して学生に説明しなければならないのです。

1. Free Pascal のダウンロード

   
   
   
   
   1. Free Pascal 公式ページにアクセスする。
   
   
   2. Downloadをクリックしてダウンロードページへ飛ぶ。
   
   
   3. BinariesセクションからCPU(中央演算処理装置)とOSのタイプを選ぶ。
      
      
      
      • Windows機の場合、大体のケースではintel/i386のWin32, Win64 and WinCEと書かれたところがリンク。
      
      
      • Apple Macintoshは現行機(intel Mac)の場合は同じくintel/i386からMac OS Xを選ぶ。
      
      
      • 数年前のApple Macintoshの場合は、powerpcからMac OS Xを選ぶ。
      
      
      
      この3つ以外はマニアックなCPUやOSなんで考えなくて良い。
      
   
   
   4. Select download mirrorからSource Forgeを選択する。
   
   
   5. 適切な実行ファイルをダウンロード/保存する。
      
      
      
      • (通常の32bit版)Windowsの場合はfpc-2.2.4.i386-win32.exeをクリック/ダウンロードして保存する。
      
      
      • 現行のIntel Macの場合はfpc-2.2.4.intel-macosx.dmgをクリック/ダウンロードして保存する。
      
      
      • ちょっと古いPowerPCベースのMacintoshの場合は、fpc-2.2.4.powerpc-macosx.dmgをクリック/ダウンロードして保存する。
      
      
      
      
   
   
   
   以下に、この手順(Windowsの場合)を纏めた解説ビデオを挙げておきます。上の説明で良く分からない人は実際動画を観てみて、同じ手順を再現してみて下さい。
   
   
   
   
   



2. Free Pascal のインストール

   
   ダウンロードしたフォルダをダブルクリックしてインストーラを起動したら、後は基本的に[Next>]ボタン連打で構いません。
   Windowsの場合、インストールフォルダは
   

   
   C:\FPC
   

   
   とCドライブ直下になります(Macintoshは残念ながら知りません)。
   Windows版Free Pascal インストールの解説ビデオは以下にあります。
   
   
   
   
   



3. NTEmacsのダウンロード

   
   さて、ここが一番悩みました。
   図2にもあるように、Free Pascal はコマンドプロンプト(DOS窓)を利用したIDE(Integrated Development Environment:統合開発環境)がデフォルトで付いてきます。
   が、図1のような文字コードによる文字化けもありますし(もちろん暫定的に解除は出来るんですが)、何にせよ使い辛い、と言うのが亀田の印象でした。
   実はFree Pascal には他にも専用のIDEを作ろう、と言うプロジェクトがあるにはあるんですが、開発中の模様ですし、またもや日本語文字コードの問題が生じるようです(少なくとも亀田が試してみた限り、あまり具合が良くありませんでした)。
   さて、一体どーしたもんだろ?Windowsからパソコンをはじめた軟弱世代の為に(笑)、昨今流行りのGUIの開発環境、例えばEclipseとかNetBeansも軒並み調べたんですが、前者はPascal用のプラグインは開発中止、後者は開発途中(pre-α版)だそうです。
   だから言ったろ、っての(苦笑)。今時Pascalなんて流行ってないんだってば(苦笑)。繰り返しますが、Schemeの開発環境探す方がずーっと簡単なんですって。通大数学コースのコンピュータ担当のおバカさん達はどう考えてるんだろね?この状況を。
   xyzzyやサクラエディタも調べてみたんですが、残念ながらオートインデントが効かず。ハッキリ言っておきますが、オートインデントが無いようなエディタでプログラムなんて書いてられませんよ。よってこれらも却下、です。
   結局Windows用で残ったのはNTEmacsしかありませんでした(Mac OS X用にはCarbon Emacsと言うのがあります)。
   よって、ここからは、
   

   
   NTEmacsでFree Pascalを使う
   

   
   のを方針とします。
   
   
   
   
   1. NTEmacsのページへアクセスする。
   
   
   2. DownloadをクリックしてSourceForgeのページへ飛ぶ。
   
   
   3. NTEmacs 22BASE Binaryのセクションからemacs_22.2_bin_20080327.exeをクリック/ダウンロード/保存する。
   
   
   
   取りあえずここまで行って下さい。
   Windows版NTEmacsのダウンロード解説ビデオは以下にあります。
   
   
   
   
   なお、Mac OS X 用のCarbon Emacsに関する情報は、これはネット上にはNTEmacsより多いんで、ご自分で検索してお調べ下さい。
   (Macはさすがに今現在所有してないので分からないのです)
   



4. NTEmacsのインストール

   
   
   
   
   1. NTEmacsはダウンロードしたフォルダを解凍するだけですぐ使えるようになっています。
      問題は「解凍場所」です。Cドライブ直下に解凍して下さい。
      パスで書けば
      

      
      C:\
      

      
      です。
   
   
   2. C:\emacs\22.2\bin\runemacs.exeを右クリックして[ショートカットの作成]を選び、ショートカットを作成します。
   
   
   3. 作成したショートカットをデスクトップ上に移動します。
   
   
   
   良く分からない人は、以下の解説ビデオを観て、それに従って下さい。
   
   
   
   
   Mac OS X 用のCarbon Emacsに関する情報は、これはネット上にはNTEmacsより多いんで、ご自分で検索してお調べ下さい。
   



5. Free Pascal + NTEmacs の環境設定

   
   
   
   
   1. [スタート]→[アクセサリ]→[コマンドプロンプト]と進んでコマンドプロンプト(DOS窓)を立ち上げる。
   
   
   2. 下のコードをコピーしてDOS窓に貼り付ける。
      
      
      mkdir C:\bin && mkdir C:\home\.emacs.d\elisp && echo "C:\FPC\2.2.4\bin\i386-win32\fpc.exe %1 %2 %3 %4 %5 %6 %7 %8" > C:\bin\fpc.bat
      
      
      
   
   
   3. DOS窓に貼り付けたらリターンキーを押してコマンドを実行。
   
   
   4. ユーザー環境変数の設定をします。
      
      
      
      • Windows 2000/XP の場合:このページを参考
      
      
      • Windows Vista の場合:このページを参考
      
      
      
      にして、これら
      
      
      
      
      

      変数	値
      PATH	C:\bin
      HOME	C:\home

      
      二つのユーザー環境変数を設定します。
      
   
   
   
   
   良く分からない人は次の解説ビデオを参考にして下さい。
   
   
   
   
   



6. NTEmacs の設定

   
   

   
   WARNING!!!
   Windows XP ユーザーの人は最初にメイリオフォントを導入しましょう(必須!!!)。非常に美しいフォントなんで、プログラムを書くのが楽しくなります(見た目は大事です)。
   メイリオフォントの導入方法はこのページを参考にしてください。
   

   
   
   • Font Changer
   
   
   • Windows XP 向け ClearType 対応日本語フォント
   
   

   
   なお、Windows Vista以降ではデフォルトのフォントはメイリオになっています。
   

   
   
   
   
   1. デスクトップ上のNTEmacsのショートカットアイコンを右クリックしてプロパティを開く。
   
   
   2. 作業フォルダーを
      

      
      C:\home
      

      
      に変更して[適用]ボタンをクリック、そして[OK]ボタンをクリックする。
      
   
   
   3. NTEmacs をダブルクリックして起動する。
   
   
   4. 重要!!!
      NTEmacsではCtrlキーとxキーを同時に押すことを
      

      
      C-x
      

      
      と表現する。同様にCtrlキーとxキーを同時に押したあと、Ctrlキーとfキーを同時に押すことを
      

      
      C-x C-f
      

      
      と表現する。こう言うキーボードでの操作をキーストローク(あるいは慣用的にキーバインド)と呼ぶ。
      NTEmacsでは、C-x C-fの後ファイル名を入力すると、そのファイルが存在する場合はそのファイルを立ち上げ、無ければ新しくそのファイル名でのファイルを立ち上げる。
      ここでは、
      

      
      C-x C-f .emacs
      

      
      とし、新規ファイルとして.emacsを立ち上げる。
      
   
   
   5. ブラウザでこのページにアクセスし、そこに書かれたコード(冒頭からEnd of Fileまで)をコピーして、NTEmacsで開いた.emacsに貼り付ける。
   
   
   6. C-x C-sで.emacsを保存する。なお、C-x C-sはファイル保存のキーストロークである。
   
   
   7. 一旦NTEmacsを閉じる
   
   
   8. 再びNTEmacsを起動した時、白色画面ではなく、肌色っぽい(あるいは黄色っぽい)画面で起動したら全ての設定は成功である。
   
   
   
   お疲れ様でした。後はNTEmacsでプログラムを書いて、コンパイルして実行するだけ、です。
   
   良く分からなかった人は次のビデオを参考にしてください。
   
   
   
   
   



7. Free Pascal と NTEmacs の使い方

   
   箇条書き程度にメモしておきます。
   
   
   
   • 最初にNTEmacsの使い方を学ぶ為、NTEmacsのプルダウンメニューから[Help]→[Tutorial]を選んで、簡単なNTEmacsの使い方を学びましょう。日本語で書かれているので読むのに特に問題は無い筈です。
   
   
   • C-x C-f ファイル名でファイルが開きます。
   
   
   • Pascalのプログラムを記述するファイル(ソースファイル、と呼びます)の拡張子は.pasです。NTEmacsはこの拡張子で判断してPascalモードを立ち上げます。従って、Pascalのソースファイル名の最後は必ず.pasにして下さい。
     例えば、hogeと言うプログラムを書きたかったら、ソースファイル作成は
     

     
     C-x C-f hoge.pas
     

     
     です。
     
   
   
   • Pascalモードとは、Pascalの文法規則に則ってキーワードを色付けしてくれたり、適切なインデントを行ってくれたりするプログラム開発補助機能です。
   
   
   • 他に、Delphiに特化されたdelphiモードと言うのも実はNTEmacsに内蔵されていますが、亀田の感触ではあまり役に立ちませんでした。少なくともISO Pascal範囲内のコードを書く以上、Pascalモードの方が機能が充実しています。
     (実はFree PascalでのEmacs推奨モードはdelphiモードです)
   
   
   • NTEmacsでプログラムを書く場合、リターンキーは滅多に使いません。代わりにC-jとします。これで改行と自動インデントを同時にやってくれます。
   
   
   • C-jで適切なインデントが施されない場合は、結果どっかで文法ミスしている、と言う事です。
   
   
   • コンパイラはC-c c(Ctrlキーとcキーを同時に押した後、またcを押す)で立ち上がります。
   
   
   • make -kはいらないんで消しましょう。
   
   
   • Free Pascalのコンパイルコマンドは
     

     
     fpc ファイル名
     

     
     です。これでファイル名から拡張子.pasを外しただけの同名の実行ファイル(オブジェクトコード)が生成されます(ホントは.exeファイルが生成されます)。
     例えば、
     

     
     fpc hoge.pas
     

     
     なら、hogeと言うオブジェクトコードが生成されます(ホントはhoge.exeが生成されます)。
     
   
   
   • NTEmacsからコマンドプロンプトを呼ぶには
     

     
     Esc-!
     

     
     つまり、Escキーを押した後!キーを押すか、
     

     
     M-x eshell
     

     
     つまり、Altキーとxキーを同時に押してからeshellと入力すれば良いです。そうすると、前者はコマンドプロンプトをNTEmacs最下部のミニバッファに呼び出し、後者はNTEmacsをコマンドプロンプトとして動作させます(※)。
     
   
   
   • どの道、コマンドプロンプトさえ呼び出してしまえば、あとはオブジェクトコード名をタイプしてリターンキーを叩けば書かれたプログラムが走ります。
   
   
   • 作成した全てのソースファイルとオブジェクトコードはC:\homeに保存されます。C:\homeは文字通り作業フォルダーです。
   
   
   • 他に便利なNTEmacsの機能としては、コメントを記述する際の
     

     
     M-;
     

     
     (Altキーを押しながら;キーを押す)機能があります。
   
   
   
   
   

   
   ※:正確にはDOS窓ではなく、Emacs Shellと呼ばれるまた別種の(Windows用語で言う)コマンドプロンプトを呼び出す。
   これはUNIX系のコマンドライン体系に則っていて、MS-DOS系のコマンド体系とは実は互換性は無い。
   しかしながら、作ったプログラムを呼び出す、と言う意味においては、作ったプログラム名は「コマンド」として認知され、DOS窓だろうとEmacs Shellだろうと同様に動く。また、動かなければならない。
   なお、コマンドプロンプト、はWindows用語だが、一般的にどう呼ぶのか、と言うとこれが実は用語が無い。端末、も用語として相応しくないし(と言うのも「端末」とは元来、ハードウェアを指し示す)、UNIX系では通称でシェル、と呼ぶ例が多いが、これも元来はWord、Excelのような「アプリケーションの名前」を指すので、一般用語としてはどうか、と思われる。
   (実は、「コマンド」も「プロンプト」も全く別の意味を指すので、Windowsでの正式名称「コマンドプロンプト」自体がかなりマズいネーミングなのだが、色々とこの辺を鑑みると、「DOS窓」と言う通称は、なかなか上手く各種の問題を避けて「モノ」を指し示した優れたネーミングである)
   敢えて言うならCLI(コマンドラインインターフェース)環境、としか呼びようが無い。DOS窓はWindowsのCLI環境、ShellはUNIXのCLI環境である。
   なお、Windows Vista以降にはPower Shellと名づけられた強力なCLI環境が存在する。
   

   
   大体の作業の流れは以下の解説ビデオを観てください。
   
   
   
   
   

Pascal の参考書

サイエンス社と言う出版社から大学用として数冊ISO Pascal準拠の教科書が出版されています。
Amazon辺りで検索すると二束三文で古本が取引されているんで、そう言う教科書を適当に選んで、自習用として入手してみて下さい。
文字通り二束三文で取引されているんでビックリします(こーゆー時だけ人気が無い言語はありがたい・笑)。

---

Pascalよもやま話

• Pascalは1970年にヨーロッパで開発されたプログラミング教育用言語である。


• Pascalは殆ど史上初のレキシカルスコープを持つ構造化プログラミング言語である。


• 正確に言うと、史上初のレキシカルスコープを持つ構造化プログラミング言語は、同じくヨーロッパで制定された理論的実験言語(と言うと語弊があるが)であるAlgolだが、言語仕様が巨大化し過ぎて、マトモな実装は誕生しなかった。


• 言わば、Pascalは縮小版Algolである。


• 従って、文法構造的にもAlgolの影響が見受けられる。


• Pascalは古典的なLispやBASICと同様の、case-insensitiveな言語である。


• case-insensitiveとは大文字、小文字を区別しない、と言う意味である。


• 元々PascalプログラミングではBASICよろしく全て大文字で記述する。


• 大文字しか使えなかった、と言う一つの理由は1970年当時のコンピュータのパフォーマンスに由来する。


• 1970年当時では、大型コンピュータでもスクリーンへ表示する為の計算能力やメモリが貧弱で、また、プリンタの出来もよろしくなく、結果解像度が稼げなかったのが一つの理由である。


• 解像度が稼げない環境だと、小文字は潰れてしまって読みづらい。


• なお、小文字表示でも問題が無いディスプレイが普及するのが1975年前後である。


• ちなみに、1973年登場のC言語はcase-sensitiveなプログラミング言語で、UNIXと言うOSでほぼ始めてcase-sensitiveな環境が整った。


• 静的型付け言語では、現在ではC言語の圧勝だが、かつてはC言語とPascalが人気を二分していた。


• C言語ユーザーは、教育目的の為に設計されたPascalは初心者にプログラミングを徹底的に叩き込む為、厳密な文法規則を採用しているのを「自由度が低い」として嫌った。


• 有名どころではC言語開発者の一人、ブライアン・カーニハン博士のWhy Pascal is Not My Favorite Programming Languageと言う論文がある。


• 一方、PascalユーザーはC言語を「汚い・デタラメ・読みづらい」と批判する傾向があった。


• 実際、C言語コミュニティではThe International Obfuscated C Code Contest(国際分かりにくいCコードコンテスト)と言うバカみたいな催しがあり、つまり、C言語では「読みづらく書こう」とすればいくらでも酷く書ける、と言う特性が存在する事を意味する。また、熟練Cハッカーでさえ「分かり辛くかつ短く」書くのが偉い、と言うようなおかしな考え方があったりする。一方、Pascalではこう言う事は起こり辛い。


• 通大の「コンピュータ」のテキストでは
  

  
  (Pascalは)プログラミングに対する深い洞察に基づいて設計されていますので、Pascalでプログラムを書くこと自体がプログラミング教育そのものである場合も少なくありません。
  ～中略～
  Pascalで書かれたプログラムは大変読みやすいため解説文書documentとしての価値も高く、研究成果の発表にも多用されています。
  

  
  とPascalベタ褒めである。
  


• 対するCに付いては、
  

  
  Cのプログラムは少し読みにくいのが難点です。
  

  
  とアッサリとした記述でまとめてある。
  


• 通大の「コンピュータ」のテキストの著者はPascalびいき、である(爆)。


• Pascal vs. C はヨーロッパ文化 vs. アメリカ文化が見え隠れして面白い。


• どっちにしても、現代的な動的型付け言語のユーザーに言わせれば目糞鼻糞の討論である(爆)。


• いずれにせよ、90年代初頭までは大学初年度の情報工学の入門用言語として、Pascalは確固とした地位の一角を担っていて、通大の「コンピュータ」テキストはその時代に書かれたものである。


• もう一角はSchemeが担っている。また、現代のアメリカではPascalは退場して、代わりにPythonが使われるケースが増えている(なお、日本でも早稲田大学ではPythonが使われている模様)。


• 当時、SchemeかPascalか、の差を生んだ一番大きな理由は、高額な大型コンピュータを買える予算があったのかどうか、である。


• Schemeは当時のレベルでは「贅沢言語」だったので、コンピュータのパフォーマンスが鍵を握っていた。一方、Pascalのコンパイラは簡素でコンピュータへの負担がSchemeに比べると少ない。


• 初期のPascalはJavaのように中間コードにコンパイルするスタイルで、その中間コードは仮想マシン上で動き、適切な仮想マシンさえあれば、どんなプラットフォームでもコンパイル済みの中間コードは動くように考慮されていた。


• ただし、当時のコンピュータではこの「仮想マシン」スタイルと言うのは負担が大きく、結局このスタイルはほどなく消えて、普通のネイティヴ・コード(機械語でのコード)にコンパイルされるスタイルへと変更されている。


• この「仮想マシン上での実行」と言うスタイルはコンピュータのパフォーマンスが劇的に進歩した90年代後半まで殆ど用いられていない。端的に言うとJavaの登場まで「死んでいた」。


• 従って、Javaからプログラミングをはじめた層が「Javaはどんなプラットフォームでも動くプログラムが書けるはじめての言語だ」と勘違いする結果を招いている。もう一回繰り返すが、元々このスタイルはJavaの専売特許ではない。かつてはPascalもそうであった。


• 他にもPerlをはじめとするスクリプト系言語、と呼ばれるジャンル(Python、Ruby等)も実は内部的には中間コードへとコンパイルされている。


• SUN(Javaの開発元)が言う"Write once, Run anywhere."と言うのはマーケティング戦略上のコピーに過ぎない(が、Javaユーザーはそれを知らないケースが多い)。


• Pascalはコンピュータ科学的に考えても文法上、厳密な区分けが存在している。


• 典型的な例としては値を返すfunctionと値を返さないprocedureが別個設定されている事が挙げられるだろう。こんなしつこい区分けをしてるのは知ってる限りPascalだけである。


• いきなりC言語を学び出したプログラミング初心者が躓くのが、例えばvoid型の返り値を持つ関数だが、これは初心者にとっては全く意味不明である。


• 実はこのC言語のvoid型の返り値を持つ関数とはPascalで言うprocedureの事である。Pascalで言うfunctionはこれに当てはまらない。


• 従って、確かに「コンピュータ科学の基礎を学ぶ」と言う意味ではPascalは優れている。少なくとも、Pascal→C言語とカリキュラムを進める意味に於いては躓きが一番少ないコースだ。


• 一方、実用的なプログラムを書く上では、一々functionとprocedureを使い分ける、ってのは邪魔臭いかもしれない。返り値の型宣言で済ませた方が「書きやすそう」なのは事実である。


• しかしこれも関数型言語のユーザーに言わせれば五十歩百歩である(爆)。


• いずれにせよ、Pascalは良く、品行方正で厳格なお嬢様言語と呼ばれたりする。


• Pascalは初期のApple Macintoshと言うパソコン上において、Apple指定のプログラム開発用言語であった。
  
  
  
  

  初代Macintosh

  
  


• 従って、Object Pascalへの独自拡張、及びDelphiへと続く道は、元々、Macintosh上で先鞭が付けられている。


• Delphiの先祖、Turbo PascalがMS-DOS機へ移植された時、その高速なコンパイルにかなりの人間がショックを受けたそうである。


• Pascalで書かれた最も有名な商用アプリケーションとしては、後にファミコンに移植されてヒットし、また、ドラゴンクエストの元ネタの半分を占める世界最古のコンピューターRPGの一つ、Wizardryが挙げられる。
  
  
  
  
  

  Apple II 版 Wizardry (オリジナル)

  
  
  
  
  
  
  
  

  Macintosh版Wizardry

  
  


• Wizardryの作者の一人でメインプログラマであるロバート・ウッドヘッドはPascalハッカーだったらしく、Wizardryのファミコンへの移植を打診された時に、
  

  
  Wizardryはパスカルでできてるからパスカルの動かないファミコンには絶対移植できない
  

  
  と難色を示した逸話が残されている。
  (ちなみに、当時のファミコンではアセンブリ言語等の低級言語でプログラムを打つのが当たり前で、C言語等の高級言語がプログラミングに導入されたのはもっと後のスーパーファミコンになってから、しかも後期になってから、である)
  


• しかし、実際に日本のスタッフがWizardryのファミコンへのアセンブリ言語での移植を成功させた時、その完成度の高さに舌を巻いた。
  
  
  
  
  

  ファミコン版 Wizardry (アセンブリ言語で移植されている)

  
  


• 日本人は凄い。
  


• いずれにせよ、Pascalの勉強を頑張ればRPGくらいなら作れる(かもしれない)。


• 他にも、組版処理ソフトであるTeXは元々Pascalで書かれた作品である。


• 動的型付け言語ユーザーにとってはPascalはB&D言語の極北とも言える言語である。


• ここでB&DとはBondage and Discipline、つまり緊縛と調教である。


• MITの伝統的コンピュータ科学の大学初年度向け入門書である計算機プログラムの構造と解釈では、序文でPascalを次のように評している。
  

  
  Pascalはピラミッド - 重い石を定位置へ運ぶ軍隊が作った堂々とした、息もつけぬ静的構造 - を作るためのものである。
  ～(中略)～
  Pascalの過度の宣言的データ構造は、関数の特殊化を惹き起こし、偶発的な協力を不可能または困難にする。
  
  

  
  



• H君への手紙: 天才

  
  

  
  また、Wirthという人がいる。いうまでもなく、
  WirthはPascalとModula-2の設計者だ。Pascal
  は教育用の言語としては非常にすぐれたもので
  ある。また、Modula-2はモジュラー・プログラ
  ミングの考え方を一般のプログラマに流布する
  のに大いに役立った。しかし、Wirthはコンピュ
  ータ・サイエンスの天才とはいえない。なぜな
  ら、PascalやModula-2には色気が感じられない
  のである。つまり、真面目過ぎて面白くないの
  である。そのくせ、泥臭いというわけでもない。
  つまり、徹底的に実用的になろうとしているわ
  けでもない。まとめると、馬鹿ではないが、
  「ださい」わりには中身がないといえよう。
  

  
  
  萩谷昌己: 東京大学大学院情報理工情報科学科教授
  
  


• お嬢様、で緊縛と調教なんで良からぬ事を想像しそうだが、ところがどっこい、緊縛されて調教されるのは貴方の方である。


• 従って、Pascalは現代風に言うとツンデレ言語である。


• PascalはドスケベなM男向けである。


• 緊縛されて調教されて泣き叫んで喜べ(笑)。


• 俺には無理だ(謎)。

Emacs ビギナーに贈る、これからバリバリ使い隊!!人のための設定講座 その1。
Emacs(中略)設定講座 その2「elisp のインストールと設定編」。
Emacs設定講座 その3「scratch バッファと eval(評価)」。
Emacs設定講座「キーバインドよ、俺色に染まれ。ア!!」。
もう初心者なんて言わせない、Anything で始まる Emacs 道。
Anything の設定ことはじめ。

方程式の近似解

さて、今まで二節を使って「再帰の練習」をしてきました。いや、事実上これらは「再帰の練習」がトピックだったのです。(そして、その再帰ネタを「反復で行う」と言うネタです)
元々、このテキストの背後にあるネタを整理してみると、

1. テキスト後半の著者である菅原昭博・現玉川大学工学部電子工学科准教授は東工大出身である。


2. 東工大出身である以上、設計理論上、再帰方程式使いまくりの関数型プログラミング言語、Lispに精通している。


3. プログラミング未経験の学生に数値計算を迅速に教えるのはLispが最適である。


4. しかしながら、90年代初頭のパソコンでは非力過ぎてLispは動かなかった。


5. しょーがないので、Lispで扱うネタを当時それなりに流行っていたPascalを模した「擬似プログラム」で解説するしか無かった。


6. だから解説がワヤクチャである。

と言う事です。実際、これまでの2節の内容は、Lisp/Schemeの教科書の「最初にやるネタ」としては良くあるトピックなんです。
(一方、当然ながら、このテのトピックは「Pascalの入門書」とか「Cの入門書」には出てきません)

プログラミングは難しい?確かに難しいかもしれません。
しかし、このテの数値計算が「余計難しく見える」最大の理由は、

初心者にとって、「数学的アルゴリズムが難しい」のか、「プログラミング自体が難しい」のか判断が付かない

からなんです。難しい×難しい、だと混乱して当たりまえ、なんですよ。
ですから、通常、「数値計算」ってトピックは「一通りPascal(あるいはC言語)を扱えるようになってから」別の教科書で学ぶ、となってるんです。
そこで当然方策としては「数学的アルゴリズムが難しい」から「プログラミング自体が難しい」を切り離してしまった方が良い、って事になります。単純に「簡単なプログラミング言語を使えば問題の半分は解決する」と言う方法です。
これは成功した、と思います。Python、Ruby等の「動く擬似コード」の導入によって「数学的アルゴリズムが難しい」、だけを意図的に切り離したんです。
今まで、演習問題の回答例を見ていて

「本体がたった2〜3行程度、でプログラムと呼べるのか?」

とか思った人もいるかもしれません。が、実は「2〜3行程度でも」れっきとした「プログラム」です。
と言うか、プログラムは「短く書ければ書けるほど良い」んです。そして、プログラミング言語自体が強力になればなるほど「短く記述する事が」可能になるのです。
これが90年代初頭と今現在の「テクノロジーの差」なのは言うまでもありません。

Python、Ruby、Rはどれも「新しい」言語です(例外はSchemeだけ、なんですが、そもそも背景が数学である以上「古くは」なりません)。プログラミング言語の選択も、原則的には「なるべく新しい言語を選んだ方が良い」と言う事です。
これはテクノロジー選択の原則で、例えば今手元に10万円程度あるとして、何か録画機器を買いたい、とします。ビデオテープレコーダー、DVDデコーダー、ハードディスクレコーダーとあった場合、まあ、十中八九「ハードディスクレコーダー」を買う人が多いでしょう。何故なら「新しいから」ですよね。今更ビデオデッキを買おう、って人はあんまりいないでしょう。何故なら、テクノロジーは基本的には「新しい方が良い」からなんです。プログラミング言語もテクノロジーの範疇である以上、同様の文脈となります。
ここで始めてPython、Rubyなんかのプログラミング言語の存在を知った人も多いと思いますが、プロの現場でも愛用されている、と言うのは先ほど書いた通り「記述能力が高い＝短くコードを書けるから」なんです。短ければ短い程「間違い」が混入する確率も低くなりませす。そして、この二つは「Webアプリケーション記述」が特に得意な分野なんで、実は知らないうちに「Python/Rubyで書かれたサイト」を見ている可能性もあります。つまり、あなた方が考えている程「マイナー言語」ではないのです。
また、Rは実際「統計解析の分野」で良く使われているソフトウェアなんで、ここでも「記述が長いと」日常的に使うのがかったるくなるんで、やっぱりなるべくシンプルに書けるように設計されています。これも特殊分野ですが、その分野ではやはり「メジャー言語」なのです。
これらの言語の隆盛は、一つ、コンピュータの処理能力が劇的に上昇した事に由来しています。これらも一昔前だったらマトモに動かすのが大変だったでしょう。しかし、今の標準的なコンピュータだと、CPUの演算速度は最低でも1GHz突破してるでしょうし、メモリにしても1Gb近くは搭載しているケースが多いと思います。既に昔の大型コンピュータの能力を凌駕してるんで、こう言う「記述が短く簡単なプログラミング言語」が登場してきたのです。
ちょっと長くなりますが、大事な事が示唆されている文書があるんで引用してみます。

100年後にコンピュータが何で作られていようが、現在のものより遥かに速いと考えるのは安全な予測だろう。ムーアの法則がこのまま続けば、コンピュータは現在の 7400京倍(73,786,976,294,838,206,464)の速度を得ることになる。想像し難い数字だ。実際、速度の面ではムーアの法則は破れるだろうと考える方が無難な予想だ。18ヵ月毎に2倍になるなんてものは、それが何であれ、いずれ根本的な限界に達しそうだと考えられる。そうだとしても、コンピュータが現在のものよりずっとずっと速くなると考えて良いだろう。たとえそれがたかだか100万倍であったとしても、プログラミング言語の基本的な法則を大きく変えるには十分だ。その中には、例えば現在では遅いと考えられている言語、つまり効率的なコードを生成しない言語の活躍の余地が大きくなるということが挙げられる。

もちろん、依然として速度を要求するアプリケーションもあるだろう。コンピュータを使って解きたいと思う問題のいくつかは、コンピュータ自身によって作られる。例えば、コンピュータで生成されたビデオイメージの処理は、生成側のコンピュータの速度に追い付いていなければならないだろう。さらに、いくらマシンサイクルがあっても本質的にそれを喰い潰してしまう類の処理というのがある。イメージレンダリング、暗号、シミュレーションといったものだ。

いくつかのアプリケーションはますます非効率になって行く一方で、ハードウェアの限界までの速度を要求するアプリケーションがあるとすると、速い計算機を手にするということは、言語は効率においてより広い範囲をカバーしなければならなくなるということだ。既にそれは起こりつつある。人気のある新しい言語の現在の実装は、10年前の基準では驚異的に非効率だ。

これはプログラミング言語だけに起こっていることではない。一般的な歴史の流れだ。技術が進むにつれ、各世代はその前の世代だったらもったいないと思っていたようなことを平気で出来るようになる。30年前の人は、我々がこんなに気軽に長距離電話をかけるのに驚愕するだろう。100年前の人は、ボストンからニューヨークまで翌日配達便で荷物を送るのに、メンフィスを経由すると聞いてひっくり返るだろう。

次の100年の間に、速いハードウェアによって我々が得る余分なマシンサイクルがどう使われるかを当ててみようか。そのほとんどは無駄に使われることになる。

私は、コンピュータの力が貴重であった時代にプログラミングを学んだ。 4KバイトメモリのTRS-80に載せるために、Basicプログラムから全ての空白を抜いたことを覚えている。同じ作業を何度も何度も繰り返すのにマシンサイクルを喰いつづける、おそろしく非効率なソフトウェアのことを考えるのと気分が悪くなる。だが、ここでは私の直観は間違っているんだろう。貧乏が身についてしまうと、例えば医者にかかるといった重要なことに金を使うのを躊躇してしまうようなものだ。

ポール・グレアム
百年の言語

ここでは、マシンが速くなればなるほど工学的な意味での「効率的なプログラミング言語」より「非効率な」しかし「記述能力が高い言語」の重要性が増してくる、と言う事が語られています。つまり、遅いマシンだと「機械に気を遣って」人間側が機械により近い立場の言語を使って「効率的な」プログラムを書かなければならないのですが、今みたいに(また将来的に)マシンが十分な速さを持つと、その重要度の比率は逆転してくる。現代の状況では「記述力の高い言語」を扱うのには十分だ、と言う事が出来るんです。
通大のテキストのように「90年代の常識で」「数値計算を語る」プログラミングの教科書の存在、ってのは本当に害悪なのです。しかも相手は「数学教員免許取得希望者」であって「情報工学専攻」じゃない。少なくともPython、Ruby等の「現存するプログラミング言語のうち、最も簡単な言語」さえそれなりに扱えれば十分、です(もちろん、これさえ扱えない、となればそもそも教員免許取得の能力が無い、のと同義でしょう)。
まあ、別にストイックに「C言語等で効率的なコードをガリガリ書くのも重要」ってのは否定しませんが、今の時代だとそれは「情報工学専門」向けです。そう言うメンド臭さは、繰り返しますが、「数学教員として」必ずしも求められているもの、とは違うのです。
(ホント、さっさとテキスト改訂するべきです)

と言う辺りで前フリを終わっておいて、この節からは本格的な「数値計算」が始まります。
今、僕等の手の中にはPython、Ruby、Scheme、Rと言った動的型付け言語のうちのどれかがあります。そして「再帰」と言う武器もあります。従って、現時点では「プログラミングの面倒なお約束」は「数値計算」自体のトピックとは完全に切り離された状態です。
通大のテキストも「数学的背景」の説明が前半、実装に付いてのアイディアが後半、と完全に切り離されていますね。これは非常にやりやすい、です。
前半の「数学的説明」は「その通り」なんで、それはキチンと読んで理解して下さい。ここは「プログラミング」ではなくって単なる「数学」です。重要な部分は下線を引いていきます。それが後半で「実装する」際のヒントとなるでしょう。
では、始めます。

関数が$f(x)=x^2+2x+1$のような場合は、方程式$f(x)=0$を代数的に解くことができますから、あえてコンピュータを用いてその解を計算する必要はありません。しかし、このように容易に解を求めることができる方程式ばかりではありません。現実には解の存在は分かっているのですが、それをきちんと求めることができない方程式に出会うことのほうが多いのです。ここでは、そのような方程式に対していかなる方法で、その解を見つけるか考えてみましょう。
次にその解決策を2通り説明します。

---

1. 2分法
   解析学の基礎を学んでいると、次の連続関数に対する重要な定理が必ず出てきます。
   
   [定理]　関数f(・)は閉区間[a, b]において連続とする。f(a)、f(b)が異符号ならば、方程式f(x)＝0は開区間(a, b)において少なくとも一つの解を持つ。
   
   これは有名な「中間値の定理」の一つの系です。また、これが証明されれば「中間値の定理」はこの定理の系として証明されます。
   この定理の証明の仕方はいくつかありますが、その中に解を具体的な手順によって求めていくものがあります。
   
   (証明)　まず、f(a)＜0、f(b)＞0の場合に証明しましょう。いま、a₀＝a、b₀＝bとおき、m₀＝(a₀＋b₀)/2を求めます。ここで、f(m₀)＝0ならば、このm₀が求める方程式の解となります。それ以外の場合、
   
   

   
   f(m₀)＞0ならば、a₁＝a、b₁＝m₀
   f(m₀)＜0ならば、a₁＝m₀、b₁＝b
   

   
   
   とし、m₁＝(a₁＋b₁)/2を求めます。このとき、f(m₁)＝0であればm₁が求める解となり、そうでないときは、
   
   

   
   f(m₁)＞0ならば、a₂＝a₁、b₂＝m₁
   f(m₁)＜0ならば、a₂＝m₁、b₂＝b₁
   

   
   
   として、m₂＝(a₂＋b₂)/2を求めます。この操作を有限回繰り返して、f(m_k)＝0となるm_kが得られば定理は証明されたことになります。そのようなm_kが存在しないときは、無限の繰り返しによって、
   
   

   
   a＝a₀≦a₁≦a₂≦・・・≦b₂≦b₁≦b₀＝b
   

   
   
   となる、有界な単調列{a_k}と{b_k}が得られます。このとき、
   
   

   
   $b_k−a_k=(b−a)/2^k$
   

   
   
   が成立しますから、この2つの数列は同じ極限値cを持つことがわかります。ところで、数列の作り方から
   
   

   
   f(a_k)・f(b_k)＜0
   

   
   
   となっています。ここで、k→∞とすれば関数の連続性から、f(a_k)とf(b_k)はf(c)に収束しますから、
   
   

   
   f(c)・f(c)≦0
   

   
   
   となり、したがってf(c)＝0、すなわちcが方程式の解となります。
   f(a)＞0、f(b)＜0のときは、関数−f(・)に、今の手順を適用します。///
   
   
   
   この定理の証明の中で使われた方法をもとにして、方程式の近似解を求める手法を2分法と呼びます。その名の通り、最初に与えられた区間の2等分を繰り返し、目的の解に近づいていきます。
   



---



2. ニュートン・ラフソン(Newton-Raphson)法
   関数f(x)の導関数f'(x)が分かっている場合は、方程式f(x)＝0の解に対して次の定理が成り立ちます。この定理の中の手順による反復計算によって、解を求める方法をニュートン・ラフソン法と呼びます。
   
   [定理]　　関数f(x)は、閉区間[a, b]で2回連続微分可能とし、
   
   
   
   1. f(a)とf(b)は異符号
   
   
   2. a≦x≦bで、常にf'(x)＞0またはf'(x)＜0
   
   
   3. a≦x≦bで、常にf"(x)≦0またはf"(x)≧0
   
   
   4. 端点aとbで、|f'(x)|が大きくない方をcとしたとき、
      

      
      |f(c)|≦(b−a)|f'(c)|
      

      
      
   
   
   
   を満たすとする。このとき、区間[a, b]の中の任意の点x₀から出発して、
   

   
   x_n+1＝x_n−f(x_n)/f'(x_n)
   

   
   により定められた数列{x_n}は、方程式f(x)＝0の唯一の解に収束する。
   
   この定理で1.の仮定から前の定理を使って開区間(a, b)の間に少なくとも1つ解があり、2.からそれが唯一であることがわかります。3.は関数のグラフがその区間で上に凸であるか、下に凸であるかを示しています。4.の仮定は|f'(x)|が最小になる端点におけるこの関数の接線が区間[a, b]でx軸と交わることを意味します。
   
   (証明)　　ここでは次の場合について証明します。
   
   f(a)＜0、f(b)＞0、f'(x)＞0、f"(x)≧0、c＝a
   
   他に3つの場合が考えられますが、すべてこの場合に帰着されます。
   方程式f(x)＝0の唯一の解をsとおくことにし、点x₀をs≦x₀≦bであるとします。(x₀, f(x₀))における接線
   
   

   
   y＝f'(x₀)(x−x₀)＋f(x₀)
   x₁＝x₀−f(x₀)/f'(x₀)
   

   
   
   となり、f'(x₀)≧0、f(x₀)＞0からx₀≧x₁が成立します。一般に、
   
   

   
   x₀≧x₁≧x₂≧・・・≧s
   

   
   
   が成り立つことを帰納法で示します。x_n≧sならば、平均値の定理より、
   
   

   
   f(x_n)＝f(x_n)−f(s)
   　　　＝(x_n−s)f'(γ)　　(s≦γ≦x_n)
   

   
   
   となります。ここでf"(x)≧0から、
   
   

   
   f(x_n)≦(x_n−s)f'(x_n)
   

   
   
   となります。したがって、
   
   

   
   x_n+1＝x_n−f(x_n)/f'(x_n)≧s
   

   
   
   が成り立ち、f(x_n+1)となります。単調減少であることも。上の式からあきらかです。
   下に有界な単調減少列は極限を持ちますから、それをαとすればs≦αとなります。fとf'の連続性から、数列を作り出す式において、n→∞とすれば、
   
   

   
   α＝α−f(α)/f'(α)
   

   
   
   からf(α)＝0です。ここで、方程式f(x)＝0の解の一意性からα＝sとなります。///
   
   以上の2つが、方程式の解を求める方法の数学的基礎となるものです。これを基にして、各方法のプログラムを作成します。
   
   
   



---



3. 収束の判定
   ところで、上に書かれたことをプログラミングするにあたって一つ問題があります。反復により生成される数列{x_n}の収束を一般にどのように扱えばよいのかということです。コンピュータがいくら高速の繰り返しを得意としても、いかなる処理も無限に行うことはできません。コンピュータを使うのは、その高速性を活かして短時間で求める結果が欲しいからです。無限の時間をコンピュータに与える訳にはいきません。
   コンピュータによる実数型の計算は、近似計算であることを思い出してください。今のように方程式f(x)＝0の解を求める場合、その解を求めるための反復計算や関数の値を計算するときに計算誤差が入り込んできます。そこで、
   
   「あらかじめ許容される誤差εを与えておき目的の解の値がその誤差の範囲内に納まれば、すなわち
   
   

   
   |x_n−x_n+1|＜ε
   

   
   
   であれば収束したとみなす」
   
   または、
   
   「方程式の解における関数値を計算するときの計算誤差δを、前もって見当をつけておき、
   
   

   
   |f(x_n)|＜δ
   

   
   
   となったら収束したものとみなす」
   
   のどちらかの判定基準を用いて反復を終了し、その時点におけるx_nを解とするのが一般的です。当然、近似値となります。
   

---

[課題3・1]　関数f(・)が与えられているとき、方程式f(x)＝0の解を2分法により求めよ。

まず、関数f(x)を計算するサブプログラムはすでにあるものとして、次のようにプログラムを分解します。

• 出発点[a, b]の左端aと右端bを入力する


• 上の区間に2分法を用いてf(x)＝0の解を求める


• 解を出力する

1番目の入力では、このaとbが適当なものであるか判断しなくてはなりません。2分法では、出発区間の左端aと右端bにおける関数の値が異符号でなければなりません。それを考慮して、さらに次のように詳細化します。

• 2つの実数a、bを読み込む


• もし、f(a)f(b)＞0　ならば　プログラム終了

ここで、「f(a)f(b)＞0」というのは、f(a)とf(b)は同符号であるかの判定を行うためのものです。共に正であるか共に負であるか別々に調べなくとも、この積の正負だけで必要な判断を行うことができます。
2番目の命令をどのように詳細化するかが問題です。ここで、2分法をもう一度簡単に説明しましょう。
左端a_kとb_kで異符号の関数値を持つ区間[a_k, b_k]を、その中点m_kで2つの区間[a_k, m_k]と[m_k, b_k]に分けます。f(m_k)≠0ならば、このうち少なくとも一方の区間で、左端と右端の関数値が異符号となります。その区間を[a_k+1, b_k+1]とします。これを繰り返して得られる無限数列{a_k}、{b_k}は、共に方程式f(x)＝0の解に収束します。
ここでは、前もって与えたεを使って|a_k−b_k|＜εで収束と判定することにします。
いままでの説明から、2分法は次のような手順で実行すればよいことがわかります。ただし、区間[a, b]の中には方程式の解が存在し、変数mはその中点を意味します。また、tは一時変数で次の二つの判断で使われます。最初の判断では、f(a)とf(m)が同符号になりますからmを新たにaとします。次の判断ではf(a)とf(m)が異符号になりますからmを新たにbとします。まず、f(m)＝0となることはありませんが、もしそうなった場合でもa＝bとなり反復は終了します。

• |a−b|≧εである限り次を繰り返す
  {
  
  
  
  • m←(a＋b)/2
  
  
  • t←f(a)×f(b)
  
  
  • もし　t≧0　ならば　a←m
  
  
  • もし　t≦0　ならば　b←m
  
  
  
  }
  

この反復が終了した時点の変数aあるいはbの値を、方程式の解とします。
以上をまとめて、プログラムは次のようになります。ここで、誤差として10^-6をとってみました。

• プログラム　　「二分法」
  
  定数　ε＝1.0E-06 : 実数型
  変数　a、b、m、t  : 実数型
  {
  a、bの値を読み込む
  もし　f(a)×f(b)＞0　ならばプログラム終了
  
  
  |a−b|≧εである限り次を繰り返す
  {
  
  m←(a＋b)/2
  t←f(a)×f(m)
  もし　t≧0　ならば　a←m
  もし　t≦0　ならば　b←m
  
  }
  
  a (またはb) の値を出力する
  }
  
  

---

下線部:亀田

さて、特にツッコミもなく、ここまで至りました。と言うのも、殆どが「数学の話」ですんで「その通り」としか言いようがないのです。
また、今回は、上の「疑似プログラム」にも敢てツッコんでません。これも後で自分でwhile文で実装してみる、ってのも良い練習だとは思うから、です。
しかしながら、ここでは2分法も「再帰の枠組み」で記述することにします。と言うのもそっちの方が「簡単だから」ですよね。

ところで、上の「疑似プログラム」を見ると、条件節が入れ子になっていて、あまり美しくありません。入れ子が必要になる時はなる、んですが、不必要に入れ子になるとコードの流れを把握するのが一般的には難しくなるから、なんです。
また、下線部引いてきたところと、上の疑似プログラムの流れを見ると、実はおおまかに言うと「次の事が」プログラムの流れになるのです。

1. プログラムBisectionMethodの引数はf、a、bの3つとする。→表記は取り合えずここではBM(f, a, b)とする。


2. 計算誤差εを$$\epsilon=10^{-6}$$とする。


3. 中間点mをm＝(a＋b)/2とする。




• 条件1:もしf(a)×f(b)≧0だったらプログラムはエラーを返す。


• 条件2:もし|a−b|＜εだったらaを返す。


• 条件3:もしf(a)×f(m)＞0ならばBM(f, m, b)を呼び出す。←再帰!!!


• 条件4:それ以外の場合、BM(f, a, m)を呼び出す。←再帰!!!

だいぶ圧縮されましたね。再帰は「分岐」ですし、「反復が分岐で書ける」のなら、結果全部分岐なんで入れ子にする必要が全く無い、と言う事なのです。
注釈を少々。
まず、上の疑似コードの大本の1.を見てほしいんですが、通大テキストでは入力値はa、bの二つの実数だったんですが、上の疑似コードではf、a、bと三つに増えています。a、bは同じで良いとしてfとは何だ???
fは「関数」です。つまり、ここでは、適当な関数fを引数として与えて、その解を2分法で解けるようにしよう、としているわけです。
ここで、通大「コンピュータ」テキストのp144辺りを見てほしいんですが、Pascalによる2分法のコード例が書かれています。これ見ていると中にx*x*sin(x)と書かれた部分があるでしょう?
実はこの部分は2分法のロジック自体とは全く関係無い部分だと言う事です。つまり、このコードはx*x*sin(x)と言う関数「だけ」を2分法しようと言ってるんですね。
ちょっと待てよ……って事はx*x*sin(x)と言う関数以外を2分法する場合は?答えはその部分を書き換えて使わないとならないと言う事を示しているのです。
しかもPascalは一般的にはコンパイラ型の言語なので、ソースコードを書き換えては一々コンパイルせねばならない……要するに汎用性としてはイマイチ、なんです。シチメンド臭いですね。
だったら任意の関数を引数に与えて、それを2分法で解いた方が面白いし便利だろ、って事です。従って、ここでは引数fを増やして2分法を「任意の関数f」に適用する事とします。
次に条件3と条件4ですが、これらは通大テキスト「疑似プログラム」繰り返し内のa、ないしはbへのtの代入と同じ行為をしています。「疑似プログラム」では変数への代入だけ、ですが、再帰版では再帰の肝、「今作成している関数自体の引数を変更して呼び出す」スタイルになっています。

Pythonによる2分法

# -*- coding: utf-8 -*-

def BisectionMethod(f, a, b):

  eps = 1.0E-06
  m = (a + b) / 2.0                   # ここに注意

  if f(a) * f(b) > 0:
      raise ValueError
  elif abs(a - b) < eps:
      return a
  elif f(a) * f(m) > 0:
      return BisectionMethod(f, m, b) # ここで再帰
  else:
      return BisectionMethod(f, a, m) # ここで再帰

再帰部分はまあ、良いですよね。
Pythonのコードでの注意点はm = (a + b) / 2.0の部分です。ここを決してm = (a + b) / 2と記述してはなりません。
と言うのも、Pythonの場合、整数/整数と言う表記をすると解も整数になる、と言う性質があるから、なんです(これは他の言語、例えばC言語なんかにも見られる性質です)。正確に言うと、余りを切り捨てて商だけ返してしまうのです。
そうすると中点が必ず(中途半端な、しかも実際は中点ではない)整数として計算されて、収束計算が終わらず無限ループに突入してしまうのです。それを避ける為には、割る方の数、この場合は2ですが、これを実数型として認識させる為にあえて小数点以下を記述して2.0としなければならないのです(もちろん、与える引数を必ず実数にする、って回避法もあるんですが、メンド臭いでしょう)。
この辺は一回はハマるので気をつけて下さい(僕も良くハマります・笑)。

Rubyによる二分法

def BisectionMethod f, a, b

eps = 1.0E-06
m = (a + b) / 2.0             # ここに注意1

if f[a] * f[b] >= 0           # ここに注意2
  raise
elsif (a - b).abs < eps       # ここに注意3
  a
elsif f[a] * f[m] > 0
  BisectionMethod(f, m, b)    # ここで再帰
else
  BisectionMethod(f, a, m)    # ここで再帰
end
end

再帰部分はまあ、良いですよね。
2分法でのRubyのコードでは注意点が全部で3つあります(ちょっと多いですね)。順番に説明していきます。
Rubyのコードでの注意点その1。m = (a + b) / 2.0の部分です。ここを決してm = (a + b) / 2と記述してはなりません。
と言うのも、Rubyの場合、整数/整数と言う表記をすると解も整数になる、と言う性質があるから、なんです(これは他の言語、例えばC言語なんかにも見られる性質です)。正確に言うと、余りを切り捨てて商だけ返してしまうのです。
そうすると中点が必ず(中途半端な、しかも実際は中点ではない)整数として計算されて、収束計算が終わらず無限ループに突入してしまうのです。それを避ける為には、割る方の数、この場合は2ですが、これを実数型として認識させる為にあえて小数点以下を記述して2.0としなければならないのです(もちろん、与える引数を必ず実数にする、って回避法もあるんですが、メンド臭いでしょう)。
この辺は一回はハマるので気をつけて下さい(僕も良くハマります・笑)。
Rubyのコードでの注意点その2。引数に関数fを取る、と言う形にしていますが、コード内部でその関数fを引数aとbや変数mに適用しています。こう言う場合、Rubyでは特殊な書法を採用していて、そう言う場合、f[a]とかf[b]とかf[m]と記述します。決して数学記法と同様にf(a)とかf(b)とかf(m)とか記述しないように。括弧が違うのです。
Rubyでのコードでの注意点その3。Rubyでは絶対値を取るとき特殊な記法を用います。通常、絶対値を取る場合、絶対値を取る関数abs(大体のケースでは、絶対値＝absolute valueからこの名前が付いている)は絶対値を取りたい数値、ないしは式の(どんな形であれ)前方に書くんですが、Rubyの場合は数値/式.absと言う書き方をします。これはかなり変わった書法に見えますが、こう言うのは実はオブジェクト指向型言語と呼ばれる言語では割に良く見かける書き方です。Rubyはオブジェクト指向型言語だ、と言うのをどっか頭の片隅にでも置いておいてください(そして、それはそれでかなり一環しているのがRubyの特徴です)。

Schemeによる二分法

(define (BisectionMethod f a b)
(let ((eps 1.0E-06)
      (m (/ (+ a b) 2))
      )
  (cond ((positive? (* (f a) (f b)))
         (error a b))
        ((< (abs (- a b)) eps)
         (exact->inexact a))          ;ここに注意
        ((positive? (* (f a) (f m)))
         (BisectionMethod f m b))     ;ここで再帰
        (else
         (BisectionMethod f a m))     ;ここで再帰
        )))

再帰部分はまあ、良いですよね。
Schemeのコードでの注意点は、まあ、注意点、って程ではないんですけど、最後の結果を返す場合、単にaを返すのではなくってexact->inexactと言う命令を使って浮動小数表記に変換した方が見やすい、と言う事です。
と言うのも、Schemeはプログラミング言語としては珍しく分数を扱えます。これは元々、世界の数理科学系大学の頂点と言うべきマサチューセッツ工科大学が「工学上の限界で不正確な値を返すプログラミング言語を好まなかった」と言う事に由来しています。それじゃあ数理科学の授業で(あくまで)数学的理論を説明するのが困難になるから、です。
この事を解決する為に、マサチューセッツ工科大学は「分数で返せる計算は分数で返す」と言うとてつもない暴挙に打って出て、従って、少なくとも表面的には、Schemeの二分法では「分数を使って延々と繰り返し計算を行っている」(!)のです。これは他のプログラミング言語ではあまり見られない(しかも優秀な)特徴です。
従って、単純にaを返させると分数表記で返してくる、んですね、Schemeは。そこでexact->inexactと言う命令で(意味は正確数から不正確数への変換を表す)一般的な「望まれる」結果に変換しておくわけです。

Rによる二分法

BisectionMethod <- function(f, a, b) {

 eps = 1.0E-06
 m = (a + b) /2

 if (f(a) * f(b) > 0) {
   return(NA)
 }
 else if (abs(a - b) < eps) {
   return(a)
 }
 else if (f(a) * f(m) > 0) {
   return(BisectionMethod(f, m, b))    #ここで再帰
 }
 else {
   return(BisectionMethod(f, a, m))    #ここで再帰
 }
}

再帰部分はまあ、良いですよね。
この中では一番、特に問題が無く「思った通りの」計算結果を返してくれるのがRです。さすが統計解析(数値計算)専門のプログラミング言語だけあって良く出来ています。

無名関数

さて、もう一度繰り返しますが、通大の「コンピュータ」テキストのp.144の例示は、「$f(x)=x^2 sin(x)$と言う関数"だけを"2分法で計算する」プログラムです。万が一、$f(x)=x^2 sin(x)$「以外の」関数に2分法を適用したい場合、一々プログラム本体に埋め込まれたx*x*sin(x)を随時修正して「コンパイルしなおして」結果を見ないとなりません。
これは、あまりにもメンド臭いんで、ここでは「任意の関数fも引数として与えて」計算させるスタイルを取りました。
ここでは、その「引数としての関数fの与え方」を説明しようと思います。これは各言語毎に違います。

その話をする前に、通大テキストで扱われていた$f(x)=x^2 sin(x)$のグラフをちょっと見てみましょうか。



こう言う場合もMaximaは便利ですね。チャッチャとグラフが描けます。また、作った数値計算のプログラムの動作確認をする場合にも、こう言った「既存の」アプリケーションは重宝します。計算結果を照らし合わせる事が出来る。
さて、任意の点a、bを選びましょうか。2分法の論理によると、

1. 収束値の中点mはf(x)とx軸が交差している点である。


2. f(a)とf(b)は異符号でなければならない。

との事でした。動作確認をする為に逆に考えていくわけですね。
そうすると、グラフを見ると、例えばx＝3付近でf(x)はx軸との交点を持っています。そしてその両側のある範囲はどう見ても異符号ですよね。
そこで。キリの良い数字として、a＝2、b＝4を初期値としましょう。
次に、各プログラムに任意の関数fを与えるんですが、プログラミング言語毎に違う記法があります。
ざーっと紹介しますが、

• Pythonの場合:lambda 変数: 式


• Rubyの場合:lambda{|変数| 式}


• Schemeの場合:(lambda (変数) (式))


• Rの場合:function(変数){式}

と言う形で記述します。これらの記法は「名前の無い関数」と言う意味で、通称無名関数と呼びます(あるいは、R以外はすべてlambdaと書いているのでラムダ式、と言う言い方もします)。
例えば、今は$f(x)=x^2 sin(x)$が対象となる関数なんで、それぞれの言語に合わせた無名関数は

• Pythonの場合:lambda x: x * x * math.sin(x)


• Rubyの場合:lambda{|x| x * x * Math.sin(x)}


• Schemeの場合:(lambda (x) (* x x (sin x)))


• Rの場合:function(x){x * x * sin(x)}

となります。形式的には$f(x)=x^2 sin(x)$として与えている、と言う事が分かるでしょう。
これで、任意の関数fを引数として与える事が出来るのです。
従って、それぞれのインタプリタ上での入力コマンドは、

• Pythonの場合:BisectionMethod(lambda x: x * x * math.sin(x), 2, 4)


• Rubyの場合:BisectionMethod(lambda{|x| x * x * Math.sin(x)}, 2, 4)


• Schemeの場合:(BisectionMethod (lambda (x) (* x x (sin x))) 2 4)


• Rの場合:BisectionMethod(function(x){x * x * sin(x)}, 2, 4)

となります(注:Pythonだけは、mathモジュールを明示的に呼び出す必要があるので、インタプリタで上の関数を走らせる前にimport mathと言うコマンドを走らせて下さい)。
恐らくどれも結果は、桁数は違いますが、


3.1415920257568359


辺りの値を返してくる、と思います。これは$sin(\pi)=0$から、$f(\pi)＝\pi^2 sin(\pi)=0$になるのは容易に想像付きますね。だから円周率π回りの値を返してきたのです。
また、円周率 1,000,000 桁と合わせてみても少数点以下第6桁までは数値があってるのが分かるでしょうか?これは計算誤差εの精度を$10^{-6}$にした事に由来しています。これ以降は「誤差を含む」結果を返してる、と言う事ですね。

これでこれら2分法のプログラムは「上手く動いている」のが分かりました(と言うか、数学的に見て「上手く動く」のは当たり前なんですが・笑)。
他にも様々な無名関数や初期値a、bを与えてみて動作を確認してみて下さい。

ちなみに、質問＜３３３１＞なんかはこれがベースの課題ですね。

[課題3・2]　　関数f(・)とその導関数f'(・)が与えられているとき、方程式f(・)＝0の解をニュートン・ラフソン法により求めよ。

ニュートン・ラフソン法は理論的には2分法と比べて難しいのですがプログラムは逆に作り易くなります。基本部分は前のプログラムと同じですから一気にプログラムを書き上げてしまいましょう。

• プログラム　　「ニュートン・ラフソン法」
  
  定数　ε＝1.0E-06 : 実数型
  変数　x0、x : 実数型
  {
  x0の値を読み込む
  x←x0−f(x0)/f'(x0)
  |x−x0|≧εである限り次を繰り返す
  {
  
  x0←x
  x←x0−f(x0)/f'(x0)
  
  }
  xの値を出力する
  
  }
  
  

ここで、変数x₀は前の反復より得られた値を保存しておくためのものです。その値を用いてさらに計算をし、結果を変数xに格納します。xとx₀の値が十分近ければ、それは方程式の近似解であるとみなして反復を終了します。
定理の仮定は比較的狭い区間で満たされることが多く、初期値の与え方によってニュートン・ラフソン法で目的の解に収束しないときがあります。実際に使う場合は、2分法を併用したり、おおよそのグラフを書く等の注意が必要です。

<演習問題>

1. 手元の電卓で(1÷3)×3を実行し、結果を確認せよ。


2. ニュートン法は初期値によって目的の解が得られないときがある。その解をグラフで考えよ。

ええと、ニュートン・ラフソン法ですか。確かに大して難しく見えません。
ところで、ここでのニュートン・ラフソン法は、

関数f(x)の導関数f'(x)が分かっている場合

との事なんで、微分自体をプログラムで行うわけではないと言うトコがミソです。
例えば、通大「コンピュータ」テキストのp.145のPascalでのサンプルプログラム「NewtonRaphson」を見てほしいんですが、ここにもロジックに全く関係がないf:=x*x - 2の記述やらDf:=2*xの記述やらがありますね。2分法の時でも見たように、ここのプログラムも$f(x)=x^2−2$専用のニュートン・ラフソン法のプログラムになってると言う事です。これも$f\prime(x)=2x$なんで、ちょっと見れば分かるでしょう。
従って、微分自体は人手で行わなければダメだ、と言う事です。
もっとも、プログラムでの自動微分は一般に難しい為、これはこれで妥当な戦略だ、とは言えます。
(ここでもMaximaなんかはかなり自由自在に微分/積分を行ってくれているので、如何に優秀なソフトウェアなのか分かるでしょう。数値計算とはまた違う記号処理と言う方法を用いているのですが、一般的にプログラミングはとても難しいです。)
そこで、ここではf(x)と微分係数Df(x)の二つも(無名関数での)引数として与える、と言う事にしてみます。シナリオは以下の通りです。

1. ここでは取り合えず、f、Df、x0と言う三つの引数を取るプログラムをNR(f, Df, x0)と呼ぶ。


2. 計算誤差εを$$\epsilon=10^{-6}$$とする。


3. x＝x₀−f(x₀)/f'(x₀)とする。


4. もし、|x−x₀|＜εなら結果としてxを返す。


5. そうじゃなかったらNR(f, Df, x)を呼び出す。←再帰!!!

本質的には局所変数x＝x₀−f(x₀)/f'(x₀)を設定する必要は無いんですが、プログラム内にxを呼び出すトコが多いんで、こう言う形になっています。要するに一々右辺のx₀−f(x₀)/f'(x₀)を書くのがメンド臭い、と言う建設的な理由に基づいています(笑)。こう言う感じで「良く使う計算式は局所変数にしてしまう」と言うのはアリです。その辺は各自色々工夫してみて下さい。
では実装に入りましょうか。

Pythonによるニュートン・ラフソン法

def NewtonRaphson(f, Df, x0):
  
   eps = 1.0E-06
   x = x0 - 1.0 * f(x0)/Df(x0)         # ここに注意

   if abs(x - x0) < eps:
       return x
   else:
       return NewtonRaphson(f, Df, x)  # ここで再帰

再帰はまあ、良いですね(いい加減慣れてきたでしょう・笑)。
Pythonの注意点はx = x0 - 1.0 * f(x0)/Df(x0) の部分なんですが、決してx = x0 - f(x0)/Df(x0)とは書かない、と言う事です。疑似コードには無い1.0 *を付け忘れちゃいけない。
理由は2分法の場合と同じです。Pythonは整数/整数の計算だと整数を返しちゃうから、なのです。 1.0 *を付け足す事によって、結果1.0 * f(x0)は整数ではなくって実数だと認識され、以降の収束計算が滞り無く行われる、と言うわけです(逆に言うと1.0 *が無いと収束計算が上手く行きません)。
亀田自身はこれは結構不具合なんじゃないか?とか思います。実際、Pythonの提供元もこれは不具合だ、と認めているようで、将来的にリリースされるPython3.0では改良予定だそうです。少なくとも、「動的型付け言語」で数値の型を色々気にしながらプログラムを打つのはあまり効率的ではない、と僕も思います(しかも明示的に型変換する方法も見当たりませんしね)。

2009年1月30日追記:新しくPython3.0がリリースされている模様です。亀田はまだ確かめていません。
従って、ここで提示されているコード類は既に少々古くなっています。亀田が使用したPythonのヴァージョンはPython 2.5.2です。いまだ配布されている現役のヴァージョンなんで、取り合えずPython2.5.2を使っていて下さい。Python3.0用に記事を書き換えるかどうか、は今のところ未定です。

Rubyによるニュートン・ラフソン法

def NewtonRaphson f, df, x0     # ここに注意1

 eps = 1.0E-06
 x = x0 - f[x0].to_f / df[x0]  # ここに注意2

 if (x - x0).abs < eps
   x
 else
   NewtonRaphson(f, df, x)     # ここで再帰
 end
end

再帰はまあ、良いですね(いい加減慣れてきたでしょう・笑)。
Rubyの注意点その1。疑似コードでは微分係数での引数をDfと表記してますが、Rubyでは引数に大文字は使えないようです。従って、Ruby版では微分係数を表す引数をすべてdfにしてあります。
Rubyの注意点その2。x = x0 - f[x0].to_f/df[x0] の部分なんですが、決してx = x0 - f[x0]/df[x0]とは書かない、と言う事です。疑似コードには無い.to_fを付け忘れちゃいけない。
理由は2分法の場合と同じです。Rubyは整数/整数の計算だと整数を返しちゃうから、なのです。 .to_fを付け足す事によって、明示的にf(x0).to_fは整数ではなくって実数に変換され、以降の収束計算が滞り無く行われる、と言うわけです(逆に言うと.to_fが無いと収束計算が上手く行きません)。
Rubyはこのような明示的な型変換のメソッドを持っています。また、この記述法にも一般的なオブジェクト指向言語の影響が見られます。
ちなみに、.to_fは"to float"、つまり「浮動小数点数(実数)に変換せよ」と言う命令を意味しています。

Schemeによるニュートン・ラフソン法

(define (NewtonRaphson f Df x0)
 (let ((eps 1.0E-06)
       (x (- x0 (/ (f x0) (Df x0))))
       )
   (if (< (abs (- x x0)) eps)
       (exact->inexact x)
        (NewtonRaphson f Df x))         ;ここで再帰
       ))

これは問題無いでしょう。再帰も既に慣れてきたでしょうしね。

Rによるニュートン・ラフソン法

NewtonRaphson <- function(f, Df, x0) {

 eps = 1.0E-06
 x = x0 - f(x0) / Df(x0)

 if (abs(x - x0) < eps) {
   return(x)
 }
 else {
   return(NewtonRaphson(f, Df, x))     #ここで再帰
 }
}

これも特に問題無いでしょう。再帰も既に慣れてきたでしょうしね。
なお、Rは統計解析/数値計算ソフトなので、ニュートン法を実行するunirootと言う組み込み関数がある事を申し添えておきます。

さて、$x^2-2$の解を考えると$x=\sqrt{2}$、$x=-\sqrt{2}$になる事は分かります。これは非常に確かめやすいですね。
無名関数を利用して、初期値x₀を2として各プログラムで解を一つ求めてみましょう。インタプリタに入力するコマンドは以下の通りです。

• Pythonの場合:NewtonRaphson(lambda x: x * x - 2, lambda x: 2 * x, 2)


• Rubyの場合:NewtonRaphson(lambda{|x| x * x - 2}, lambda{|x| 2 * x}, 2)


• Schemeの場合;(NewtonRaphson (lambda (x) (- (* x x) 2)) (lambda (x) (* 2 x)) 2)


• Rの場合:NewtonRaphson(function(x){x * x - 2}, function(x){2 * x}, 2)

これで計算すると、恐らく初期値2の近傍の解として、桁数は違うでしょうが、次のような数値が得られる事と思います。

1.4142135623746899

これは確かに$\sqrt{2}$に極めて近い値となっています。
また、これも一応、確実な値は小数点以下第6位まで、となっています。それ以降は計算誤差を含んでいるんで、あまり信頼出来ませんね。
他にも関数fと初期値x₀を色々と変えてみてニュートン・ラフソン法を試してみて下さい。

<演習問題回答例>

1. 省略。


2. これはこのページを参考の事。

最大公約数と最小公倍数

さて、最大公約数と最小公倍数、です。
実はこれらの計算アルゴリズムもLisp系では「再帰の例」として良く使われる例、です。
ほらね、このセンセ、やっぱ「Lispっぽいネタ」が大好きなのです(多分、東工大の情報工学系の学生は皆やらされます・笑)。
しかし、これらの「再帰だったら簡単に書ける計算アルゴリズム」を「反復」で書かなければならないとしたらどうなるか?
これは非常に大変、です。そして説明が大変になる。従って読んでる読者はもっと大変になる、って事です。
以下はその典型例だ、って事を含んで始めましょうか。

[課題2・1]　　２つの正の整数が与えられたとき、その最大公約数を求めよ。

プログラム作成の第1段階として上の問題を次のように分解しましょう。

• 2つの正整数m、nを入力する


• mとnの最大公約数GCDを求める


• 最大公約数を出力する

1番目の入力部分については、非正値の入力があればプログラムを強制終了することにし、次のように分解します。

• 正整数m、nを読み込む


• mとnのどちらか一方が非正値であればプログラムを強制終了する

2番目の命令について、後からその手順を詳細に考えることにし、いまはそれを実行してくれる手続き"最大公約数(m、n、GCD)"があるものとします。この手続きは、2つの正整数m、nを与えると、その最大公約数GCDを返すものとします。
最後の出力は、前節と同様にこれ以上詳細に考えません。
これから、メインプログラムは次のように書かれます。

• プログラム　　「最大公約数を求める」
  
  変数　m, n, GCD : 整数型
  
  {
  
  m、nを入力する
  もし　　(m≦0またはn≦0)
  　　　　ならば　プログラムを終了
  最大公約数(m, n, GCD)
  GCDの値を出力する
  
  }
  

---

ここから、最大公約数を求める具体的な手順を考えていきましょう。数学的には、最大公約数を求める方法はいくつかあります。ここではユークリッドの互除法によって最大公約数を求めてみます。
ユークリッドの互除法が拠り所とするのが、次の定理です。

[定理]　　2つの正の整数m、n　(m≧n)　があるとき、mをnで割った余りをr　(0≦r<n)とすれば、

1. r = 0ならば、mとnの最大公約数はnである


2. r ≠ 0ならば、mとnの最大公約数は、nとrの最大公約数に等しい

上の1.はあきらかですし、2.も簡単ですからこの証明は省略します。演習問題として自分で考えてください。

下線部:亀田

はいはいはいはいはい、ストップストップストップ。
ここで、世界最古のアルゴリズム、と呼ばれる「ユークリッドの互除法」が表れました。そして、実はこの「ユークリッドの互除法」自体が数学的に言えば「帰納」、プログラミング用語で言うと「再帰」の構造である、ってのが分かるでしょうか?
ここで、mとnの最大公約数を取り合えずGCD(m、n)と置いてみて、また、mとnの剰余をm mod nと書き表す事とします。
そうすると、下線部の部分に注視すると、次の「たった」3ステップで「ユークリッドの互除法」を表現出来るんです。

1. 正整数m、nを読み込む。mとnのどちらか一方が非正値であればエラーを返す


2. m mod n = 0ならば、GCD(m, n)はnである


3. m mod n ≠ 0ならば、CCD(m, n)は、GCD(n, m mod n)である

ここまで分かれば早速実装です。んで、不思議に思うかもしれませんが「これで上手く動く」んですよ(笑)。

# -*- coding: utf-8 -*-
# Pythonの場合

def GreatestCommonDivisor(m, n):
   if m <= 0 or n <= 0:
       raise ValueError
   elif m % n == 0:
       return n
   else:
       return GreatestCommonDivisor(n, m % n) # ここで再帰

# Rubyの場合

def GreatestCommonDivisor m, n
 if m <= 0 || n <= 0
   raise
 elsif m % n == 0
   n
 else
   GreatestCommonDivisor(n, m % n) # ここで再帰
 end
end

;; Schemeの場合

(define (GreatestCommonDivisor m n)
 (cond ((or (<= m 0) (<= n 0))
        (error m n))
       ((zero? (modulo m n))
        n)
       (else
        (GreatestCommonDivisor n (modulo m n))) ;ここで再帰
       ))

## Rの場合

GreatestCommonDivisor <- function(m, n) {
 if (m <= 0 || n <= 0) {
   return(NA)
 }
 else if (m %% n == 0) {
   return(n)
 }
 else {
   return(GreatestCommonDivisor(n, m %% n))    #ここで再帰
 }
}

不思議でしょ(笑)?単に「数学的定義」を「そのまま」置き換えれば良いのです。「反復」なんて影も形も出てきませんし、「それでも動く」のは、元々数学自体が「そう言う風に」作られている、って事なんです。一旦枠組みさえ大まかに設定してしまえば、「個々の細かい計算」は全然考えなくって良い。あとはコンピュータ(と言うか、プログラミング言語)任せで良い、んです。
そろそろ「再帰」と言うプログラミングに於ける数学的手法が如何に強力なのか、分かってきたでしょ(笑)?「再帰」が使えないプログラミング言語なんて学ぶに値しない、って言った意味を。
ちなみに、「再帰が難しい」とか思うんだったら、数学が分からん、って意味です。数列や漸化式、数学的帰納法が全くわかっていない、って事なんで、「数学教員免許取得」なんて諦めた方が良い、です。あるいは、一旦プログラミングの学習を中止して、通大のテキストで良いんで、解析をもう一度やり直してください。その理論は数学の範疇なんで、プログラムをやる前に数学で押えておくべきネタです。
いずれにせよ、これを「再帰」ではなく「反復」で実装するのはなかなか骨が折れる仕事です。まあ、練習代わりにはやっても良いでしょうが、基本的にコードは「長く」なりがちですね。
以下の通大テキストの抜粋は「反復」を使う場合のコードの書き方、になります。

この命題から、2つの正整数m、nがあるとし、わり算を続けて行い

$$n > r_1 > r_2 > r_3 > r_4 > \ldots \ge 0$$

という整数で各わり算の余りを実現したとき、

• r₁ = mをnで割った余り


• r₂ = nをr₁で割った余り


• r₃ = r₁をr₂で割った余り


• r₄ = r₂をr₃で割った余り


• ・・・


• ・・・

であるとすれば、この演算の繰り返しは必ず有限回で終了します。最後のわり算は割り切れて

• 0=r_kをr_k+1で割った余り

となります。このときr_k+1が、mとnの最大公約数となります。これが、ユークリッドの互除法と呼ばれる方法です。ここで、定理の仮定にあるようにm≧nを確かめていませんが、m<nのときは、

• r₁=mをnで割った余り＝m


• r₂=nをr₁で割った余り＝nをmで割った余り
  

と考えられますから、手順としてその確認は必要ありません。この数学的手順を、これからプログラムとして書かなくてはなりません。
数学的表現では添え字を使って、すべての余りを区別しています。これにより、なにを数学的にやっているのか分かりやすい表現となります。では、プログラム上も配列等を使って、それらを区別して記憶しなくてはならないのかというと、その必要はありません。ここでは、最大公約数として最後のr_k+1だけが必要です。したがって、1つの変数rを用意して、新たな余りが得られるたびにその値を変数rに代入すればよいことになります。これは、数学では変数はなにか具体的な値そのものを表しており、時間的に変化しません。そこで、添え字を使って、別の変数として記述することによりその変化を表現します。しかし、コンピュータプログラムにおいては、変数の中身は時間(処理が進むにつれてという意味です)によってダイナミックに変化していきます。
ユークリッド互除法による最大公約数を求めるプログラムを手続きの形で書いてみましょう。

• 手続き　最大公約数(m:整数, n:整数, GCD:整数型変数)
  
  局所変数　　d, r, t : 整数型
  
  
  {
  
  d←m
  
  r←n
  
  (r≠0)であるかぎり次を繰り返す
  {
  
  t←dをrで割った余り
  
  d←r
  
  r←t
  
  
  }
  
  GCD←d
  
  
  }
  

この手続きが呼び出されると、仮引き数mとnの最大公約数が変数GCDの中に格納されます。mとnは、値だけをサブプログラムに渡す引数ですが、GCDは呼び出し先に値を返さなければならないため変数の仮引数となります。

局所変数dとrは、1つ前に実行されたわり算における除数divisorと剰余residueの値を格納するための変数です。

• n＝○○をmで割った余り

と解釈すれば、このわり算において、除数はmで余りはnとなります。そこで、dにmを代入、rにnを代入します。ユークリッドの互除法は、余りが0になるまで1つ前に実行されたわり算における除数を被除数に、また、余りを除数にした新たなわり算をおこない余りを求めていきます。それが

• l←dをrで割った余り

の部分です。ここでは、余りをすぐにrに代入せずに一時的に変数tに代入しています。ここで実行されたわり算の除数であるrの値を、後のためにdとして保存しておかなければならないからです。

• r←dをrで割った余り

と、すぐに余りを求めてそれをrに代入したのでは、次のわり算に必要な代入前のrの値が失われてしまいます。プログラムを書くとき、このように一時変数に値を保存しておき、後で必要となる値を失わないようにします。代入の順序に注意してください。
先ほどのメインプログラムの後に、この手続きを書けば課題に対するプログラムとなります。

---

極めて長ったらしい説明ですよね(笑)。さすがに読んでる途中で嫌になってきます。
もう一度繰り返しますが、元々「ユークリッドの互除法」と言うアルゴリズム自体が「再帰」的、なんです。従って、再帰的アルゴリズムを「反復」に直す事は極めて「不自然」で、上のように「長ったらしく」考えないと「反復」に変換出来ない、って事を意味しています。
91年当時のパソコンの「テクノロジー」ってのは、こう言う風に「再帰を楽々扱えない」限界が存在してた、って言い方も出来るのです。

[課題2・2]　　２つの正の整数が与えられたとき、その最小公倍数をもとめよ。

この課題のメインプログラムは、前の課題のプログラムにおける最大公約数を求める手続きを最小公倍数を求める手続きに変えるだけです。
2つの正整数mとnが与えられたとして、その最小公倍数を求める手順を考えてみましょう。このための数学的手順もいくつかありますが、上で作った最大公約数を求めるプログラムを利用することを考えてみます。

m×n＝(mとnの最小公倍数)×(mとnの最小公約数)

が成立することは、よく知られた事実です。これから、すでに作成してある最大公約数を求める手続きを使って、最小公倍数を求める手続きは次のようになります。

• 手続き　最小公倍数(m : 整数, n : 整数, LCM : 整数型変数)
  
  局所変数　GCD整数型
  
  
  {
  
  最大公約数(m, n, GCD)
  
  LCM←(m×n)/GCD
  
  
  }
  

これから、課題のプログラムを完成させることは容易ですから省略します。

<演習問題>

1. ユークリッドの互除法の拠り所となる定理を示せ。


2. 3つの正整数a、b、cの最大公約数と最小公倍数を求めるプログラムを作成せよ。

まずは課題2・2を解いてしまいましょう。
基本的には全然難しくないんですが、ある「流儀」を説明しておこうと思います。
それは別ファイルに保存した「プログラム」を呼び出したりする方法です。

課題2・2自体は全然難しくないんですが、このプログラムでは先に作ったプログラム「GreatestCommonDivisor」を呼び出さなければなりません。そしてその「呼び出し方法」にはプログラミング言語毎に流儀があります。
まずは、プログラムを書いたテキストファイルを保存するには「拡張子」と言うものを保存するテキストファイルの名前に付けないとなりません。一般にOS(オペレーティングシステム)はこの「拡張子」によって、そのテキストファイルが何のプログラムなのか識別するようになっているから、です。

• Pythonプログラムの拡張子は".py"である。


• Rubyプログラムの拡張子は".rb"である。


• Schemeプログラムの拡張子は".scm"である。


• Rプログラムの拡張子は".R"である。

ここでは、先ほど作ったGreatestCommonDivisorを記述したテキストファイルをそれぞれ

• Pythonの場合は"GCD.py"として保存。


• Rubyの場合は"GCD.rb"として保存。


• Schemeの場合は"GCD.scm"として保存。


• Rの場合は"GCD.R"として保存。

したとして、それぞれのコードがどうなるか見てみます。
なお、プログラムの保存場所はどこにすべきか?と言う問題がありますが、一般に、デフォルト指定されている場所(フォルダ/ディレクトリ)に保存すれば大丈夫、です。その辺にはデフォルトでパスが通ってるでしょうから。

# -*- coding: utf-8 -*-
# Pythonの場合

import GCD                              # これが呼び出し方

def LeastCommonMultiple(m, n):
    return (m * n) / GCD.GreatestCommonDivisor(m, n)
# Pythonではドット(.)は〜の、と言う意味

# Rubyの場合

load "GCD.rb"                   # "GCD.rb"をロード

def LeastCommonMultiple m, n
  (m * n) / GreatestCommonDivisor(m, n)
end

;; Schemeの場合

(load "GCD.scm")                        ;"GCD.scm"をロード

(define (LeastCommonMultiple m n)
  (/ (* m n) (GreatestCommonDivisor m n))
  )

## Rの場合

source("GCD.R")                         #これが呼び出し方

LeastCommonMultiple <- function(m, n) {
  return((m * n) / GreatestCommonDivisor(m, n))
}

<演習問題解答例>

1. Phaos氏が数学的に説明してるんで、それをパクります(笑)。


2. まずは作っておいたLeastCommonMultipleと言う関数(あるいは手続き/メソッド)を
   
   
   
   • Pythonの場合は"LCM.py"として保存
   
   
   • Rubyの場合は"LCM.rb"として保存
   
   
   • Schemeの場合は"LCM.scm"として保存
   
   
   • Rの場合は"LCM.scm"として保存
   
   
   
   します。こうやって保存した"GCM.*"と"LCM.*"を再利用して演習問題を解きます(これが、通大のテキストに書かれてある「分割」「統合」の例だ、と言う事を忘れないように!!!)。
   なお、これは問題としては単純で、一般に3変数a、b、cの最大公約数、最小公倍数を求める場合、最大公約数のアルゴリズムをGCM、最小公倍数のアルゴリズムをLCMとすると、
   
   
   
   • 3変数a、b、cの最大公約数＝GCM(a, GCM(b, c))
   
   
   • 3変数a、b、cの最小公倍数＝LCM(a, GCM(b, c))
   
   
   
   となります。こう言う表記を入れ子(あるいはネスト)と呼ぶのです。
   つまり、上の「入れ子表現」をそのまま書けば解答としては一丁上がり、って事なんです。
   なお、通大のテキストだと一々出力命令を噛ましていますが、一般に、出力命令を噛ますと再利用がしにくい、と言う欠点が生じます(これはC言語でも同様です)。
   従って、ここでは2つの計算結果を返す為、リスト(配列)を用いて計算結果を返すようにしてみました。
   

   
   
   # -*- coding: utf-8 -*-
   # Pythonの場合
   
   import GCD, LCM                         # 二つのファイルをインポート
   
   def GCDandLCM(a, b, c):
       return [GCD.GreatestCommonDivisor(a, GCD.GreatestCommonDivisor(b, c)),
               LCM.LeastCommonMultiple(a, LCM.LeastCommonMultiple(b, c))]
   
   # Rubyの場合
   
   load "GCD.rb"                   # "GCD.rb"をロード
   load "LCM.rb"                   # "LCM.rb"をロード
   
   def GCDandLCM a, b, c
     [GreatestCommonDivisor(a, GreatestCommonDivisor(b, c)),
      LeastCommonMultiple(a, LeastCommonMultiple(b, c))]
   end
   
   ;; Schemeの場合
   
   (load "GCD.scm")                        ;"GCD.scm"をロード
   (load "LCM.scm")                        ;"LCM.scm"をロード
   
   (define (GCDandLCM a b c)
     (list
      (GreatestCommonDivisor a (GreatestCommonDivisor b c))
      (LeastCommonMultiple a (LeastCommonMultiple b c))
      ))
   
   ## Rの場合
   
   source("GCD.R")                         #"GCD.R"をロード
   source("LCM.R")                         #"LCM.R"をロード
   
   GCDandLCM <- function(a, b, c) {
     return(list(GreatestCommonDivisor(a, GreatestCommonDivisor(b, c)),
                 LeastCommonMultiple(a, LeastCommonMultiple(b, c))))
   }
   

   
   はい、問題無いですね。
   以上です。
   

総和

[課題1・1]　1からnまでの和、$\sum_{k=1}^n k$を求めよ。

最初の議題として、1からnまでの和を求めるプログラムを作成することにします。この問題をコンピュータにやらせる場合、第1段階として、問題を次のようにおおまかに分解します。このとき、直接コンピュータが理解できるかできないかは考えません。

• 正の整数nを入力する


• 1＋2＋・・・＋nを計算する


• 上の計算結果を出力する

最後の出力命令は、コンピュータの基本命令の中に存在します。これ以上、ここでは詳細化しないことにします。ただし、その形式は人間のように融通がきくものではないことに注意してください。望むような形式で出力を行いたいときは、やはり、コンピュータにそのための手順を詳細に指示しなくてはなりません。

1番目の命令は、一見これ以上細かくすることができないようにみえますが次のように細分化しなければなりません。入力したnの値が正の整数である保証はありません。

• nを入力する


• nの値が正か調べる

この順序は変えられません。nの値が入力されない限りは、正負の判定ができないからです。次に、nの値が正でないとき、どうすればよいかも考えなくてはなりません。ここでは、強制的にプログラムの実行を終了することにします。これは本来の目的とはあまり関係ないことのようですが重要な問題です。プログラムの間違いをなくし信頼性を増すためにも、「nに負の値が入力されるはずはない」というような、思い込みを持ってはいけません。

下線部:亀田

うわあ、これ全部を「プログラムを書く前に」考えるんなら、確かにプログラム書くのは億劫でしょう(笑)。すげえな(苦笑)。これ読んでたらさすがに「大仕事」に感じて嫌気が差してきます(笑)。
いや、間違っちゃいないでしょう。確かに言ってる事は正しい、です。
でも、僕だったら「いきなり書き始め」ますね。何も考えません(笑)。
僕みたいに「いきなりコードを書き始める」スタイルを、ラピッド・プロトタイピング(rapid prototyping)と呼びます。そして、今はそっちの方が「流行り」なのです。
ラピッドプロトタイピング、と言うのは、「速い試作品化」って意味です。元々UNIXなんかでも

できるだけ早く試作を作成する

Mike Gancarz

のがベストだと言われています。
ちょっと長いですが、UNIXという考え方―その設計思想と哲学と言う書籍から引用してみましょうか。

「できるだけ早く」とは、本当に「できるだけ早く」ということだ。「大至急」だ。アプリケーションの立案に少しの時間をかけ、あとはまっしぐらに進むだけだ。命をかけてコードを書く。端末が熱いうちにキーボードを打つ。1ナノ秒も無駄にする時間はない。
この考えは、多くの人が考える「正しい設計作法」と真っ向から対立している。ほとんどの人は「アプリケーション設計を完全にしてからコーディングにかかれ」と教えられている。「まず、機能仕様書を書かなくちゃ」と言う。定期的なミーティングで方向性を確認する。細部まではっきりさせた考えを設計仕様書に書く。90パーセントの設計ができて始めてコンパイラを使う。
原理的には、もっともな指針に聞こえる。しかしこの考え方は、試作というものの重要性を見過ごしている。あるアイディアがものになりそうかどうか、目に見える現実的な場面でテストするには試作が一番だ。試作以前のアイディアは、これはこう動くはずだという憶測の域を出ない。この時点では、設計構想はほとんど理解されておらず、おそらく人によって解釈が異なっているだろう。プロジェクトの前進には、全員の合意が必要だ。試作は、具体的に目標を示すことで全員の合意を醸成する。

ほら、全然真逆の事書いてるでしょう(笑)。
実は、UNIXなんかは「そんなに窮屈な」システムでも無いんです。もちろんその延長線上で言うと、C言語さえ「そんなに窮屈な」言語でもありません(もちろん難しいですが)。
大事なのは「やっつけ仕事」なんです。そして、UNIXにはその「やっつけ仕事用」のツールが山ほど揃ってるのです。
さて、「いきなりプログラムを書き始められる」のは僕が頭が良いから、でしょうか?あるいは慣れてるから?どっちも違いますね。単に「やっつけ仕事で早く目的に達成できる」ツールをプログラミング言語として選んでいるから、に過ぎません。
もう、PythonやRubyを弄ってみた人なら分かるでしょうが、通大御用達の「疑似プログラム」で「紙の上に」プログラムの流れ、なんて書くよりもPythonやRubyで「いきなり」書いちゃった方が速い、ってのは何となく分かったでしょう。それが下手な「プログラム設計書」より良い、と言う事が。「紙の上に」疑似コード書いていったって「実際に動く」わけではありません。反面、PythonやRubyなら「紙の上に」疑似コードを書く程度の労力で、しかもコッチの方は「目の前で動く」んです。どうしてPythonやRubyが「動く疑似コード」と呼ばれるのか、そろそろ分かってきたんじゃないか、と思います。
そして、そう言う言語の方が、今は人気があるのです。ラピッド・プロトタイピングが「21世紀型の」プログラミング法、なのです。
もちろん、システム・プログラミング(例えばOSとかのプログラミング)は同様な文脈では語れませんが、数値計算のプログラムを書く程度で……余計な脅しは必要無いですよね。

本来の目的とはあまり関係ない

ホント関係無い、ですよ(笑)。関係ない事は書くべきじゃないです。脅しが好きだなあ(苦笑)。
なお、一応ここでは「プログラムの実行を終了する」のではなくってエラーを返す方向で対処していきましょうか。

プログラムの間違いをなくし信頼性を増すためにも、「nに負の値が入力されるはずはない」というような、思い込みを持ってはいけません

そうか(笑)?まあ、そう言う部分もあるでしょう。
ただし、です。プログラマ側が「全ての入力値を予測出来る」ってわけでも無いでしょう。だったらいきなり「文字」を入力されたら?どうすんだろ(笑)?
このテの問題は、ラピッド・プログラミングの文脈では「問題が起きてから修正する」方が結果効率的、なんです。大体、プログラミングの世界では「ユーザーはいつもプログラマが予測もしないソフトウェアの使い方をする」と言う格言がある程、なんですよ。全ての「禁じ手」を列挙しよう、ってのは土台無理なんです。
大体、ここでやってんのは「個人で使う」数値計算プログラムでしょ?しかも学科が「数学コース」ですし。何かの「商用製品」作ろう、とかじゃないんです。
あんま脅しても良い事ないんじゃないの?とか思うんですけどね。
気楽に行きましょうよ(笑)。「お気楽プログラミング」がここでのモットーです。

2番目の命令をどのようにすれば、コンピュータに理解できるものにすることができるかを考えます。ところで、

1＋2＋3＋・・・＋n
＝(((((0＋1)＋2)＋3)・・・)＋n)

が成り立つことに注意しましょう。この式の右辺は、演算"＋"が2項演算であることを認識し、演算の順序まで考えた記述です。コンピュータに計算をさせるときは、この演算の順序が重要な意味をもつことを常に意識しなければなりません。

いやいやいやいやいやいや。ちょっと待て。
確かに

1＋2＋3＋・・・＋n
＝(((((0＋1)＋2)＋3)・・・)＋n)

は正しいですし成り立ちます。んでもそんな考え方普通のプログラミング言語でするか?
ちょっと待て。

しかし、ここでハタ、と気づく。

「これってSchemeだったら正しい解説だよな……。」

実際、Schemeの書き方として以下のやり方はアリです。

(+ (+ (+ (+ (+ 0 1) 2) 3)・・・) n)

確かにそう言う考え方はします。
でもこの奇妙な一致は何故?
もうちょっと先を読んでみましょう。

ここで、変数"和"を用意して、命令

• 和←和＋k

を実行すれば、変数"和"の中の値がkだけ増加します。したがって、最初に変数"和"の値を0にしておき、その値を2増し、3増し、・・・、n増せば、最終的に求める結果が変数"和"の中にあることになります。すなわち、次のように分解された命令を、順番に実行すればよいことになります。

• 和←0


• 和←和＋1


• 和←和＋2


• 和←和＋3


• ・・・


• ・・・


• 和←和＋n

最初に変数"和"に0を代入していることに注意しましょう。変数に最初から0が入っているという保証はありません。
さて、コンピュータは数学等でよく使う省略≦である"・・・"を使って、上のように命令を与えても理解できません。しかし、これは同じことの繰り返しを表現しているのですから、制御構造の1つである反復を使って次のように記述することができます。

• 和＝0


• kを1からnまでとして次を繰り返す
  {
  
  
  
  • 和←和＋k
  
  
  
  }
  

下線部:亀田

がああああああああああああああああ!!!!!!!
ダメだ、もう我慢が出来ません(笑)。

確かに上の通大用語である「疑似プログラム」の通り書けば良いのは明らか、です。
が、その「繰り返し」をさせる辺りが初心者が躓くトコなんじゃないのか???

ちょっと下線部引いたトコに注目して下さい。
これら抜き書きして見ると手順としては次の3段ステップになってる事が分かるでしょう(0≦k≦nと言う変位幅である事に注意して下さい)。

1. 入力nがn<0の場合は計算が不可能である。


2. n＝0の時は和＝0である。


3. 和←和＋n

もうこうなると、Schemeユーザーとしては次のように書いちゃうのです。一回コード提示しておきますが、上の3ステップとの対応を(Scheme選んだ人以外も)見てみてください。

(define (Summation n)
(cond ((< n 0) (error n))              ;手順1
      ((zero? n) 0)                    ;手順2
      (else (+ (Summation (- n 1)) n)) ;手順3←ここが重要!!!
      ))

これで実は[課題1・1]はもう解けちゃってる、んです。「ウソ????」って思うかもしれませんが、本当です。
念のため、もう一回だけ、上のSchemeコードを手順に書き換えてみます。

1. 入力nがn<0の場合は計算が不可能である。：0以下のnが入力されたらエラーを返す。


2. n＝0の時は和＝0である。：nが0だったらそのまま0を返せば良い。


3. 和←和＋n：n番目のSummationはn-1番目のSummationにnを足したものである(ここが重要!!!)。

3番目が大事なのが分かるでしょうか?分かんなかったら上のSchemeコードの4行目を目に穴が開くほど見てください。
これは数学的には次と等価なんです。

$$a_{n} = a_{n-1} + n$$

これをプログラミングの用語で再帰(recursion)と呼びます。そして、数学の用語では帰納(induction)と呼びます(※)。
そして、上のSchemeのコードの一つの特徴は、「分岐」を使っているけど全く「反復」を使っていません。と言うか、「反復は分岐で書くことが出来る」と言うのを指摘した事を覚えているでしょうか?これが「プログラミングに於ける制御の基本2構造で十分だ」と言った最大の理由です。数学では「反復」はいらないのです(が、再帰を用いると自然に反復を表しているのです)。
また、通大のテキストのここまでの解説は、中心的な部分を抜き出してみたら、原理的にこの「再帰」を説明していて、Scheme等のLisp系プログラミング言語での説明だったら「ピッタシカンカン」なんです。
何でこんな事が起こっているのでしょうか?種明かしをしましょう。

亀田が初めてこのテキストを読んだ時、

この説明はLispやSchemeだったら合ってるのにな。

と感じました。
先にも書きましたが、

計算モデルを論じるのだったらLisp系言語が最適

なんです。かつ、明らかにこの数値計算のセクションでは「Lispっぽい説明」が随所に見られます。
学生に「数値計算モデル」を最速で教えるにはLispが最適である。特に薄い、分量が決まったテキストであればあるほど「Lispによる説明」の方が最速で効率的、なんです(だから多くの有名大学の授業ではSchemeが用いられているのです)。

「おっかしいなあ、何でだろ?」

と思ったら、このテキスト後半の筆者、菅原昭博氏、現玉川大学工学部電子工学科准教授のプロフィール見た時、謎が氷解したんです。

「謎は解けたよ、ワトソン君。」

そこにはこんな事が書いてあった。

東京工業大学大学院理工学研究科博士課程修了

「東工大か!!!!!」とか思って(笑)。
いや、東京工業大学、ってのは過去、Lisp専用のコンピュータ、通称「Lispマシン」の開発実績がある程の大学なんです。従って、「東工大」で「情報工学を学んだ」って事は当然Lispを知っています(恐らくSchemeも知ってますよ)。
このセンセ、「Lisp型の解説を」「Pascalでやろう」としてたんですね。道理で随所で歯切れ悪いのも当然だよ、と(笑)。結構、無茶苦茶承知でこのテキスト書いてるんですよ(笑)。
では、だったらどうしてScheme等のLisp系言語でこのテキストを書かなかったのでしょうか?理由は単純ですよね。1990年代初頭だから、だったんです。
当時のパソコンはとても非力だったんです。そして元々Lisp系言語は大容量のメモリとCPUパワーを必要とする言語で、「大型コンピュータ」でしか動かなかった、んです。パソコンで扱えるような代物じゃなかった、んですね。

大型コンピュータの例

PDP-11 名機、と呼ばれるミニコン(ミニ、とは言ってもコッチの感覚ではやっぱり巨大)である。大学/研究所で絶大な人気を誇った。これはまだ古い機械の部類だが、これを生産してたDECと言うメーカーはこの後もこのテの大型コンピュータを作り売りつづけていた。 なお、DECはそのうちCompaqに買収されて、そのCompaqもヒューレッド・パッカート社に買収された。

この辺で、「何故Lisp系言語が知名度が低いのか?」その理由も分かるとは思います。歴史的には、大型コンピュータを所有出来るような大学、なんてのは数が限られていましたから。国家から購入予算をぶんどってこれる大学と言えば……。そう言うわけ、なんです。そして当然東京工業大学なんてのはそう言う数少ない大学なのは間違いありません。
21世紀に入ってパソコンの能力が飛躍的に上がって過去の大型コンピュータの能力を遥に凌駕しています。要するに現代は、中学生〜高校生辺りでも「自宅で楽々Lispを扱えるようになった」空前絶後の状態なんですね(考えてみれば、亀田が90年代に人生初めて購入したパソコンなんかは、今ではUSBメモリに丸まる入ってなお余ります・笑)。
一般人の逆襲はこれから、です(笑)。パソコンの能力が桁違いに上がった以上、もはや大学/研究機関じゃなくっても彼らが愛用している「便利ツール」は自宅でも楽々扱えるのです。

取り合えずこのテキストの特徴と言えば「Lisp系言語っぽい説明を」「Pascal(を模した疑似コード)で無理矢理やろうとしている」って事です。これを把握しておいてください。解説がチグハグで、プログラミング未経験者が「分かりづらい」って思うのは当然、なんです。
多分このセンセもLispで書けたら書きたかった、ってのが本音なんじゃねえのかな、とか思います。時代がそれを許さなかった(そしてパソコンではPascalが当時はそこそこ人気があった)、って事なんでしょう。

では、再帰はPython、Ruby、R辺りでも使えるのか?使えます。元々Lisp系言語の影響受けてるんで、これらの言語はこう言うのも大得意、なんですよ(笑)。ちょっと書いてみましょう(Schemeが苦手だ、って人はこっちの方が分かりやすいでしょうし)。

# -*- coding: utf-8 -*-
# Pythonの場合

def Summation(n):
  if n < 0:
      raise ValueError
  elif n == 0:
      return 0
  else:
      return Summation(n - 1) + n　# この部分が再帰

# Rubyの場合

def Summation n
if n < 0
  raise
elsif n == 0
  0
else
  Summation(n - 1) + n  #この部分が再帰
end
end

## Rの場合

Summation <- function(n) {
if (n < 0) {
  return(NA)
}
else if (n == 0) {
  return(0)
}
else {
  return(Summation(n - 1) + n) # この部分が再帰
}
}

こんな感じですね。何を行っているのか、もう分かりますね?「現在設計している関数内」で「作っている最中の関数を(nを一個減らして)呼び出している」のです。
比べてみると……この中で一番シンプルなのはRubyかしら?Pythonだと明示的にreturn噛まさないとエラーになるんですが、一方Rubyではへっちゃらけのけ、ですね。コードの見てくれ、そしてタイピング量は結果一番短いと思います。Rもまあまあ、ですね(C言語っぽさは、やっぱり個人的には好きじゃない、んですが・笑)。
そして、最初の方に掲げた「Summation」、あれらは通大のテキストのPascalのコード例にわざと合わせた、んですが、こっちの「再帰版」の方が遥に短くシンプルに書けてるのが分かると思います。もちろん入出力の分も引数と返り値で解消しているんで当たり前なんですが、forループ系を使うよりメンド臭くないのが分かるでしょう。数学的定義を厳密に置き換えれば一丁上がり、なのですから。ループであれこれ悩む必要が無い、のです。
前の方で「一生何らかの形でプログラミング言語と付き合っていける事を目標とする」と書きました。んで、別にここに掲げた言語じゃなくても構わないんですけど、プログラミング言語を選ぶ際、大事なポイントが一つだけあります。世の中にはオブジェクト指向言語であるとか、新しくはアスペクト指向言語とか、まあ、色々あるんですけど、その辺はどうでも良くって、一番注目しなければならない事は次の一点です。それは

再帰を難なく扱えるプログラミング言語が良い言語

です。再帰を扱うのが難しいプログラミング言語はそもそも勉強するに値しません(例えばVBAとか)。これは絶対的な鉄則です。
何故なら、高級言語を使う目的は「短くコードを書けるから」の一点なんですよ。ここの数列の和の例を見れば分かる通り、forループを使うより再帰を使った方が簡単なんです。これは一体何を表しているのか?
反復ってのは「コンピュータは得意」ですが、元々人間は「反復が嫌い」なのです。従って、「反復を考える」事自体が苦痛です。書くのも嫌ですし、そもそも人間の思考回路としては「反復は不自然」なのです(だからプログラミング初心者にとっては、ループを書く事が一番難しく見えるのです)。
再帰を使う方が単純で済むのに「ループ構文を書かなければならない」と言う事は、これはそもそも人間が「ループ構文を書く」事によって一種「(プログラミング言語の為の)人間コンパイラになっている」って事ですね。「機械が得意な事は機械にやらせれば良い」のだったら、人間が反復を考えるんじゃなくって、「勝手に反復に翻訳してくれる」プログラミング言語を使った方が良い、と言うのは自明でしょう。
よって、プログラミング言語を選択するにあたって一番重要なのは「再帰を簡単に書けるかどうか」をチェックする事になるんです。

注:なお、これが人間の不思議なところなんですが、先にも書いた通り、プログラミング初心者が、必ず最初に躓くのがとにかく「反復」なのです。しかし、「反復をガリガリ書く」練習をしてしまうと、今度は「反復は簡単だけど再帰は難しい」と言う風に概念が「逆転」してしまうんです。慣れってのは恐ろしいモノです(笑)。
事実、多くのプログラミング言語の入門書ですと、最初に「反復」をガリガリ練習させておいて「反復思考の不自然さ」に初心者を慣れさせるんですが、反面、再帰の取り上げ方は「プログラミングの奥義」「難しい概念」っぽい扱いになっています。繰り返しますが、これは本来は逆なんです。再帰の方が実は簡単に書けて、スピードを稼いだり、メモリ効率を良くする為に、後により難しい反復で書き直すのが本来は正しいのです。こっちの方が順番から言うと人間にとって「優しい」のは間違いありません。
では、どうしてこう言う悪習(反復の後の再帰)が根づいたままなのか、と言うと、元々再帰の方が、工学的に「コストがかかってた」からなんです。過去のハードウェア上の制限への対応が今も引きずられているから、に過ぎません。そう言う古い時代にプログラミングを覚えた人たちがプログラミング入門書を書くと、やっぱり「反復の方が簡単だ(慣れちゃったから)」「再帰はコストがかかる(今じゃ大したコストじゃないのに)」と言う思考から抜けきれないまま初心者に語る羽目になるわけです。確かにそれは、ある種のプログラミング言語(例えばC言語やPascal)では「正解」ですが、その他では「それほどでもない」無駄な「方便」になってしまってるのです。
と言うわけで、ここではより自然な「再帰」に最初に慣れるべきだ、って事を言っておきます。特にプログラミング初心者こそ「再帰」を最初にやるべきです。少なくとも作成すべきコードと数学とが一対一対応になりやすいんで「ややこしい思考の強制」は極力減ります。そして「徐々に」反復に慣れていった方が遥に「学習がラク」です。これが「Lisp系言語の知恵」なのです。

さて、こう言う風に、原理的にはここまでは背後ではLispっぽい「再帰」ベースで解説されてるのが通大のテキストなんですが、これ以降の疑似コードでPascal調の「疑似プログラム」が提示されています。今までの話を鑑みながら読んでみてください。どっちがより複雑で技巧的なのか、分かると思います。

これまでをまとめると、目的のプログラムは次のようになります。

• プログラム　　「1からnまでの和」
  
  変数　n, k, 和:整数型
  
  {
  
  nの値を読み込む
  もし　(n≦0)　ならば　プログラム終了
  和←0
  kは1からnまでとして次を繰り返す
  {
  
  和←和＋k
  
  }
  
  和の値を出力する
  
  }
  

なお、実はPascalでもC言語でも「再帰」は可能です。ただし、一般的にメモリ管理が無茶苦茶難しくなります。
また、十進BASICなんかでも

再帰呼び出し可能な手続き定義

組込み関数にない関数は，DEF文のほか，複数行での記述が可能な関数定義を用いて利用者自身が定義して用いることができます。また，副プログラム定義を利用すれば，アルゴリズムを定義しておき，それを呼び出して利用することができます。関数定義や副プログラム定義のなかで自分自身を利用することもできるので，再帰的なアルゴリズムも簡単に実現できます。

とか書かれているんですが、どうなんでしょうねえ?
こんな感じか。

REM 十進BASICの場合
DECLARE EXTERNAL FUNCTION Summation
INPUT n
PRINT Summation(n)
END
EXTERNAL FUNCTION Summation(n)
IF n<0 THEN
 LET Summation$="ERROR!"
ELSEIF n=0 THEN
 LET Summation=0
ELSE
 LET Summation=Summation(n-1)+n
END IF
END FUNCTION

まあ、出来なくはないけど……。何じゃこりゃ、ゴチャゴチャしてて汚ねえなあ(爆)。
大体、外部関数定義、って何やねん(苦笑)。そもそも何で「必ず」入力命令経由しなきゃなんないんだか(笑)。不自由過ぎるにも程があります(苦笑)。
一つ提案。上の十進BASICヴァージョン見れば分かりますが、、一応十進BASICでも再帰は可能なようなんで(ホント一応、ですが)レポートやテストを「全部再帰で書いて」提出してやれや(笑)。
いくら何でも「91年製のテキスト」を現行で使いつづける、ってのはダメとしか思えないので、そう言う「反逆」もアリだよ、って事です(笑)。何せ「動くことは動く」んで減点のしようがありません(笑)。
そう言う形で、

「再帰はメモリ効率が悪い」

とか言ってきたら

「僕等、メモリ効率とか習ってませんから」

とか言い返せます(笑)。そもそも「再帰がダメ」とか減点してくる教授がいたら、そいつら本当に「ダメ教官」で確定ですし(笑)。いや、ホント、マジな話ですよ、これ(笑)。
まあ、もっともPython、Ruby辺りやったら十進BASICで何が何でも書きたい、とか思わなくなるでしょうけどね。「どうせだったらCかPascalの方がマシっぽい」とか思うようになるとは思います。その辺がレポートで「使いたい」って思う言語になるでしょうね。

---

[課題1・2]　次の一般項を持つ数列{$a_{k}$}の、第1項から第n項までの和を求めよ。

$a_{k} = k^2 + \sqrt{k}$、k = 1, 2, 3,・・・

もうこの辺も、前問題解ければ別段難しくないでしょう。
「整数型」も「実数型」もこれらは静的型付け言語の話なんで、動的型付け言語には一切関係ありません。まずは「ロジックが正しくて」「動くことは動く」と言う事を確認してから、C言語やPascalに「どうやって翻訳しよう?」って考えれば良い。ロジック自体はどんな言語にも移植可能なわけですから、それ以外の「言語特有の部分で」初めて「型」を考えれば良いのです(しかも十進BASICでは型を考えなくて済むし)。最初に知らなければならない事は、「どんな結果が返るか?」です。
その辺に「動く疑似コード」を使う利点がある、のです。

# -*- coding: utf-8 -*-
# Pythonの場合

import math                             # これがPythonの場合必要

def Summation(n):
  if n < 0:
      raise ValueError
  elif n == 0:
      return 0
  else:
      return Summation(n - 1) + n ** 2 + math.sqrt(n)

# Rubyの場合

include Math                    # これがRubyの場合必要

def Summation n
if n < 0
  raise
elsif n == 0
  0
else
  Summation(n - 1) + n ** 2 + sqrt(n)
end
end

;; Schemeの場合

(define (Summation n)
(cond ((< n 0) (error n))           
      ((zero? n) 0)
      (else (+ (Summation (- n 1)) (expt n 2) (sqrt n)))
      ))

## Rの場合

Summation <- function(n) {
if (n < 0) {
  return(NA)
}
else if (n == 0) {
  return(0)
}
else {
  return(Summation(n - 1) + n ^ 2 + sqrt(n))
}
}

さて、一つだけ注意点があります。
PythonとRubyの場合、(ある意味)欠点があって、それは「平方根を取る」と言う簡単な数学的操作でさえ、「数学関係のライブラリ」をインポートしないと使えない、と言う事です。
この辺、言語設計者の好み、ってのもあるんですが、ある主義によると「言語の中核部分はなるべく小さくしたい」と言う流儀があるようで、Python、Rubyはその流儀に従っています。
確かに、通常のプログラミングに於いては「数学的な計算」ってそんなにやらないんですよ(笑)。そこで、Python、Rubyは「数学関係の機能」を本体から切り離しちゃっている、のです。よって、数学的計算をやる場合、明示的に「数学関係のライブラリを使います」と宣言しないとならないのです。
反面、Schemeは数学出身なんで、数学的関数はたくさん揃っています。また、Rは元々「統計解析用」なんで、当然数学的関数はそのままで使い放題なんですね。
平たく言うと、どうして高校数学の窓で紹介する言語としてPythonが最終候補から落ちたか、と言うと理由はそんなトコ、なんです。いちいち毎回import mathって書くのがメンド臭かったから、です(笑)。
(ここ、良く覚えておいてください。「メンド臭い」って言うのがプログラミングに於いて、如何に強力な理由になるのか、を・笑)
まあ、Python、Rubyは「数学には恒常的に使うにはメンド臭い」って思っただけで、日常用のプログラミング言語として、とか、情報工学系の初心者用言語としては、いずれにせよ優れているとは思います。

さて、余談ですが、こう言う「機能」の「本体との切り離し」、ってのはプログラミング言語設計に於いて、結構良く見かけるんです。
例えば。
一番典型的な例としては、やっぱりC言語がありますね。こいつはクセモノで、何と「本体だけ」では入出力機能さえ無いんです。
C言語で有名な「一番最初に書くべきプログラム」として、通称「HelloWorld」プログラム、って言うものがあります。単純に"Hello World!"って画面に表示させるだけ、のしょーもないプログラムですね(笑)。
典型的なHelloWorldプログラムは次のように書きます。

#include <stdio.h>  /* ここだ!!!これは一体何だ? */

int main(void)
{
  printf("Hello World!\n");

  return 0;
}

まあ、大体、プログラミング初心者はこのコード見るだけでも「わけが分からない」って不安に陥る、んですよ(笑)。どーしてたかが"Hello World!"って表示させる為だけにこんなにいっぱい書かなきゃならんのか?と。
やはり冒頭ですよね。ここです。

#include <stdio.h>

これで「入出力関係のライブラリをインポートします」って言ってるわけなんです。何せ、Cには入出力機能がない。先に見た、「Python、Rubyには数学的機能が本体には無い」と言うのと対比してみれば良く分かるでしょう。「必要となるライブラリは明示的に呼び出す」ってのがある種のプログラミング言語の流儀、なんです。
ちなみに、一番簡単なCのプログラムは次のようなプログラムです。

int main(void)
{
  return 0;
}

酷いでしょ(笑)?このプログラムは実は「何もしない」プログラムなのです(笑)。入出力が使えない、となると「これくらいしか」やる事無いんですよ。それは「何もしない」事です(笑)。
まあ、いずれにせよ、この「ライブラリのインポート」と言うのは、どのみちいつかは経験する羽目になるんで(例えばC言語とか、で)、Python、Ruby組は「数学やるときは数学ライブラリをインポートする」と念仏のように唱えてても良いでしょう。ここでもいずれ、もっと多用する羽目になるでしょうから。

さて、そこまで了承して、以降は流していきます。
上の4つの「走る疑似コード」をどうやってPascal(あるいはC言語)へと翻訳するのか、と言う説明だと考えれば以下はそれほど難しくもありません。結構重要なのは「型に関する」説明ですね。
また、Pascalとかが「如何にメンド臭い言語なのか」大変分かりやすい解説になっている、と思います(それはC言語に付いても、です)。

1段落目の問題の分解は、課題1・1と同様に、

• nを入力する


• $a_1 + a_2 + \ldots + a_n$を計算する


• 上の計算結果を出力する

となります。当然、問題となるのは2番目の命令です。$a_k$の値を求めることと、その値のk=1からnまでの和を求めることとは別々に分けて考えることができます。そこで、$a_k$の値を計算する実数値関数a(k)があるとすれば、実数型変数"和"を導入して、この課題のプログラムは、次のように書けます。

• プログラム　　「数列の第n項までの和」
  
  変数　n, k : 整数型
  　　　　和 : 実数型
  
  
  {
  
  nの値を読み込む
  もし　(n≦0)　ならば　プログラム終了
  和←0
  kは1からnまでとして次を繰り返す
  {
  
  和←和＋a(k)
  
  }
  
  和の値を出力する
  
  }
  

関数a(k)の仕様は問題の中に与えられています。したがって、そのサブプログラムをすぐに次のように書くことができます。

• 関数　a(k : 整数) : 実数型
  {
  
  $a \leftarrow k^2 + \sqrt{k}$
  
  }
  

前のメインプログラムとこの関数のプログラムを一つにして、課題1・2のプログラムとなります。
上の関数a(k)のプログラムは、なにも問題ないように見えますが、実引数に負の整数が与えられたときは、正しく機能しないことに注意してください。負の平方根は存在しません。今の場合、これを呼び出すメインのプログラムでは、実引き数として負の値を与えることは確かにありません。しかし、この関数を他のプログラムで流用したりする場合も考えて、メインプログラムのnの値の判定と同様に、引き数が本当に非負の値であるか検査する部分を追加することにより信頼性を増すことにします。このような姿勢によって、プログラムをコンピュータで実際に動かしたときでるエラー(実行時エラー)を減らすことができます。そこで、上の関数のプログラムを次のように書きかえることにします。

• 関数　a(k : 整数) : 実数型
  {
  
  もし　($k\le 0$)　ならば　プログラム終了
  $a \leftarrow k^2 + \sqrt{k}$
  
  }
  

この節では、同じ変数に繰り返し代入することで数学的にはΣを用いて表されるものを計算できることを学習しました。

<練習問題>

1. n!(nは非負の整数)を求めるプログラムを作成せよ。


2. 1.のプログラムにおいて、nが大きいとき整数型の最大値32767を超えるが、どのように処理すればよいかを考えよ。

<回答例>

1.においては0!=1である、と言う数学上の約束さえ思い出せば、今まで書いたプログラムを改造してすぐ作成可能です。
これもプログラミングの学習に於いて「再帰の例」としては良く使われます。
(つまり、通大のテキストのように「繰り返しで」書く事は滅多にありません。)

# -*- coding: utf-8 -*-
# Pythonの場合

def Factorial(n):
    if n < 0:
        raise ValueError
    elif n == 0:
        return 1
    else:
        return Factorial(n - 1) * n     # ここが再帰

# Rubyの場合

def Factorial n
  if n < 0
    raise
  elsif n == 0
    1
  else
    Factorial(n - 1) * n        # ここが再帰
  end
end

;; Schemeの場合

(define (Factorial n)
  (cond ((< n 0) (error n))             
        ((zero? n) 1)
        (else (* (Factorial (- n 1)) n)) ; ここが再帰
        ))

## Rの場合

Factorial <- function(n) {
  if (n < 0) {
    return(NA)
  }
  else if (n == 0) {
    return(1)
  }
  else {
    return(Factorial(n - 1) * n)                #ここが再帰
  }
}

まあ、試しにforループとかwhileループで書いてみてください。練習代わり、としては良いでしょう。
2.に関して言うと、動的型付け言語を使う以上「そんな事知るか!!!」です(笑)。その辺はプログラミング言語の方で回避出来る範囲では回避してくれるでしょうから(笑)。
真面目に考えると次の方策が考えられます。

• 単精度の整数型ではなくって倍精度の整数型を宣言して使う。


• あるいは、32767を超える最小のnを先に計算しておいて、そのn以上の数値が入力された場合、プログラムが停止するかエラーを返すかするように仕込んでおく。

辺りでしょうね。
なお、本格的な数値計算に於いては、

$$n! = 1 \times 2 \times 3 \times \ldots \times n$$

と言うのはなかなか大変な計算なのは確か、です。すぐ整数が巨大化してしまう。
こう言う場合、トリックとしては対数を取って、

$$\log{1} + \log{2} + \ldots + \log{n}$$

と和の形にしてしまう事が良く行われています。
と言うのも、

1. 浮動小数点型である対数の方が、数値の増加率を抑えられてコンピュータで扱いやすい。


2. 一般的にコンピュータでは、乗算よりも加算の方が計算スピードが速い。

と言う特徴があるから、なんです。必要になったら指数で元の形に戻す、と言うトリックを良く使います。
ここではそれを書きませんが(と言うか、すぐ書けるでしょう)、興味のある人は実装してみて下さい。

※:あるいは単に「漸化式」って言った方が通りが良いかもしれません。
なお、「再帰の方が簡単だ」と再三書いてますが、これは本当です。と言うことは、主張しているのは「漸化式が簡単だ」と言う事です。果たしてこれは本当か?数学が苦手な人間でも「漸化式が簡単だ」と思えるのかどうか?
結論から言ってしまえば「その通り」です。実は数学が苦手な人間でも漸化式自体にはあまり抵抗を示さないもの、なのです。

ウッソ〜〜〜〜!!!!!

と言う声が聞こえてきますが(笑)、本当です。
高校教育現場等で、数列が苦手、な生徒は事実大量に存在しているでしょうし、「漸化式なんか点数取れない分野だよ」って思う人もいるでしょう。はい、それは事実だと思います。ただし、そこに勘違いがあります。
「数学が苦手な人」が嫌なのは、「漸化式そのもの」が嫌いなんじゃなくって、「漸化式を"解け"」って言われるのが嫌、なんです。この二つは全然意味が違います。「解け」って言われた段階で、Σが出てきたり、計算が技巧的でメンド臭かったりで「嫌だ、と感じる」のが本当のところなのです。
十中八九、「漸化式の"意味"を述べよ」とか「書け」とか言われたら割にスラスラ読めるだけは読める/書けるだけは書ける、って生徒の方が多いだろ、と思います。連中は「解く」のが嫌なだけ、なんです(笑)。
これを鑑みると、「再帰」って方法論は「漸化式を設定して」、"解く"作業はプログラミング言語に丸投げ、って方法論です。一方、「反復」はΣの中身を想像して「動作を書き下す」と言うのが行われている内容です。果たしてどっちが楽なのか?と言うと「漸化式を作るだけ作っておいてあとは知らんぷり」の方が圧倒的にラクだろ、と思います。