バランスのとれた 3 進法は、各桁が-1、0、1の値を持つ、バランスのとれた符号付き数字の整数表現を使用する3進法 (つまり、3桁の基数)です。これは、各桁が0、1、2の値を持つ標準 (バランスのとれていない) 3 進法とは対照的です。バランスのとれた 3 進法では、別のマイナス記号を使用せずにすべての整数を表すことができます。つまり、数値の先頭の非ゼロ桁の値は、その数値自体の符号を持ちます。バランスのとれた 3 進法は、非標準の位置記数法の例です。これは、初期のコンピューターで使用されていました[1] 。また、バランス パズルを解くためにも使用されました。[2]
異なるソースでは、バランスのとれた 3 進法の 3 つの数字を表すために異なるグリフを使用しています。この記事では、T (マイナス記号と 1 の合字に似ています) は-1 を表し、0と1 はそれ自体を表します。他の慣例には、それぞれ '-' と '+' を使用して -1 と 1 を表したり、ギリシャ文字のシータ (Θ) を使用して-1を 表したりすることが含まれます。これは、円の中にマイナス記号が描かれています。Setun コンピューターに関する出版物では、-1 は 1 をひっくり返して表します。"1「」[1]
平衡三進法は、マイケル・スティフェルの著書『積分算術』(1544年)に早くから登場している。 [3]また、ヨハネス・ケプラーとレオン・ラランヌの著作にも登場する。他の基数における関連する符号付き数字体系は、ジョン・コルソン、ジョン・レスリー、オーギュスタン=ルイ・コーシーによって議論されており、おそらく古代インドのヴェーダにも登場している。[2]
意味
を記号(グリフや文字とも呼ばれる)の集合とします。記号はの代わりに使用されることもあります。整数値関数を次のように 定義します。
- [4]
ここで、右辺は通常の値を持つ整数です。この関数は、整数値が記号/グリフに割り当てられる方法を厳密かつ形式的に確立するものです。この形式の利点の 1 つは、「整数」の定義 (どのように定義されるかに関係なく) が、それらを記述/表現するための特定のシステムと混同されないことです。このようにして、これら 2 つの異なる (ただし密接に関連している) 概念は分離されています。
このセットと関数を組み合わせると、バランスのとれた 3 進数システムと呼ばれるバランスのとれた符号付き数字表現が形成されます。これは整数と実数を表すために使用できます。
三項整数評価
を のクリーネプラスとします。これは、 1つ以上の記号(その数字と呼ばれる)の有限長の連結文字列の集合です。ここで は非負の整数で、すべての数字はから取られます。の始まりは記号(右側)、終わりは(左側)、長さはです。三項評価は、すべての文字列に整数 を割り当てることによって定義される関数です。
文字列は整数を( に関して)表す。値は で表記されることもある。 写像は射影的だが単射的ではない。例えば、 である。しかし、すべての整数は の下で、(左側が)記号で終わらない表現を1つだけ持つ。すなわち、
が次を満たす場合:
これは、 が一種の再帰関係 を満たすことを示しています。この再帰関係には、 が空の文字列 である初期条件があります 。
これは、すべての文字列に対して
言葉で言えば、先頭の 記号 (2 つ以上の記号を含む文字列の左側) は結果の値に影響を与えません。
次の例は、 のいくつかの値を計算する方法を示しています。ここで (前と同じように) すべての整数は 10 進数 (基数 10) で記述され、 のすべての要素は単なる記号です。
そして上記の再帰関係を用いると
10進数への変換
平衡三進法では、小数点のn桁左側の数字の値は、その数字と 3 nの積です。これは、十進法と平衡三進法を変換するときに便利です。以下では、平衡三進法を表す文字列に接尾辞bal3 が付きます。たとえば、
- 10 bal3 = 1 × 3 1 + 0 × 3 0 = 3 dec
- 10𝖳 bal3 = 1 × 3 2 + 0 × 3 1 + (−1) × 3 0 = 8小数点
- −9小数点以下= −1 × 3 2 + 0 × 3 1 + 0 × 3 0 = 𝖳00 bal3
- 8小数点以下= 1 × 3 2 + 0 × 3 1 + (−1) × 3 0 = 10𝖳 bal3
同様に、基数点の右側の最初の桁は 3 −1 = となります。1/3、2位は 3 −2 = です。1/9など。例えば、
- − 2/3小数点以下= −1 + 1/3 = −1 × 3 0 + 1 × 3 −1 = 𝖳.1 bal3 .
整数は、一の位の数字が 0 の場合にのみ 3 で割り切れます。
すべての 3 進数の合計のパリティをチェックすることで、バランスの取れた 3 進数の整数のパリティをチェックできます。この合計は整数自体と同じパリティを持ちます。
バランスのとれた3進法は、小数が基数点の右側に書かれるのと同様に、分数にも拡張できます。[5]
10進数や2進数では、整数値と小数部には複数の表現方法があります。たとえば、1/10 = 0.1 = 0.1 0 = 0.0 9 . そして、1/2 = 0.1 2 = 0.1 0 2 = 0.0 1 2。バランスの取れた三分法の分数にも複数の表現方法があります。たとえば、1/6 = 0.1 𝖳 bal3 = 0.0 1 bal3。確かに、10進数と2進数では、基数点の右端にある無限の0を省略して、整数または終端の小数の表現を得ることができます。しかし、バランスのとれた3進数では、整数または終端の小数の表現を得るために、基数点の右端にある無限の-1を省略することはできません。
ドナルド・クヌース[6]は、バランスのとれた3進法では切り捨てと四捨五入は同じ操作であり、まったく同じ結果を生み出す(他のバランスのとれた数値システムと共有される特性)ことを指摘した。数1/2は例外ではありません。2 つの等しく有効な表現と 2 つの等しく有効な切り捨てがあります。0. 1 (0 に丸め、0 に切り捨て) と 1. 𝖳 (1 に丸め、1 に切り捨て) です。奇数の基数では、偶数の基数とは異なり、 2 回の丸めは最終精度への直接の丸めと同等です。
基本的な演算(加算、減算、乗算、除算)は、通常の 3 進数と同じように実行されます。2 の乗算は、ある数値をそれ自身に加算するか、a-trit-left-shift の後にその数値自体を減算することで実行できます。
バランスの取れた 3 進数の算術左シフトは、3 の (正の整数) 累乗による乗算に相当します。また、バランスの取れた 3 進数の算術右シフトは、3 の (正の整数) 累乗による除算に相当します。
分数との変換
循環平衡三進数を分数に変換することは、循環小数を変換することに似ています。たとえば、(111111 bal3 = ( 3 6 − 1/3 − 1 ) 12月):
無理数
他の整数基数と同様に、代数的無理数と超越数は終了したり繰り返したりしません。例:
の平衡三元展開はOEISでは A331313 として与えられ、 の平衡三元展開は A331990 として与えられます。
三進法からの変換
不平衡 3 進法は、次の 2 つの方法で平衡 3 進法表記に変換できます。
- 最初の非ゼロのトリットからキャリー付きで 1 トリットずつ加算し、次に同じトリットから借用なしで 1 トリットずつ減算します。たとえば、
- 021 3 + 11 3 = 102 3 , 102 3 − 11 3 = 1T1 bal3 = 7 dec .
- 三進法に2がある場合は、それを1Tに変換します。たとえば、
- 0212 3 = 0010 bal3 + 1T00 bal3 + 001T bal3 = 10TT bal3 = 23 dec
三進法の3つの値がfalse、unknown、true であり、これらが T、0、1 としてバランスのとれた三進法に、また 0、1、2 として従来の符号なし三進法にマッピングされる場合、バランスのとれた三進法はオフセット二進法に類似したバイアス数体系と見なすことができます。三進法の数がn個のトリットを持つ場合、バイアスbは
これは、従来の形式またはバイアス形式のいずれかですべて1として表されます。[7]
その結果、これら 2 つの表現をバランスのとれた 3 進数と符号なし 3 進数に使用すると、符号なしのn進数の正の 3 進数値はバイアスbを加算することでバランスのとれた形式に変換でき、正のバランスのとれた数はバイアスb を減算することで符号なし形式に変換できます。さらに、xとyがバランスのとれた数の場合、従来の符号なし 3 進数演算を使用して計算すると、それらのバランスのとれた合計はx + y − bになります。同様に、xとy が従来の符号なし 3 進数の場合、バランスのとれた 3 進数演算を使用して計算すると 、それらの合計はx + y + bになります。
任意の整数基数からバランスのとれた3進数への変換
次の式を使用して、バランスのとれた 3 進数に変換できます。
どこ、
- a n a n −1 ... a 1 a 0 . c 1 c 2 c 3 ... は元の記数法による元の表現です。
- b は元の基数です。10進数から変換する場合、 b は10 になります。
- a kとc k は、それぞれ小数点の左と右のk桁目の数字です。
例えば、
−25.4 dec = −(1T×101 1 + 1TT×101 0 + 11×101 −1 )
= −(1T×101 + 1TT + 11÷101)
= −10T1. 11TT
= T01T. TT11
1010.1 2 = 1T 10 + 1T 1 + 1T −1
= 10T + 1T + 0. 1
= 101. 1
加算、減算、乗算、除算
以下に、1 トリットの加算、減算、乗算、除算の表を示します。減算と除算は可換ではありませんが、最初のオペランドは表の左側に示され、2 番目のオペランドは表の上部に示されます。たとえば、1 − T = 1T の答えは、減算表の左下隅にあります。
マルチトリット加算と減算
マルチトリットの加算と減算は、2 進数と 10 進数の加算と減算に似ています。トリットごとに加算と減算を行い、適切にキャリーを加算します。例:
1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1
+ 11T1.T − 11T1.T − 11T1.T → + TT1T.1
_______________ _______________ _______________
1T0T10.0TT1 1T1001.TTT1 1T1001.TTT1
+ 1T + T T1 + TT
__________
1T1110.0TT1 1110TT.TTT1 1110TT.TTT1
+ T + T 1 + T 1
__________
1T0110.0TT1 1100T.TTT1 1100T.TTT1
マルチトリット乗算
マルチトリット乗算は、2 進数と 10 進数の乗算に類似しています。
1TT1.TT
× T11T.1
_____________
1TT.1TT 1を掛ける
T11T.11 Tを掛ける
1TT1T.T 1を掛ける
1TT1TT 1を掛ける
T11T11 Tを掛ける
_____________
0T0000T.10T
マルチトリット分割
平衡三進法の除算は、二進法と十進法の除算に類似しています。
ただし、0.5 dec = 0.1111... bal3または 1.TTTT... bal3です。被除数が正または負の半分除数を超える場合、商のトリットは 1 または T でなければなりません。被除数が除数の半分の正と負の間にある場合、商のトリットは 0 です。商のトリットを設定する前に、被除数の大きさを除数の半分の大きさと比較する必要があります。たとえば、
1TT1.TT商
0.5 × 除数 T01.0 _____________
除数 T11T.1 ) T0000T.10T 被除数
T11T1 T000 < T010、セット1
_______
1T1T0
1TT1T 1T1T0 > 10T0、Tを設定
_______
111T
1TT1T 111T > 10T0、Tを設定
_______
T00.1
T11T.1 T001 < T010、セット1
________
1T1.00
1TT.1T 1T100 > 10T0、Tを設定
________
1T.T1T
1T.T1T 1TT1T > 10T0、Tを設定
________
0
もう一つの例は、
1TTT
0.5 × 除数 1T _______
除数 11 )1T01T 1T = 1Tだが、1T.01 > 1Tなので、1とする
11
_____
T10 T10 < T1、Tを設定
TT
______
T11 T11 < T1、Tを設定
TT
______
TT TT < T1、Tを設定
TT
____
0
もう一つの例は、
101.TTTTTTTTTT…
または 100.111111111...
0.5 × 除数 1T _________________
約数 11 )111T 11 > 1T、セット 1
11
_____
1 T1 < 1 < 1T、0に設定
___
1T 1T = 1T、トリット終了、1.TTTTTTTTTT... または 0.11111111... を設定します。
平方根と立方根
平衡 3 進数で平方根を抽出するプロセスは、10 進数または 2 進数の場合と同様です。
割り算の場合と同様に、まず除数の半分の値を確認する必要があります。たとえば、
1. 1 1 T 1 TT 0 0 ...
_________________________
√ 1T 1<1T<11、セット1
− 1
_____
1×10=10 1.0T 1.0T>0.10、セット1
1T0 −1.T0
________
11×10=110 1T0T 1T0T>110、セット1
10T0 −10T0
________
111×10=1110 T1T0T T1T0T<TTT0、Tを設定
100T0 −T0010
_________
111T×10=111T0 1TTT0T 1TTT0T>111T0、セット1
10T110 −10T110
__________
111T1×10=111T10 TT1TT0T TT1TT0T<TTT1T0、Tを設定
100TTT0 −T001110
___________
111T1T×10=111T1T0 T001TT0T T001TT0T<TTT1T10、Tを設定
10T11110 −T01TTTT0
____________
111T1TT×10=111T1TT0 T001T0T TTT1T110<T001T0T<111T1TT0、0を設定
− T リターン 1
___________
111T1TT0×10=111T1TT00 T001T000T TTT1T1100<T001T000T<111T1TT00、0を設定
− T リターン 1
_____________
111T1TT00*10=111T1TT000 T001T00000T
...
バランスのとれた 3 進数での立方根の抽出は、10 進数または 2 進数での抽出と同様です。
除算と同様に、まず除数の半分の値を確認する必要があります。例:
1. 1 T 1 0 ...
_____________________
³√1T
− 1 1<1T<10T、セット1
_______
1.000
1×100=100 −0.100 100倍を借りて割り算をする
_______
1TT 1.T00 1T00>1TT、セット1
1×1×1000+1=1001 −1.001
__________
0T000
11×100 − 1100 100倍を借りて割り算をする
_________
10T000 TT1T00 TT1T00<T01000、Tを設定
11×11×1000+1=1TT1001 −T11T00T
____________
1TTT01000
11T×100 − 11T00 100倍を借りて割り算をする
___________
1T1T01TT 1TTTT0100 1TTTT0100>1T1T01TT、セット1
11T×11T×1000+1=11111001 − 11111001
______________
1T10T000
11T1×100 − 11T100 100倍を借りて、割り算をする
__________
10T0T01TT 1T0T0T00 T01010T11<1T0T0T00<10T0T01TT、0を設定
11T1×11T1×1000+1=1TT1T11001 − TT1T00 100×を返す
_____________
1T10T000000
...
したがって、3√2 = 1.259921 dec = 1.1T1 000 111 001 T01 00T 1T1 T10 111 bal3。
アプリケーション
コンピュータ設計において

