Greatest Comum Divisor

realmaster42 · 2015-05-27 22:14:43

So i found a way to find the Greatest Comum Divisor between two numbers, and it's tested.

If you don't know what GCD is, then or search math OR:

GCD is the highest integer between two number's divisors that matches.

It was coded in LUA just today

▼Hidden LUA

C#:

▼READ ME

SmittyW · 2015-05-27 23:15:41

MCD, also known as GCD (Greatest Common Divisor) for you fellow english folks. This honestly got me confused for a second before I realized you were spanish. Anyway, I guess it's nice to know they have it. Is it really ground-breaking news?

realmaster42 · 2015-05-27 23:24:18

SmittyW. wrote:

MCD, also known as GCD (Greatest Common Divisor) for you fellow english folks. This honestly got me confused for a second before I realized you were spanish. Anyway, I guess it's nice to know they have it. Is it really ground-breaking news?

wtfno why does everyone think im spanish

You nuggets it's MARCO NOT MARCOS

ANTONIO NOT ANTONIOS

I'm PT

anyways okay. here its MDC

TiKen · 2015-05-27 23:34:57

Off-topic: Marco and Antonio are also Italian names. Are you Italian?

On-topic: Better solutions where found with the GOOGLE research "greater common factor c#". It's only the 3rd link. It took me 30sec.

realmaster42 · 2015-05-27 23:46:08

TiKen wrote:

Off-topic: Marco and Antonio are also Italian names. Are you Italian?
On-topic: Better solutions where found with the GOOGLE research "greater common factor c#". It's only the 3rd link. It took me 30sec.

Off-topic: I've said im portuguese. now plsgo.

On-topic: Who cares, I'm showing a new way of reaching there. Can you actually read why Bots and 'Programming' ('Programming') word exists?

Xfrogman43 · 2015-05-27 23:54:26

Basically you wanted to create something new and you did it? Well congratulations on your success.
Note: Haters everywhere and people who would rather use google or something else to find answers rather than coming up with it on their own.

realmaster42

TiKen · 2015-05-28 00:41:08

Ok different points:

