課題

2015/11/1,2019/4/25,2022/6/7

準備

フィボナッチ数列(P44)を生成する関数を定義しなさい。
fib(x)
引数nは0以上の整数とする。nが負の値であるときの動作は保証しない。
fib,fib2を定義しなさい。関数fibは再帰関数であるが線形再帰関数ではない。関数fib2は線形再帰関数であり末端再帰関数である。
008a.scmとして保存008b.scmとして保存
関数fibは再帰関数であるが線形再帰関数ではない。
#lang racket
(define (fib n)
  (cond ((equal? n 0) 1)
        ((equal? n 1) 1)
        (else 各自検討)    ))
関数fib2は線形再帰関数であり末端再帰関数である。
#lang racket
(define (fib2 l m n)
  (cond ((equal? n 0) l)
        ((equal? n 1) m)
        (else 各自検討)    ))
(define (fib n) (fib2 1 1 n))

課題

課題Aができた段階で「印刷」を行う。ソースプログラム(001a.scmから~008b.scm)を印刷し、「実験報告書」(当日提出分)を提出する。
「実験報告書」(当日提出分)を提出した後、課題B以降を実施する。まとめ(実験結果)は考察と併せて、次回実験時に提出する。
  1. 非末端再帰関数と末端再帰関数の違いを理解する。
    n=40について、008a.scm,008b.scmの処理時間を計測する。処理時間の計測はtime関数(Scheme組込関数)を使用する。
    (fib 40) (fib 40)

  2. インタプリタとコンパイラの違いを理解する。
    n=5×105について、008b.scmの処理時間を計測する。インタプリタによる処理時間とロードモジュール(コンパイラが生成した実行可能形式ファイル)による処理時間を比較する。
    インタプリタによる処理コンパイラによる処理
    インタプリタでの処理時間はtime関数(Scheme組込関数)を使用する。
    実行時間はcpu timeとreal timeを記録する。
    計測後、Drracketはすべて終了する。
    (fib 500000)
    		008b.scmをコンパイルした後、実行する。コンパイル及び実行手順を示す。
    インタプリタの処理時間計測で使用したtime関数(組み込み関数)の結果は無視する。
    #端末を開く
cd ~/scheme
mzc --exe 008b.bin 008b.scm
time ./008b.bin
    実行時間はrealとuserを記録する。
    (fib 500000)

  3. 非末端再帰関数の実行時間(user)を計測する。
    008a.scmをコンパイルし実行時間を計測する。Schemeインタプリタは使用しない。
    ソースコード中のtime関数(組み込み関数)は削除する。
    n=40,42,44,46,48,50について実行時間(user)を計測する。
    008a.bin 008a.bin
  4. 末端再帰関数の実行時間(user)を計測する。
    008b.scmをコンパイルし実行時間を計測する。Schemeインタプリタは使用しない。
    ソースコード中のtime関数(組み込み関数)は削除する。
    n=3×105,5×105,7×105, 1×106,2×106,3×106,5×106について実行時間(user)を計測する。
    008a.bin 008a.bin
  5. C言語でフィボナッチ数列を求めるプログラムを作成し、実行時間を計測する。
    言うまでもないことだが、C言語で開発するプログラムを実行するコンピュータの同じ能力はScheme言語を実行したコンピュータと同じものを使用する。
    LinuxにおけるC言語によるプログラミングは「情報工学実験2」(3SJ)で実施している。その他の科目でもMicrosoft WindowsにおけるC言語によるプログラミングを行っている。プログラミングの詳細はこれらのテキストを参考にする。
    C言語実行環境がScheme言語実行環境と異なる場合、まとめE,FにおいてC言語実行環境を明記する。
    C言語開発環境(OS,開発ツール等)はとくに指定しないが、C++言語およびC++コンパイラは計算時間が遅くなる傾向にあるので使用しないほうがよい。統合開発環境ではでC++コンパイラをデフォルトで使用する場合があるので注意する。
    C言語で作成したプログラムは作成者により実行時間に大きな違いがあるので、測定するnの範囲は指定しないが、n=1×105から3×106程度の範囲を期待する。 実行時間が2秒以上10分以下の範囲で測定点は6点以上とする。グラフを描いたとき横軸方向について測定点が偏ることがないようにnの値を配慮する。
    まとめEにおいてScheme言語との比較を行うため、n=5×105以外の値を使用する場合は課題Cにおいても同じ値nで計算時間を測定する。
    実行結果に基づいて、まとめEを実施する。
    scanf関数等を使用したとき、人間が値の入力に要する時間は実行時間・計算時間に含まれる。
    入力に要する時間を排除するためには、 等の工夫が必要になる。
    計算に配列(固定長配列)を使用する場合、配列の長さ(配列の添字の最大値)はnの値に依存してはならない。
    nが大きくなり計算ができなくなった等の理由で配列の長さを変更したときは、すべてのnについて、計算時間を測定しなおす。
    連結リスト、動的配列等を使用する場合は、測定を続行してよい。
    提出するプログラムリストには n=5×105程度の値(2秒〜10分程度で計算できる値)に対するフィボナッチ数を求め、この処理に要した時間を記載しなさい。処理に要する時間はtimeコマンドで確認する。C言語から用意する時間関数(time関数等)ライブラリは使用しない。

    ファイル名は008c.c等とする。(008c.cppはC++コンパイラを使用することがあるので避けたほうがよい)
    処理系・開発環境によってはcコンパイラと言いつつ、c++コンパイラを使用している場合がある。
    どのような開発環境を使用してもよいが、「自己責任で開発環境を選択」し、「自分が使用している開発環境の詳細を把握」し、「自己責任で開発環境を選択」してほしい。
    プログラムは再帰関数(あるいは末端再帰関数)を使用してもよいが、再帰関数の使用は必須ではない。

    以下Linuxでコンパイル・実行する方法について説明する。
    メモリリークの発生が疑われる場合はコンパイルオプションに-fsanitizeをつけて動作確認を行うとよい。 
    #Linuxでメモリリークをチェックする方法
