hi,
what would be the easiest way to find the "gr??tes gemeinsames Vielfaches". The problem is, that i don't know how that's called in english. Here's the explanation:

if i've two different numbers, for example 3 and 4. so what's the best way to find out, what the smallest number is, that the two have in common if i would multiply them by 2, 3, 4, ....

for the numbers 3 and 4 this number would be 12, because if I multiply 3 by 4 and 4 by 3 i get 12! and that's the smallest number that can be reached with this method. another example:
numbers 5 and 7. the smallest number that they have in common is 35. you know what i mean?

now i would like to have a fast algorythmn to do that. in mathematics you would do a "primfaktorzerlegung". if i translate it, it's prime factor division or something like that. so you divide the two numbers in the prime factors and ...... it's difficult to explain. the people who are good in maths know what i mean. but this method is really difficult to program (not important which language).

cya,
NOP-erator
Posted on 2001-08-14 12:31:07 by NOP-erator
Hi !

Well, the simplest answer to your question is done by this nice
symbol "oo" :grin: (Well, you asked for the greatest common multiply !)

So do you want to know the greatest common divisor or the smallest common product of two numbers ?

if you want the gcc of both, I don't know a better algorithm as the euklidian. Of course there are others, but they aren't faster really.

Greetings,

CALEB
Posted on 2001-08-14 13:15:18 by Caleb
least common multiple: as a 1st approximation...

lcm(a,b) = ab / gcm(a,b)

to get the gcm (greatest common multiple) see the following link...

http://hissa.nist.gov/dads/HTML/binaryGCD.html

hope this helps
Posted on 2001-08-14 15:22:13 by rafe
#include <stdio.h>


int gcm(int a, int b);

int main()
{
int m, n;

printf("Enter two number:\n");
scanf("%d%d", &m, &n);

printf("GCM = %d\n", gcm(m, n));
printf("LCM = %d\n", (m * n) / gcm(m, n));

return 0;
}

int gcm(int a, int b)
{
int max, gcd;
int c;

max = a > b ? a : b;
gcd = a > b ? b : a;

while (max % gcd != 0)
{
c = max;
max = gcd;
gcd = [b]c[/b] % gcd; /* FIXED! */
}
return gcd;
}

; gcd - greatest common divisor

; by Paul Hsieh
;
; input:
; eax = a
; edx = b
;
; output:
; eax = gcd
;
; destroys:
; edx
; flags
;
gcd: neg eax
je L3
L1: neg eax
xchg eax,edx
L2: sub eax,edx
jg L2
jne L1
L3: add eax,edx
jne L4
inc eax
L4: ret
Posted on 2001-08-14 19:35:09 by bitRAKE
i can't believe it. sorry to you all, but i'm looking for the least (smallest) common multiple, although i wrote that i'm looking for the greatest. sorry, i'm really silly, seems to be the weather. it would be nice if you could post some code or examples for the smallest common multiple.

tnx.

NOP-erator
Posted on 2001-08-15 12:27:30 by NOP-erator
no 'blem... but what you got was info on the least common multiple. I didn't test myself but BitRake's posting of P. Hsieh's asm code looks like it'll do the trick & the c code looks solid too.

In my posting you'll note that the two are related algebraically so any algo that gets you the the greatest common denominator also gives you the LCM. The link was to an algo for gcd using a binary approach not real code but I was only trying to get you started.

I think you're in business but let me know if I'm wrong or if you need more help.
Posted on 2001-08-15 13:04:54 by rafe
hi,
actually i don't understand the c-code. anyway, why is it only possible to calculate the least common multiply (LCM) by first calculating the greatest common multiply (GCM)?

cyaz
Posted on 2001-08-16 09:28:30 by NOP-erator


Sorry for the delay... local net was/is down.

ooh, excellent question!

short answer:
I dunno... you probobly can but I don't know the algo to do it directly. It been a while since i did number theory... well this stuff at least. sorry.

longer answer:

The algorithm for getting the gcd is quick & robust. so adding the extra multiply & divide isn't going to slow things down much at all.

