位置計算

位置算術（ラテン語：arithmeticae localis）は、加法的な（位置を問わない）2進数 記数法であり、ジョン・ネイピアが論文「ラブドロジー」 （1617年）の中で、記号とチェス盤のようなグリッドの両方で計算手法として研究した。

ネイピアの用語は、ボード上のカウンターの位置を使用して数字を表すことから派生したものですが、実際のところ、現在の語彙では数字の表記法は位置に基づいていないため、誤解を招く可能性があります。

ネイピアの時代には、計算のほとんどはタリーマークやジェトンのついたボード上で行われていました。そのため、現代の読者が考えるのとは異なり、彼の目的はボード上のカウンターの動きを使って掛け算や割り算、平方根を求めることではなく、ペンと紙を使って記号的に計算する方法を見つけることでした。

しかし、この新しい手法をボード上で再現すると、試行錯誤による計算や複雑な繰り上がりの記憶（10 進法の計算とは異なり）は不要になりました。彼はこの発見に非常に満足し、序文で次のように述べています。

これは、単にカウンターをある場所から別の場所へ移動させるだけで、加算、減算、乗算、除算、平方根の算出を実行するため、労働というよりもむしろ遊びであると表現されるかもしれない。^[1]

2 進数表記法はまだ標準化されていなかったため、ネイピアは 2 進数を表すために位置数字と呼ばれるものを使用しました。ネイピアのシステムでは、数値を表すために符号値表記法を使用します。ラテン アルファベットの連続する文字を使用して、2 の累乗を連続して表します。a = 2 ⁰ = 1、b = 2 ¹ = 2、c = 2 ² = 4、d = 2 ³ = 8、e = 2 ⁴ = 16 などです。

特定の数値を位置数値として表すには、その数値を 2 の累乗の合計として表し、各 2 の累乗を対応する数字 (文字) に置き換えます。たとえば、10 進数値から変換する場合は次のようになります。

87 = 1 + 2 + 4 + 16 + 64 = 2 ⁰ + 2 ¹ + 2 ² + 2 ⁴ + 2 ⁶ = abceg

逆のプロセスを使用して、位置の数値を別の数値システムに変換できます。たとえば、10 進数値に変換する場合:

abdgkl = 2 ⁰ + 2 ¹ + 2 ³ + 2 ⁶ + 2 ¹⁰ + 2 ¹¹ = 1 + 2 + 8 + 64 + 1024 + 2048 = 3147

ネイピアは、彼の記数法で数値を変換したり、数値を彼の記数法から変換したりする複数の方法を示しました。これらの方法は、現代の2 進記数法で数値を変換する方法と似ているため、ここでは示しません。ネイピアは、加算、減算、乗算、除算、平方根の算出方法も示しました。

符号値表記法を使用するあらゆる数値システム（位置表記法を使用するシステムを除く）と同様に、数字（文字）を繰り返して複数の数字で 1 つの数字を表すことができます。例:

abbc = acc = ad = 9

また、数字の順序は重要ではありません。例:

abbc = bbca = bcba = ... = 9

位置数値の各桁は、その次の桁の値の 2 倍を表すため、同じ桁が 2 つ出現した場合、それを次の桁の値に置き換えても、数値は変わりません。したがって、位置数値にaa → b、bb → c、cc → dなどの置換規則を繰り返し適用すると、その数値から重複する桁がすべて削除されます。

ネイピアはこのプロセスを省略と呼び、結果として得られる位置数字をその数字の省略形と呼びました。また、繰り返し数字を含む位置数字を拡張形式と呼びました。各数字は、数字の順序を考慮せずに、一意の省略形で表すことができます (たとえば、abc、bca、cbaなどはすべて数字 7 を表します)。

位置数値を使用すると、加算のためのシンプルで直感的なアルゴリズムが可能になります。

1. 数字を端から端までつなげる
2. 必要に応じて、この結合された数字の数字を昇順になるように並べ替えます
3. この並び替えられた連結された数字を省略する

たとえば、157 = acdehと 230 = bcfghを加算するには、数字を端から端まで結合します。

acdeh + bcfgh → acdehbcfgh

