# Efficient construction of positive and negative matrix

3 views (last 30 days)
Adam Shaw on 6 Nov 2022
Edited: Bruno Luong on 7 Nov 2022
I am trying to efficiently constuct a vector along the lines of the following paradigmatic code:
% Setup
N = 20;
B = de2bi((1:2^N)-1,N);
P = [1 3 8 18]; % Some random integers from 1 to N
% Actual code to optimize
tic;
C = 2*B-1;
D = C(:,P);
R = prod(D,2); % result
toc;
Essentially, the desired result is to construct a binary positive/negative vector, which is negative when an odd number of bits within a given subset (P) are 0, and is positive otherwise. Any help would be appreciated - my implementation here is fine, but only works decently up to N in the low to mid 20s. I have tried tricks with bitand, bitset, etc but have not found anything more efficient on my own.
I'll add that ultimately what I actually want is to take the sum of this vector R with another vector, A, like so:
A = rand(2^N,1);
R2 = sum(R.*A); % Actual result I ultimately want
This is similar to a recent question I asked here (https://www.mathworks.com/matlabcentral/answers/1826493-efficient-multiplication-by-large-structured-matrix-of-ones-and-zeros?s_tid=srchtitle), but is made more complicated because the vector R is positive/negative instead of binary, but perhaps similar tricks apply. Any solution which also addresses constructing R2 would be very appreciated.
Adam Shaw on 6 Nov 2022
Thanks for switching the dec2bin to de2bi, sorry I was a bit lazy rewriting the code here and let that slip through!

Steven Lord on 6 Nov 2022
Instead of creating a very large binary matrix in order to extract a handful of columns, why not use bitget?
x = (0:7).'
x = 8×1
0 1 2 3 4 5 6 7
b = [bitget(x, 3) bitget(x, 2) bitget(x, 1)]
b = 8×3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Adam Shaw on 7 Nov 2022
At least on my machine, this is slower than the method based on using the pregenerated binary matrix (which is assumed to be given, and not part of the timing).

Bruno Luong on 7 Nov 2022
Edited: Bruno Luong on 7 Nov 2022
If your B is given then the 2nd method in this script is faster
P = [1 3 8 18];
N = 20;
B = fliplr(dec2bin((1:2^N)-1,N)-'0');
tic
C = 2*B-1;
D = C(:,P);
R2 = prod(D,2);
toc
Elapsed time is 0.054876 seconds.
tic
x = zeros(N,1);
x(P) = 2;
R3 = 1-mod(B*x,4);
toc
Elapsed time is 0.015032 seconds.
isequal(R2,R3)
ans = logical
1