高速计算器第一代-----gcd------【8bit最大公因数计算器！】
步入正题前先祝广大妹纸们3月8号节日快乐（23333~）愉悦的23333
好的步入正题。
不对步入正题前先自我介绍，我叫comne！就是上次那个发四则混合运算器的渣比。
好的步入正题。
不对步入正题前先跟大家说下本次作品的作者有两个：comne和xilly联合制造。make in ……make in china!（路人砸了个砖头过来：你废话啥呢！还讲不讲了）
好吧真的步入正题了。
好的，此次带给大家的是：高速计算器第一代-----gcd------【8bit最大公因数计算器！】，为什么说是第一代？因为接下来还将会有各种计算器，如开方，最小公倍数等。并且我们追求高速，因此全部运用并行结构！给大家带来最快的计算速度！
先欣赏下外貌
西西运用它那土豪金电脑进行加工做的截图，简直酷炫霸气吊炸天！
在这里说下布线，布线都是经过反复推敲的，我们要考虑到外貌，速度，结构。如下图，我们采用阵列式除法器，并行传输，追求最高速！
这是7-SEG背部图
我和西西都有同一个追求：速度，大家也看到了，无论是我和西西的任何作品多数都是并行的。还有这个除法器我们也是采用了主席的伪超前进位加法器。
接下来我们看看这个计算器的效果。
首先我们进行计算9和6的最大公因数，大家都知道，那便是3. 3*3=9,3*2=6
好的，那我们看看结果正确否？
图片表示的结果是3，正确的！
再来算算10和10的最大公因数，a=b，所以最大公因数是a或者b。
如图所示，10和10的最大公因数是10，是正确的！
再来算算比较大的数吧——96和56
仔细算算，8*12=96,8*7=56,最大公因数是8
图中表示正确！
我们再来演示下更大的速 143和231 11*13=143,11*21=231 最大公因数是11
图中显示11，正确！
好了，那么我来给大家讲解下原理，即算法——辗转相除法
什么是辗转相除法？辗转相除法，又称又称欧几里德算法（Euclidean algorithm），是求两个正整数之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。
辗转相除法的实现，是基于下面的性质：
1：(a,b)=(a,ka+b)，其中a、b、k都为自然数
就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数组，其公约数不变，比如(4,6)=(4+6,6)=(4,6+2×4)=2。这里有一个比较简单的证明方法来说明这个性质：如果p是a和ka+b的公约数，p整除a，也能整除ka+b。那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的。
还有另外一个性质也是很必要：
2：(0,a)=a
由这两个性质得到的，就是更相减损术：
(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
基本上思路就是大数减去小数，一直减到能算出来为止。不过在平时的计算过程中，往往不必计算到最后一步，比如在上面的过程中，到了(8,6)，就已经能够看出其结果。
我们可以看到，在上面的过程中，由(78,14)到(8,14)完全可以一步到位，因为(78,14)=(14×5+8,14)=(8,14)，由此就诞生出我们的辗转相除法。
用辗转相除法求(a,b).设r0=b，r1=a，反复运用除法算式，得到一系列整数qi，ri和下面的方程：
r0=q1r1+r2，r2＜r1(r2,r1)
r1=q2r2+r3，r3＜r2(r3,r2)
r2=q3r3+r4，r4＜r3(r4,r3)
………………
rn-3=qn-2rn-2+rn-1，rn-1＜rn-2 (rn-1,rn-2)
rn-2=qn-1rn-1+rn，rn-2＜rn-1 (rn-1,rn)
rn-1=qnrn。 (rn,0)
相当于每一步都运用原理①把数字进行缩小，上面右边就是每一步对应的缩小结果，可以看出，最后的余数rn就是a和b的公约数。我们以一个题为例说明基本过程。
例题：求(326,78)
326=4×78+14(78,14)
78=5×14+8 (14,8)
14=1×8+6 (6,8)
8=1×6+2 (6,2)
6=3×2 (0,2)
所以(326,78)=2。这和我们用更相减损术算出来的结果是一样的。
上面是我在百度百科所复制黏贴的，大家嫌字多的可以不看第二个性质，看下面：
首先有三个数，a，b，c 进行声明 a=4 b=8
第一步：输入a和b 即 输入4和8
第二步：比较a和b的大小，如果a＞b，则原值输出。如果a＜b，则a和b的值交换，因a＜b（4＜8）所以a和b进行交换，a=8，b=4
第三步：两数进行除法运算，c=a÷b的余数，若c=0，则输出b，即b就是a和b的最大公因数。若c≠0，则a=b，b=c，并重新进行一次除法运算，若c还是不等于0，则依然a=b，b=c，也就是循环。学过编程的同志们都只知道这是当型循环。直到最终c=0，就输出b。我们这边a=8，b=4（第二步进行了交换），所以c=a÷b的余数也就是0，就输出了b=4.
所以a和b的最大公因数就是4
如下是流程图：
还有个结束没照出来……
接下来，参数如下：
时钟周期：120t（根据数字的不同，可能需要几个周期不等）
输入数字范围：1~255（8bit）
存档：http://pan.baidu.com/s/1pJunqYZ
版本1.8
还有个要求，不能输入0
两个数字都不能输入0
好的，第一代计算器——gcd——8bit最大公约数计算器暂时这样
好的步入正题。
不对步入正题前先自我介绍，我叫comne！就是上次那个发四则混合运算器的渣比。
好的步入正题。
不对步入正题前先跟大家说下本次作品的作者有两个：comne和xilly联合制造。make in ……make in china!（路人砸了个砖头过来：你废话啥呢！还讲不讲了）
好吧真的步入正题了。
好的，此次带给大家的是：高速计算器第一代-----gcd------【8bit最大公因数计算器！】，为什么说是第一代？因为接下来还将会有各种计算器，如开方，最小公倍数等。并且我们追求高速，因此全部运用并行结构！给大家带来最快的计算速度！
先欣赏下外貌
西西运用它那土豪金电脑进行加工做的截图，简直酷炫霸气吊炸天！在这里说下布线，布线都是经过反复推敲的，我们要考虑到外貌，速度，结构。如下图，我们采用阵列式除法器，并行传输，追求最高速！
这是7-SEG背部图
我和西西都有同一个追求：速度，大家也看到了，无论是我和西西的任何作品多数都是并行的。还有这个除法器我们也是采用了主席的伪超前进位加法器。
接下来我们看看这个计算器的效果。
首先我们进行计算9和6的最大公因数，大家都知道，那便是3. 3*3=9,3*2=6
好的，那我们看看结果正确否？
图片表示的结果是3，正确的！
再来算算10和10的最大公因数，a=b，所以最大公因数是a或者b。
如图所示，10和10的最大公因数是10，是正确的！
再来算算比较大的数吧——96和56
仔细算算，8*12=96,8*7=56,最大公因数是8
图中表示正确！
我们再来演示下更大的速 143和231 11*13=143,11*21=231 最大公因数是11
图中显示11，正确！
好了，那么我来给大家讲解下原理，即算法——辗转相除法
什么是辗转相除法？辗转相除法，又称又称欧几里德算法（Euclidean algorithm），是求两个正整数之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。
辗转相除法的实现，是基于下面的性质：
1：(a,b)=(a,ka+b)，其中a、b、k都为自然数
就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数组，其公约数不变，比如(4,6)=(4+6,6)=(4,6+2×4)=2。这里有一个比较简单的证明方法来说明这个性质：如果p是a和ka+b的公约数，p整除a，也能整除ka+b。那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的。
还有另外一个性质也是很必要：
2：(0,a)=a
由这两个性质得到的，就是更相减损术：
(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
基本上思路就是大数减去小数，一直减到能算出来为止。不过在平时的计算过程中，往往不必计算到最后一步，比如在上面的过程中，到了(8,6)，就已经能够看出其结果。
我们可以看到，在上面的过程中，由(78,14)到(8,14)完全可以一步到位，因为(78,14)=(14×5+8,14)=(8,14)，由此就诞生出我们的辗转相除法。
用辗转相除法求(a,b).设r0=b，r1=a，反复运用除法算式，得到一系列整数qi，ri和下面的方程：
r0=q1r1+r2，r2＜r1(r2,r1)
r1=q2r2+r3，r3＜r2(r3,r2)
r2=q3r3+r4，r4＜r3(r4,r3)
………………
rn-3=qn-2rn-2+rn-1，rn-1＜rn-2 (rn-1,rn-2)
rn-2=qn-1rn-1+rn，rn-2＜rn-1 (rn-1,rn)
rn-1=qnrn。 (rn,0)
相当于每一步都运用原理①把数字进行缩小，上面右边就是每一步对应的缩小结果，可以看出，最后的余数rn就是a和b的公约数。我们以一个题为例说明基本过程。
例题：求(326,78)
326=4×78+14(78,14)
78=5×14+8 (14,8)
14=1×8+6 (6,8)
8=1×6+2 (6,2)
6=3×2 (0,2)
所以(326,78)=2。这和我们用更相减损术算出来的结果是一样的。
上面是我在百度百科所复制黏贴的，大家嫌字多的可以不看第二个性质，看下面：
首先有三个数，a，b，c 进行声明 a=4 b=8
第一步：输入a和b 即 输入4和8
第二步：比较a和b的大小，如果a＞b，则原值输出。如果a＜b，则a和b的值交换，因a＜b（4＜8）所以a和b进行交换，a=8，b=4
第三步：两数进行除法运算，c=a÷b的余数，若c=0，则输出b，即b就是a和b的最大公因数。若c≠0，则a=b，b=c，并重新进行一次除法运算，若c还是不等于0，则依然a=b，b=c，也就是循环。学过编程的同志们都只知道这是当型循环。直到最终c=0，就输出b。我们这边a=8，b=4（第二步进行了交换），所以c=a÷b的余数也就是0，就输出了b=4.
所以a和b的最大公因数就是4
如下是流程图：
还有个结束没照出来……
接下来，参数如下：
时钟周期：120t（根据数字的不同，可能需要几个周期不等）
输入数字范围：1~255（8bit）
存档：http://pan.baidu.com/s/1pJunqYZ
版本1.8
还有个要求，不能输入0
两个数字都不能输入0
好的，第一代计算器——gcd——8bit最大公约数计算器暂时这样
comne的作品集：
乘法器：http://tieba.baidu.com/p/3203867738?pid=54856402593&cid=0#54856402593
除法器：http://tieba.baidu.com/p/3203882166?pid=54856762905&cid=0#54856762905
RAM：http://tieba.baidu.com/p/3207288753?pid=54957410447&cid=0#54957410447（此RAM纯属逗比。因为太巨大了QAQ）
全加器：http://tieba.baidu.com/p/2700280342?pid=41555925561&cid=0#41555925561
7-SEG：http://tieba.baidu.com/p/2697968060?pid=41501266041&cid=0#41501266041
以上2个均为教程
幻灯片制作器[url]http://：[/url]http://tieba.baidu.com/p/3572267032?pid=64029848084&cid=0#64029848084
四则混合计算器：http://tieba.baidu.com/p/3585999125?pid=64375587691&cid=0#64375587691
加法器版小数bin-bcd：http://tieba.baidu.com/p/3603274465?pid=64843280815&cid=0#64843280815
乘法器：http://tieba.baidu.com/p/3203867738?pid=54856402593&cid=0#54856402593
除法器：http://tieba.baidu.com/p/3203882166?pid=54856762905&cid=0#54856762905
RAM：http://tieba.baidu.com/p/3207288753?pid=54957410447&cid=0#54957410447（此RAM纯属逗比。因为太巨大了QAQ）
全加器：http://tieba.baidu.com/p/2700280342?pid=41555925561&cid=0#41555925561
7-SEG：http://tieba.baidu.com/p/2697968060?pid=41501266041&cid=0#41501266041
以上2个均为教程
幻灯片制作器[url]http://：[/url]http://tieba.baidu.com/p/3572267032?pid=64029848084&cid=0#64029848084
四则混合计算器：http://tieba.baidu.com/p/3585999125?pid=64375587691&cid=0#64375587691
加法器版小数bin-bcd：http://tieba.baidu.com/p/3603274465?pid=64843280815&cid=0#64843280815
因为洗澡的原因，没拿到2L艾特各位，那么只能13L艾特了QWQ：@阿散井发了@TF_813@Mark_forget114@2进制码@红石锁存器@说大话的小孩籽