On iterated integer product (Q1198074)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 92128
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On iterated integer product |
scientific article; zbMATH DE number 92128 |
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
0.6820071935653687
0 references
0.6802406311035156
0 references
0.6795883774757385
0 references
0.668565571308136
0 references
0.6675153970718384
0 references
