请输入您要查询的字词:

 

单词 EuclidsCoefficients
释义

Euclid’s coefficients


The following program is based on Euclid’s algorithm and it determines Euclid’s coefficients t and d of the integers x and y.

INPUT x, y  (positive integers)
m:=x,  n:=y
b:=0,  d:=1
p:=1,  t:=0
WHILE   m0   DO
BEGIN
q:=n DIV m  (integer division)
h:=m,  m:=n-qm,  n:=h
h:=b,  b:=d-qb,  d:=h
h:=p,  p:=t-qp,  t:=h
END
WRITE   — The gcd of the numbers x and y is   n=tx+dy.

Remark.  The values of t and d produced by the program have the absolute valuesMathworldPlanetmathPlanetmathPlanetmath as close each other as possible (Proof = ?).  They differ very often only by 1 when x and y are two successive prime numbersMathworldPlanetmath, e.g.

1= 30523-29541.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 4:01:56