Prove the algorithm for LCM

  • Thread starter flying2000
  • Start date
  • #1
40
0

Main Question or Discussion Point

algorithm to prove lcm:

a:=m
b:=n
while a != b
if a < b
a:= a + m
else
b:= b + n

//postcondition: a is the lcm(m,n)

what's the loop invariant?I thought it is(not sure):
lcm(ak, bk) = lcm(ak/m, bk/n) *lcm(m,n)
I am not sure and also impossible to prove my loop invariant....
Another loop invariant I thought is "ak=qm and bk=rn",but I don't know how to
show it's the lcm of m and n,
Thanks in advance!!
 

Answers and Replies

  • #2
40
0
Forget it! problem soloved ...

Forget it! problem soloved ...
 
  • #3
517
0
I'm curious, how do you solve that?
 
  • #4
40
0
loop invariant..

Bartholomew said:
I'm curious, how do you solve that?
the loop invariant should be
1)ak >=m and bk> =m
2)ak mod m=0 and bk mod n=0
3)ak<=lcm(m,n) and bk<=lcm(m,n)

U can prove a is the lcm(m,n) by these LI..
 
  • #5
517
0
Cool, I see.
 
  • #6
517
0
Wait, I think you also need ak > a(k-1) and bk > b(k-1)

That's not really a loop invariant though because it's not true until the second iteration.

I guess you could say something like "if k is > 1, then (that condition) is true."
 
Last edited:
  • #7
40
0
U right..

Bartholomew said:
Wait, I think you also need ak > a(k-1) and bk > b(k-1)

That's not really a loop invariant though because it's not true until the second iteration.

I guess you could say something like "if k is > 1, then (that condition) is true."

I forget to mention that.. m,n>=1 is the precondition..
 
  • #8
517
0
No, that's not what I said. For example, what if the loop were:
for(i = 0; i < 10; i++)
{
a = m;
b = n;
}

That satisfies the loop invariants you gave, but it's not going to find the LCM.
 

Related Threads on Prove the algorithm for LCM

Replies
7
Views
2K
Replies
3
Views
3K
Replies
2
Views
527
Replies
9
Views
3K
  • Last Post
Replies
1
Views
623
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
430
  • Last Post
Replies
2
Views
858
  • Last Post
Replies
4
Views
767
  • Last Post
Replies
3
Views
2K
Top