コンピューティングの黎明期には、ソ連の実験用コンピュータが二進法ではなく平衡三進法で構築された。最も有名なのはニコライ・ブルセンツォフとセルゲイ・ソボレフが構築したセトゥンである。この記法は、従来の二進法や三進法に比べて計算上の利点が数多くある。特に、プラスマイナスの一貫性により、多桁の乗算における桁上がり率が低下し、丸めと切り捨ての等価性により、端数の丸めにおける桁上がり率が低下する。平衡三進法では、1桁の乗算表は1桁のままで桁上がりがなく、加算表は9つのエントリのうち2つしか桁上がりがない。一方、不平衡三進法ではそれぞれ1つと3つの桁上がりがある。クヌースは「おそらく、この数体系の対称性と単純な算術は、いつか非常に重要になるだろう」と記している [6]。
平衡三進法の演算回路の複雑さは二進法の場合とそれほど変わらず、与えられた数値を表現するのに必要な桁数は同じだけである。」[6]
その他のアプリケーション
すべての整数は平衡三進法で一意に表現できるという定理は、レオンハルト・オイラーによって形式冪級数の同一性を正当化するために使用された[8]
バランスのとれた 3 進法には、計算以外にもさまざまな用途があります。たとえば、3 の累乗ごとに 1 つの重りが付いた古典的な 2 皿天秤は、2 つの皿とテーブルの間で重りを移動させることにより、比較的重い物体を少数の重りで正確に計量できます。たとえば、3 から 81 までの累乗ごとに重りが付いている場合、60 グラムの物体 (60 dec = 1T1T0 bal3 ) は、もう一方の皿に 81 グラムの重り、別の皿に 27 グラムの重り、別の皿に 9 グラムの重り、別の皿に 3 グラムの重り、別の皿に 1 グラムの重りを入れ、別に置いた皿に 1 グラムの重りを入れると、完全にバランスがとれます。
同様に、1¤、3¤、9¤、27¤、81¤ の価値があるコインがある通貨システムを考えてみましょう。買い手と売り手がそれぞれ各種類のコインを 1 枚ずつしか持っていない場合、121¤ までの取引が可能です。たとえば、価格が 7¤ (7 dec = 1T1 bal3 ) の場合、買い手は 1¤ + 9¤ を支払い、お釣りとして 3¤ を受け取ります。
また、キュートリットとそれを使用するシステム に対して、より自然な表現を提供することもできます。
参照
参考文献
- ^ ab NA Krinitsky; GA Mironov; GD Frolov (1963)。「第 10 章 プログラム制御マシン Setun」。MR Shura-Bura (編) 『プログラミング』(ロシア語)。モスクワ。
{{cite book}}: CS1 maint: location missing publisher (link) - ^ ab ヘイズ、ブライアン(2001)、「サードベース」(PDF)、アメリカンサイエンティスト、89 (6): 490–494、doi :10.1511/2001.40.3268ヘイズ、ブライアン(2008年)「寝室での群論とその他の数学的転換」ファラー、ストラウス、ジルー、179~200頁、ISBNに再録 9781429938570
- ^ Stifel、Michael (1544)、Arithmetica integra (ラテン語)、apud Iohan Petreium、p. 38。
- ^ と の等式には記号が2 回出現しますが、これらは同じものを表しているわけではありません。右側のと は整数を意味しますが、 の括弧内のインスタンス( に属する) は単なる記号として考える必要があります。
- ^ Bhattacharjee, Abhijit (2006 年 7 月 24 日). 「Balanced ternary」. 2009 年 9 月 19 日時点のオリジナルよりアーカイブ。
- ^ abc ドナルド・クヌース(1997年)。『コンピュータプログラミングの芸術』第2巻。アディソン・ウェズレー。pp. 195–213。ISBN 0-201-89684-2。
- ^ Douglas W. Jones、Ternary Number Systems、2013年10月15日。
- ^ アンドリュース、ジョージ E. (2007)。 「オイラーの『De Partitio numerorum』」。アメリカ数学協会の会報。新しいシリーズ。44 (4): 561–573。土井:10.1090/S0273-0979-07-01180-9。MR 2338365。
外部リンク
- モスクワ国立大学における三元コンピュータの開発
- 平衡三進法による分数の表現
- 「三進法」、三進法と平衡三進法
- バランス三進法(10進整数からバランス三進法への変換機能を含む)
- OEISシーケンス A182929 (二項三角形をバランスのとれた三項リストに縮小)
- バランス型(符号付き)三進法 2016-03-03 にWayback MachineでアーカイブされましたBrian J. Shelburne 著(PDF ファイル)
- マーク・グラスカーによるトーマス・ファウラーの三進法計算機
