Results 1 to 5 of 5
 03282009, 04:51 PM #1Member
 Join Date
 Mar 2009
 Posts
 2
 Rep Power
 0
 03282009, 06:15 PM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 22
So whats the logic you have followed to do this? Did you use a specific algorithm for calculation or your own way? How did you do it for 2 number?
 03282009, 08:54 PM #3Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
gcd n
When I started contemplating the problem, I got the feeling a brute force method would be computationally demanding. Although my initial research suggested the problem was npcomplete, I also found that Algorithm 386 by Bradley is linear in time and space. Many of the sources for the paper are academic and require a professional subscription or access as a student. I finally found this source and downloaded it.
h t t p : / / w w w .
eknigu.com/.../Bradley.%20Algorithm%20386
Warning: do not go directly to the home page. It's Russian.
The paper is in djvu format. Do a search to find the reader, it's open source.
You will have to port your code from a FORTRAN program, but it's not a terribly long program, less then 80 lines including comments and GOTOs.
Rots of Ruck.
from another forum
**********
the greatest common denominator of n+1 numbers, where n is a number of values for which you have already generated a GCD, is the GCD of the next value you want to put in your calculation and the GCD you have already obtained. For example, take a function int GCD(36, 24) that would return 12. Then let's say we overload it to take three numbers, int GCD(36, 24, 18) which would return 6. If you already have the code for the first function that got the GCD of two numbers, you have half the code already, because GCD(36, 24, 18) will return the same value as GCD(GCD(36, 24), 18), or GCD(12, 18). All you need to do, then, is modify your code to work on an array or list of values and pass that data by reference recursively to calculate the GCD of the next two values, with a base case being that you are processing the last two values in the set.
This is, however, based off of my knowledge of C++, I'm not sure how those techniques would work in Java.
In pseudocode, where <T> is a data type that contains the n values you're calculating:
void nGCD(<T> values)
{
...Begin at the first two values of <T>.
...Calculate the GCD of those two variables, store it in the
...second variable. The code you already wrote goes here.
...Delete the first variable.
...Move forward by one variable. The second variable
...becomes the new first variable.
...If (the new second variable exists in <T>)
......nGCD(values)
}
The GCD of all of the numbers in <T> will be stored in the last variable of <T>.
**********
Also found this in C
********
#include<stdio.h>
#include<conio.h>
void main(){
int a[10],b[10],q,i,j,min,max,cnt;
cnt=max=q=0;
clrscr();
printf("Enter the no of values to find GCD");
canf("%d",&i);
for(j=0;j<i;j++){
printf("enter the element %d\n",(j+1));
scanf("%d",&a[j]);
} //for
min=a[0];
for(j=0;j<i;j++) {
if(min>a[j]) {
min=a[j]; }
} for
for(j=1;j<=min;j++) { //for 1
for(int k=0;k<i;k++) {
if(a[k]%j==0){
++cnt;} // if
}
if(cnt==i) {
b[q]=j;
++q;} //if
cnt=0;
} //outer for
for(int p=0;p<q;p++) {
if(max<b[p]) {
max=b[p]; } // if
} // for
printf("The GCD is %d",max);
getch();
}
**************
The first algorithm is from a peer reviewed paper.
Haven't really studied the other two, but they seem to be saying to reursively call gcd on each pair (gcd(n, gcd (n1, Gcd(n2 ...(Gcd N1, N0)))...). Don't know if complexity is linear or higher.
If you want to ignore the fact that I have'nt read the code carefully, this should work
lst = {dat0, dat1 ...., datn}
iGcd = dat0
lst = rest of list
while lst {
iGcd = GCD(iGcd, head of list)
lst = rest of list
} //while
Rots of Ruck
 02152011, 10:08 AM #4Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,712
 Rep Power
 14
abuse reported
 02152011, 10:23 AM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 22
Similar Threads

Help about Guess the Numbers Program in java
By macfrik in forum New To JavaReplies: 6Last Post: 03252009, 04:59 AM 
prime numbers program
By i contra i in forum New To JavaReplies: 9Last Post: 01152009, 08:22 AM 
Why my program cannot calculate the decimal value?
By pearllymary78 in forum New To JavaReplies: 4Last Post: 06232008, 12:52 AM 
Addition program that displays the sum of two numbers
By Java Tip in forum Java TipReplies: 0Last Post: 03282008, 09:46 PM 
Calculate Tax in java
By toby in forum New To JavaReplies: 2Last Post: 07302007, 09:03 AM
Bookmarks