[Tutor] LCM

[Dave Angel]

On 11/14/2012 01:34 PM, Selby Rowley Cannon wrote:
> On 14/11/12 18:27, Dave Angel wrote:
>> On 11/14/2012 12:52 PM, Selby Rowley Cannon wrote:
>>> Hey,
>>>

Tell us what version of Python you're targeting.  I'm going to assume
2.x, since you have print without parens.

>>>      I've been trying to write a function to find the Lowest Common
>>> Multiple of two numbers, but it isn't working and I've kinda hit a
>>> dead end on the thought-process end of things. Anyone mind looking at
>>> it, and tell me what's wrong? (I hop you don't think it's too long to
>>> put in an email)
>>>
>>> Code:
>>>
>>> def lowestCommonMultiple(a, b, amount): #k

Why would you require the caller to specify the "amount" ?  It's easier
for you to calculate the two ranges below, as needed.

>>>      float(amount)

This statement does nothing, which is good, since range doesn't work on
floats.

>>>      if a == b:
>>>          print 'You cannot find the LCM of the same number twice.'

here you should just return a

>>>      else:
>>>          numbersList = list(range(amount))

In Python 2.x, range already returns a list.  Besides, you'd be better
off with a sequence, so I'd use xrange.

>>>          aMultiples = []
>>>          bMultiples = []
>>>          for aNumber in numbersList:
>>>              aMultiples.append(a*aNumber)
>>>          for bNumber in numbersList:
>>>              bMultiples.append(b*bNumber)
>>>          if aMultiples[1] == bMultiples[1]:

This will never be true, since lhs is 2*a, and rhs is 2*b, and a != b
What you really need is some form of loop, which compares every item in
the first list to every item in the second, returning the lowest number
that's in both.  Try something like:

for item in aMultiples:
    if item in bMultiples:
        return item

>>>              print 'The LCM of ', a, ' and ', b, ' is ', aMultiple[1]

It's generally better to return a calculated result, and print it
separately, than always to print it.

>> Which are you interested in, finding what's wrong with the code, or a
>> simpler way to actually find an LCM ?
>>
>> Is this an assignment, or just part of a bigger program you're writing?
>>
> a.) Finding what's wrong with the code;
> b.) Part of a bigger program.
> 
> 

This algorithm is fine for small numbers, but the loop you'll have to
write at the end is going to be very slow for large ones.  It'll also
use up lots of memory for those lists.

You could speed it up a tiny bit by using different ranges for the two
lists.  After all the first list needn't have more than b items in it,
and the second needn't have more than a items in it.

You could cut the memory usage a lot by making the first list simply an
xrange.

The second, though, has to be traversed multiple times, so you
presumably need a list.  But a set would be MUCH faster.


Anyway, if all you care about is the result, then use Euclid's method,
and the % operator to calculate the gcd.  A few loops around, and even
pretty large numbers will crumble.  Then the lcm is simply the product
of a and b, divided by the gcd of a and b.

The heart of such a gcd loop is something like:
while b > 0:
    a, b = b, a%b

-- 

DaveA