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

DOI10.1016/0020-0190(90)90228-PzbMath0695.68044MaRDI QIDQ910227

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A carry-free algorithm for finding the greatest common divisor of two integers
• Area-time lower-bound techniques with applications to sorting
• On problem transformability in VLSI
• Area—Time optimal VLSI integer multiplier with minimum computation time
• Information transfer and area-time tradeoffs for VLSI multiplication
• The Area-Time Complexity of Binary Multiplication
• Fast Algorithms for Manipulating Formal Power Series
• An algorithm with guaranteed convergence for finding a zero of a function