コミックマーケット89記念！ANSI C89コンパイラを作る【KMCアドベントカレンダー12日目】 - prime's diary
この記事はKMC Advent Calendar 2015 - Adventar12日目の記事です。 宣伝 サークル「京大マイコンクラブ」は、コミックマーケット89で「木曜日 東地区 "モ" 42b」に配置されました！ コミケWebカタログにてサークル情報公開中です https://t.co/BtKSerlV6R #C89WebCatalog— 京大マイコンクラブ (@KMC_JP) 2015年10月30日 部誌、自作ゲーム、そして今回の本題であるコンパイラのソースコードを置く予定です。 3日目(12月31日)東地区 "モ" 42bです！よろしくお願いします！！*1 本題 今度のコミックマーケットは89回目です。コミックマーケット89は通称C89と呼ばれています。 C89といえばC言語の最初の標準規格ANSI-C:1989(通称C89, ANSI C89など)ですね！ こうなったらやること
RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい - prime's diary
qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。 40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。 こちらが元のソースコード def fib(n) f0, f1, v = 0, 1, 0 n.times do |x| if x <= 1 v = x else v = f0 + f1 f0, f1 = f1, v end end return f0 + f1
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