Yes, "Bots and programming" contains indeed "Programming" (and yes this word exists). However, the problem and solution you show here are (apart from the fact that you gave c# code) not exactly related to EE, but more to general programming.
Do you see me creating topics here about this N-D parametric active contours method I coded recently? (hint: the answer starts with 'n' and finishes with 'o')
And yes, you're super happy because you created a cool code that is very inefficient.
Your algorithm has at least a O(n) complexity, which is (sure), not too bad. However, the Euclidean algorithm (the one used in the link I found) that I learn in middle school (and forgot about) has a way better complexity (O(#of digits²)).
The guy (Euclide) who invented this simple, yet effective algorithm lived in 300 BC.
Do we have to re-invent the wheel every time we create a car? Again, the answer is no. (hopefully, otherwise we would still be fighting each others with sticks n' stones)

I'm a bit sorry it falls on you, but it just gets very annoying: most of the topic on the "Bots and Programming" forum are now wannabe "bot-makers" that do not know how to proofread a code for a missing semicolon or how to use Google to find answers they'll get way faster than posting here.

There is no shame in asking for help, but is it necessary to post it here? Is it really related to EE? Or is it just a general problem? Same goes for the "tips" that people found interesting.

This section seems to be stagnating into the primordial soup of development... T_T

Finally: Now, I don't ask people to simply copy-paste what they found on the net. Most of the time it won't work. You have to read the stuff, understand it, and then rewrite it on your own.

P.S.: Hater? No. I just try to learn from others and there's no shame in that.
P.P.S.: Off-topic was a joke. Humor? Get it?

kurtv13

realmaster42 · 2015-05-28 08:21:38

TiKen wrote:

Ok different points:
Yes, "Bots and programming" contains indeed "Programming" (and yes this word exists). However, the problem and solution you show here are (apart from the fact that you gave c# code) not exactly related to EE, but more to general programming.
Do you see me creating topics here about this N-D parametric active contours method I coded recently? (hint: the answer starts with 'n' and finishes with 'o')
And yes, you're super happy because you created a cool code that is very inefficient.
Your algorithm has at least a O(n) complexity, which is (sure), not too bad. However, the Euclidean algorithm (the one used in the link I found) that I learn in middle school (and forgot about) has a way better complexity (O(#of digits²)).
The guy (Euclide) who invented this simple, yet effective algorithm lived in 300 BC.
Do we have to re-invent the wheel every time we create a car? Again, the answer is no. (hopefully, otherwise we would still be fighting each others with sticks n' stones)
I'm a bit sorry it falls on you, but it just gets very annoying: most of the topic on the "Bots and Programming" forum are now wannabe "bot-makers" that do not know how to proofread a code for a missing semicolon or how to use Google to find answers they'll get way faster than posting here.
There is no shame in asking for help, but is it necessary to post it here? Is it really related to EE? Or is it just a general problem? Same goes for the "tips" that people found interesting.
This section seems to be stagnating into the primordial soup of development... T_T
Finally: Now, I don't ask people to simply copy-paste what they found on the net. Most of the time it won't work. You have to read the stuff, understand it, and then rewrite it on your own.
P.S.: Hater? No. I just try to learn from others and there's no shame in that.
P.P.S.: Off-topic was a joke. Humor? Get it?

I am a bot maker but i do not post everything i don't know here. Please...

Also okay.
(I made this from the scratch, plsgo)

Zumza · 2015-05-28 10:33:15

How it should be done in my opinion:

int gcd(int a, int b) {

     while(a != b)
          if(a < b)
               b-= a;
          else
               a-= b;
      return a;

}

goeyfun · 2015-05-28 13:50:56

plz no
Wasting memory and long run-time
try using Euclidean algorithm

scanf("%d %d",&a,&b);
while(b>0){
int temp=a%b; 
a=b; 
b=tmp;
}
GCD=A;

Zumza · 2015-05-28 14:46:18

Wikipedia wrote:

The operation of subtraction is faster than division, particularly for large numbers

The efficient algorithm is the one who suits the input best...

Edit: Binary GCD algorithm should also be noticed.

ewoke · 2015-05-28 15:19:26

private static int gcd(int a, int b) 
{
	int t;
 
	// Ensure B > A
	if (a > b) 
	{
		t = b;
		b = a;
		a = t;
	}
 
	// Find 
	while (b != 0)
	{
		t = a % b;
		a = b;
		b = t;
	}
 
	return a;
}

gotta love google

kurtv13 · 2015-05-28 15:26:32

The question is, why does this thread even exist?

SmittyW · 2015-05-28 17:14:28

kurtv13 wrote:

The question is, why does this thread even exist?

Do you want to start a flame war? Because this is how you start a flame war.

Marco just wanted to show his work, so then people offer their criticism to make it better, even if there is a better one on google. This is how this thread works.

@marco
Sorry I got your nationality mixed up, I didn't mean anything by it. I just googled MCD and it turned up spanish.

realmaster42

realmaster42 · 2015-05-28 18:48:24

kurtv13 wrote:

The question is, why does this thread even exist?

SmittyW. wrote:

kurtv13 wrote:
The question is, why does this thread even exist?
Do you want to start a flame war? Because this is how you start a flame war.
Marco just wanted to show his work, so then people offer their criticism to make it better, even if there is a better one on google. This is how this thread works.
@marco
Sorry I got your nationality mixed up, I didn't mean anything by it. I just googled MCD and it turned up spanish.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Well guys the advantage of this method is that you actually can check divisores.

Official Everybody Edits Forums

#1 2015-05-27 22:14:43, last edited by realmaster42 (2015-05-27 23:25:17)

Greatest Comum Divisor

#2 2015-05-27 23:15:41

Re: Greatest Comum Divisor

#3 2015-05-27 23:24:18, last edited by realmaster42 (2015-05-27 23:25:41)

Re: Greatest Comum Divisor

#4 2015-05-27 23:34:57

Re: Greatest Comum Divisor

#5 2015-05-27 23:46:08

Re: Greatest Comum Divisor

#6 2015-05-27 23:54:26

Re: Greatest Comum Divisor

#7 2015-05-28 00:41:08

Re: Greatest Comum Divisor

#8 2015-05-28 08:21:38

Re: Greatest Comum Divisor

#9 2015-05-28 10:33:15, last edited by Zumza (2015-05-28 10:34:48)

Re: Greatest Comum Divisor

#10 2015-05-28 13:50:56, last edited by goeyfun (2015-05-28 13:52:07)

Re: Greatest Comum Divisor

#11 2015-05-28 14:46:18, last edited by Zumza (2015-05-28 14:50:13)

Re: Greatest Comum Divisor

#12 2015-05-28 15:19:26

Re: Greatest Comum Divisor

#13 2015-05-28 15:26:32

Re: Greatest Comum Divisor

#14 2015-05-28 17:14:28

Re: Greatest Comum Divisor

#15 2015-05-28 18:48:24

Re: Greatest Comum Divisor

Board footer