On iterated integer product (Q1198074): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:30, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On iterated integer product |
scientific article |
Statements
On iterated integer product (English)
0 references
16 January 1993
0 references
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)\).
0 references
iterated product
0 references
complexity
0 references