Fast dot product for a very special case

Posted by psihodelia on Stack Overflow See other posts from Stack Overflow or by psihodelia
Published on 2010-05-13T10:00:02Z Indexed on 2010/05/13 10:04 UTC
Read the original article Hit count: 267

Filed under:
|
|
|
|

Given a vector X of size L, where every scalar element of X is from a binary set {0,1}, it is to find a dot product z=dot(X,Y) if vector Y of size L consists of the integer-valued elements. I suggest, there must exist a very fast way to do it.

Let's say we have L=4; X[L]={1, 0, 0, 1}; Y[L]={-4, 2, 1, 0} and we have to find z=X[0]*Y[0] + X[1]*Y[1] + X[2]*Y[2] + X[3]*Y[3] (which in this case will give us -4).

It is obvious that X can be represented using binary digits, e.g. an integer type int32 for L=32. Then, all what we have to do is to find a dot product of this integer with an array of 32 integers. Do you have any idea or suggestions how to do it very fast?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about c