On iterated integer product

DOI10.1016/0020-0190(92)90035-TMaRDI QIDQ1198074zbMATH OpenFDO

Authors Bruce Litow

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90035-T

zbMATH Keywords

complexityiterated product

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Review text

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)\).

Recommendations

• Bits and relative order from residues, space efficiently
• On the complexity of integer matrix multiplication
• Integer multiplication in time \(O(n\log n)\)
• New results on the complexity of the middle bit of multiplication
• On realizing iterated multiplication by small depth threshold circuits

Cites work

• A taxonomy of problems with fast parallel algorithms
• Fast Parallel Arithmetic via Modular Representation
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• Log Depth Circuits for Division and Related Problems
• Logarithmic Depth Circuits for Algebraic Functions
• On Relating Time and Space to Size and Depth
• On uniform circuit complexity

Cited in

(5)

• Nondeterministic NC^1 computation
• Bits and relative order from residues, space efficiently
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Computing a context-free grammar-generating series
• ON ITERATED PRODUCT SETS WITH SHIFTS

This page was built for publication: On iterated integer product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198074)