In this paper we first give a uniform AC0 algorithm which uses partial sums to compute multiple addition. Then we use it to show that multiple addition is computable in uniform TC0 by using count only once sequentially. By constructing bit matrix for multiple addition, we prove that multiple product with poly-logarithmic size is computable in uniform TC0 (by using count k+1 times sequentially when the product has size O((logn)k)). We also prove that multiple product with sharply bounded size is computable in uniform AC0.
展开▼
