赤げふの数学

数学・物理・微分の高校生 赤げふのBLOG

2020 学園祭 発表資料

こんにちは(*^^*)

バーゼル問題の初等幾何的証明のGeogebraツールを使用したスライドのリンクを置いておきます。

https://www.geogebra.org/m/wqjxctwc

 

左上のスライダーを右に移動させるとスライドを切り替え、

そして左上のスライダーを1番右にした上で、左下のスライダーを右に移動させると分裂の様子が見れます。右下のスライダーを移動させるとライトを分裂させられます。

D^(2)型Affine Geometric Crystal

 


こんにちはヽ(^0^)ノ

https://arxiv.org/pdf/math/0512657.pdf

 


アフィン型幾何結晶(geometric crystal)のこの論文を読んでいたら、微分作用素表示が出せそうと思ったので計算したら公式を発見・導出できたので紹介します。今回はD_{n+1}^{(2)}型です。

論文にある写像eは幾何結晶として要請からリー群の作用とみなせてパラメータ微分の計算をタラタラすると得られました。derivative representationと言う名前を見かけたので使っていますが、この対象を微分作用素の環の元として表示するモチベはあまり無いっぽいですね(?)

\begin{align}e_0=\dfrac{x_0^2-x_1y_1}{x_0^2+x_1y_1}x_0 \dfrac{\partial}{\partial x_0} -\dfrac{2x_1y_1}{x_0^2+x_1y_1}\left(x_n \dfrac{\partial}{\partial x_n}+\sum_{k=1}^{n-1}x_k\dfrac{\partial}{\partial x_k}+y_k\dfrac{\partial}{\partial y_k}\right)\end{align}

\begin{align}e_i=\dfrac{y_i}{x_iy_i+x_{i+1}y_{i+1}}\left(x_i^2\dfrac{\partial}{\partial x_i}+x_{i+1}y_{i+1}\dfrac{\partial}{\partial y_i}\right)\ \ \ \ (1≦i≦n-2)\end{align}

\begin{align}e_{n-1}=\dfrac{y_{n-1}}{x_{n-1}y_{n-1}+x_n^2}\left(x_{n-1}^2\dfrac{\partial}{\partial x_{n-1}}+x_n^2\dfrac{\partial}{\partial y_{n-1}}\right)\end{align}

\begin{align}e_n=x_n\dfrac{\partial}{\partial x_n}\end{align}

D^{(2)}_{n+1}型Cartan行列(a_{ij})

\begin{align}a_{ij}=2\ \ \ i=j\end{align}

\begin{align}a_{ij}= -2 \ \ \ (i,j)=(0,1),(n,n-1)\end{align}

\begin{align}a_{ij}=-1 \ \ \ |i-j|=1かつ(i,j)≠(0,1),(n,n-1)\end{align}

\begin{align}a_{ij}=0\ \ \ \rm{otherwise} \end{align}

このとき次のVerma関係式が成立する(c,d∈ℂ^×)

\begin{align}a_{ij}=0⇒c^{e_i}d^{e_j}=d^{e_j}c^{e_i}\end{align}

\begin{align}a_{ij}=-1⇒c^{e_i}(cd)^{e_j}d^{e_i}=d^{e_j}(cd)^{e_i}c^{e_j}\end{align}

\begin{align}a_{ij}=-2⇒c^{e_i} (c^2d)^{e_j} (cd)^{e_i} d^{e_j}=d^{e_j} (cd)^{e_i} (c^2d)^{e_j} c^{e_i}\end{align}

次の等式も要請されます(m=0,1,\ldots,n)

\begin{align}c^{e_m}d^{e_m}=(cd)^{e_m}\end{align}

 


c^{e_i}の作用は以下の通りです。

f=f\dbinom{x_0,x_1,x_2\ldots ,x_{n-1},x_n}{y_1,y_2,\ldots y_{n-1}}T_0=\dfrac{c^2x_0^2+x_1y_1}{c^2(x_0^2+x_1y_1)}T_i=\dfrac{cx_iy_i+x_{i+1}y_{i+1}}{x_iy_i+x_{i+1}y_{i+1}}(i≠0,n-1,n)T_{n-1}=\dfrac{cx_{n-1}y_{n-1}+x_{n}^2}{x_{n-1}y_{n-1}+x_n^2}

\begin{align}c^{e_0}・f=f\dbinom{x_0cT_0,x_1T_0,x_2T_0\ldots,x_{n-1}T_0,x_nT_0}{y_1T_0^{-1},y_2T_0^{-1},\ldots,y_{n-1}T_0^{-1}}\end{align}

\begin{align}c^{e_i}・f=f\dbinom{x_0,x_1,\ldots,x_iT_i,\ldots,x_n}{y_1,\ldots,y_{i}cT_i^{-1},\ldots,y_{n-1}}\end{align}

\begin{align}c^{e_{n-1}}・f=f\dbinom{x_0,x_1,\ldots,x_{n-1}T_{n-1},x_n}{y_1,\ldots,y_{n-1}cT_{n-1}^{-1}}\end{align}

\begin{align}c^{e_n}・f=f\dbinom{x_0,x_1,\ldots,x_{n-1},cx_n}{y_1,\ldots,y_{n-1}}\end{align}

 


