我决定实现一个程序,可以在TI-Basic中找到任意两个数字(包括非整数)的GCD.我在Java中使用它很好,所以我知道它有效.它在TI-Basic中运行得很好,但与内置gcd(函数相比,它非常缓慢; 该gcd(函数似乎以毫秒为单位获得结果,其中我的可能需要几秒钟.为什么TI-Basic比预定义的计算器功能慢得多？
以下是TI-Basic中的程序代码,供您检查:
PROGRAM:GCD
:ClrHome
:Disp "Greatest Common"," Divisor"," ---"
:Input "First number? ",X
:Input "Second number? ",Y
:
:X?I
:Y?J
:
:If (I?int(I) or J?int(J))
:Then
:ClrHome
:Disp "Non-integer","inputs may be","innacurate!",""
:End
:If (I=1 or J=1)
:Then
:1?I
:1?J
:Goto Z
:End
:For(C,0,2^8)
:If I=J
:Goto Z
:
:If I>J
:I-J?I
:
:If J>I
:J-I?J
:
:End
:
:Disp "This is a hard","one! Thinking","harder..."
:
:For(C,0,2^15)
:If (I=J)
:Goto Z
:While (I>J)
:I-J?I …在进行我自己的BigInteger实现时,我遇到了扩展的GCD算法,这是寻找模乘法逆的基础.由于众所周知的欧几里德方法执行速度太慢,混合和二进制算法的速度只有5-10倍,因此选择Lehmer对经典算法的修改.但困难在于,当谈到描述Lehmer时,我发现的所有书籍(Knuth,应用密码学手册,互联网等)都有同样的缺点:
至于第一个问题,我最初感到惊讶的是无法找到任何实际的实现(不要指向我的GNU MP库 - 它不是学习的源),但最终通过反编译微软的实现获得灵感来自.Net 4.0,显然是基于Jebelean撰写的文章" 用于查找长整数GCD的两位数Lehmer-Euclid算法 "的思想.由此产生的功能很大,看起来很可怕,但效果很好.
但Microsoft的库仅提供基本功能,不计算任何辅助因子.嗯,准确的,一些辅助因子都在速记步计算,并且在第一步的辅助因子简单地是初始的,但在执行手写步骤之后,那么他们就不再匹配.我目前的解决方案是将"真实"辅助因子与"替代"辅助因子并行更新(第一步除外),但它使性能降至零以下:此功能现在仅比二进制文件快25-50%基本模式下的方法.因此,问题在于,虽然输入数字仅在长手步骤中完全更新,但辅助因子也会在每个速记步骤的迭代中更新从而摧毁了莱默方法的几乎任何好处.
为了加快速度,我实现了一个"融合乘法 - 加法"函数,因为"融合乘法 - 乘法 - 减法"确实有助于更新输入数字,但这次影响可以忽略不计.另一个改进是基于这样的事实,即通常只需要一个辅助因子,因此另一个辅助因子根本就不能计算.这应该减少开销(或者更多,因为第二个数字通常明显小于第一个数字),但实际上开销仅减少了预期的 25%到50%.
因此,我的问题归结为:
因此,尽管我对基本算法的性能感到满意,但是相反的情况适用于扩展操作模式,这在我的情况下是主要的.
algorithm computability discrete-mathematics greatest-common-divisor
def gcd(e, z):
if z == 0:
return e
else:
return gcd(z, e % z)
e = int(input("Please enter the first number:"))
z = int(input("Please enter the second number:"))
print ("The GCD of ",e," and ",z," is ",gcd(e,z))
d = 1
while d < e:
if d * e == 1 % z:
print (d," * ",e," = 1 (mod ",z,")")
d = d + 1
else:
d = d + 1
我试图使用这个代码通过蛮力找到rsa的候选人,它似乎应该工作,但它不能任何人帮助我吗？
z =(p - 1)(q - 1)用于计算z之前使用p = …
以下关系仅适用于两个(3,12)数字,当用于三个数字(3,12,10)时,它无法产生正确的答案.只是想知道它是我的理解还是只是两个数字,对我来说同样适用于Euclid算法.
LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b)
从这个问题Java：得到最大公约数
在获取任何数据类型的 gcd 时，无论是int, long, Integer, Long，哪个答案在精度、速度、cpu 使用率等方面更好？
A：
private static int gcdThing(int a, int b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).intValue();
}
乙：
public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }
我想使用断言测试 gcd 函数，但我不知道如何捕获异常（并防止程序崩溃）。
int gcd(int a, int b) {
if(a<0 || b<0) {
throw "Illegal argument";
}
if(a==0 || b==0)
return a+b;
while(a!=b) {
if(a>b) {
a = a - b;
}
else {
b = b - a;
}
}
return a;
}
void test_gcd() {
assert(gcd(16,24) == 8);
assert(gcd(0, 19) == 19);
try {
gcd(5, -15);
assert(false);
} catch (char* s) {
assert(true);
cout << "Illegal";
}
}
我已经编写了以下代码来计算两个正数的最大公约数.在代码中是否存在一些不是最优或足够的问题,如果是这样的话,那么做GCD的更多cloujerian方式是什么？
(def gcd (fn [a b] (->> (map (fn [x]
(filter #(zero? (mod x %)) (range 1 (inc x))))
[a b])
(map set)
(apply clojure.set/intersection)
(apply max))))
(gcd 1023 858)` => 33
模逆可以计算如下（来自Rosetta Code）：
#include <stdio.h>
int mul_inv(int a, int b)
{
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
但是，ints如您所见，输入为 。上面的代码是否也适用于无符号整数（例如 …
math integer-overflow greatest-common-divisor modular-arithmetic
给定一个正数数组。我想将数组拆分为2个不同的子集，以使它们的gcd（最大公约数）的总和最大。
数组示例：{6,7,6,7}。
答案：两个必需的子集是：{6,6}和{7,7}; 它们各自的gcd是6和7，它们的sum = 6+7=13；这是最大可能的gcd总和。
GCD：的GCD {8,12}是{4}作为图4是其将8以及12中的最大数目。
注意：gcd(X)=X如果子集仅包含一个元素。
我的方法：通过暴力破解，找到数组的所有可能子序列，然后找到最大和，但是如果输入大小大于30个数字，则此方法不起作用。我正在寻找一种更有效的方法。
额外：任何输入数字的最大大小为10 ^ 9，时间限制：-1s似乎不错，输入大小可能高达10 ^ 5