Bug in LCM function (possibly 32bit integer overflow) octave 3.0.3 64bit linux

[Rob Mahurin]

On Mar 24, 2009, at 8:33 PM, Mikael Leiviskä wrote:
> Bug report for Octave 3.0.3 configured for x86_64-pc-linux-gnu
>
> Description:
> -----------
>
> There seems to be an odd problem with the implementation of LCM and/or
> possibly errornous memory handling.
>
> Repeat-By:
> ---------
> Here is how I produce the bug.
>
>
> ~$ octave
> GNU Octave, version 3.0.3
> Copyright (C) 2008 John W. Eaton and others.
> This is free software; see the source code for copying conditions.
> There is ABSOLUTELY NO WARRANTY; not even for MERCHANTIBILITY or
> FITNESS FOR A PARTICULAR PURPOSE.  For details, type `warranty'.
>
> Octave was configured for "x86_64-pc-linux-gnu".
>
> Additional information about Octave is available at http:// 
> www.octave.org.
>
> Please contribute if you find this software useful.
> For more information, visit http://www.octave.org/help-wanted.html
>
> Report bugs to <bug at octave.org> (but first, please read
> http://www.octave.org/bugs.html to learn how to write a helpful  
> report).
>
> For information about changes from previous versions, type `news'.
>
> octave:1> A = 1.89e9/88, B = 4*A
> A =  2.1477e+07
> B =  8.5909e+07
> octave:2> A = int32(A), B = int32(B)
> A = 21477273
> B = 85909091
> octave:3> lcm(A,B), lcm([A,B])
> ans = 2147483647
> ans =  1.8451e+15
> octave:4> A = 21477273, B = 85909091
> A =  21477273
> B =  85909091
> octave:5> lcm(A,B), lcm([A,B])
> ans =  1.8451e+15
> ans =  1.8451e+15

I can confirm this on 3.0.3 (I don't currently have a working  
development tree).  However, note that neither your A nor your B is  
an integer:

octave:14> A = 1.89e9/88, B = 4*A, printf("%#.19g\n",A,B)
A =  2.1477e+07
B =  8.5909e+07
21477272.72727272660
85909090.90909090638

and that the nearest integers have no factors in common

octave:16> factor(round(A)), factor(round(B))
ans =        3       17   421123
ans =      31      47   58963

> Note that the answer is not correct in any of the cases, it should be
> 85909091 (which is B) It's not only incorrect but it's off by a
> magnitude of 7...

The correct least common multiple is A*B.

> The number 2147483647 that occurs as a result after the first call to
> lcm(A,B) is suspiciously close to 2^31 - 1 = 2147483647 which is  
> max for
> signed 32bit ints. Perhaps it's an integer overflow bug?

When lcm preserves the input type, the result is the same as int32 
(A*B), which is also the same as int32(Inf).

It's probably a bug for lcm to inconsistently "upgrade" to double  
precision when passed an array of integers:

octave:27> class( lcm( int32(A), int32(B) ) )
ans = int32
octave:28> class( lcm( [int32(A), int32(B)] ) )
ans = double

That probably also happens in the development branch's lcm.m.

Cheers,
Rob

-- 
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee 		865 207 2594
Knoxville, TN 37996 			rob at utk.edu