\documentclass[a4j]{jarticle}

\title{退屈な人向け課題(1)}
\author{数学と情報処理}
\date{}

\begin{document}
\maketitle

\section*{A}
MuPAD を利用して階乗計算をあなたのPCでは何桁まで(実用的に)計算できるでしょうか？
ソフトウェアの構造・設定やハードウェア性能などに依存するのでケースバイケースですが
大雑把には以下のような評価が成立しそうです。
\begin{itemize}
\item メモリ消費量 $\sim$ 桁数(ビット長) $\sim \ln n!$
\item 計算量 $\sim$ 桁数(ビット長) $\times$ 掛算の回数 $\sim n \ln n!$
\end{itemize}

現行のPC上で、上記のような概算が成立する根拠を示してください。
あるいはこの概算が誤りである根拠を示してください。


\section*{B}
階乗の近似式: スターリング(Stiriling)の公式
\[
n! \sim \sqrt{2\pi}  n^{n+\frac{1}{2}} e^{-n}
\]  
このスターリングの公式を証明してください($\sim$ の意味も示すこと)。


\section*{C}

ものすごく荒い近似
\[
\ln n! \sim (n+\frac{1}{2}) \ln(n) - n \sim n \ln n
\]
\[
n \ln n! \sim n^2 \ln n
\]
\begin{description}
\item[メモリ消費量] $m(n) \sim n \ln n$
\item[計算量] $c(n) \sim n^2 \ln n$, $c(k n) \sim k^2 n^2 (\ln n + \ln k) \sim k^2 c(n)$
\end{description}
上記のような近似が成立する根拠を示してください。余裕があれば上限・ 下限を示して挟み打ち評価もしてみてください。

\section*{D}

time を使って大雑把に計算量の計測実験(例)
\begin{verbatim}
  MuPAD Light 2.5.3
  OS: Windows XP Pro SP2
  CPU: Peutium M 1.2GHz
  メモリ: 1GB

↓あまりよくないプログラム例

for i in [10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000,
          90000, 100000, 110000, 120000, 130000, 140000] do
         print(expr2text(i) . "!   " . expr2text(time(i!)/1000.0) . "sec")
end_for

  10000!   0.32sec
  20000!   0.992sec
  30000!   2.363sec
  40000!   4.316sec
  50000!   7.24sec
  60000!   10.114sec
  70000!   13.931sec
  80000!   18.706sec
  90000!   23.855sec
 100000!   29.893sec
 110000!   35.981sec
 120000!   43.413sec
 130000!   51.103sec  
 140000!   エラー (MuPAD が暴走状態となる)
\end{verbatim}  

time コマンドの内容をオンラインヘルプで調べ てみてください。 そして、あなたのPC上で MuPAD を使って階乗計算がどこまで実用的に可能 かどうか実験してみましょう。
\begin{itemize}
\item ハードウェア・ソフトウェア(OSなど)の仕様を明記しましょう。
\item プログラムの方法は上記例に拘る必要はありません。 
\end{itemize}


\section*{E}
理論値 C と 実験値 D の比較検証をして論評してみてください。 

%\section*{事務的なこと}
%\begin{itemize}
%\item 課題提出方法: メールもしくは紙。
%\item 締切: とりあえずなし(講義の進み具合によって決めます)。
%\item その他: 提出があれば、この講義の単位評価には組込みます。
%\item 提出されたレポートは講義中で公開することがあります。 
%\end{itemize}

\end{document}