Efficient construction of positive and negative matrix

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.

[Bruno Luong]

Please check/test the code you post, it seems having typo (dec2bin) and error (remove '0' missing), so that we know exactly what you are trung to compute.

[John D'Errico]

@Bruno Luong

de2bi is a function in MATLAB, though not in MATLAB proper. It resides in a toolbox you may not have, though it serves a similar purpose, just not creating a character result but a numeric array. It also flips the result, so the lowest order bits are first.

which de2bi

/MATLAB/toolbox/comm/comm/de2bi.m

de2bi([2 3 5 7 11],6)

ans = 5×6

0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0

[Bruno Luong]

@John D'Errico thanks for clearing that out.

[Adam Shaw]

Thanks for switching the dec2bin to de2bi, sorry I was a bit lazy rewriting the code here and let that slip through!

Answer 1

[Steven Lord]

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]

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).

Answer 2

[Bruno Luong]

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