gcc -g -fsanitize=address -O3 008c.c&&./a.out
    処理に要した時間はtimeコマンドで確認できる。
    gccを使用する場合、最適化オプション(-O0,-O1,-O2,-O3,-Os等)は省略してもよいが、計算時間に影響するので、同一のオプションを指定する。 
    gcc -O3 -o 008c 008c.c
time ./008c
    コンパイラの使い方がわからない場合はgcc自身に聞くか(--hオプション)、manコマンドで詳しい説明を見ることができる。 
    gcc --h 
man gcc
==アルゴリズムがわからない君へ==
ヒントを見る他に、後藤先生に謝りに行き、「多精度演算のアルゴリズム」をおしえてもらうという方法もある。
ヒントを見る前に言っておくが、「プライドが高い人」「自力でどうにかするという人」「心が弱い人」　は　ヒントを見ないほうがいい。
このヒントはあなたのメンタルを著しく侵食する場合があります。
自らの魂を差し出してでもアルゴリズムを知りたいという強い意志を持つものだけに許されたことであると行為であるとわかった上でヒントをみてほしい。



==GMP:The GNU Multiple Precision Arithmetic Libraryで楽をしようとしている君==
ハッキリ言おう。「フィボナッチ数列がほしい」わけではない。それはscheme言語がすでに答えを出している。
ここでC言語が登場するのは、1年生から学習してきたC言語の知識をアレコレ駆使して、自分の知識と経験を積んでほしいからだ。
GMPのソースコードは公開されている。
　・ソースコードを熟読し
　・内部構造と処理を理解し
　・自身のコードとして利用できる
のであれば、GMPの使用を禁止するつもりはない。
そのようなことをせず、中身もわからないまま他人様が作ったライブラリを使うことがこの実験の目的ではない。
以上のことを踏まえ、GMPを使うというのであれば、
　・自分が学習するチャンスを放棄したわけではないことを示し
　・「この中身はどうなっているの?」　「高速化のためにどのような工夫をしているの?」という質問に答えてもらいたい。

まとめ

