高速な累乗計算 - あどけない話
累乗(x^n)を単純に計算すると、オーダーは O(n)となり効率が悪いです。そこで、nを2の累乗に分解して計算する高速化手法が一般に知られています。 たとえば、3 の 11 乗を計算する場合を考えましょう。11 は 1 + 2 + 8 に分解できます。 この累乗の系列では、ある値は一つ前の値を2乗することで計算できます。たとえば、こうです。 3^1 = 3 3^2 = 3 * 3 = 9 3^4 = (3^2)^2 = 9^2 = 81 3^8 = (3^4)^2 = 81^2 = 6561よって、3^11 は以下のように計算できます。 3^11 = 3^(1+2+8) = 3^1 × 3^2 × 3^8 = 3 × 9 × 6561 = 177147この方法のオーダーは、O(log2(n)) です。 遅延評価風に RSA のために高速な累乗計算を Haskell で実装したことがありまし
プリエンプション - Wikipedia
プリエンプション（英: preemption）は、マルチタスクのコンピュータシステムが実行中のタスクを一時的に中断する動作であり、基本的にそのタスク自体の協力は不要で、後でそのタスクを再実行するという意味も含む。このような動作をコンテキストスイッチと呼ぶ。通常、保護されたタスクか、システムの一部であるプリエンプティブスケジューラが行う。それらは、システム内の他のタスクに割り込み、後でそれらタスクを再開させることができる。「プリエンプト」とは「先取りする、差し替える」の意。 ユーザーモードとカーネルモード[編集] どんなシステム設計でも、プリエンプション不可能な操作が存在する。それは通常カーネルの機能や割り込み処理であり、それらを完了まで実行できるようにしておかないと、競合状態が発生しやすくなり、デッドロックを誘発する。タスクがカーネル機能を処理中は、スケジューラがプリエンプションできないよ
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
volatileによる多重定義::実装技術
2005-09-25 μITRONのようなマルチタスク環境でC++を使う場合、静的なオブジェクトの操作や、クラスのメンバ変数の操作では排他制御が必要になることが多いと思います。しかし、参照やポインタを引数として受け取る関数や、クラスのメンバ関数を、何でもかんでも排他制御しようとすると、大きなオーバーヘッドになってしまいます。 そんなとき、volatile修飾子による多重定義が役に立ちます。volatile修飾子は、構文上はconst修飾子と対等の関係にありますから、volatile参照やvolatileポインタに対して関数を多重定義することもできますし、volatileメンバ関数を定義することもできます。 具体的な例として、オブジェクトの値を入れ替えるためのswap関数について考えてみましょう。標準C++ライブラリが提供しているstd::swap関数は、原則としてマルチタスク環境にには対応
ボゴソート - Wikipedia
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。 英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。 アルゴリズム[編集] トランプを順に並べる場合を例にすると、次のようになる。 トランプ52枚の束を放り投げて、ばらばらにする。 1枚ずつ無作為にすべてを拾い集める。 ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 カードの束をひたすらシャッフルし続けて順番に並ぶまで待つア
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