基数10を経由せずに任意の基数から任意の基数に変換する背後にある数学？

これは私には非常に基本的な質問のようですので、少し講義をさせていただきます。ここで学ぶ最も重要な点は、数値はその数字表現ではないことです。数字は抽象的な数学的対象ですが、その数字表現は具体的なものです。つまり、紙の上の記号のシーケンス（または計算メモリ内のビットのシーケンス、または数字を伝達するときに鳴る音のシーケンス）です。あなたを混乱させているのは、あなたが数字を見ることは決してないが、常にその数字表現を見るという事実です。したがって、数字は 表現であると考えることになります。

したがって、正しい質問は”あるベースから別のベースに変換する方法”ではなく、むしろ”指定された数字の文字列で表されている番号を見つけるにはどうすればよいですか”および”指定された数値の数字表現を見つけるにはどうすればよいですか”。

では、Pythonで2つの関数を作成しましょう。1つは数字表現をに変換するためのものです。数、および反対を行うための別のもの。注：関数を実行すると、Pythonはもちろん画面に基数10で取得した数値を出力します。ただし、これはコンピューターが基数で数値を保持していることを意味するわけではありません 10（そうではありません）。コンピュータが数字をどのように表すかは無関係です。

def toDigits(n, b): """Convert a positive number n to its digit representation in base b.""" digits = [] while n > 0: digits.insert(0, n % b) n = n // b return digits def fromDigits(digits, b): """Compute the number given by digits in base b.""" n = 0 for d in digits: n = b * n + d return n 

これらをテストしてみましょう：

>>> toDigits(42, 2) [1, 0, 1, 0, 1, 0] >>> toDigits(42, 3) [1, 1, 2, 0] >>> fromDigits([1,1,2,0],3) 42 

変換関数を使用すると、問題を簡単に解決できます。

def convertBase(digits, b, c): """Convert the digits representation of a number from base b to base c.""" return toDigits(fromDigits(digits, b), c) 

テスト：

>>> convertBase([1,1,2,0], 3, 2) [1, 0, 1, 0, 1, 0] 

注：実行しましたベース10の表現を通過しない！ベースの $ b $ 表現を数値に変換してから、数値をベースの $ c $ 。数字はどの表現でも ありませんでした（実際には、コンピューターは何らかの形で表現する必要があり、電気信号とファンキーを使用して表現していました）チップで起こること、しかし確かにそれらのw 0と1ではありません。）

コメント

• これは’納得できません私は100％。実際、コンピューターはプラトニック数学者ではなく、アルゴリズムはベース$ b_1 $の任意の数字シーケンスをベース$ b_2 $に変換できないため、数値を何らかの表現に変換しました（ただし、それが何であるかはわかりません）。具体的なマシンで表現できるシーケンスのみを変換できます。 Pythonは魅力的に柔軟性があります。 Cはそれほど寛容ではなかっただろう。任意の文字列を$ b_1 $から$ b_2 $に変換する方法を尋ねることは完全に有効です。ただし、これは、特定の基本の組み合わせ（2 <-> 16など）を除いて、線形時間でのみ可能です。
• 質問することは有効ですが、正しい答えを見つけるには、数字が抽象的な実体であるという事実に注意するのが最善です。
• これは数字を渡します fromDigitsは10進数の数値を返すため、10進数の表現を使用します。
• @anorton：いいえ、間違いなくありません。 。 Pythonは、数値を基数10桁で画面に出力しますが、数値自体はそのように格納されません。私が理解しようとしているのは、Python内で数値を実装する方法は無関係であるということです。それは問題ではありません。重要なのは、数字のように動作することだけです。
• 最後に、特定のユースケース、36未満のベース、または十分な一意の記号を考え出すことができるインスタンスに限定されない、あらゆるベースの一般的なソリューション。

これを理解する最善の方法は、エイリアンと話し合うことだと思います（少なくとも類推）。

定義 $ x $は基数$ b $の数値です。 は、$ x $が数字の文字列$ < b $であることを意味します。

例 10010011011の数字の文字列は2を底とする数字であり、68416841531の文字列は10を底とする数字であり、BADCAFEは16を底とする数字です。

