問題タブ [base-conversion]

整数の配列を使用して JavaScript で BigInt 型を実装しようとしています。今のところ、それぞれに 256 の上限があります。すべての整数演算の実装を終了しましたが、BigInt をその文字列表現に変換する方法がわかりません。もちろん、簡単な方法は次のとおりです。

しかし、BigInts が実際に大きくなると、追加して変換できなくなります。base-x の配列を base-y の配列に変換するにはどうすればよいですか?

Zeckendorf と Golden Ratio Base は明らかに密接に関連していますが、それでも一方から他方へ変換するのは難しいようです。これについて Frougny と Sakarovitch による研究があることは知っていますが、私はこれを完全には理解していません。1 つの問題は、黄金比の基本表現が基数点を中心にかなり対称的であることです。これは、これらの表現がコンテキストフリーである可能性があることを示唆しています。Sakarovitch と Frougny は、「折り畳まれた」黄金比基数を使用してこれに対処しています。この修正された表現を使用すると、有限状態変換器で変換できると思われますが、これがどのように機能するかはわかりませんでした。

黄金比ベースの部分的な対称性に関しては、これは根が対になっていることに関係しています (これについては、George Bergman (pc) からの長い説明があります)。

これら 2 つの表現の関係について私が知っていることの 1 つは、d-1...d_i*d_j...d_n (基数として「*」を使用) の形式のすべての黄金比基本表現に対して、対応するフィボナッチ数を含む方程式:

(など。すべてが 4 の黄金比の基本表現と同じ Zeckendorf ビット パターンを持つ一連の数字があります)。これは確かに役立つはずですが、どうすればよいでしょうか。

このパターンは、D. Gerdemann 著 Combinatorialproofs of Zeckendorf family identities Fibonacci Quarterly、2008/2009 で説明されています。

ところで: Fibonacci Quarterly に論文を書いているにもかかわらず、私はこの分野ではまったくの素人です。私が質問しているギャップを含め、私の知識には多くのギャップがあります。

私はインターネット上で人々が写真を投稿し、短い文字列を生成するサービスを持っています。これまでに使用できるのは1つだけです。ただし、データベースで重複が発生し、大きな問題が発生しています。

これが私が使用しているものです：

それを修正するための最良の方法は何でしょうか？データベースからチェックして、一致しなくなるまでループを続けますか？考えられるすべての解決策が無限ループに陥った場合はどうなりますか？

私のアプリケーション データの一部には、9 つ​​の 3 進数 (base-3) の「ビット」のセットが含まれています。データベースのデータをコンパクトに保つ​​ために、そのデータを単一の短いものとして保存したいと思います。3^9 < 2^15 であるため、9 桁の 3 進数を短縮形で表すことができます。

私の現在の方法は、長さ 9 の文字列として処理することです。任意の数字をインデックスで読み取ったり設定したりできます。これは便利で簡単です。ただし、それを short に変換するために、現在、手動で (シフト加算ループを使用して) base 10 に変換し、次に Int16.Parse を使用してバイナリ short に変換しています。格納された値を基数 3 の文字列に戻すには、プロセスを逆に実行します。これにはすべて時間がかかるため、可能であれば最適化したいと考えています。

私がやりたいことは、常に値を short として保存し、3 進数のビットを読み取って設定することです。理想的には、バイナリから個々の数字を取得して設定する関数が必要です。

いくつかのビット シフトと mod 関数で遊んでみましたが、これを行う正しい方法が思い浮かびませんでした。完全な変換を行わずにそれが可能かどうかさえわかりません。

これに役立つビット単位の算術魔法を教えてくれる人はいますか?

この次の関数は常に一意の文字列を生成しますか？次の関数から生成される文字列の長さの範囲はどのくらいですか？より独自性を生み出すために改善できますか？

ありがとう

そのため、私の暗号化ライブラリには、頻繁に使用するベース コンバーターがあります。これは世界で最も効率的な方法ではありませんが、すべての範囲の入力に対して非常にうまく機能します。

作業の大部分は、コールバック ループによって行われます。

基本的に、これは の数値の配列を受け取り、$srcBaseそれらを の数値の配列に変換します$dstBase。したがって、入力例は、結果としてarray(1, 1), 2, 10得られるものになります。array(3)もう 1 つの例は、次のようarray(1, 0, 0), 256, 10になりますarray(1, 6, 7, 7, 7, 2, 1, 6)(配列の各要素は、$dstBase.

私が今直面している問題は、2kb のデータをフィードすると、実行に約 10 秒かかることです。だから私はそれを最適化することに着手しました。これまでのところ、構造全体を次の再帰ループに置き換えることで、約 4 秒に短縮できました。

私が直面している問題は、それをさらに最適化する方法です (それが可能であれば)。問題は、大きな入力にかかる反復回数のせん断だと思います (2000 要素の配列の場合、基数 256 から基数 10 まで、合計で 4,815,076 回の反復が必要です)。

何かご意見は？

base_convert（）関数は符号を保持していないようです。

例えば：

これの出力は100です

サインを失うことなくベースを変換する方法はありますか？

10進数を2進数に変換したい。私はこの方法を使用しています：

数「要素」が >0 の場合、すべてがうまくいっています。数値が <0 の場合、問題があります。たとえば、このメソッドは数値 "-1" を変換できません。問題を解決するにはどうすればよいですか? 前もって感謝します！！

10 進数と他の基数との間の変換を可能にする C++ 構造またはテンプレート (任意のライブラリ内) はありますか (bitset ができるように) ?

そのため、私たちのクラスには、10 進数を 8 進数表現に変換する割り当てが与えられました。機能するまでなんとかいじくり回しましたが、なぜ機能するのか理解できません。より単純な方法で再帰を説明する可能性はありますか? ありがとう。