Find doesn't seem to work with Matrix larger than 127x127

[i,j]=find(A);

A is matrix of size n where n varies in size from 100 to 2000 (each time calculation is completed it's incremented by 50). For n = 100 all is fine, but once I reach 150 i and j only record values to 127.

If it is relevant A is matrix of adjacency for complete binary tree of n nodes

[John D'Errico]

I'm sorry, but that would seem to be wrong. Find does not have that limit. So you would need to tell us more.

M = rand(150); M = M + M';
G = graph(M);
A = adjacency(G);
[I,J] = find(A);
max(I),max(J)

ans = 150

ans = 150

It may be that in some way, an int8 variable has been created. That would limit a result to 127, because int8 overflows above 127.

int8(129)

ans = int8 127

[Bruno Luong]

can you type

A(end) = 1;
[i,j] = find(A),
size(A)

and report the output when the issue occurs (according to your judgement)

[Bartosz]

Well that's the output.

Similarly for i variable, everything is fine untill it hits 63 - for i and 127- for j, which are both 339th values in their corresponding vectors. However the code you've send (you == Bruno Luong) added 150 at 340th place.

I'm also sending my code. In mean time I've been working on solution that doesn't use find(), that's the commented part of code. This new solution of mine doesn't crash, but still I cannot achive Covrage above 127.

[Bruno Luong]

FIND works just fine. Just your A matrix filling does something that you are not expected.

max(i) = 150, max(j) = 127

[Bartosz]

Thanks, problem has been solved. Sorry for your wasted time on such a simple mistake of mine

Answer 1

[Walter Roberson]

I am certain that find works. I speculate that you are putting the values together in an array with values of datatype int8. When you put together values of mixed data type, the output result is typically the most restricted data type of all of the inputs.

[Walter Roberson]

    lastfullrow=floor(log2(n));%for n=100 it should be 6
    usednumbers=(2.^(lastfullrow-1))-1;%that is 31 because it's

when n = 150, lastfullrow = 7 and usednumbers = 63

    parents=usednumbers+1;%how many nodes
    unused=n-usednumbers-parents;%unused nodes left for las

so 64 for parents and 150-63-64 = 23 for unused. unused can be increased later under certain conditions for the case

   doublechildren=unused1-parents;%how many nodes will have 2 children

unused1 = 23, parents = 64, so unused1-parents is negative and so doublechildren will be negative.

    elseif c<=usednumbers+parents

You have

    if c<=usednumbers

which is going to be false beyond 63,

    elseif c<=usednumbers+parents %here we fill last full row

which is going to be false beyond 63+64 = 127 -- notice that magic number 127 is the value you were referring to earlier

      else%full rows with full row beneath them
                A(c,floor(c/2))=1;%parent node
                A(c,2*c)=1;
                A(c,(2*c)+1)=1;

that is inside the part where c is at most usednumbers, so you write to at most column 2*usednumbers+1 but whith parents = usednumber+1 then that value is at most usednumbers+parents = 127

How about the

           elseif c<=usednumbers+parents %here we fill last full row

section, does it ever write past column 127 ?

             if doublechildren>0 %case one
                ...
                A(c,(2*c)+1)=1;

Potentially... but doublechildren is negative from the start, so that clause is never executed.

              else    %case 2
                ...
                if Q==1
                    A(c,unused*2)=1;
                    unused=unused+1;
                    Q=0;
                else
                    A(c,2*(unused-1)+1)=1;

so maybe... it depends on how many times that section gets executed. You flip back and forth between Q = 0 and Q = 1, so unused gets incremented at most (unusednumbers+parents - unusednumbers)/2 = 64/2 = 32 times. It started at 23, and 32 is added to unused so unused ends at 55, and (55-1)*2+1 = 109 so that code cannot write beyond column 109 -- which is less than was already written into in the "else%full rows with full row beneath them" section.

So nothing beyond column 127 is written into.

    [i,j] = find(A),
    B=[j,i];

j cannot exceed 127 because you did not write beyond column 127, and B is put first in B so the first column in B cannot be more than 127.

        startnode=randi([1,n]); 

but that can generate random values up to the full 150, and your code breaks when

            [o,p]=find(B(:,1)==startnode);

is empty .

[Bartosz]

Huge thanks! I didn't see this one. If I ever met you, I'd buy you a beer. Once again thanks a lot

[Walter Roberson]

I would suggest that your code would probably be clearer if you were to build A as being n by 2 by something -- you could reshape it back afterwards.

Answer 2

[Jan]

This observation does not match the facts:

X = randi([0, 1], 150, 150);
[i,j] = find(X);
max(i)

ans = 150

max(j)

ans = 150

If you observe a very strange behavior, which implies, that hundrets of thousands Matlab users did not notice a serious problem in standard function for many years, you can be sure, that your observation is wrong.

If no indices > 127 are found in your case, there are no non-zeros with such indices. The limit of 127 sounds like the maximum value of int8 values.

Please post some code, which reproduces the problem. I'm sure, that the proble ist not the find() command, but hidden in your code.