Already a member?

oleber

Lets see the performance.

Which is the fastest algorithm?

GCM seems to be at most n

LCM seems to be at most n*m

so, if you do lcm(a,b) := (a*b)/gcm(a,b), you get a n complexity

This is mathematics.

oleber

Swamp is the subject of another post:
http://www.go4expert.com/showthread.php?t=1732

shabbir

Quote:

Originally Posted by oleber
Swamp is the subject of another post:
http://www.go4expert.com/showthread.php?t=1732

Could not get what you meant here.

oleber

clocking and shabbir are speaking of swaping variables.

This subject was already spoken in the other thread. Just that

clocking

hi !
thanks for your idea. But I only want someone tell me about that algorithm.
Swapping is not difficult, but I'm interested in the easier way solving it.

Code:

tmp = ts[i];
ts[i] = ts[j];
ts[j] = tmp;

can't we use tmp ?

Balaselvi

Hi,

This is Bala.
I want to know how to calculate GCD of many numbers, ex 2048 values.

Please help.

Thanks in advance.

asadullah.ansari

Code:

int main()
{
    int n1,n2,n3,n;
    cout<<" Numbers are : ";
    cin>>n1>>n2>>n3;
    n=FindGcd(FindGcd(n1,n2),n3);
    cout<<"GCD of n1,n2,and n3 is "<<n<<endl;
    return 0;
}

int FindGcd(int num1, int num2)
{
    int temp;    
    while(num2!=0)
    {
        temp = num2;
        num2 = num1%num2; 
        num1 = temp;
    }     
    return num1;
}

aisha.ansari84

can you please tell me when the loop will actually stop

zeeme

correct code is this 100% checked!

for(n=1;n%a != 0 || n%b != 0;n++);
return n

vanishing_stapler

When I searched for lcm c++, this thread had the top two spots, so I figured that I'd join and put this here.

For finding the LCM (Least Common Multiple) of two integers, a and b, in C++, use:

for(n=a;n%b != 0;n+=a);
return n;

For maximum speed, try to set it up so that the larger number is "a" and the smaller one is "b".

The reasoning:
The least common multiple (LCM) of two numbers, a and b, is the smallest number that is a multiple of "a" AND a multiple of "b". If we already know that the LCM is a multiple of "a", then why not count by "a"? When we count by "a", starting at "a", we are testing every number that is a multiple of "a" already, and only have to see if it is a multiple of "b" too. This code does just that. When "a", the number we're counting by, is larger than 1, the process will be much faster than with those other suggestions, because it's taking bigger steps (at the same speed per step) to get to the same solution.

If "a" is a billion, then this will be at least a billion times faster than this:

for(n=1;n%a != 0 || n%b != 0;n++);
return n;

(even though both work)

I hope this helps.

oleber Go4Expert Member
23Jul2007,18:33	#21
	Lets see the performance. Which is the fastest algorithm? GCM seems to be at most n LCM seems to be at most nm so, if you do lcm(a,b) := (ab)/gcm(a,b), you get a n complexity This is mathematics.

oleber Go4Expert Member
24Jul2007,13:50	#22
	Swamp is the subject of another post: http://www.go4expert.com/showthread.php?t=1732

shabbir Go4Expert Founder
24Jul2007,14:17	#23
	Quote: Originally Posted by oleber Swamp is the subject of another post: http://www.go4expert.com/showthread.php?t=1732 Could not get what you meant here.

oleber Go4Expert Member
24Jul2007,14:26	#24
	clocking and shabbir are speaking of swaping variables. This subject was already spoken in the other thread. Just that

clocking Ambitious contributor
24Jul2007,19:11	#25
	hi ! thanks for your idea. But I only want someone tell me about that algorithm. Swapping is not difficult, but I'm interested in the easier way solving it. Code: tmp = ts[i]; ts[i] = ts[j]; ts[j] = tmp; can't we use tmp ?

Already a member?

Not a member yet?

Search Go4Expert

Latest Forum Topics

Find Us On Facebook

Latest Articles

Balaselvi Newbie Member
27Feb2008,10:13	#26
	Hi, This is Bala. I want to know how to calculate GCD of many numbers, ex 2048 values. Please help. Thanks in advance.

aisha.ansari84 Contributor
5Mar2008,18:22	#28
	can you please tell me when the loop will actually stop

zeeme Newbie Member
22Feb2009,20:00	#29
	correct code is this 100% checked! for(n=1;n%a != 0 \|\| n%b != 0;n++); return n

vanishing_stapler Newbie Member
15May2009,01:55	#30
	When I searched for lcm c++, this thread had the top two spots, so I figured that I'd join and put this here. For finding the LCM (Least Common Multiple) of two integers, a and b, in C++, use: for(n=a;n%b != 0;n+=a); return n; For maximum speed, try to set it up so that the larger number is "a" and the smaller one is "b". The reasoning: The least common multiple (LCM) of two numbers, a and b, is the smallest number that is a multiple of "a" AND a multiple of "b". If we already know that the LCM is a multiple of "a", then why not count by "a"? When we count by "a", starting at "a", we are testing every number that is a multiple of "a" already, and only have to see if it is a multiple of "b" too. This code does just that. When "a", the number we're counting by, is larger than 1, the process will be much faster than with those other suggestions, because it's taking bigger steps (at the same speed per step) to get to the same solution. If "a" is a billion, then this will be at least a billion times faster than this: for(n=1;n%a != 0 \|\| n%b != 0;n++); return n; (even though both work) I hope this helps.

User Name:		Save
Password