Euler's Totient Function Calculator
Euler's Totient Theorem
public static int totient(int num){ //euler's totient function calculator. returns totient
int count=0;
for(int a=1;a<num;a++){ //definition of totient: the amount of numbers less than num coprime to it
if(GCD(num,a)==1){ //coprime
count++;
}
}
return(count);
}
public static int GCD(int a, int b){ //faster euclidean algorithm-see GCD for explanation
int temp;
if(a<b){
temp=a;
a=b;
b=temp;
}
if(a%b==0){
return(b);
}
return(GCD(a%b,b));
}
The Euler Totient function, denoted phi(n) or totient(n), is the amount of numbers less than n relatively prime, or coprime to it. It has many uses, particularly Euler's Totient Theorem that for all a coprime to n. There is also other ways to calculate totient(n), but they were slower than my implementation. It works by looping through 2->num, because 1 is always relatively prime to all numbers, we account for that and start at 2. We check if GCD(num,i) is 1, which shows they are relatively prime. The Euclidean algorithm provides a quick recursive way to do this (see GCD page), and I sped it up considerably by implementing the fast Euclidean algorithm. The Javascript totient calculator implementation is above, using the exact same Java algorithm.
int count=0;
for(int a=1;a<num;a++){ //definition of totient: the amount of numbers less than num coprime to it
if(GCD(num,a)==1){ //coprime
count++;
}
}
return(count);
}
public static int GCD(int a, int b){ //faster euclidean algorithm-see GCD for explanation
int temp;
if(a<b){
temp=a;
a=b;
b=temp;
}
if(a%b==0){
return(b);
}
return(GCD(a%b,b));
}
The Euler Totient function, denoted phi(n) or totient(n), is the amount of numbers less than n relatively prime, or coprime to it. It has many uses, particularly Euler's Totient Theorem that for all a coprime to n. There is also other ways to calculate totient(n), but they were slower than my implementation. It works by looping through 2->num, because 1 is always relatively prime to all numbers, we account for that and start at 2. We check if GCD(num,i) is 1, which shows they are relatively prime. The Euclidean algorithm provides a quick recursive way to do this (see GCD page), and I sped it up considerably by implementing the fast Euclidean algorithm. The Javascript totient calculator implementation is above, using the exact same Java algorithm.
Provided by website-hit-counters.com site. |