you're into an area of number theory where it's easy to ask questions but finding the answers has proven to be very difficult. Prime decomposition. Which is what the public key encryption stuff is based upon. & why they are thought to be secure.

Think of the two numbers as sets of primes:
so if

a = 12 then a = 2 * 2 * 3
b = 15 then b = 3 * 5

what has proven to be easy is & known for a long time (hundreds of yrs) is finding the intersection of these two sets of primes aka finding the gcd(). here it's {3}

what you are asking for is the union of these two sets aka the LCM. {2, 2, 3, 5} multiplies out to 60

ab = the union of the two sets but it doubles the intersection. {2, 2, 3, 3, 5} multiplies out to 180

so the easy & direct way to find the set union of the two prime decompositions to multiply the two numbers and remove one of the doubled intersections. or {2, 2, 3, 3, 5} - {3} becomes 180/3

standard set op thinking. Which is what the formula

lcm(a,b) = ab / gcd(a,b)

translates to in plain(er) speak.

mmm... i sense that i may be droning on a bit in a clear like mud manner.

maybe, if you're really interested you should pick up a book on elementary number theory or better yet cryptography.
Posted on 2001-08-16 12:24:34 by rafe
i understand what you mean. i knew about that prime decomposition stuff. but here is my proposal (proposition): i just try to divide the second number by the first. if there is no remainder, the first number is the least common multiply. but if there is a remainder, i just multiply the bigger number first by 2, then by 3, 4, 5, and every time i divide the product by the second number, till there is no remainder.

wouldn't be that a possibility to find the LCM?

bye
Posted on 2001-08-16 13:37:54 by NOP-erator
net's back up... temporarily

yes it would. But it's a "brute force" method for doing it. it would work for "smaller" numbers, no problem.

Nothing wrong with that per se. But ask yourself what happens when you're looking for the lcm() of (rafe randomly hits keys) 9712937127 & 434668411? how many times thru the loop are you willing to go?

The old algorithms for getting the gcd() are MUCH quicker... i don't remember the big-O just now but.... for bigger numbers going the apparently roundabout way is actually quicker.
Posted on 2001-08-16 14:59:54 by rafe
you know what's really confusing me? how is it possible to find the greatest common multply? there is no limit for numbers, how far does that go?

cya
Posted on 2001-08-17 10:18:56 by NOP-erator
didn't mean to leave you completely hanging... i have a short attention span.

You can usually swamp an algorithm by choosing out rageously large numbers... it's now a question of what's the most appropriate algo for the task & now you're into what i consider seriously fun stuff.

now for the lame-o finish...

Look into an introductory book on algorithmic complexity/design. Read up on things like "Big-O" & "NP". I don't want to completely cut you off but the books will do a much better job of explaining this than i can. None of this is difficult to understand mind you it's just that a book at this point would be more appropriate.

Unfortunately, I don't speak German so... I'm probobly not the best to ask for recomendations. Sorry.
Posted on 2001-08-29 23:32:19 by rafe

you know what's really confusing me? how is it possible to find the greatest common multply? there is no limit for numbers, how far does that go?

cya

rafe gave you the whole function.
forget of the term you are confused by.
Just do 3 things
1. Multiply A & B (It IS the GCM - the greates com multiplier)
2. Find greatest common divider (a,b) - it's done by wellknown Eucledian algo(divider to devident;remindor to divider until there is no reminder(0). One of asm implementation of the algo by Paul Hsieh is in this very thread posted by bitRake
3. Divide result of 1. by result of 2.
And you get LCM (The least common mutiplier)
Posted on 2001-09-17 00:40:49 by The Svin
thanks!!

NOP-erator
Posted on 2001-09-17 11:35:18 by NOP-erator
gcd = t % gcd;


bitRake, whats "t" over here? You havent initialized it anywere in your code?
Posted on 2001-09-19 04:00:01 by MovingFulcrum
I am sorry: should be a c. :rolleyes:
Posted on 2001-09-19 08:41:34 by bitRAKE