### A lower bound for integer greatest common divisor computationsA lower bound for integer greatest common divisor computations

Access Restriction
Subscribed

 Author Mansour, Yishay ♦ Schieber, Baruch ♦ Tiwari, Prasoon Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1991 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Floor operation ♦ Greatest common devisor ♦ Lower bound ♦ Mod operation ♦ Truncation Abstract It is proved that no finite computation tree with operations { +, -, *, /, mod, < } can decide whether the greatest common divisor (gcd) of $\textit{a}$ and $\textit{b}$ is one, for all pairs of integers $\textit{a}$ and $\textit{b}.$ This settles a problem posed by Gro¨tschel et al. Moreover, if the constants explicitly involved in any operation performed in the tree are restricted to be “0” and “1” (and any other constant must be computed), then we prove an &OHgr;(log log $\textit{n})$ lower bound on the depth of any computation tree with operations { +, -, *, /, mod, < } that decides whether the gcd of $\textit{a}$ and $\textit{b}$ is one, for all pairs of $\textit{n}-bit$ integers $\textit{a}$ and $\textit{b}.A$ novel technique for handling the truncation operation is implicit in the proof of this lower bound. In a companion paper, other lower bounds for a large class of problems are proved using a similar technique. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1991-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 38 Issue Number 2 Page Count 19 Starting Page 453 Ending Page 471

#### Open content in new tab

Source: ACM Digital Library