CODEWITHSUNDEEP
matlabvectorizationxor
bhavs
bhavs

Reputation: 2301

how to vectorise an xor operation in matlab

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

Upvotes: 0

Views: 1328

Answers (1)

Pablo
Pablo

Reputation: 8644

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.

Upvotes: 1

Related Questions