階乗計算

• [A] ソフトウェアの構造・設定やハードウェア性能などに依存するのでケースバイケース
  • メモリ消費量 〜 桁数(ビット長) 〜 ln(n!)
  • 計算量 〜 桁数(ビット長) * 掛算の回数 〜 ln(n!) * n
  Q: 現行のPC上で、上記のような概算が成立する根拠を示してください。 あるいはこの概算が誤りである根拠を示してください。
• [B] 階乗の近似式: スターリング(Stiriling)の公式

  n! 〜 sqrt(2*PI)*n^(n+1/2)*exp(-n)
    

  Q: スターリングの公式を証明してください(〜 の意味も示すこと)。
• [C] ものすごく荒い近似

  ln(n!) 〜 (n+1/2) * ln(n) - n 〜 n * ln(n)
  ln(n!)*n 〜 n^2 * ln(n)
  
    m := n -> n * ln(n)    (メモリ消費量)
    c := n -> n^2 * ln(n)  (計算量)
    c(k*n) 〜 k^2 * n^2 * (ln(n) + ln(k)) 〜 k^2 * c(n)
    

  Q: 上記のような近似が成立する根拠を示してください。余裕があれば上限・ 下限を示して挟み打ち評価もしてみてください。
• [D] time を使って大雑把に計算量の計測実験(例)

    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 が暴走状態となる)
    

  Q: time コマンドの内容をオンラインヘルプで調べ てみてください。 そして、あなたのPC上で MuPAD を使って階乗計算がどこまで実用的に可能 かどうか実験してみましょう。
  • ハードウェア・ソフトウェア(OSなど)の仕様を明記しましょう。
  • プログラムの方法は上記例に拘る必要はありません。
• [E] 理論値 C と 実験値 D の比較検証をして論評してみてください。

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