Why this function infinity loop

%It give an integer x which contains d digits, find the value of n (n > 1) such that
%the last d digits of x^n is equal to x. Example x=2 so n=5 because 2^5=32 and last 
%digits of 32 is 2
%So why this take infinity loop
function n = bigNumRepeat(x)
d = length(num2str(x))
y=2
n=2
while 1
    y = y*x
    y = num2str(y)
    y = str2num(y(end - d + 1:end))
    if y==x
        break
    end
    n=n+1
end
end

Answer 1

[John D'Errico]

Because if your powers grow larger than 2^53-1 (i.e., flintmax), the number is no longer expressable exactly as an integer. All of those operations with str2num will produce garbage at some point. You CANNOT do this using doubles if the number grows too large.

[Nguyen Huy]

But in my loop,i only take last digit of power,so it cant grow larger than 2^53

[John D'Errico]

What numbers are you testing this on? Because you can easily overwhelm a double. That is, if d is as large as 8 or 9, this will still fail.

By the way, using str2num and num2str repeatedly is an extremely inefficient way to do any such computation. I would point out that mod does so very well. That is, mod(X,10^d) gives you the last d digits directly.

[John D'Errico]

As you can see, this code works reasonably well.

d = 1;
x = 2;
y = x;
n = 1;
flag = true;
modulus = 10^d;
while flag
  n = n + 1;
  y = mod(x*y,modulus);
  flag = y ~= x;
end
n

n = 5

Howver, if I used larger values for d and x, it could fail at some point. In that case, I might be forced to use symbolic computations.

[Nguyen Huy]

i tried this code,but it only true with x from 1-10,i dont understand why it fail

[Walter Roberson]

x = randi([11 99])

x = 93

d = length(num2str(x))

d = 2

y = x;
n = 1;
flag = true;
modulus = 10^d;
while flag && n <= 1000
  n = n + 1;
  y = mod(x*y,modulus);
  flag = y ~= x;
end
if flag
  fprintf('not found in 1000 iterations\n')
else
  n
end

n = 5

Note that x is not relatively prime with 10^d then there might not be a solution.

Answer 2

[Walter Roberson]

y=2

y = y*x

That does not give you x^n, it gives you 2 * x^n . You should initialize y = 1

See also https://www.mathworks.com/matlabcentral/fileexchange/932-big-x-y-modulo-function and see the symbolic powermod() function

[Nguyen Huy]

I tried y=1,but it only work when you know n.In this situation i dont know what is n,so if i take y=1 it will stop at the first loop because x^1=x and the condition is true,the loop is end

[Walter Roberson]

then initialize y=x