[algorithm] 数ベースシステムに基づくアルゴリズム?



Answers

"三元数は、シエルピンスキー・トライアングルやカンター・セットのような自己相似構造を便利に伝えるために使用できます。" source

「四角形の数字は、2Dヒルベルト曲線の表現に使用されています。 source

「クァーター・虚数数字システムは、1955年にドナルド・クヌスによって、高校の科学才能検索に提出された最初に提案されたもので、虚数2iをベースにした非標準の位置指定数字システムです。数字0,1,2、および3のみを使用してすべての複素数を表現します。 source

"ローマ数字はバイバイナリシステムです。" source

「基数6で表現されるとき、2と3以外のすべての素数は1桁または5桁を最終桁とするため、偶数の研究で有用とみなされる可能性があります。 source

古代バビロニア人に受け継がれていた古代シュメール人が起源となっており、古代バビロニア人に受け継がれています。時間、角度、および角度である地理座標」を参照してください。 source

等...

このリストは良い出発点です。

Question

私は最近、創造的な基盤における数の巧妙な使い方に基づいて、部分的にまたは全体的に非常に多くのアルゴリズムが存在することに気づいた。 例えば:

  • 二項ヒープは2進数に基づいており、より複雑なスキュー2項ヒープはスキュー2進数に基づいています。
  • 辞書学的に順序付けられた順列を生成するためのいくつかのアルゴリズムは、ファクタデジット数システムに基づいている。
  • 試行は、適切なベースのために、一度に文字列の1桁を見ているツリーと考えることができます。
  • ハフマン符号化ツリーは、ツリー内の各エッジがいくつかのバイナリ表現で0または1を符号化するように設計されています。
  • フィボナッチ符号化は、フィボナッチ検索で使用され、特定のタイプの対数を反転させます。

私の質問は、彼らの直感や証明の重要なステップとして巧妙な数字システムを使用している他のアルゴリズムはありますか? 。 私は話題を話し合うことを考えているので、私が描かなければならない例が多くなるほど、より良いものになります。




素晴らしい質問。 リストは本当に長いです。 話す時間は、混合ベースの単純な例です(days | hours | minutes | seconds | am / pm)

あなたがそれについて聞くことに興味があるなら、私はメタベースの列挙型n-tupleフレームワークを作成しました。 それは、ベースナンバリングシステムのための非常に甘い構文的砂糖です。 それはまだリリースされていません。 私のユーザー名をメールで送信します(Gmailで)。




いくつかの行列乗算を高速化するために、二重基本システムについて何か漠然と覚えています。

ダブルベースシステムは、1つの番号に対して2つのベースを使用する冗長システムです。

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

冗長とは、1つの番号をさまざまな方法で指定できることを意味します。

あなたはVassil Dimitrov、Todor Cooklevの記事 "Matrix Polynomialの計算のためのハイブリッドアルゴリズム"を探すことができます。

私ができる最善の短い概観を与えることを試みる。

彼らは行列多項式G(N,A) = I + A + ... + A^{N-1}を計算しようとしていました。

私たちがJ = 2を適用すると、次のようになりますG(N,A) = G(J,A) * G(K, A^J)

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

また、

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

これらの方程式のいくつかは、最初のシステムでは高速で、次のシステムではより良いものが「明白」なので、 N応じて最適なものを選択することをお勧めします。 しかし、これは2と3の両方に対して高速のモジュロ演算を必要とします。ここではダブルベースが入っています - あなたは基本的にモジュロ演算を両方とも高速で行うことができ、

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

私はこの分野の専門家ではないので、より良い説明のために記事を見てください。







私は最近、0と2 n - 1の間の数のバイナリ表現に基づいて部分配列を辞書順に生成するためのすばらしいアルゴリズムを見つけました。それは、両方のビットを使って、セットのためにどの要素を選択し、生成されたセットをそれらを辞書順に取得する。 あなたが好奇心が強いなら、私はhere投稿を書きましhere

また、多くのアルゴリズムは入力問題の数値のバイナリ表現を使用して大まかな近似を完全な解に徐々に改良するスケーリング(Ford-Fulkerson max-flowアルゴリズムの弱多項式など)に基づいています。







暗号は、整数リング(モジュラ・アルスティック)と有限フィールドを大量に使用します。その演算は、整数係数を持つ多項式の動作に直感的に基づいています。




AKSの場合があります。




Links