前回と記事の構成ほぼ同じですゴメンなさい(Dynkin図形似てるので)

C_n^1型アフィン幾何結晶の微分作用素表示

 


こんにちはヽ(^0^)ノ

https://arxiv.org/pdf/math/0512657.pdf


アフィン型幾何結晶(geometric crystal)のこの論文を読んでいたら、微分作用素表示が出せそうと思ったので計算したら公式を発見・導出できたので紹介します。今回はC_n^{(1)}型です。
論文にある写像eは幾何結晶として要請からリー群の作用とみなせてパラメータ微分の計算をタラタラすると得られました。derivative representationと言う名前を見かけたので使っていますが、この対象を微分作用素の環の元として表示するモチベはあまり無いっぽいですね(?)
\begin{align}e_0=\dfrac{x_0-x_1y_1}{x_0+x_1y_1}x_0 \dfrac{\partial}{\partial x_0} -\dfrac{x_1y_1}{x_0+x_1y_1}\left(2x_n \dfrac{\partial}{\partial x_n}+\sum_{k=1}^{n-1}x_k\dfrac{\partial}{\partial x_k}+y_k\dfrac{\partial}{\partial y_k}\right)\end{align}
\begin{align}e_i=\dfrac{y_i}{x_iy_i+x_{i+1}y_{i+1}}\left(x_i^2\dfrac{\partial}{\partial x_i}+x_{i+1}y_{i+1}\dfrac{\partial}{\partial y_i}\right)\ \ \ \ (1≦i≦n-2)\end{align}
\begin{align}e_{n-1}=\dfrac{y_{n-1}}{x_{n-1}y_{n-1}+x_n}\left(x_{n-1}^2\dfrac{\partial}{\partial x_{n-1}}+x_n\dfrac{\partial}{\partial y_{n-1}}\right)\end{align}
\begin{align}e_n=x_n\dfrac{\partial}{\partial x_n}\end{align}
C^{(1)}_n型Cartan行列(a_{ij})

\begin{align}a_{ij}=2\ \ \ i=j\end{align}
\begin{align}a_{ij}= -2 \ \ \ (i,j)=(1,0),(n-1,n)\end{align}
\begin{align}a_{ij}=-1 \ \ \ |i-j|=1かつ(i,j)≠(1,0),(n-1,n)\end{align}
\begin{align}a_{ij}=0\ \ \ \rm{otherwise} \end{align}
このとき次のVerma関係式が成立する(c,d∈ℂ^×)
\begin{align}a_{ij}=0⇒c^{e_i}d^{e_j}=d^{e_j}c^{e_i}\end{align}
\begin{align}a_{ij}=-1⇒c^{e_i}(cd)^{e_j}d^{e_i}=d^{e_j}(cd)^{e_i}c^{e_j}\end{align}
\begin{align}a_{ij}=-2⇒c^{e_i} (c^2d)^{e_j} (cd)^{e_i} d^{e_j}=d^{e_j} (cd)^{e_i} (c^2d)^{e_j} c^{e_i}\end{align}

次の等式も要請されます(m=0,1,\ldots,n)

\begin{align}c^{e_m}d^{e_m}=(cd)^{e_m}\end{align}

このような系があります。


\begin{align}φ(x):=\dfrac{z}{yz+x}\left(y^2\dfrac{\partial}{\partial y}+x\dfrac{\partial}{\partial z}\right),c,d∈ℂ^×\end{align}
\begin{align}c^{φ(d^{-1})}d^{φ(c)}=d^{φ(c^{-1})}c^{φ(d)}=(cd)^{φ(1)}\end{align}

 

Minecraft Redstone D-CCA Multiple&Division(part2)

こんにちはヽ(^0^)ノ

この記事はpart1の続きなので、読んでなければ先ずpart1から見て欲しいです。

乗除算について解説していきます。

 

 

この連続加算器は6tick周期でパイプライン演算をしているので時刻毎に割り当てられた6個の連続加算を同時並行でできるが、乗除算を行う際はそのうち2区画を使っておこなう(工夫すれば3個同時並行でできる)。

以後tickはrstickのことを指すとする。

 

昔私は乗除算をこのDCCA(decimal carry cancel adder)上で同じ手法でできる方法を思いついたので解説する。DCCAの桁数は上限の13桁が出力の限界だが、理論上最大誤差が50(最下位桁が1の位として)出るので出力の有効数字は11桁であるが、平均的な誤差は10程度で済む。

この計算機では小数点の位置をあまり自由に動かすことが出来ないため、入出力の形式は

A×B\cdots 0≦ A\lt 10, 0≦B\lt 10,0\lt AB\lt 100、有効数字12

A÷B\cdots 0≦A\lt 10 ,0\lt B\lt 10,0\lt A÷B \lt 10

 


先ず除算X÷Yについて見るが、手順は筆算ベースであり、X=6.91、Y=2.73を例に取って見ていく(ちなみにB_{12}=-\frac{691}{2730}はベルヌーイ数)

 

f:id:AkaGhef:20200715222214j:image

 