私が惑星QUUXで育ったとしましょう。そこでは、誰もが一生$ q $で働くように教えられており、$ b $のベースに慣れているあなたに会います。それであなたは私に番号を見せてくれます、そして私は何をしますか？解釈する方法が必要です：

定義解釈できます 次の式による基数$ b $の数値（注：$ b $は基数$ q $の数値）

$$ \ begin {array} {rcl} [\！[\ epsilon] \！] & = & 0 \\ [\！[\ bar sd] \！] & = & [\！[\ bar s] \！] \ times b + d \ end {array} $$

where $ \ epsilon $は空の文字列を示し、$ \ bar sd $は数字$ d $で終わる文字列を示します。この表記法の概要については、追加によって追加されるという私の証明を参照してください。

では、ここで何が起こったのですか？あなたは私に番号を教えてくれました基数$ b $で、私はそれを基数$ q $に解釈しましたが、実際の数についての奇妙な哲学はありません。

キーこれの鍵は、私が持っている$ \ times $と$ + $が、基数の$ q $数で動作する関数であるということです。これらは、基数の$ q $数（文字列）で再帰的に定義される単純なアルゴリズムです。桁数）。

私は全体を通して実際の数ではなく変数を使用しているので、これは少し抽象的なように見えるかもしれません。それで、あなたがベース13のクリーチャー（記号$ 0123456789XYZ $を使用）であり、私が記号$ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $を使用して7を基数とする（はるかに賢明です）ために使用されます。

だから私はあなたのアルファベットを見て、次のように表にしました：

$$ \ begin {array} {| c | c || c | c || c | c |} \ hline 0 & \ alpha & 1 & \ beta & 2 & \ガンマ\\ 3 & \ delta & 4 & \ rho & 5 & \ zeta \\ 6 & \ xi & 7 & \ beta \ alpha & 8 & \ beta \ beta \\ 9 & \ beta \ gamma & X \ beta \ delta & Y & \ beta \ rho \\ & & Z & \ beta \ zeta & & \\ \ hline \ end {array} $$

つまり、あなたがベース$ \ beta \ xi $で作業していること、そしてベース7の番号がどの桁であるかを知っています。書き込みはに対応します。

物理について話し合っていて、基本定数（たとえば、$ 60Z8 $）について教えてくれた場合は、これを解釈する必要があります。

$$ \ begin { array} {rcl} [\！[60Z8] \！] & = & \ xi（\ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ beta \ zeta（\ beta \ xi）+ \ beta \ beta \\ \ end {array} $$

つまり、$ \を乗算することから始めます。 beta \ zeta \ times \ beta \ xi $ですが、これは私にとっては小学校のものです。覚えています：

Quux乗算テーブル

$$ \ begin {array} {| c | cccccc |} \ hline \\ \ times & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ hline \ beta & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ gamma & \ gamma & \ rho & \ xi & \ beta \ beta & \ beta \ delta & \ beta \ zeta \\ \ delta & \ delta & \ xi & \ beta \ gamma & \ beta \ zeta & \ gamma \ beta & \ gamma \ rho \\ \ rho & \ rho & \ beta \ beta & \ beta \ zeta & \ gamma \ gamma & \ gamma \ xi & \ delta \ delta \\ \ zeta & \ zeta & \ beta \ delta & \ gamma \ beta & \ gamma \ xi & \ delta \ rho & \ rho \ gamma \\ \ xi & \ xi & \ beta \ zeta & \ gamma \ rho & \ delta \ delta & \ rho \ gamma & \ zeta \ beta \\ \ beta \ alpha & \ beta \ alpha & \ gamma \ alpha & \ delta \ alpha & \ rho \ alpha & \ zeta \ alpha & \ xi \ alpha \\ \ hline \ end {array} $$

$ \ beta \ zeta \ times \ beta \ xi $を見つけるには：

$$ \ begin {array} {ccc} & \ beta & \ ze ta \\ \ times & \ beta & \ xi \\ \ hline & \ xi & \ gamma \\ & \ rho & \\ \ beta & \ zeta & \\ \ hline \ delta & \ beta & \ gamma \\ \ gamma & & \\ \ end {array} $$