前の結果の数字を並べ替えます ( acdehbcfghの数字は昇順ではないため)。

acdehbcfgh → abccdefghh

前の結果を省略すると次のようになります。

abccdefghh → abddefghh → abeefghh → abffghh → abgghh → abhh → abhi

最終結果abhiは 387 ( abhi = 2 ⁰ + 2 ¹ + 2 ⁷ + 2 ⁸ = 1 + 2 + 128 + 256 = 387) になります。これは、157 と 230 を 10 進数で加算した結果と同じです。

減算も直感的ですが、借用を実行するために省略形を展開形に拡張する必要がある場合があります。

減数（減らしたい最大の数）を書き、そこから減数（最小の数）に現れるすべての数字を削除します。削除する数字が減数に現れない場合は、単位を少しだけ大きくして借ります。減数の数字がすべて削除されるまで繰り返します。

いくつかの例を見ると、思ったより簡単だということがわかります。

• 77 = acdgから5 = ac を引きます 。

acdg - ac = ac dg = dg = 8+64 = 72。

• 77 = acdgから3 = ab を引きます 。

acdg - ab = abbdg - ab = ab bdg = bdg = 2+8+64 = 74。

• 77 = acdgから7 = abc を引きます 。

acdg - abc = abbccg - abc = ab b c cg = bcg = 2+4+64 = 70.

ネイピアは、当時一般的だったそろばんを使って、残りの算数、つまり掛け算、割り算、平方根計算に取り組みました。しかし、マイクロプロセッサ コンピュータが開発されて以来、倍算と半分算に基づいた応用可能なアルゴリズムが数多く開発または復活しました。

倍増は、数字をそれ自体に加えることによって行われます。つまり、数字の各桁を倍増することを意味します。これにより拡張形式が得られ、必要に応じて省略する必要があります。この操作は、数字の各桁を次の大きな桁に変更することで 1 つの手順で実行できます。たとえば、aの倍はb 、 bの倍はc 、 abの倍はbc 、 acfgの倍はbdghなどです。

同様に、2 の累乗を掛ける場合も、単に数字を変換するだけです。たとえば、 c = 4 を掛ける場合は、数字をa → c、b → d、c → e、... と変換します。

半分にすることは、2 倍にすることの逆です。つまり、各数字を次の小さい数字に変更します。たとえば、bdghの半分はacfgです。

すぐにわかるように、半分にする数字に a が含まれていない(または、数字が拡張されている場合はaが奇数個) 場合にのみ実行可能です。言い換えると、省略された数字はaが含まれている場合は奇数で、含まれていない場合は偶数です。

これらの基本的な操作 (2 倍化と半分化) を使用すると、二分法や二分探索など、あらゆるバイナリ アルゴリズムを適応させることができます。

ネイピアは、当時一般的だったそろばんを使って掛け算と割り算をしました。しかし、エジプトの掛け算は、倍、半分、足し算だけを使って表を使わずに掛け算を実行するエレガントな方法でした。

1 桁の数字を別の 1 桁の数字で乗算するのは簡単なプロセスです。すべての文字は 2 の累乗を表すため、数字を乗算することは指数を加算することと同じです。これは、アルファベットの 1 つの数字のインデックス ( a = 0、b = 1、...) を見つけて、アルファベットで他の数字をその量だけ増やす ( b + 2 => d )と考えることもできます。

たとえば、4 = c を16 = eで乗算します。

c * e = 2^2 * 2^4 = 2^6 = g

または...

AlphabetIndex ( c ) = 2 なので... e => f => g

2 つの複数桁の数字の積を求めるには、2 列の表を作成します。左の列に、最初の数字の数字を 1 つずつ下に書きます。左の列の各数字について、その数字と 2 番目の数字を掛け合わせて、右の列に記録します。最後に、右の列のすべての数字を合計します。

例えば、238 = bcdfghに 13 = acd を掛けます。

結果は右の列の合計bcdfgh defhij efgijk = bcddeefffgghhiijjk = bcekl = 2+4+16+1024+2048 = 3094 になります。

興味深いことに、左の列は、最初の数字から偶数を除いた連続した半分によっても得られます。例では、acd、bc (偶数)、ab、aです。右の列に 2 番目の数字の連続した 2 倍が含まれていることに注意すると、農民乗算が正確である理由がわかります。

