この記事の過程で、1秒未満の任意の回数の反復を持つネストされたループを使用して、限られた数の変数に対して単純な操作（代入、加算、減算、切り捨て乗算）を実行できるインタープリターの作成方法について説明します（もちろん、計算の中間値が合理的な制限）。 たとえば、インタープリターに送信されるコードは次のとおりです。
loop 1000000000 loop 1000000000 loop 1000000000 a += 1 b += a end end end end
プログラムが単純に実行された場合、インタプリタは10億操作を実行する必要があるという事実にもかかわらず、a = 1000000000000000000000000000、b = 5000000000000000000000000000000000000000000000000000000を直ちに出力します。
読者は、マトリックスとは何か、マトリックスの積は何かを知っていると思います。 この記事では、正方行列のみを使用し、正方行列の乗算という非常に重要な特性である結合性に依存します。
簡単にするために、インタープリターを4つの変数-A、B、C、およびDに制限します。特定の瞬間のインタープリターの状態を表すために、サイズ5のベクトルを使用します。最初の4つの要素にはそれぞれ4つの変数の値が含まれ、最後はインタープリター全体で1に等しくなります。
(A, B, C, D, 1)
インタプリタの作業の開始時に、すべての変数の値がゼロに等しいと仮定します。
(0, 0, 0, 0, 1)
プログラムコードの最初の操作に文字列が含まれているとします
A += 5
このコマンドの効果は、変数Aの値が5増加し、他の3つの変数の値は変わらないことです。 これは、次のマトリックスとして表すことができます。
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 5 0 0 0 1
これを見ると、最初の列の最後の要素である5を除いて、恒等行列とほとんど同じであることがわかります（ご存じのように、ベクトルを乗算しても値は変わりません）。 ベクトルとマトリックスの乗算方法を思い出せば、最初の要素を除くすべての要素の値は変わらず、最初の要素の値は等しくなることがわかります。
v[0] * 1 + v[4] * 5
v [0]には変数Aの現在の値が含まれ、v [4]は常に1に等しいため、
v[0] * 1 + v[4] * 5 = A + 5
現在の状態のベクトルにこの行列を掛けると、結果のベクトルは、必要に応じてAがさらに5である状態に対応します。
マトリックスが少し変更された場合、最初の行の最初の要素の単位を削除します。
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 5 0 0 0 1
前と同様に、最初の要素を除くすべての要素の値は変更されませんが、最初の要素はv [4] * 5または5に等しくなります。 このような行列で現在の状態ベクトルを乗算することは、コマンドを実行することと同等です
A = 5
そのようなマトリックスを見てみましょう：
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1
単位行列との唯一の違いは、4番目の行の2番目の要素であり、1に等しいです。 明らかに、現在の状態ベクトルにこの行列を掛けても、最初と最後の3つの要素の値は変わりませんが、2番目の要素の値は
v[1] * 1 + v[3] * 1
v [1]には変数Bの現在の値が含まれ、v [3]には変数Dの現在の値が含まれるため、状態ベクトルにこのような行列を掛けることは、コマンドB + = D
同様に議論すると、状態ベクトルに次の行列を掛けることは、コマンドC * = 7を実行することと同等であることが理解できます。
1 0 0 0 0 0 1 0 0 0 0 0 7 0 0 0 0 0 1 0 0 0 0 0 1
チームの結合に移りましょう。 ベクトルvが現在の状態を指定し、行列MaがコマンドA + = 5に対応し、行列MmがコマンドA * = 7に対応するようにします。次に、これら2つのコマンドの実行後の状態のベクトルrを取得するには、まずvにMaを乗算し、次にMm：
r = v * Ma * Mm
予想どおり、初期状態ベクトルにこれらの2つの行列を乗算すると、a = 35の状態になります。
1 0 0 0 0 7 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 5 0 0 0 1 0 0 0 0 1 0 0 0 0 1 5 0 0 0 1 35 0 0 0 1
別の例を考えてみましょう-7を掛ける代わりに、Aに5を7回足したいだけです。
r = v * Ma * Ma * Ma * Ma * Ma * Ma * Ma
ここで、行列乗算の連想特性が助けになります。
r = v * Ma * Ma * Ma * Ma * Ma * Ma * Ma = v * (Ma * Ma * Ma * Ma * Ma * Ma * Ma) = v * Ma ^ 7
これは単純なサイクルの例です。vにMaを7回乗算する代わりに、行列Maを7乗してから1回の乗算を実行するだけで十分です。 次の2つの操作をループで3回実行したい場合：
A += 5 B -= C
（操作B-= Cを行列Mbcで表すと）、次のようになります。
r = v * Ma * Mbc * Ma * Mbc * Ma * Mbc = v * ((Ma * Mbc) * (Ma * Mbc) * (Ma * Mbc)) = v * (Ma * Mbc) ^ 3
サイクルの本体に対応する行列を一度だけ計算し、その後で累乗します。
上記の例は、割り当て、加算、減算、乗算（定数のみによる）、およびループをサポートする単純な言語のインタープリターで作業を開始するのに十分です。 これを行うには、サイズN + 1 x N + 1の行列の形式でそのようなプログラムを表現する方法を学習します。ここで、Nはプログラムが動作する変数の数です。その後、単純にベクトルにこの行列を初期状態で乗算します。
プログラムを行列形式で表すための規則は非常に簡単です。
1.個々のコマンドは、1つの要素（または割り当て操作の場合は2つ）がユニットと異なるマトリックス形式で表されます。 このようなマトリックスの例については、この記事で前述しました。
2.いくつかの連続したチームは、各チームのマトリックス表現の積に等しいマトリックスの形で提示されます。
3.サイクルは、サイクルの本体を表す行列として表され、サイクルの反復回数の累乗になります。
恒等行列を返す恒等関数がある場合：
def identity(): return [[1 if i == j else 0 for j in range(REGS + 1)] for i in range(REGS + 1)]
コマンドr1 + = r2（r1とr2は変数）の行列を作成する関数は、次のようになります。
def addreg(r1, r2): ret = identity() ret[r2][r1] = 1 return ret
コマンドr + = val（rは変数、valは定数）の場合、次のようになります。
def addval(r, val): ret = identity() ret[REGS][r] = val return ret
他のチームのマトリックスを構築するための関数は似ています-1つの要素が置き換えられた単一のマトリックスを取得します。
ループのないインタープリターは、非常に簡単に記述されるようになりました-既に読み込まれたコードにmatマトリックスを対応させてください。 空のプログラムは状態を変更しないため、最初は単位行列に等しくなります。 次に、コマンドを1つずつ読み取り、3つの要素（左オペランド、演算子、右オペランド）に分割し、演算子に応じて、プログラム全体に対応する行列に現在のコマンドに対応する行列を乗算します。
def doit(): mat = identity() while True: line = sys.stdin.readline().lower() tokens = line.split() if tokens[0] == 'loop': # elif tokens[0] == 'end': return mat else: r1 = reg_names.index(tokens[0]) try: r2 = reg_names.index(tokens[2]) except: r2 = -1 if tokens[1] == '+=': if r2 == -1: cur = addval(r1, long(tokens[2])) else: cur = addreg(r1, r2) elif tokens[1] == '-=': .... mat = matmul(mat, cur)
残っているのは、ループのサポートを追加することだけです。 ループは、ループ本体の行列をループの反復回数の累乗にします。 知られているように、累乗にはO（log N）操作のみが必要です。ここで、Nは行列が累乗される累乗です。 べき乗アルゴリズムは非常に簡単です。
1.次数がゼロの場合、単位行列を返します。
2.次数が偶数の場合、2Nとすると、M ^ Nを再帰的に計算し、結果の行列の二乗を返すことができます。
3.次数が奇数の場合、2N + 1とし、値M ^ 2Nを再帰的に計算し、結果の行列にMを掛けた値を返します。
2回の反復ごとに次数が2ずつ減少するため、このようなアルゴリズムの複雑さは対数です。
def matpow(m, p): if p == 0: return identity() elif p % 2 == 0: tmp = matpow(m, p / 2) return matmul(tmp, tmp) else: return matmul(m, matpow(m, p - 1))
インタープリターでは、1行追加する必要があります。
... if tokens[0] == 'loop': cur = matpow(doit(), long(tokens[1])) ...
通訳の準備ができました。
インタープリターの例はgithubで入手できます。 すべてのコードは100行未満です。
速度テストのために、すでに述べたフィボナッチ数に戻ることができます。 たとえば、次のコード：
A = 1 B = 1 loop 100 C = A C += B A = B B = C end end
101番目と102番目のフィボナッチ数が計算されます。
A = 573147844013817084101、B = 927372692193078999176
100を1,000,000に置き換えると、最初の100万と100万の秒数が4秒で計算されます。 このようなプログラムの実行には、プログラムが何桁もの数字で動作する必要があるため、はるかに多くの額が必要になります。 記事の冒頭で与えられた算術的進行の合計を計算するためのコードなど、大きな数で動作する必要のないコードを記述する場合、反復回数は妥当な範囲を超える可能性がありますが、コードは一瞬で実行されます
loop 1000000000000000000000000000000000000000000000 loop 1000000000000000000000000000000000000000000000 loop 1000000000000000000000000000000000000000000000 a += 1 b += a end end end end
実際には、このアプローチは、たとえば、コンパイラを最適化する際に適用できます。これにより、少数の変数で動作する多数の反復でループを折り畳むことができます。