課題A,B,C,D,Eより、実験の結果をまとめる。
  1. 非末端再帰関数と末端再帰関数の違い
    例
    プログラム実行時間memo
    非末端再帰関数
    008a.scm    		cpu time: 6129 real time: 6134 gc time: 10
    時間の単位はミリ秒    		 
    末端再帰関数
    008b.scm    		cpu time: 0 real time: 0 gc time: 0
    時間の単位はミリ秒    		008b.scmは処理時間が短すぎて008a.scmと比較できない。

  2. インタプリタとコンパイラの違い
    例
    プログラム実行時間memo
    インタプリタによる処理cpu time: 3308 real time: 3313 gc time: 1439
    時間の単位はミリ秒    		インタプリタによる処理を基準とする
    ロードモジュール
    (コンパイルしたもの)    		real 0m2.690s
    user 0m2.108s
    sys 0m0.572s    		(user)/(cpu time)=0.6372
    (real)/(real time)=0.8120

  3. 非末端再帰関数の実行時間
    実行時間Tの近似式を導出する際、手順を省略することなく記述する。計算時間はcpu timeを使用する。
    近似式の導出で使用する計算時間T(実測cpu time)は2秒以上のものを使用する。 近似式よりn=100の計算に要する時間を予測する。

    記述例
    記述例[片対数グラフ]
    記述例[片対数グラフ]
    (fib 100)の計算には2.7721×1012秒=xxx年かかる。

    [重要]グラフを作成するときははつぎのことに注意する。
    記述例[片対数グラフ]

  4. 末端再帰関数の実行時間
    実行時間Tの近似式を導出する際、手順を省略することなく記述する。計算時間はuserを使用する。
    近似式の導出で使用する計算時間T(実測user)は2秒以上のものを使用する。 近似式よりn=1×107の計算に要する時間を予測する。

    記述例
    記述例[両対数グラフ]
    記述例[両対数グラフ]
    (fib 10000000)の計算には899.299秒=xxx分xx秒かかる。

  5. C言語で作成したプログラムについて実行時間を計測する。
    実行時間Tの近似式を導出する際、手順を省略することなく記述する。計算時間はuserを使用する。
    近似式の導出で使用する計算時間T(実測user)は2秒以上のものを使用する。 近似式よりn=1×107の計算に要する時間を予測する。
    処理手順はCまたはDと同様になる。グラフは、各軸を対数にするなどの工夫により測定点を直線状にプロットする。
    C言語実行環境がScheme言語実行環境と異なる場合、まとめE,FにおいてC言語実行環境を明示する。

  6. Scheme言語(インタプリタ,コンパイラ)とC言語(コンパイラ)を比較
    C言語による処理時間とScheme言語(インタプリタによる処理)を比較する。
    C言語実行環境がScheme言語実行環境と異なる場合、まとめE,FにおいてC言語実行環境を明示する。
    実行環境について記載がない場合、実験報告書は再提出となるので注意する。
    虚偽の報告は許されない。 実行環境について虚偽の報告があった場合、再実験の後に正しい報告書を提出することになる。これに伴い本実験の評価は著しく低くなるので注意する。
    C言語実行環境記述例1
    「C言語実行環境記はScheme言語実行環境と同じ」と記載する。     		C言語実行環境記述例2
    C言語実行環境記はScheme言語実行環境と異なる場合は、各自で調査する
    OS:Linux Pr 5.10.0-14-amd64 #1 SMP Debian 5.10.113-1 (2022-04-29) x86_64 GNU/Linux
    C言語コンパイラ:gcc version 10.2.1 20210110 (Debian 10.2.1-6)     		OS:Microsoft Windows 10 version 21Hxxx(OSビルド xxxxx.xxxx)
    統合開発環境:Visual Studio 20xx Academic version xx.xx.x
    C++コンパイラ:Microsoft Visual C++ 20xx

    プログラム実行時間memo
    Scheme言語
    インタプリタによる処理    		cpu time: 3308 real time: 3313 gc time: 1439
    時間の単位はミリ秒    		インタプリタによる処理を基準とする
    C言語
    ロードモジュール
    (コンパイルしたもの)    		real xmx.xxxs
    user time: xmx.xxxs
    sys xmx.xxxs    		(user)/(cpu time)=x.xxx
    (real)/(real time)=x.xxx