割り算は連続した減算によって実行できます。商は、除数を被除数から減算できる回数であり、剰余は、可能なすべての減算を行った後に残る値です。

このプロセスは非常に長くなる可能性がありますが、除数の代わりに除数の倍数を減算すると効率化できます。また、倍数を 2 の累乗に制限すると計算が簡単になります。

実際、これは長除法で行っていることです。

位置演算では、グリッド上の各マスが値を表す正方形グリッドを使用します。グリッドの 2 つの側面には、2 の累乗が増加でマークされています。内側のマスは、この 2 つの側面にある 2 つの数字で識別できます。1 つは内側のマスの垂直下にあり、もう 1 つはその右端にあります。マスの値は、この 2 つの数字の積です。

たとえば、この例のグリッドの正方形は、右列の 4 と下行の 8 の積であるため、32 を表します。グリッド自体は任意のサイズにすることができ、グリッドが大きいほど、より大きな数字を処理できるようになります。

1 マスを左に、または 1 マスを上に移動すると、値が 2 倍になることに注意してください。このプロパティを使用すると、グリッドの 1 行だけを使用して 2 進加算を実行できます。

まず、カウンターを使って 2 進数を 1 行に並べ、その数字の 1 を表します。たとえば、29 (2 進数では 11101) は、次のようにボード上に配置されます。

29 という数字は、明らかにカウンターが置かれているマス目の数字の合計です。次に、この行に 2 番目の数字を重ねます。9 (2 進数では 1001) を次のように配置するとします。

これら 2 つの数字の合計は、ボード上のカウンターが表す合計値に過ぎませんが、一部のマス目にはカウンターが複数あります。ただし、マス目の左に移動するとその値は 2 倍になることを思い出してください。したがって、ボード上の合計値は変更せずに、マス目の 2 つのカウンターをその左側の 1 つのカウンターに置き換えます。これは、位置の数字を省略する場合と同じ考え方であることに注意してください。まず、右端のカウンターのペアをその左側のカウンターに置き換えて、次の式を作成します。

まだ 2 つのカウンターが置かれている別のマス目があるので、もう一度繰り返します。

しかし、このペアを置き換えると、カウンターが 2 つ付いた別の正方形が作成されたため、3 回目の置き換えを行います。

これで、各マス目にはカウンターが 1 つだけ存在するようになり、結果を 2 進数 100110 (= 38) で読み取ると正しい結果が得られます。

減算は加算よりもそれほど複雑ではありません。ボード上のカウンターを追加する代わりに、カウンターを削除します。値を「借りる」には、マス目のカウンターをその右側の 2 つと置き換えます。

38 から 12 を引く方法を見てみましょう。まず 38 (= 2 進数では 100110) を行に置き、次にその下に 12 (= 2 進数では 1100) を置きます。

下の列にあるカウンターのうち、上にカウンターがあるカウンターは、両方とも取り除きます。ボード上のこのようなカウンターのペアを 1 つ取り除くと、次のようになります。

ここで、一番下の残りのカウンターを取り除くために、カウンターを「借りる」必要があります。まず、一番上の行の一番左のカウンターを、その右側の 2 つのカウンターに置き換えます。

次に、2 つのカウンターのうちの 1 つを、その右側にさらに 2 つ追加して置き換えます。

これで、一番上の列にあるカウンターの 1 つを取り除き、一番下の列に残っているカウンターを取り除くことができます。

そして最終結果である26を読み上げます。

加算や減算とは異なり、乗算、除算、平方根の抽出にはグリッド全体が使用されます。グリッドには、これらの演算で利用される便利な特性がいくつかあります。まず、左下から右上に向かう対角線上のすべての正方形の値は同じです。

斜めの移動は、右への移動 (値が半分になる) とそれに続く上への移動 (値が 2 倍になる) に分解できるため、正方形の値は変わりません。

この対角線の特性と組み合わせると、グリッドの下端と右端の数字を分割する簡単な方法があります。

