5
$\begingroup$

Suppose that I have an array $\{a_i\}$ of $n$ elements, each $k$ bits wide, and an array $\{b_i\}$ of $n$ elements, each $\lceil\log_2n\rceil\le k$ bits wide. I need a boolean circuit which will compute an array $\{c_i\}$, where $c_i=a_{b_i}$. I'm interested in a circuit with as few gates (with fan-in of 2) as possible.

There is a trivial solution with $O(kn^2)$ gates. Also, if it is known that $\{b_i\}$ is a permutation, it is possible to use a sorting network to solve the problem with only $O(kn\log n)$ gates, but with a large constant factor. I don't know how to extend this solution to the general case. Also, a circuit can do more that a sorting network, so it could potentially be more efficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.