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.


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.