how to vectorise an xor operation in matlab

Question

I have run the following code in Profiler in Matlab and it is quite essential for me to vectorise this code as I feel that this is an unnecessary for loop.

I have 2 matrices G and source_data. every column in G will determine the rows which I need to pick up from source_data and xor them together.

I am creating G and source_data using the following piece of code

for i=1:10
 source_data(i,:)=rand(1,20)<.8;
end 

for i=1:15
 G(:,i)=rand(10,1)<.9;
end

I am performing an xor operation using the for loop below:

z=1;
while(i<=15) 
for j=1:10
    if(G(j,i)==1)
       intersum(z+1,:)=xor(intersum(z,:), source_data(j,:));
        z=z+1;
    end
end
C(i,:)=intersum(z,:);
i=i+1;
end

Is there a way to vectorise this code ? The time lag is acceptable for a small matrix but for large matrices this code is quite in efficient.

Thanks,

Bhavya

What is i and what is K in the last loop? xor itself is already vectorized, perhaps it's helpful for you: mathworks.de/help/techdoc/ref/xor.html Otherwise you could have a look at arrayfun — tim
@Alexandrew thanks for pointing this out editing the above question — bhavs

Pablo Pablo · Accepted Answer · 2012-02-01T10:00:32

Assuming that:

i starts at 1
intersum starts at zeros

Here's a vectorized form of you code that produces the exact same result as your original:

function C = version_a()
  source_data = rand(10,20)<.8;
  G = rand(10,15)<.9;

  intersum = zeros(1, size(source_data,2));
  z = 1;
  i = 1;
  while i <= 15
    for j=1:10
        if(G(j,i)==1)
           intersum(z+1,:)=xor(intersum(z,:), source_data(j,:));
            z=z+1;
        end
    end

    C(i,:)=intersum(z,:);
    i=i+1;
  end
  ret = C;
end

function C = version_b()
  source_data = rand(10,20)<.8; % Can initialize in a single call
  G = rand(10,15)<.9;           % Same here
  C = zeros(size(G,2),size(source_data,2));

  C(1,:) = mod(sum(source_data(G(:,1),:)),2);
  for i = 2:15
    C(i,:) = mod(C(i-1,:) + sum(source_data(G(:,i),:)),2);
  end
end

To check the timing of both versions I used this test function:

function ret = xor_test()
  ret = 0;

  seed = 123456789;
  laps = 10000;

  tic
  for i = 1:laps
    RandStream.getDefaultStream.reset(seed);
    a = version_a();
  end
  toc

  tic
  for i = 1:laps
    RandStream.getDefaultStream.reset(seed);
    b = version_b();
  end
  toc

  ret = ret + sum(sum(b ~= a));
end

And I got the following timings on my machine:

Elapsed time is 13.537738 seconds.
Elapsed time is 2.302747 seconds.
ans =
     0

Now to why I changed it that way...

A xor operation over an array of logicals is pretty much checking the parity of the sum (treating true values as 1). Furhtermore, intersum is being used as an accumulator, so there's who's values eventually ends up in C so we skip it altogether. Taking the rows for which G(j,i) is 1 can be done by logical indexing.

And finally, even if you don't like this proposed version, I'd recommend preallocating your your C and intersum vectors (in case you're not doing so already). That has made a lot of difference for me in the past.

how to vectorise an xor operation in matlab

1 Answers