被除数 32 をグリッドの右側に、除数 8 をグリッドの下端に見つけます。被除数から対角線を延長し、除数からの垂直線と交差する正方形を見つけます。商はこの正方形からグリッドの右端にあり、この例では 4 です。

なぜこれが機能するのでしょうか? 対角線に沿って移動しても値は変わりません。交差点の正方形の値は依然として被除数です。しかし、これは下端と右端の正方形の積であることもわかっています。下端の正方形が除数なので、右端の正方形が商です。

ネイピアはこの考え方を拡張して、以下に示すように 2 つの任意の数を除算します。

2 進数のペアを掛け合わせるには、まずグリッドの下部と右側に 2 つの数字をマークします。たとえば、22 (= 10110) を 9 (= 1001) で掛け合わせたいとします。

次に、各数字の 1 の縦列と横列のすべての「交差点」にカウンターを配置します。

グリッド上の各列のカウンターは、22に2の累乗を掛けたものであることに注意してください。実際、カウンターの合計値は2列の合計です。

22*8 + 22*1 = 22*(8+1) = 22*9

したがって、ボード上のカウンターは実際には 2 つの数値の積を表しますが、答えを「読み取る」ことはまだできません。

カウンターを斜めに動かしても値は変わらないので、内側のマスにあるすべてのカウンターを、一番下の行または左の列に当たるまで斜めに動かします。

ここで、加算のときと同じ動きをします。マスにある 2 つのカウンターを、その左にあるカウンターと交換します。マスが左の列にある場合は、2 つのカウンターをその上にあるカウンターと交換します。マスの値は上に移動すると 2 倍になるため、グリッド上の値は変更されないことに注意してください。

まず、一番下の 2 番目のマスにある 2 つのカウンターをその左側の 1 つと置き換えて、角に 2 つのカウンターが残るようにします。

最後に、角にある 2 つのカウンターをその上の 1 つに置き換え、左上から左下隅まで、そして右下まで、L 字型に 2 進数を「読み取り」ます。

L に沿ってカウンターを読み取りますが、角の四角形を二重に数えないでください。バイナリの結果 11000110 = 198 が読み取られ、これは実際には 22*9 です。

なぜ 2 進数をこの L 字型に読み取ることができるのでしょうか。下の行には、もちろん 2 の最初の 6 つの累乗だけが表示されていますが、左端の列には次の 5 つの 2 の累乗が表示されています。つまり、グリッドの左側と下側にある 11 個の正方形の L 字型セットから、11 桁の 2 進数を直接読み取ることができるのです。

6x6 の小さなグリッドでは、最大 63 までの数字を掛け算できますが、一般にn x n のグリッドでは、2 つの数字を最大 2 ⁿ -1まで掛け算できます。これは非常に高速にスケーリングされるため、たとえば、各面に 20 個の数字があるボードでは、最大 100 万を超える数字を掛け算できます。

マーティン・ガードナーはネイピアの除算法の少し分かりやすいバージョン^[2]を提示しており、それがここに示されているものです。

割り算は、掛け算の逆の働きをします。485 を 13 で割りたいとします。まず、485 (= 111100101) の数字を下端に置き、13 (= 1101) の数字を右端に書きます。スペースを節約するため、実際に使うのはボードの長方形の部分だけなので、その部分だけを見ます。

このゲームでは、左から始めて、カウンターを斜めに「約数の列」に移動します (つまり、各行に約数の 1 がマークされたカウンターが 1 つあります)。これを、左端のカウンター ブロックで説明しましょう。

次に試すカウンターのブロックは、一番左のカウンターから始めて、次のようなものを試します。

ただし、下端から斜めに「約数の列」の残りの部分を形成する正方形に移動できるカウンターはありません。

このような場合、代わりに一番下の行のカウンターを「ダブルダウン」して、右に 1 つ列を形成します。すぐにわかるように、この方法で常に列を形成できます。まず、一番下のカウンターをその右側の 2 つに置き換えます。

次に、1 つを斜めに列の上部に移動し、ボードの端にある別のカウンターをその場所に移動します。

残りの正方形に斜めに移動するためのカウンターが下端にまだないように見えますが、代わりに左端のカウンターをもう一度 2 倍にして、目的の正方形に移動できることに注目してください。

