-5

It is usually desirable to compute the greatest common divisor of two numbers efficiently, one such method being the Euclidean Algorithm. What about inefficient methods to find the $\gcd$ of two numbers? Have I found one? Equivalent to the "fifth grade and up" method, we could construct the prime factorization of each number in various ways, e.g. iteratively dividing primes out, and then list the prime factors as two multisets (repeats are allowed). Then the $\gcd$ and $\text{lcm}$ would be the intersection and union respectively of the two multisets.

Example: $$ \text{f}(1890) =\{ 2,3,3,3,5,7\} \\ \, \\ \text{f}(510510) =\{2,3,5,7,11,13,17\} \\ \, \\ \gcd(1890,510510) = \text{f}(1890) \cap \text{f}(510510) =\{2,3,5,7\} \\ \, \\ \text{lcm}(1890,510510) = \text{f}(1890) \cup \text{f}(510510) =\{2,3,3,3,5,7,11,13,17\} $$ where $\text{f(n)}$ stands for the multiset of primes in the factorization of $\text{n}$.

john
  • 860
  • 3
    Slowest? Successive tests, starting at the value of the lowest number, and stepping down by 1 and iterating? – David G. Stork Dec 11 '19 at 05:16
  • 1
    @DavidG.Stork You could waste more time by starting with the value of the largest number and stepping down. – Angina Seng Dec 11 '19 at 05:36
  • 3
    Ummm.... OK, then... start at the largest number and iterate UPWARD! And only after $10^{10000}$, return to the smaller numbers... (Why are we even thinking like this?) – David G. Stork Dec 11 '19 at 05:46
  • 1
    Shouldn’t the answer be that there is no such slowest procedure? For all algorithms $P$, one could construct a algorithm $P’$ that cost more time by adding trivial steps into $P$. – fantasie Dec 11 '19 at 06:09
  • 1
    Yes, I should re-title it to "what is a slow or inefficient method to compute the gcd". – john Dec 11 '19 at 06:10
  • In fact, as stated, there is no slowest algorithm in the strict sense. So, changing the title would be indeed helpful. It might be worth to think about "sensible" but inefficient algorithms, like trial division for factoring an integer, if some useful number-theoretical connections are shown by such an algorithm. A motivation for the question this way would be nice. – Peter Dec 11 '19 at 10:09

1 Answers1

3

Well, there's a reason one asks for the fastest way more than for the slowest way: you can always just stall for however long you like, and there's no well-defined notion of what counts as stalling and what's just a slow algorithm.

However, there is a very reasonable way to find the GCD that is decidedly slow. It's the greatest common divisor so... just list all of the divisors of each number, and find the biggest one they have in common. Pretty much no matter how you implement this, if you implement prime factorization with just as much care, listing all of the divisors is still a slower method.

Milo Brandt
  • 60,888