だから私はここまで来ました

$$ \ begin {array} {rcl} [\！[60Z8] \！] & = & \ xi（\ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ beta \ zeta（\ beta \ xi）+ \ beta \ beta \\ & = & \ xi（\ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ \ end {array} $$

次に、次のアルゴリズムを使用して加算を実行する必要があります。以前に言及された：

$$ \ begin {array} {ccc} \ delta & \ beta & \ gamma \\ & \ beta & \ beta \\ \ hline \ delta & \ gamma & \ delta \\ \ end {array} $$

so

$$ \ begin {array} {rcl} [ \！[60Z8] \！] & = & \ xi（\ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ beta \ zeta（\ beta \ xi）+ \ beta \ beta \\ & = & \ xi（ \ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ & = & \ xi（\ beta \ xi）^ 3 + \ alpha（\ beta \ xi）^ 2 + \ delta \ gamma \ delta \\ \ end {array} $ $

この方法を続けると、$$ [\！[60Z8] \！] = \ zeta \ delta \ xi \ gamma \ rho。$$

In要約：ベース$ q $の数字の文字列に関して独自の数値の概念がある場合、基本的な算術演算に基づいて、ベース$ b $から独自のシステムに数値を解釈する方法があります。ベース$ q $。

コメント

• それはかなりの波線でした。どうすればコンピュータにそれを実行させることができますか？
• @Griffin、あなたはその（奇妙な）質問を時期尚早に行っていると思います。プログラミング言語を選択し、基数qの数値（桁のリストとして表される）に加算と乗算のアルゴリズムを入力してから、基数bの桁を基数qの数値に解釈し、基数bの数値を基数qの数値に解釈する関数を定義します。 ‘これについてすべて説明しました。
• あなたが表現しようとしている概念を知っています。私の問題は、私のコンピュータが’波線を使用できないことです。
• あなたが説明したことは知っていますが、それを実践するのははるかに困難です。これらの数字の定義は’簡単ではないことがわかります。
• また、なぜ最も重要な位置にアルファベットを落としたのですか？ 6 = & xi;なので、’ t 7 = & alpha; & alpha;？

これはリファクタリングです（Python 3） Andrej “s コード。Andrej” sのコード番号は数字（スカラー）のリストで表されますが、以下のコード番号はカスタム文字列から取得した任意の記号のリスト：

def v2r(n, base): # value to representation """Convert a positive number to its digit representation in a custom base.""" b = len(base) digits = "" while n > 0: digits = base[n % b] + digits n = n // b return digits def r2v(digits, base): # representation to value """Compute the number represented by string "digits" in a custom base.""" b = len(base) n = 0 for d in digits: n = b * n + base[:b].index(d) return n def b2b(digits, base1, base2): """Convert the digits representation of a number from base1 to base2.""" return v2r(r2v(digits, base1), base2) 

カスタムベースで値から表現への変換を実行するには：

>>> v2r(64,"01") "1000000" >>> v2r(64,"XY") "YXXXXXX" >>> v2r(12340,"ZABCDEFGHI") # decimal base with custom symbols "ABCDZ" 

（カスタムベースでの）表現から値への変換を実行するには：

>>> r2v("100","01") 4 >>> r2v("100","0123456789") # standard decimal base 100 >>> r2v("100","01_whatevr") # decimal base with custom symbols 100 >>> r2v("100","0123456789ABCDEF") # standard hexadecimal base 256 >>> r2v("100","01_whatevr-jklmn") # hexadecimal base with custom symbols 256 

ある顧客ベースから別の顧客ベースへのベース変換を実行するには：

>>> b2b("1120","012","01") "101010" >>> b2b("100","01","0123456789") "4" >>> b2b("100","0123456789ABCDEF","01") "100000000" 

コメント

