Large Integer problem

Asked by deniz kartan

deniz kartan (view profile)

on 3 Mar 2011
Latest activity Commented on by Walter Roberson

Walter Roberson (view profile)

on 14 Jan 2016
Accepted Answer by Sean de Wolski

Sean de Wolski (view profile)

Hi, I am getting these strange results:
Equations are of the form (x*y + n) - x*y which has the obvious result n. But Matlab gives strange results. These are the results I get in Matlab 2007 and 2010a:
(1812433253*19650218 + 1) - (1812433253*19650218) = 0
(1812433253*19650218 + 2) - (1812433253*19650218) = 0
(1812433253*19650218 + 3) - (1812433253*19650218) = 4
I realized that 1812433253*19650218 has more than 53 bits and these results has something to do with the way Matlab handles numbers between 53 bits and 64 bits. But I couldn't find a reliable way to carry out above operations correctly. Thanks.

Products

Answer by Sean de Wolski

Sean de Wolski (view profile)

on 3 Mar 2011

Answer by Matt Fig

Matt Fig (view profile)

on 3 Mar 2011

You are seeing the results of the limitations of floating point arithmetic.
Read this if you plan on using MATLAB much:
You can see what is going on by looking at this:
N = 1812433253*19650218;
eps(N)
ans =
4
This means that whenever you add a number greater than eps/2 to N, the result is represented as the next largest number available, N+eps(N). Then it will make sense that:
N + eps(N) - N % Equals eps(N)
ans =
4
Conversely, whenever you add a number smaller than eps(N)/2 to N, the result is represented as N. So it makes sense that
N + eps(N)/3 - N % eps(N)/3 is less than eps(N)/2.
ans =
0

deniz kartan

deniz kartan (view profile)

on 3 Mar 2011
Thank you Matt, that's exactly what's going on in my calculations. I am now trying to use John D'Errico's vpi.
Matt Fig

Matt Fig (view profile)

on 3 Mar 2011
I recommend thoroughly understanding this because it is the same thing for non-integers.

Answer by the cyclist

the cyclist (view profile)

on 3 Mar 2011

I recommend John D'Errico's "Variable Precision Integer" code from the FEX:

Answer by Michelle Hirsch

Michelle Hirsch (view profile)

on 13 Jan 2016

I'm 5 years late to the party, but another lightweight way to address this specific behavior is to force the variables to be int64 (or uint64), which can express integer values larger than 2^53.
>>(int64(1812433253*19650218) + 1) - int64(1812433253*19650218)
ans =
1

John D'Errico

John D'Errico (view profile)

on 13 Jan 2016
True. I totally agree that this can help, with the caveat that you must be sure that the numbers stay in 63 or 64 bits, then you can use int64 or uint64.
The problem is you get a little extra room over 2^53 for a double, but never enough. And when those int64 or uint64 multiplies overflow, you get no warning.
uint64(2^33)^2
ans =
18446744073709551615
uint64(2^35)^2
ans =
18446744073709551615
Personally, I'd rather they at least overflowed into inf or NaN instead as a warning.
So definitely use those large integer forms when they will help, but keep a careful eye out.
Walter Roberson

Walter Roberson (view profile)

on 14 Jan 2016
There are also some things that cannot be done with int64 or uint64. Like bin2dec() into one of them, or get a correct dec2bin()
>> dec2bin((uint64(2^33)^2) - uint64(1023))
ans =
10000000000000000000000000000000000000000000000000000000000000000
>> dec2bin((uint64(2^33)^2) - uint64(1024))
ans =
1111111111111111111111111111111111111111111111111111100000000000
dec2bin() converts to double() before it does the conversion to bits, which is a waste of computation power.