中段の1450,85などの数字は部分剰余と言い、無限小数である場合は部分剰余を割る操作を永遠と繰り返すことになるが、計算機は途中で打ち切る。簡単の為に加算器は13桁ではなく6桁とし、小数点は無視する。Aは部分剰余で初期値は被除数X、Bを除数Y(をシフトしたもの)、Iは商をカウントするためのインクリメント[デクリメント]の±1であり、Oは(暫定的な)商で、初期値は0ある。筆算と少し違う点が、次の段の部分剰余を求める際にAからB×(0〜9)を引くのでは無く、AからBを何回か引いて行う点であり、乗算を使わずに済み、0~9の値を見積もる必要が無い。
AからBを引く度にOにIを足すことで商をカウントしている。これを繰り返しAからBを引きすぎたら一旦BAに足して修正して、OからIを引いてカウントをバックしている。これで次の段の部分剰余が求まるので、BとIを1つシフトダウンしてまた次の段の部分剰余を求める操作を行う。ループは以下の手順。

(1)AからBを負の数になるまで0~9回引く(赤線)
(2)引く毎にOIを足し、商をカウント(赤線)
(3)Aが負の値になったらBを足す(緑線)
(4)OからIを引き、カウントをバック(緑線)
(5)BとIを1つシフトダウン(青線)

 

f:id:AkaGhef:20200715222406j:image

 

次に乗算X×Yについて、被乗数X=4.56、乗数Y=1.23を例にとって見ていく。

[筆算]

 

 

f:id:AkaGhef:20200630072408j:image

 

3つの数を同時に足しあげるのは計算機的に困難なので2数ずつ足しあげる筆算の書き方をしているが、雰囲気は掴んで貰えるだろう。途中で出てくる456,5472の数字の段(緑矢印)を部分和と呼び、除算同様に小数点は無視する。Aは乗ずる回数の書かれた数で初期値は乗数YBは被乗数X(をシフトしたもの)、Iは乗ずる回数をAからカウントダウンするためのインクリメント[デクリメント]の±1である。Oは部分和の役割で、最終的に積X×Yの答えとなる。
AからIを引いてカウントダウンし同時にOにBを加える操作をAが負になるまで行う。Aが負になるとカウントし過ぎなのでAにIを加え、OからBを引き修正する。これで部分和が求まったので次の段の部分和を求める為にBとIを1つシフトダウンする。ループをまとめると以下のようになる:

(1)AからIを負になるまで引く(赤線)
(2)引くごとにOにIを足す(赤線)
(3)Aが負の値になったらIを足す(緑線)
(4)OからBを引く(緑線)
(5)BとIを1つシフトダウン(青線)

[表]

f:id:AkaGhef:20200715232031j:image

乗除算の類似性と実際の回路の手順について説明していく。図や、乗除算それぞれで示したループの手順を見るとほぼBとIを入れ替えただけで、処理内容がとても似ていることが分かる。そこで連続加算器がパイプライン処理であったことを巧妙に使って、
計算機のコア内に入っているOとAにタイミングよくBとIを入力することで乗算と除算を使い分けることが出来る。加算器は6tick周期なのでそれと同期できるようにBとIを保存する外部のメモリは6tick周期で巡回するコンパレータの構造となる。
パイプライン処理で同時に3個の乗除算を行えるが本解説では1個の乗除算のみに限定し更に高速化を試みる。先程ループの手順を示したが(5)のBとIをシフトダウンする際、6tick周期のメモリの場合

シフトする部分に信号が回ってくるまで待つ必要があるためシフトダウンする部分で遅延が生じて、[表]での緑,青の部分の処理をした後の赤の部分の処理に入力が間に合わない。そこでメモリを2tick周期にしてみると、連続加算器の周期が6tickで、2tickはその約数となっているため、2つのスロットにB,Iを入れておくと問題なく処理できる。そしてB,Iが奇数時刻か偶数時刻にコアに入力されるかどうかで乗算と除算を切り替えられる。(これを閃いた時はまさに最適解だったのでめちゃ嬉しかった)


制御回路で実際に動かしていく方法を見る。今手元に制御回路が完成された乗除算器が無く、申し訳ないが忙しいせいで載せることが出来ない。

f:id:AkaGhef:20200715222825j:image
前回補数の項目で話をしたように、減算結果が負であるかどうかは、減算したときに最上位の繰り上がり出力(以後C^Oと書く)がC^O=1ならば結果は0以上である。乗算の場合A-Iの減算をしたときC^O=1ならば減算結果が0以上なので次は赤色の矢印の操作を行い、減算か加算かを制御する(J)の配線をonにして次も減算を行う。逆にC^O=0のとき減算結果が負なので青,緑の矢印の操作を行う、すなわち(J)の信号をoffにし次は加算モードにして、(K)に信号を送ってB,Iを1つシフトダウンする。また除算の場合は、上記のA-IA-Bに読み替えると全く同様の処理であることが理解出来る。
((J)に信号を送る部分を最小遅延で行える回路の実現がかなり大変で2ヶ月も苦労したんですよね)

以上の手続きをアセンブリ風に書いてみる(だいぶ前に書いたものなので正当性怪しいのでお気持ち程度に...)

アセンブリは、デカい命令が書いてある主記憶装置、演算を行う部分、演算結果を記憶する部分(以下Acc)、の3つに分かれる。命令はadd・subで番地指定した所の値をAccに加えたり引いたり