そして、カウンターを 1 つ斜めに目的の場所に移動します。

次の列の構築に進みましょう。もう一度、左端のカウンターを列の上部に移動しても、残りのマスを埋めるのに十分なカウンターが下部に残らないことに注意してください。

そこで、カウンターを 2 倍にして、1 つを斜めに次の列に移動します。右端のカウンターも列に移動してみましょう。これらの手順を実行すると、次のようになります。

まだ足りないマス目がありますが、もう一度ダブルダウンしてカウンターをこの場所に移動すると、

この時点で、下端のカウンターは右端に寄っているため、どの列の上端にも斜めに移動できず、作業が完了したことを示します。

結果は列から「読み取られ」ます。つまり、カウンターのある各列は 1 として扱われ、空の列は 0 として扱われます。したがって、結果は 100101 (= 37) となり、余りは下端に残っているカウンターのバイナリ値になります。右から 3 番目の列にはカウンターが 1 つあるため、これを 100 (= 4) と読み取ると、485 ÷ 13 = 37 となり、余りは 4 になります。

このプロセスでは、そろばん（盤）にカウンターを追加して正方形の数字を作る必要があります。149 ページの上部に、このプロセスを説明する図が示されています。まず、盤にカウンターを 1 つ置きます（実際には、点線のマス目のいずれかに置きます）。隣接する 3 つのカウンターを追加すると（または、最初に置いたカウンターとの間に空白の行と列を置くと）、そろばんに別の正方形の数字が作成されます。同様に、これにさらに 5 つのカウンターを追加すると（空白の行と列の有無にかかわらず）、さらに大きなマス目が作成されます。検討する数字を取り、その値を表す 1 つの余白に沿ってカウンターを配置します。その値の最大カウンターの位置から、点のあるマス目に到達するまで、盤全体の対角線（ビショップの動き）をたどります。そのマス目にカウンターを置きます。この 1 つのカウンターによって表される値を、余白の元の数値から引きます。 3 (以降の手順では 5、7、...) を追加してボード上に正方形を作成し、余白の数字から追加したカウンターの値を減算します。この減算は、数字が大きすぎて減算できなくなるか、ボード上にスペースがなくなるまで続きます。ボード上にはカウンターの大きな正方形 (間に空白の行と列がある場合もあります) が残るはずです。正方形の各行のカウンターの 1 つを余白に移動すると、これらの余白カウンターの位置から数字の平方根が求められます。

ネイピアは、1238 の平方根を求める例を示しています。最大のカウンターは 1024 の位置にあるため、最初のカウンターは 1024 の対角線を下に移動して見つかったドット (32,32 の位置) に配置されます。この値 (1024) を元の数値から減算すると、カウンターは 128、64、16、4、2 (= 214) になります。最初のカウンターと正方形を形成するようにボード上に 3 つのカウンターを配置し、その値が 214 から減算できるようにすると、カウンターの位置は 32,2、2,2、になります。そして 2,32 (その値は 64、4、64 で、214 の余りから引くと 82 になります)。5 つのカウンターから作成できる次の正方形では、その 5 つのカウンターの値がまだ 82 から引くことができるため、カウンターの位置は 32,1、2,1、1,1、1.2、1,32 になります。これら 5 つのカウンターの値は合計 69 で、82 から引くと 13 が余りになります。ボード上にはこれ以上スペースがないため、ここで終了する必要があります。各行から 1 つのカウンターを余白 (行 32、2、1) に移動すると、この値 (35) が必要な平方根、または少なくともその整数部分 (実際の値は 35.1852....) になります。

ネイピアは2209（= 47）の平方根を計算する2番目の例を示しています。 ^[1]

• ジェトン

1. ^ジョン・ネイピア著、ウィリアム・フランク・リチャードソン訳、ロビン・E・ライダー序文（1990年）。ラブドロジー。MITプレス。ISBN 0-262-14046-2 。
2. ^マーティン・ガードナー (1986)。『結び目のあるドーナツとその他の数学的エンターテイメント』WHフリーマン・アンド・カンパニー。ISBN 0-7167-1794-8。 

特定の

• 位置計算のJavascriptシミュレーション