• サイトへようこそ。ご協力いただきありがとうございます。ただし、十分に最適化されたソースコードを作成することは、このサイトの本当の目的ではありません。’ Andrej ‘のコードは、彼の答えに必要な概念を明確にしますが、それを超えてコードを改善することは、コンピューターの科学ではなくプログラミングの問題です。 i>。
• @DavidRicherby私は部分的に同意しますが、この投稿はコメントするには長すぎたため、Andrej ‘の回答の近くが最適です。そのため、’ここに投稿しました。とにかく、’の方が良いと思う場合は、コードへのリンクを含むコメントに変換できますが、’ではありません。過剰な純粋主義？
• @David ‘ s ” site-purist 反対意見ですが、関係するベースはより抽象的な用語で”アルファベット —通常の2〜36文字の範囲に制限されません。実際、バイトのストリームは、基数256の整数値の”桁”と見なすことができます。

基本変換の基本的な操作は、@ AndrejBauer回答のtoDigits()操作です。ただし、それを作成するために、数値の内部表現で数値を作成する必要はありません。これは、基本的に基数2の表現からの変換です。元の基本表現で必要な操作を行うことができます。

したがって、最初のステップは、モジュロ除算演算を繰り返すことです

def convertBase(n,original_base,destination_base): digits = [] while not is_zero(n): digits.insert(0,modulo_div(n,original_base,destination_base)) return digits 

内部表現は数字であるため、特定の値を作成する必要がありますゼロをテストするための関数

def is_zero(n): for d in n: if d != 0: return False return True 

最終的には、学校で学んだように、実際には宛先ベースによる標準除算であるmodulo_div演算を実行する必要があります。

def modulo_div(n,original_base,destination_base): carry = 0 for i in range(len(n)): d = n[i] d+=original_base*carry carry = d%destination_base d=(d//destination_base) n[i] = d #print(i,d,carry) return carry 

コードが正しいことを確認するためのテストチェック：

print(convertBase([1,1,2,0], 3, 2)) #[1, 0, 1, 0, 1, 0] print(convertBase([1, 0, 1, 0, 1, 0], 2, 3)) #[1, 1, 2, 0] 

コメント

• 投稿していただきありがとうございますが、’はコーディングサイトではないため、コードの大きなブロックは’ここでの回答としては適切ではありません。特に、質問で「”コードは必要ありません’コードは必要ありません。基本的な計算が必要です。”
• @DavidRicherbyテキストを追加しようとしました。
• ありがとうございます。そして、私が言ったことにもかかわらず、’このページにはたくさんのコードがあります！
• @David：FWIW、これはOPに答えると思います’の質問は、最初に元の表現を中間形式に変換してから、それを宛先ベースに変換せずに、2つのベース間で変換する方法を示しているためです。
• 良い試みですが、dはまだ10進数にあるので、実際にはnの一部を抽出して10進数に変換し、それを目的のベースに変換して、最終結果に収集しています。

コンピュータプログラムを必要としない基本変換を行う簡単な方法を知っています。それは次のように定義します。任意のベースからベース2に、またはその逆に変換し、最初に最初のベースからベース2に変換し、次にベース2から別のベースに変換することによって1つのベースから別のベースにカバーする方法。 2は、任意の基数で乗算または除算するのが非常に簡単です。

任意の基数から基数2に変換するには、基数2の表記を使用して開始すると、任意の数についてそれを認識するだけです。 0から、次に各桁について、左から右の順に、その桁が0の場合はdouble、その桁が1の場合は1を加算するよりも、その番号自体に到達します。これで、任意の基数でその数が与えられた場合、その基数で2で割って、商と剰余を得ることができます。余りが1の場合、最後の2進数は1で、余りが0の場合、最後の2進数は0です。もう一度2で割ります。残りが1の場合、最後から2番目の桁は1であり、残りが0の場合、最後から2番目の桁は0であり、商が0になるまで続きます。

基数2から任意の値に変換するには基数、あなたがしなければならないのはその基数で、0から始めて、左から右に行く各2進数について、その基数が0の場合はその基数を2倍にし、その桁が1の場合はその基数に1を追加するだけです。

コメント

• 2 is so easy to multiply or divide by in any base.私は’ t 2の累乗（最初は11と13）から1を超える奇数の基数については、これを参照してください。

中間基数に変換せずに、基数nから基数10に変換できます。

たとえば、基数nから基数9に変換するには、基数10に変換するアルゴリズムを使用し、「10」を「9」に置き換えます。他のベースについても同じです。