基本番地が低い所から命令を実行していく。
loadは指定した番地から値を引き出し、Accに上書き。
atoreは指定した番地にAccの値を上書き。
jumpは指定した番地から処理を始める。
jump minusはAccの値が負ならjumpと同じことをする。
本当は無いが、面倒なのでmultipleとdivideという命令を追加し、それぞれ掛ける、割る の命令とした。

f:id:AkaGhef:20200715222648j:image

最後まで見て頂きありがとうございますm(*_ _)m

記事は2週間前に完成してたのですが、アップロードエラーを吐かれてやる気を失って遅くなりました。

暫定的ではありますが、高3の身分ゆえ冠模試があるので受験勉強に集中したいと思いますまる

sin計算機の解説も未定です。。。

それでは〜〜

Minecraft Redstone Decimal Carry Cancel Adder(part1)

 

こんにちはー(・ω・*)ノノ

計算機を制作していたのですが、cloneミスで計算機が吹っ飛んだり度重なるクラッシュで戦意喪失したので解説を投げて私の受験が終わるまで制作を中断しようと思います(;´д`)

基礎的な論理回路と2進数の加算器は既知として説明しますが、他何か不詳な点あれば説明を足すので指摘ください!

作り方は最後の方にあります。

 

タイトルのCarry Cancel Adder(CCA)とは外国人のMajic氏が開発した2進数加算器(binary adder)であり、2進数14bitの加算が繰り上がり(carry)の遅延が無いという凄すぎる技術を天才すぎるアイデアで実現したものである。元動画リンク:

youtu.be

 

しかし、5年経った今でも知名度が低いのが現状である。私は丁度3年前にこの2進数の加算器を10進数の連続加算器(decimal loop adder)にかなり時間をかけて改良し、加算を何回も出来るようにした。CCA(Carry Cancel Adder)の説明をした後、連続加算器があれば乗除算を高速かつ同じマシンで出来るようになる方法があるので紹介したい次第である。最終的には三角関数計算機の解説を目標とする。便宜上数式を使うが、実際の理解としては感覚に近いと思う。

 

信号強度半加算器

信号強度加算器では信号強度とデータの値を対応させて、コンパレータの減算モードを何個か用いて計算するもので、2進数と半加算器が2つ並んで全加算器を構成し、全加算器が加算器を構成していることと似ている。

コンパレータ減算モードの挙動は、背面,側面の入力,出力をそれぞれa,b,cとしてc=R(a-b)と表される。

ここでRはRamp関数でありR(x)=x(x≧0),R(x)=0(\rm{それ以外のとき} )

0≦a,b≦9の整数の加算について見ていく。

a+b≦9のときa+b=9-(9-b-a)となるが、値の範囲を確かめれば

a+b=R(9-R(R(9-b)-a))となることが確認出来ると思う。

a+b≧10のとき1の位の値はa+b-10=a-(10-b)なので

a+b-10=R(a-R(9-b))-1で表せる。2つの数式を見比べると、共通してR(9-b)という部分が含まれているので、ここから回路を小型化できそうだと私は昔閃いた。R(x-y)の形をコンパレータ減算モードだと思えば、数式に従って次のように回路が実現できる。(-1は強度1減衰と考える)

[図2]

f:id:AkaGhef:20200608074744p:image

 

この回路は下位からの繰り上がりを考慮していないので半加算器と呼ぶ。2進数の場合は半加算器を2つ並べて、ある桁の入力a,b,下位からの入力C^iからその桁の出力O,上位桁への繰り上がり出力C^oを出力する全加算器を構成している。10進数の場合は全加算器は半加算器1つと、C^iを考えた+1,+0の操作をする部分に分かれる。

 CCA 繰り上がり計算機構

ここからがCCAの枢要たる部分だが、12桁程度の加算では全てのC^iを各桁のa,bから瞬時に計算できるのである。加算の筆算では下位桁から順に計算するように、加算する桁数に比例して計算に時間がかかるので、全体の計算時間のネックとなるのでここを高速化する必要がある。アイデアは冒頭で挙げたリンク先から得たもので、加算器の理論を後から知ったのでそれを加えて解説していこうと思う。下位から第k桁目のa,b,C^i,C^o値をそれぞれA_k,B_k,C_k^i,C_k^oと書く。

 現実の々加算器には高速化の手段としてCarry Look Aheadがありその中にPG信号という理論がある。繰り上がりがどう上位の桁に影響を及ぼすかを見るために、各桁について"propagate"か"generate"という概念を定める。N進法(N=2,10で十分)の加算で、A_k+B_k=N-1であるとき、第k桁はpropagate状態、(P)という。また、A_k+B_k≧Nのとき、generate状態、(G)という。本解説では便宜をはかって、(P)でも(G)でもないとき、cancel状態、(Cc)と呼ぶことにする。(P)、(G)、(Cc)は排反(2つが同時に起こり得ることは無い)で、いずれかひとつの状態である。足し算の筆算を書きまくって確かめて欲しいが、具体例を1つ書いた。

[図4]

f:id:AkaGhef:20200606024845j:image

 

 

CCAでは2本の信号強度の配線の強度の大小関係でC^i_kを決定しており、ワイヤーと大小関係を比較するコンパレータしかいらないので上位桁にもほぼ遅延無く情報が届き即座にC^iの決定ができる。第k+1桁が(P)であるときC^o_k=C^i_{k+2}が成り立つが、まさに第k桁の繰り上がり出力が第k+1桁をそのまま伝搬(propagate)し、第k+2桁に入力されている。(G)は繰り上がりが発生(generate)すること意味し、(P)が続く限り伝搬し続ける。ここまでは現実の理論体型と同じだが、繰り上がりが発生しない(Cc)のときは「(P)が続く限り繰り上がりを阻止(cancel)する波が伝搬する」と捉えることで2本目の信号強度配線を導入したのである(私はそれまで1本だったので驚いた)。マイクラで回路を作成する際、(P)の伝搬は上位への一方通行であることに注意して、下の[図6]のように半blockを使って整流して下位に信号が流れないようにする(開発者の発想が天才すぎて泣く)

 

 

[図4]のように階段状の図を描き、(G)側の赤色のグラフと、(Cc)側の水色のグラフを規則に従って書いている。赤色のが水色より上側のときC^i=1で、逆ならばC^i=0である。グラフの縦軸は信号強度を指し示しており、強度の大小関係をコンパレータで決定してC^iを出力する。グラフの規則は、(G)があったときは赤色を上限値まで上げて、(Cc)があったときは水色を上限まで上げる。(P)であるとき(黄色矢印)は信号強度配線には何もせず、赤色と水色両方を1段階減衰させるが、大小関係は保存されている。

  以上がC^i決定の流れである。半加算器をベースに、(P)、(G)、(Cc)のどれであるかを決定する回路を見ていく。E_k=R(R(9-B_k)-A_k)F_k=R(A_k-R(9-B_k))としたときに、

「k桁目が(P)」\Leftrightarrow E_k=F_k=0

「k桁目が(G)」\Leftrightarrow F_k≧1

「k桁目が(Cc) 」\Leftrightarrow E_k≧1

となることを[図4]を見て確かめてみてほしい。

1以上か0であるかはリピーターやトーチで簡単に判定できるし、(P)はNOR回路である。CCAの機構をE,Fを用いて回路にするとこうなる。

[図6]

f:id:AkaGhef:20200607154501j:image

 

f:id:AkaGhef:20200607154506j:image

 

信号強度全加算器

最後のステップである加算結果を出力する回路について見てく。

Eは(Cc)のときの加算結果を計算する回路に使える、つまり繰り上がり入力をC^i=0,1としたとき

(Cc)\Rightarrow O=R(R(10-R(1-C^i))-E)

である。Fは(G)のときの加算結果を計算する回路に使える、つまり

(G)\Rightarrow O=R(F-R(1-C^i))

(P)のときはめんどくさいことが起きる。k桁目が(P)のとき半加算器の出力は9で、C_k^i=0ならばO_k=9だがC_k^i=1ならばO_k=0となるので、信号強度にC^iを足し引きしてOを計算するわけには行かない。だから別途配線を用意する必要がある。

[図8]

f:id:AkaGhef:20200608083130j:image

実際のマイクラの回路は上のようになる。(めんどくさいので)連続加算器の画像をそのまま使っているが、加算器も連続加算器も仕組みはほぼ同じで、加算結果OがそのままAに繋がれて代入されているという違いだけである。[HA]は半加算器、[C]はCCAの繰り上がりの計算機構、Bが入力、[R]はリセットの配線、[I]はB9-Bにする回路で、桁毎に何層も積み重なっている計算機の1桁分(2マス)だけ切り出してきた断面の画像である。さっきの[HA]でE,Fを計算し、(G)の繰り上がり計算部分は[図4]の階段のグラフの赤色と同じで、信号強度配線に繋がっている。(Cc)の繰り上がり計算のための信号強度配線は同じように水色である。(G)のときの加算結果はピンク色で、(Cc)のときは黄色、(P)のときは橙色の矢印で書いている。黄色破線は、E,Fどちらの値を半加算器の出力として使うかを決定するものである。

[図8]の橙色破線は、(P)の時のOを出力する部分のE,Fからの入力で、E=F=C^i=0のときはO=9を出力するようになっている。[C]の部分からC^iが出力され、(P)以外のときは水色の丸の部分で半加算器の値とC^iからOを計算している。[R]はリセットの配線で、Aの値を0にするが、ここの部分の回路だけ非同期なのでパイプライン処理出来ない。 

パイプライン演算

パイプライン演算は計算機においてかなり重要な概念であるのでここで説明しておきたい。ループ式の計算回路で、信号を回路内で何周もさせて計算する際、信号の辿るルートによって遅延が異なる場合は周回する毎に遅延が拡大していき周回するうちに1周回遅れて前の信号と干渉してしまう。このためループ計算の回路において、「信号が回路を1周回して戻るときの遅延量は経路によらず等しい」という強い条件「同期」が必要となる。ここではループ計算において同期を定義したが、一般に信号の入力から出力までの遅延量が経路によらず等しければ同期式回路である。

同期式のループ回路において時刻毎に処理が独立していて、1rstick毎に違う信号を入力したとき何個もの計算をほぼ同時にやることが可能で、これをパイプライン処理と言う。信号が波形を崩さずに配線を伝搬していく様子が波に見えることから特にウェーブパイプラインと呼ばれる。マイクラの場合で注意すべきだが、遅延2のリピーターに1rstickパルスが入力された時に2rstickのパルスが出力されて前の時刻の信号と干渉してしまうため1tick毎に違う処理を行う際は2rstick遅延のリピーターは使用できないという制約が追加される。ウェーブ型以外もあって、遅延量が一定でない場合一旦バッファという領域に信号を保存し回路全体の時刻調整をする"クロック"の制御のもとで同時に情報を次の処理領域に渡したりする。

補数による減算

減算は補数の概念を使えば驚くほど楽に加算器上に実現できることが知られている。今回は信号強度加算器が主題なので、10進数N桁の整数x,y \lt 10^{N}の補数の計算から減算x-yを行う方法を考える。まず答えが正になる場合について見ることにし、yの10^nの位をy_nと書くとy=\displaystyle \sum_{n=0}^{N-1}10^{n}y_nと表せる。\overline{y}_k=9-y_kとし、さらに\bar{y}=\displaystyle \sum_{n=0}^{N-1}10^n \overline{y}_nと定義する。yの補数とは\overline{y}+1であり簡単な計算から

 \displaystyle \overline{y}=10^N-y-1=(\underbrace{99\cdots 9}_{9がN個}-y)と分かる。

x-y=x+(\underbrace{99\cdots 9}_{9がN個}-y)+1-10^Nとなり、下位N桁には影響が及ばないので10^Nを無視すると、x+\overline{y}+1という「足し算」を計算すればいいことになる。ここでyから\overline{y}を求めるには各桁で独立にy_kから\overline{y}_kを求めればいいので、すぐに求められる。

また、+1の部分は加算器の最下位桁の繰り上がり入力C_1^iが空いているので、ここから入力すれば良い(インクリメントをここで使うのか!と、最初知ったときは仰天した)

この加算を行うと、無視した10^Nの分があるので答えが正のとき必ず最上位桁の繰り上がりが起こる(C_{N+1}^i=1)

e.g.) 512-128\rightarrow 512+871+1=1384\rightarrow 512-128=384

 

逆に減算結果が負ならば最上位桁の繰り上がりが起こらずC_{N+1}^i=0となるので、負になったかどうか判別できる。しかし減算結果の数字を出力するには絶対値を出力しなければならないので、加算結果の補数を見る必要がある(丁寧な説明が困難なので具体的な計算手順をみて掴んでください)

e.g.)128-512→ 128+487+1=\underline{0}616\rightarrow \overline{616}+1=383+1=384

\rightarrow 128-512=-384

一応数式を載せると、|x-y|=-(x-y)=10^N-(x+\overline{y}+1-10^N)-10^N=\overline{x+\overline{y}+1}+1

しかし減算器単体として運用する場合は、加算結果の補数を求める際に+1(インクリメント)をしなければならず面倒なので連続加算器であることを利用した2つの解決方法を述べる。\overline{y}yの補数反転と呼ぶことにする(元々補数は2進数の概念で、補数を求める時は各桁でNOTゲートを通す、つまりbit反転すればよい)

ひとまず+1なしで加算を計算しx+\overline{y}の加算でC^i_{N+1}=1ならば+1をして出力、C^i_{N+1}=0ならば

補数反転を計算して出力する(\overline{x+\overline{y}})

114-514\rightarrow 114+485=\underline{0}599→114-514=-\overline{599}=-400

514-114\rightarrow 514+885=\underline{1}399→514-114=399+1=400

連続加算器なのでオーバーフローしなければ連続減算も可能で、引く時は減数の補数を加えると良いが、第2の方法としては総和結果が負になる場合、1を引く、すなわち補数である\underbrace{99\cdots 9}_{9がN個}を加えてから、出力を補数反転させてやると絶対値が出る

e.g.)137-343-729→(137+656+1)-729→0794+270+1=1065

065+999=1064→(\rm{answer})=-\overline{064}=-935

 

私の計算機は当初から乗除算を前提として設計された為、加減算を同じマシンでできるようにしている。x+yx-yは補数にしてから足すかの違いなので、1つの入力で切り替えられるようにしている。それが[図8]における[I]の役割であり、(J)の部分で加算か減算かを制御している。(J)がonなら減算するモードになる。

 

最後に連続加算器全体の構造と作り方を見ていく。[図8]では少し説明を端折ったが[図12]のように加算器は下位桁から上位桁に向かって下側から左右交互ジグザグに桁が配置されていて(偶数桁目は右側という感じで)、CCAの機構を最大限活かして限界である10進数13桁(14もギリギリ)の構成になっている。ただこの加算器を2個上下に重ねて下側の加算器の最上位の繰り上がりのところを上側の加算器の最下位桁の繰り上がり入力に繋げれば2倍の桁数の加算器が作れる。また、交互に重ねずに2highずつ重ねていくと高さは半分で桁数が半分の7桁、横の長さが半分の連続加算器も作れる(ちと時間が無くて作れないので今は画像が無い )

[K]は入力Bをコア内に入力するかどうか決める配線で、[M]はシフトレジスタ(メモリ)、[S]はシフトする部分

 

出力する機構が少し面倒で、信号が内部を流れているのでF側の配線から信号取り出す必要がある。

B99\cdots 9を代入する、またはB=0の状態で(J)をonにすると補数反転されて99\cdots 9が代入される。そうすると[図8]のようにピンク色の配線にAの強度の信号が流れるので、[output]と書いた部分から信号を取り出す。

[図10]

f:id:AkaGhef:20200608083140j:image

[図12]

f:id:AkaGhef:20200606222322j:image

各層は2highの厚さで、左右交互に桁が積み重なっているので、線対称な直線で切った[図14]を左右交互に積み重ねるようにして、cloneコマンドを実行すると13桁の計算機が出来上がる。1桁分に必要な回路の部分は[図8]の仕組みを理解していれば分かるだろう。

赤色の部分は乗除機を作る上で上から下に信号を送る必要があるのでそこの部分だけは螺旋状にワイヤーを設置する([図15]参照)

[図14]

 

f:id:AkaGhef:20200609233430j:image

 

[図15]

f:id:AkaGhef:20200609233444p:image

 

 

なお、最下層は減算のインクリメントを配置する必要があるので最下層のC_1^iの回路は以下のようにつくる。(修正箇所は青で囲ったところのみ)

[図16]

f:id:AkaGhef:20200607154738p:image

 

上で解説した方法は2〜15進数の信号強度にも一般化できるが、16進数は少し仕組みが違う。

Minecraft計算機解説part1はここまでです!

この計算機は構想から実現まで2ヶ月かかってて、半加算器とかCCAの繰り上がり機構を何度も組み替えて百通り以上の組み合わせを試して見た結果、うまく乗除算に使える10進数最速(0.6tick周期)連続加算器がやっとできました。橙色の配線を見れば分かりますが強度上限15ギリギリで配線が繋がっていて、この理論上最速の計算機が存在すること自体が奇跡的な気がします(他の数十の組み合わせは多分うまくいかないので)

かなり苦しかったですが実現できた時の感動は忘れられません(´;ω;`)

