!進数表示
に対しを以下のように定める(上は添字)
この時はに関して周期的
(つまり )
であるか?
■
,のとき
方程式をと( º дº)<キエェェェエエェェェ
計算機のアルゴリズム上のコンパクト化
lobiでの解説。
minecraftで計算機を制作する事を目的としています。
アルゴリズムの観点からどういった高速化・コンパクト化(究極を目指すにあたり、同義ともいえる)を施せるかを見ていこうと思いく、アセンブリ言語がわかりやすい為使用する。
ざっくり解説挟みますが、分からない場合は個チャにて聞いてください(ここに貼ると文献の著作権に抵触する恐れがあるので)
アセンブリは、デカい命令が書いてある主記憶装置、演算を行う部分、演算結果を記憶する部分(以下Acc)、の3つに分かれる。命令はadd・subで番地指定した所の値をAccに加えたり引いたり
基本番地が低い所から命令を実行していく。
loadは指定した番地から値を引き出し、Accに上書き。
atoreは指定した番地にAccの値を上書き。
jumpは指定した番地から処理を始める。
jump minusはAccの値が負ならjumpと同じことをする。
本当は無いけど、面倒なのでmultipleとdivideという命令を追加し、それぞれ掛ける、割る の命令としました。
実際に乗除算のアルゴリズムを見ていきます。
乗除算のアルゴリズムなのになんで乗除算の命令が入っとんねん!ってなるかも知れませんが、
10進数で100を掛ける事は左に2回数字をずらし、0を付け加える操作と等価なのでまぁ書いてます。
あと除算はマシンの性能を規定して、一定の桁以下は切り捨てするとします。
図を見よ。
部分剰余や、部分和は筆算の途中に出てくる数字だなと思えばいいです(ニコッ)
乗算の都合上、除算は非回復型になるんですが、本筋と関係ないのでポイっ。
BとIを入れ替えたような構図になっています。これがパイプライン化(あとで話す)と組み合わさり、演算クロック(演算を行うリズム)をずらすだけで乗除算を切り替える事ができます。
実装の観点の高速化はまだワイがゴミクズでまだ出来てないので、完成したらちゃんと解説出そうと思います。数式バンバン出ます(笑)
パイプラインってこれのことだな(言い忘れた)
「Minecraft」の攻略「Minecraft 装置開発所+雑談」での「 赤げふ」の投稿「ゲニキ理論(仮)の講義 ~パ...」 | Lobi
あとstopはstopするって事です(おい
一旦解説打ち切りです
衒学的ですいませんでしたm(*_ _)m