LCM seems broken. What am I missing?

Possibly I have missed the obvious or made some other dumb mistake, but I'm trying to find the least common multiple of a vector like this one:

v= [3, 4, 15, 26, 20, 10, 8, 6, 1]

which happens to be 1560 (according to these guys: https://www.calculatorsoup.com/calculators/math/lcm.php )

I have not been able to find any way to input v into lcm and get 1560 or any other number that returns an integer vector when divided by v. In fact the help examples, like this one:

A = [5 17; 10 60];
B = 45;
L = lcm(A,B)

L = 2×2

45 765 90 180

Also do not give results I was expecting, which in this case would be: 3060

Help appreciated and thanks!

Answer 1

[Dyuman Joshi]

"What am I missing?"

You are expecting it to work a particular way.

You looked up an example from the documentation page of lcm, but you did not go through the syntax of the function i.e. what input arguments need to be provided and what is the corresponding output.

The function lcm (the built-in function lcm) expects two inputs, where either

> Both the inputs must be of the same size, in which the output is the lcm of respective pairs of the input - C_ij = lcm(A_ij, B_ij)

A = randi([1 10],2,3)

A = 2×3

9 3 6 1 6 1

B = randi([11 20],2,3)

B = 2×3

12 18 17 20 13 13

C = lcm(A,B)

C = 2×3

36 18 102 20 78 13

> One input must be a scalar, in this case, the output is lcm of each element of non-scalar input with the scalar input - C_ij = lcm(A_ij,B)

A = randi(50,3,4)

A = 3×4

8 38 43 31 30 1 41 38 11 5 44 3

B = 3

B = 3

C = lcm(A,B)

C = 3×4

24 114 129 93 30 3 123 114 33 15 132 3

One way of finding the lcm of an array of values -

v= [3, 4, 15, 26, 20, 10, 8, 6, 1]

v = 1×9

3 4 15 26 20 10 8 6 1

out = 1;
for k=v
    out=lcm(out,k);
end
out

out = 1560

[Paul]

The Symbolic version of lcm can be directly applied for this case

v= [3, 4, 15, 26, 20, 10, 8, 6, 1]

v = 1×9

3 4 15 26 20 10 8 6 1

double(lcm(sym(v)))

ans = 1560

[Dyuman Joshi]

It certainly can be, provided OP has the Symbolic math toolbox.

[James Brown]

Thanks Dyuman & Paul!

Paul's symbolic solution:

• Intuitive and close to what I was expecting for lcm
• Takes 20x longer than Dyuman's numerical solution
• Keeps working with much larger vectors with much larger elements without any significant execution time penalty

Dyuman's numerical solution:

• Took me a minute to understand
• Run 20x faster than the symbolic solution on my computer with the given input
• Gives warnings with larger vectors and larger elements, at which point answers diverge from the symbolic method. Execution time increases with the number of elements as expected.

Bottom Line:

• If I have to do a large number of small vectors with small elements, I'll use the numerical method to save time
• Most of the time, including this one, the symbolic approach will be fast enough with more intuitive coding.

[Walter Roberson]

v= [3, 4, 15, 26, 20, 10, 8, 6, 1]

v = 1×9

3 4 15 26 20 10 8 6 1

fold(@lcm, v, 1)

ans = 1560

Here, fold is not very well known -- it is a little better known in Maple. It turns out that fold is part of the symbolic toolbox, but it does not inherently use any symbolic operations, so it can operate at numeric speeds.

What fold is doing in this case is just iterating lcm() calls, very similar to @Dyuman Joshi code. It is a convenience function that can make for nice compact code. Because a function handle is being called each time, it would be expected to be a little slower than a plain loop, but not all that much slower for a "simple" function handle like @lcm -- if you were using an anonymous function handle, the overhead can start to add up.

The major drawback for fold is probably that people are not used to seeing it, so people reading the code might have to refer to the help documentation to figure it out -- at least the first couple of times they see it being used.

[James Brown]

Thanks Walter!

I'll look into that

[Dyuman Joshi]

@James Brown

Symbolic operations, in general, will be slower than numerical operations.

"Gives warnings with larger vectors and larger elements, at which point answers diverge from the symbolic method. "

Yes, that is a drawback of the numerical method as it is limited by the precision of the input. A work around to that is using integer data types for larger number instead of double data type.

v1 = randi(1000,1,10)

v1 = 1×10

488 816 878 256 565 489 412 944 427 252

v2 = uint64(v1)

v2 = 1×10

488 816 878 256 565 489 412 944 427 252

out1 = 1;
for k=v1
    out1=lcm(out1,k);
end

Warning: Inputs contain values larger than the largest consecutive flint.
Result may be inaccurate.

Warning: Inputs contain values larger than the largest consecutive flint.
Result may be inaccurate.

fprintf('%d',out1)

4109122419083862016

out2=uint64(1);
for k=v2
    out2 = lcm(out2,k);
end
fprintf('%d',out2)

4109122419083861760

You can compare the output using LCM on wolfram alpha.

But keep in mind that the integer data types also have a finite precision. If you want infinite precision, you will have to use symbolic numbers.

Another option for using arbitary precision arithmetic is Java BigInteger. You can use the numerical method for it, it will work smoothly for any (input and output) values that your computer can store and will be quite faster than the symbolic method.

[Paul]

fold using numerical lcm will have the same concerns with accuracy that @James Brown alreay identified, won't it?

The function argument to fold is expected to take two inputs, but if the input v is a scalar then fold just returns the input. For some cases, that might be sensible value, like

[fold(@sum,5) fold(@prod,5)]

ans = 1×2

5 5

But for other cases, such as

fold(@or,5)

ans = 5

returning the input might not be a logical result.

[Walter Roberson]

Yes, if the input values to fold are not symbolic, then fold will have the same accuracy concerns -- although fold is part of the symbolic toolbox, it makes no attempt to convert the datatypes. Basically, it is just a convenient shortcut for a loop -- not unlike arrayfun()