The area-time complexity of the greatest common divisor problem: A lower bound

DOI10.1016/0020-0190(90)90228-PMaRDI QIDQ910227zbMATH OpenFDO

Authors Carla Neaderhouser Purdy, George B. Purdy

Publication date 1990

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

zbMATH Keywords

greatest common divisorinteger arithmeticarea-time complexityarea-time lower boundsVLSI model of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4126699
• scientific article; zbMATH DE number 4057005
• A modular integer GCD algorithm
• A lower bound for integer greatest common divisor computations
• scientific article; zbMATH DE number 3915623

Cites work

• scientific article; zbMATH DE number 3887073 (Why is no real title available?)
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 4126699 (Why is no real title available?)
• A carry-free algorithm for finding the greatest common divisor of two integers
• An algorithm with guaranteed convergence for finding a zero of a function
• Area-time lower-bound techniques with applications to sorting
• Area—Time optimal VLSI integer multiplier with minimum computation time
• Fast Algorithms for Manipulating Formal Power Series
• Information transfer and area-time tradeoffs for VLSI multiplication
• On problem transformability in VLSI
• The Area-Time Complexity of Binary Multiplication

Cited in

(2)

• scientific article; zbMATH DE number 3960996 (Why is no real title available?)
• scientific article; zbMATH DE number 1113848 (Why is no real title available?)

This page was built for publication: The area-time complexity of the greatest common divisor problem: A lower bound

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