On iterated integer product (Q1198074): Difference between revisions

Let \(z=\prod_{i=1}^ n z_ i\) be the product of \(n\) \(n\)-bit integers. It is known that \(z\) can be calculated in \(\text{DSPACE}(\log n\log\log n)\) but not whether it can be calculated in \(\text{DSPACE}(\log n)\). In the present note it is shown that the \(\log n\) highest order bits of \(z\), and the \(\log n\) lowest order bits of \(z\), can each be calculated in \(\text{DSPACE}(\log n)\).