计算非常大数字JAVA的欧拉函数 [英] Calculating Eulers Totient Function for very large numbers JAVA
问题描述
我已经设法得到一个版本的Eulers Totient Function工作，虽然它适用于较小的数字（较小的这里较小的1024位数，我需要它来计算）
I've managed to get a version of Eulers Totient Function working, albeit one that works for smaller numbers (smaller here being smaller compared to the 1024 bit numbers I need it to calculate)
我的版本在这里 -
My version is here -
public static BigInteger eulerTotientBigInt(BigInteger calculate) {
BigInteger count = new BigInteger("0");
for(BigInteger i = new BigInteger("1"); i.compareTo(calculate) < 0; i = i.add(BigInteger.ONE)) {
BigInteger check = GCD(calculate,i);
if(check.compareTo(BigInteger.ONE)==0) {//coprime
count = count.add(BigInteger.ONE);
}
}
return count;
}
虽然这适用于较小的数字，但它可以通过迭代到正在计算的数字。有了BigIntegers，这是完全不可行的。
While this works for smaller numbers, it works by iterating through every possible from 1 to the number being calculated. With large BigIntegers, this is totally unfeasible.
我已经读过，每次迭代都可以分割数字，不需要逐个遍历它们。我只是不知道我应该划分什么（一些例子，我看过是在C和使用longs和平方根 - 据我所知，我不能计算准确的准确我也想知道，如果对于模运算这样的函数需要包含一个参数说明什么是模块。我完全不确定这一点，所以任何建议很赞赏。
I've read that it's possible to divide the number on each iteration, removing the need to go through them one by one. I'm just not sure what I'm supposed to divide by what (some of the examples I've looked at are in C and use longs and a square root - as far as I know I can't calculate an accurate an accurate square root of a BigInteger. I'm also wondering that if for modular arithmetic such as this, does the function need to include an argument stating what the mod is. I'm totally unsure on that so any advice much appreciated.
任何人都可以在这里指向正确的方向？
Can anyone point me in the right direction here?
PS当我发现修改Euler Totient函数。我修改了它与BigIntegers工作 -
PS I deleted this question when I found modifying Euler Totient Function. I adapted it to work with BigIntegers -
public static BigInteger etfBig(BigInteger n) {
BigInteger result = n;
BigInteger i;
for(i = new BigInteger("2"); (i.multiply(i)).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
if((n.mod(i)).compareTo(BigInteger.ZERO) == 0)
result = result.divide(i);
while(n.mod(i).compareTo(BigInteger.ZERO)== 0 )
n = n.divide(i);
}
if(n.compareTo(BigInteger.ONE) > 0)
result = result.subtract((result.divide(n)));
return result;
}
它给出了一个准确的结果，运行永远（我仍然不知道如果它甚至完成，它已经运行了20分钟）。
And it does give an accurate result, bit when passed a 1024 bit number it runs forever (I'm still not sure if it even finished, it's been running for 20 minutes).
推荐答案
您尝试编写的算法等效于参数 n ，这意味着你应该期望它永远运行，实际上直到你的计算机死亡或你死。有关详细信息，请参阅mathoverflow中的此帖子：如何计算欧拉常数函数有多难？
The algorithm you are trying to write is equivalent to factoring the argument n, which means you should expect it to run forever, practically speaking until either your computer dies or you die. See this post in mathoverflow for more information: How hard is it to compute the Euler totient function?.
另一方面，如果你想要一个大的您要进行因式分解的数字，将参数作为（素数，指数）对的序列传递。
If, on the other hand, you want the value of the totient for some large number for which you have the factorization, pass the argument as sequence of (prime, exponent) pairs.
这篇关于计算非常大数字JAVA的欧拉函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