ちなみに、私はモチベが尽きたので作ってませんでしたが加算だけなら、やくみさんが16進数0.6tick周期のを実現しています。

part2は乗除算、part3はCORDICとsin計算機の解説にしようと思います。

読んで頂きありがとうございました〜ヽ('∀'*)ノ

Kac-Moody代数の疑問

こんにちは

 

自分でもまだ整理が済んでない部分がありますが、自分の思いついた概念(多分既出)がどう出てくるのか知りたいので書きました

Kac-Moody代数:

f:id:AkaGhef:20200415131635p:plain



Weyl代数:有限N=|Λ|、ベクトル変数x=(x_λ)_{λ∈Λ}、\partial_λ =\frac{\partial}{\partial x_λ},有限次多項式p_v ∈ℂ[x|]

有限部分集合A⊂ℤ_{≧0}^N,\nabla=(\partial_λ)
(多重指数)ベクトルy=(y_λ),v=(v_λ)∈Aに対してy^v=\prod_{λ∈Λ}y_{λ}^{v_λ}
Weyl代数を以下のように表されるもの全体の集合とする:
 \displaystyle \sum_{v∈A}p_v (x)\nabla^{v}

行列単位E_{ij},交換子括弧[X,Y]=XY-YX,kronecker 's\ δ

