12/3 /2018 Euclidean algorith m - Wikipedia
ht t ps://en .wikipedia.org/wiki /Eu cl i dean _algorith m 6/3 0
St ep k Equation Quotient and remainder
0
1071 = q
0
462 + r
0
q
0
= 2 and r
0
= 147
1
462 = q
1
147 + r
1
q
1
= 3 and r
1
= 21
2
147 = q
2
21 + r
2
q
2
= 7 and r
2
= 0; algorithm ends
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the
greatest common divisor.
[17]
Assume that we wish to cover an a-by-b rectangle with square
tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle
using b-by-b square tiles; however, this leaves an r
0
-by-b residual rectangle untiled, where
r
0
< b. We then attempt to tile the residual rectangle with r
0
-by-r
0
square tiles. This leaves a
second residual rectangle r
1
-by-r
0
, which we attempt to tile using r
1
-by-r
1
square tiles, and so
on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the
previous residual rectangle exactly. The length of the sides of the smallest square tile is the
GCD of the dimensions of the original rectangle. For example, the smallest square tile in the
adjacent figure is 21-by-21 (shown in red), and 21 is the GCD of 1071 and 462, the
dimensions of the original rectangle (shown in green).
At every step k, the Euclidean algorithm computes a quotient q
k
and remainder r
k
from two
numbers r
k−1
and r
k−2
r
k−2
= q
k
r
k−1
+ r
k
where the magnitude of r
k
is strictly less than that of r
k−1
. The theorem which underlies the
definition of the Euclidean division ensures that such a quotient and remainder always exist
and are unique.
[18]
In Euclid's original version of the algorithm, the quotient and remainder are found by repeated
subtraction; that is, r
k−1
is subtracted from r
k−2
repeatedly until the remainder r
k
is smaller
than r
k−1
. After that r
k
and r
k−1
are exchanged and the process is iterated. Euclidean division
reduces all the steps between two exchanges into a single step, which is thus more efficient.
Moreover, the quotients are not needed, thus one may replace Euclidean division by the
modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply
r
k
= r
k−2
mod r
k−1
.
Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed
as
[19]
function gcd(a, b)
while b ≠ 0
t:= b;
Subtraction-based
animation of the Euclidean
algorithm. T he initial
rectangle has dimensions
a = 1071 and b = 4 62.
Squares of size 4 62×4 62
are placed within it leaving
a 4 62×147 rectangle. T his
rectangle is tiled with
14 7×14 7 squares until a
21×14 7 rectangle is left,
which in turn is tiled with
21×21 squares, leaving no
uncovered area. T he
smallest square size, 21,
is the GCD of 1071 and
4 62.
Visualization
Euclidean division
Implementations
剩余29页未读，继续阅读
osakaanarg
- 粉丝: 30
- 资源: 473
我的内容管理
展开
最新资源
- 前端面试必问：真实项目经验大揭秘
- 永磁同步电机二阶自抗扰神经网络控制技术与实践
- 基于HAL库的LoRa通讯与SHT30温湿度测量项目
- avaWeb-mast推荐系统开发实战指南
- 慧鱼SolidWorks零件模型库：设计与创新的强大工具
- MATLAB实现稀疏傅里叶变换(SFFT)代码及测试
- ChatGPT联网模式亮相，体验智能压缩技术.zip
- 掌握进程保护的HOOK API技术
- 基于.Net的日用品网站开发：设计、实现与分析
- MyBatis-Spring 1.3.2版本下载指南
- 开源全能媒体播放器：小戴媒体播放器2 5.1-3
- 华为eNSP参考文档：DHCP与VRP操作指南
- SpringMyBatis实现疫苗接种预约系统
- VHDL实现倒车雷达系统源码免费提供
- 掌握软件测评师考试要点：历年真题解析
- 轻松下载微信视频号内容的新工具介绍
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
