Gcd of $314159265358979323846264338$ and $271828182845904523536028747$?

Solution 1:

Euclid's algorithm is very fast, running in (at worst) time proportional to the length of the input numbers, and is also simple.

To find $GCD(a,b)$, where $a>b$, you first see if $b=0$; if so, the answer is simply $a$. Otherwise divide $a$ by $b$, yielding a remainder $r$. The answer is then the same as $GCD(b, r)$, which you can calculate by the same method.

Pseudo-pseudocode:

function gcd(a, b) {
  while (b ≠ 0) {
    r = a mod b;
    a = b;
    b = r;
  }
  return a;
}

Solution 2:

Given that these numbers are $\lfloor{10^{26}\pi}\rfloor$ and $\lfloor{10^{26}e}\rfloor$, there's probably not any faster trick than the Euclidean algorithm (using the continued fraction expansion of $\pi/e$ is the equivalent computation), which is probably what Stein is leading up to. When he says by any means, I think using sage or Wolfam Alpha is fair game. It is quite an impressively efficient algorithm, although there exist special implementations such as binary GCD that may or may not be more efficient, depending on your CPU.

Gcd of $314159265358979323846264338$ and $271828182845904523536028747$?

Solution 1:

Solution 2:

Related

Recent Posts