[E_{ab},E_{cd}]=δ_{bc}E_{ad}-δ_{ad}E_{cb}が成立するが
[\partial_i ,x_j]=δ_{ij}より、E_{ij}\cong x_i ∂_jと同一視できる。すなわち
[x_a ∂_b,x_c ∂_d] =δ_{bc}x_a ∂_d-δ_{ad}x_c ∂_b
と書ける。Kac-Moody代数をの生成元がある行列と対応するが、この同一視によってWeyl代数の元にKac-Moody代数を埋め込め、どの項も∂の次数は1である。例えばA型では次のようなリー同型が取れる:
\begin{align}e_k =x_k∂_{k+1},f_k=x_{k+1}∂_k\end{align}\begin{align}h_k=x_k∂_k- x_{k+1}∂_{k+1}\end{align}
この埋め込みに関して全く情報がないので、
あれば知りたいのです。
そして本題。行列による表示だと分かりませんが、2階微分作用素への埋め込みも存在する。例えばB型のカルタン行列に対し次の同型が取れる:

\begin{align}e_k=\partial_k x_{k+1},f_k =x_k ∂_{k+1},h_k=-x_k ∂_k +x_{k+1}\partial_{k+1}(1≦k\lt N)\end{align}
\begin{align}e_N=\frac{1}{2}∂_{N}^{2},f_N=\frac{1}{2}x_N^2,h_N=x_N ∂_N+\frac{1}{2}\end{align}

