CORDIC アルゴリズム 1. CORDIC アルゴリズムとは "CORDIC" は COordinate Rotation DIgital Computer の略語. 1956年に Jack E. Volder が考案したため, Volderのアルゴリズムとも呼ばれる. 三角関数, 双曲線関数, 平方根関数, 指数関数, 対数関数など様々な関数の近似値を, 加算, 減算のみを使用して求めることができる. →複雑な回路をもたない計算機でも計算できる. このドキュメントでは, 三角関数を近似するアルゴリズムを説明する. 2. 前提知識 三角関数 (正弦, 余弦, 正接) の定義 図のような$∠C$を直角とする直角三角形において, $∠A=\theta$ に対する正弦, 余弦, 正接は次式で表される. 正弦関数 $\sin \theta = \frac a h$ 余弦関数 $\cos \th
B+木(英: B+ tree)は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント(「ブロック」などと呼ばれる。木構造におけるノードに相当)にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層(葉ノード)に格納され、内部ノードにはキーのみが格納される。 B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ の記憶装置があるとき、 の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い(2分探索木はブロック型でない記憶装置に適している)。 ReiserFS(UNIX、Linux)、XFS(IRIX、Linux)、JFS2(AIX、OS/2、Linux)、HammerFS(DragonFly BSD)、NTFSといったファイルシステムはいずれ
コンピュータにおける三角関数の実装 ※この文章は主に Intel社の文献 1 をもとに記述しています。 歴史的な話 1980年代に開発された Intel 8087 プロセッサーでは、sin cos を含む数学関数がハードウェア実装された。 現在の Intel や AMD の x86_64 アーキテクチャ CPU にも、互換性を維持する目的で実装され続けている。(x87) しかしながら、最近のプログラミング言語で sin cos を呼び出しても、 これらの x87 命令が使用されることはなく、ソフトウェア的に計算が行われる。 それには、x87 命令の実装に使用されたアルゴリズムに、速度や精度上の欠点があるため、と言われている。 1 から引用 In the 1990s Intel replaced the 8087's CORDIC-based approximations of the el
ソートアルゴリズムにはクイックソートやマージソートといった伝統的なものから、PythonやJava 7のデフォルト実装になっている「Timsort」までいろいろな種類があります。中には正しいソート順になるまでひたすらシャッフルし続ける「Bogosort」のようなジョークアルゴリズムもあります。これから紹介するアルゴリズムもそのうちの一つに入るかもしれません。 「4chan」という2ちゃんねるに似たアメリカの匿名掲示板があり、そのプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立ちました。2ちゃんねる風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じでしょうか。スレッドを立てた1氏は「Sleep Sort」と称したリスト2のようなシェルスクリプト実装を載せています。 ソート対象の数値データを次々にs
図書館ソート(としょかんソート)またはライブラリソート(英: library sort, gapped insertion sort)は、ソートのアルゴリズムの一つ。挿入ソートをベースとし、挿入操作を高速化するために配列に隙間(gap)を設けるもの。名前は次のアナロジーに由来する: 司書が長い本棚にアルファベット順に本を陳列しようとしているとする。本棚は左端がAで始まり、右端のZの終わりまで隙間なく本で埋まっている。司書が新しい本をBの区画に収めるには、Bの区画に適切な位置を見つけ、スペースを空けるために後ろのすべての本をずらす必要がある。これが挿入ソートである。しかし、各区画の間(BとCの境界など)に空白があったなら、新しい本のためにずらすべき本の数は少なくて済む。これが図書館ソートの基本的な原理である。 このアルゴリズムは2004年[1]にMichael A. Bender、Martí
概要 MD5ハッシュアルゴリズムをRFC1321に記載された仕様に従ってRustで実装します。付録として、その中で利用される 4294967296|\sin i| の整数部分という値の計算方法も示します。 背景 しばらく前から主に公式ドキュメントでRustを学び始めました。Zennの以下の記事にもお世話になっています。 RustCoder ―― AtCoder と Rust で始める競技プログラミング入門 Rust入門 学ぶうちにちょっとしたサイズのアルゴリズムを実装してみたくなり、今春放送されたゴジラSP[1]で重要な役割を果たしたMD5ハッシュの実装を試してみることにしました。 MD5とは MD5は任意長のビット列を128ビットという固定長のハッシュ値に変換するアルゴリズムです。したがって理想としては任意長のビット列を引数に取るべきですが、本記事では文字列に対するMD5ハッシュ関数をR
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く