Can I believe the values of these large integers?

1 view (last 30 days)
Geoffrey Fox on 28 Dec 2022
Commented: John D'Errico on 28 Dec 2022
% coinStackv4
%
% Geoffrey T Fox
%
% https://projecteuler.net/problem=78
%
% Based on Bob's Excel work
%
% 27 December 2022
%
clear; clc; tic;
mAx = 10000;
daTa = zeros(mAx,mAx);
daTa(:,2) = 2;
daTa(:,1) = 1;
daTa(1,:) = 1;
daTa(3,3) = 3;
for idx = 3:mAx
daTa(2,idx) = 1 + floor(idx/2);
end
for idx = 3:mAx % mAx
jMid = 1 + idx;
for jdx = 3:mAx
if idx < jdx
daTa(idx,jdx) = daTa(idx-1,jdx)+ daTa(idx,jdx-idx);
elseif idx == jdx
daTa(idx,jdx) = daTa(idx-1,idx) + 1;
elseif idx > jdx
daTa(idx,jdx) = daTa(idx-1,jdx);
end
end
end
for idx = 1:mAx
if mod(daTa(idx,idx), 1000000) == 0
fprintf("%3.0f yields %15.0f\n",idx,daTa(idx,idx))
fprintf("above line is divisable by 1,000,000\n")
end
end
2301 yields 17022871133751703055227888846952967314604032000000
above line is divisable by 1,000,000
toc
Elapsed time is 1.925014 seconds.
Stephen23 on 28 Dec 2022
Edited: Stephen23 on 28 Dec 2022
"...which I understand to be the largest integer possibe under 64 bit."
The largest possible integer using DOUBLE() class is:
realmax()
ans = 1.7977e+308
Possibly you are actually thinking of the largest contiguous integer, which is 2^53:
flintmax()
ans = 9.0072e+15
"Can I believe the values of these large integers?"
You should never believe anything that any calculation tells you.

John D'Errico on 28 Dec 2022
Edited: John D'Errico on 28 Dec 2022
clear; clc; tic;
mAx = 10000;
daTa = zeros(mAx,mAx);
daTa(:,2) = 2;
daTa(:,1) = 1;
daTa(1,:) = 1;
daTa(3,3) = 3;
for idx = 3:mAx
daTa(2,idx) = 1 + floor(idx/2);
end
for idx = 3:mAx % mAx
jMid = 1 + idx;
for jdx = 3:mAx
if idx < jdx
daTa(idx,jdx) = daTa(idx-1,jdx)+ daTa(idx,jdx-idx);
elseif idx == jdx
daTa(idx,jdx) = daTa(idx-1,idx) + 1;
elseif idx > jdx
daTa(idx,jdx) = daTa(idx-1,jdx);
end
end
end
for idx = 1:mAx
if mod(daTa(idx,idx), 1000000) == 0
fprintf("%3.0f yields %15.0f\n",idx,daTa(idx,idx))
fprintf("above line is divisable by 1,000,000\n")
end
end
2301 yields 17022871133751703055227888846952967314604032000000
above line is divisable by 1,000,000
Should you "trust" that value? NO!!!!!!!!!!!
A double that is larger than 2^53-1 is not known exactly as an integer. So while doubles can represent floating point numbers larger than 2^53-1, as integers, that is the absolute limit. In terms of an integer, beyond that point all is garbage when you are working with integers.
I'm sorry, but if you think that number should be an integer, you are kidding yourself if you perform these computations using doubles. The least significant bits of that number will be garbage. Even an int64 or uint64 will fail you, due to overflows.
And sadly, trying to perform that large of a computation with either syms (or my own variable precision tools) will fail, due to memory (AND time) problems. That is a huge array, when each element of the array requires more memory than just a double.
What you actually are trying to do I have no clue, since your code has no comments. It is pretty much unreadable as such. If your goal is to compute moduli. For example, to know if a number is actually divisible by that relatively small integer, then you are doing this the wrong way. You need to compute the modulus at EVERY step. But I really have no clue what you are trying to do in the end.
John D'Errico on 28 Dec 2022
I feel like I am approaching that age far more quickly than I want. Anyway, PE problems are great fun, and pretty challenging.

Image Analyst on 28 Dec 2022
Your data is double. You can make it 64 bit unsigned integer like
daTa = zeros(mAx,mAx, 'uint64'); % Pass in the option to make it 'uint64'.
Jan on 28 Dec 2022
Remember, that Matlab stores numbers with about 16 valid digits as doubles in the IEEE754 format. This means, that the trailing zeros of 17022871133751703055227888846952967314604032000000 are not meaningful.
The used approach is not applicable.

Paul on 28 Dec 2022
What happens if you change this line to work in symbolic world? It will be slow .... (couldn't run here, exceeded the 55 second limit)
%daTa = zeros(mAx,mAx);
daTa = zeros(mAx,mAx,'sym');
Geoffrey Fox on 28 Dec 2022
I don't have that toolbox
'sym' requires Symbolic Math Toolbox.

Categories

Find more on Logical in Help Center and File Exchange

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by