(証明は忙しいので省きます...)
D型も2階の微分を使って表せます。1階の微分だと接空間として考えられますが、2階微分だと一般論はあるんでしょうか??
例外型EFGでも1階の微分では書けますが、2階微分はどうなのか1番知りたいです!

メビウス変換の微分作用素表示

こんにちは~(*`・ω・´*)ノ 無自覚にも、もう高3になってしまいました。数式blog始めたのは中3からで、自分で発見した数学を載せ続けられているのは嬉しいです。

関数へのPSL_{2}作用(メビウス変換)について話します。

[定理]

fを無限回微分可能な関数、\partial=\frac{d}{dx}、ad-bc=1、d\neq 0とする。このとき \begin{align}e^{-cd^{-1}(x^2 \partial+λx)}d^{-2x\partial +λ}e^{bd^{-1} \partial}・f(x)=(cx+d)^{λ} f\left(\dfrac{ax+b}{cx+d}\right)\end{align}

 

証明

[補題1]並進変換 e^{a \frac{d}{dx}}・f(x)=f(x+a)

証明:http://akaghef.hateblo.jp/entry/2017/11/10/192508

オワリ

 

[補題2]\begin{align}\exp (f'(x)+\partial) =\exp(f(x+1)-f(x))\exp \partial\end{align} 証明:線形代数固有値の話を思い出すと良い。

任意のk∈ℂについて関数\exp(kx-f(x))上記の作用素固有値e^{k}の固有関数であり、線形独立なので関数全体を張る基底となる。実際

\begin{align}(f'(x)+\partial)・exp(kx-f(x))\\
&=(f'(x)+(k-f'(x))\exp (kx-f(x))\\
&=k\exp (kx-f(x))\end{align}

であるからf'(x)+\partial固有値kの関数なので(左辺)の固有値e^{k}

一方[補題1]より

\begin{align}(右辺)・\exp (kx-f(x))\\
&=\exp (f(x+1)-f(x)) \exp(kx+k-f(x+1))\\
&=e^{k}\exp (kx-f(x))\end{align}

なので固有値e^{k}です。

固有値と固有関数の一致が取れたので作用素は等しいです。 オワリ

 

補題2は割と有能ですが全く見かけないのなんででしょうね(BCH公式の系でもあります)

微分作用素は合成関数の公式で変数変換をすることができます:

\dfrac{d}{dx^{-1}}=-x^{2}\dfrac{d}{dx}

\dfrac{d}{d\log x}=x\dfrac{d}{dx}

です。 ここまで来ればスムーズに定理を証明できます。

z=\dfrac{d}{cx}として

\begin{align}&\exp -cd^{-1}(x^2 \partial+λx)\exp(-\log (d) (2x\partial -λ))\exp(bd^{-1} \partial)・f(x)\\
&=d^λ\exp -cd^{-1}(x^2 \partial+λx)\exp(-2\log (d) \dfrac{\partial}{\partial \log x} )・f(\exp (\log x)+bd^{-1})(補 題1)\\
&=d^λ \exp -cd^{-1}(x^2 \partial+λx)・f(\exp (\log x -2\log d)+bd^{-1})(補 題1)\\
&=d^{λ}\exp \left(\dfrac{\partial}{\partial z}+λz^{-1}\right)・f(d^{-2}x+bd^{-1} )\\
&=d^{λ}\exp (λ\log (z+1)-λ\log z)\exp\left(cd^{-1}\frac{\partial}{\partial x^{-1}}\right) ・f\left(\dfrac{1}{d^2}\dfrac{1}{x^{-1}}+\frac{b}{d}\right)( 補 題2)\\
&=d^{λ}\left(\dfrac{z+1}{z}\right)^{λ}f\left(\dfrac{1}{d}\left(\dfrac{x(1+bc)+bd}{cx+d}\right) \right)\\
&=(cx+d)^{λ} f\left(\dfrac{ax+b}{cx+d}\right)\end{align}

最後はad-bc=1を用いました。

オワリ

メビウス変換はPSL₂行列と同型な構造を持ちます:

2次行列M=(a,b;c,d)について作用素Aを

\begin{align}A_λ(M)・f(x)=(cx+d)^{λ} f\left(\dfrac{ax+b}{cx+d}\right)\end{align}

と定義すると、行列がM_1M_2 =M_3のとき作用素の合成として \begin{align}A_λ(M_1)A_λ(M_2)=A_λ(M_3)\end{align}

と成立します(暇つぶしに証明できると思います)

またA_λ(1,0;0,1)=1も成立。 定理は次と同様の形をしている事が見て取れると思います。 https://wikimedia.org/api/rest_v1/media/math/render/svg/4d403484a19b08a14eb693cb9f93606ca5fa7239

 

これはリー群の話を学ぶと理解出来て、行列のUDL分解(上下三角と対角の分解)を表しています。そしてなぜ行列が作用素と対応するかと言うと

E=-x^2∂+λx,F=∂,H=2x∂-λ

リー環sl_2構造を成し、交換子積[A,B]=AB-BAについて

関係式[E,F] =H,[H,E]=2E,[F,H] =2Fを満たしますが、

E=(0,1;0,0),F=(0,0;1,0),H=(-1,0;0,1)

と定義しても同様の関係式を満たすからなのです。

このsl2の微分作用素表現はλ=0のとき射影平面の正則ベクトル場を貼り、

メビウス変換の生成子になっています。

今回はexpでリー環からリー群に具体的に対応させた公式になっています。

局所的な感じで、こんな公式もあります。

 

またPSL_2 ℤ固有関数についてみると保型形式が出現します。

akaghef.hateblo.jp

今回は1変数で証明しましたが、行列変数の公式に書き換えると

Siegel保型形式も今回と同様な形で書き表せます。

 

どうだったでしょうか〜? 公式は自分で発見しましたが、

微分形式の意味づけが出来るとしってもっと学びたいなと思いました。結果的に理解につながったので良いですが、数学はあまり具体的な計算に興味ないんですかね?

最初の方はわかりやすくしたつもりなので、分かって頂けたら幸いです(*’ω’*)

では(。・ω・)ノ゙