What is a faster way to iterate through large numbers in Ruby?

Question

Im learning Ruby and currently this is my exercise:

Using any pair of numbers, prove integer n is a Perfect Power. If there are no pairs, return nil.

In mathematics, a perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m > 1, and k > 1 such that mk = n

Currently this is my code:

def pp(n)
# [m,k] m^k

idx1=2
  while idx1 <n
  idx2=2
    while idx2<n
        if idx1**idx2 == n
          ans = [idx1,idx2]
          break
        end
     idx2 +=1
    end
    idx1 +=1
  end
return ans

end

I would like to write this such that for a given random huge number my repl.it does not time out.

Thank you in advance!

                                      ###Edit###

There is a mention(How to make perfect power algorithm more efficient?) of this problem in the context of Python. As much as I tried to understand it and translate the syntax, I could not. I hope that asking this question will also help those studying Ruby as much as it has helped me.

Answer 1

Wanna solve really large numbers like this instantaneously? With a much shorter solution?

pp(908485319620418693071190220095272672648773093786320077783229)
=> [29, 41]

Then read on :-). It'll be a little journey...

---

Let's first just make your code nicer without changing the logic at all. Just rename your variables to m and k and loop with each:

def pp1(n)
  ans = nil
  (2...n).each do |m|
    (2...n).each do |k|
      if m**k == n
        ans = [m, k]
        break
      end
    end
  end
  ans
end

Now checking n up to 200 takes me about 4.1 seconds (same as your original):

> require 'benchmark'
> puts Benchmark.measure { (1..200).each { |n| pp1(n) } }
  4.219000   0.000000   4.219000 (  4.210381)

First optimization: If we find a solution, return it right away!

def pp2(n)
  (2...n).each do |m|
    (2...n).each do |k|
      if m**k == n
        return [m, k]
      end
    end
  end
  nil
end

Sadly it still takes 3.9 seconds for the test. Next optimization: If m^k is already too large, let's not try even larger k!

def pp3(n)
  (2...n).each do |m|
    (2...n).each do |k|
      break if m**k > n
      if m**k == n
        return [m, k]
      end
    end
  end
  nil
end

Now it's so fast that I can run the test 1000 times in about the same time:

> puts Benchmark.measure { 1000.times { (1..200).each { |n| pp3(n) } } }
  4.125000   0.000000   4.125000 (  4.119359)

Let's instead go up to n = 5000:

> puts Benchmark.measure { (1..5000).each { |n| pp3(n) } }
  2.547000   0.000000   2.547000 (  2.568752)

Now instead of computing m**k so much, let's use a new variable that we can update more cheaply:

def pp4(n)
  (2...n).each do |m|
    mpowk = m
    (2...n).each do |k|
      mpowk *= m
      break if mpowk > n
      if mpowk == n
        return [m, k]
      end
    end
  end
  nil
end

Sadly, this almost didn't make it faster at all. But there's another optimization: When m^k is too large, then not only can we forget trying this m with even larger k. If it was too large for k=2, i.e., m² is already too large, then we don't need to try even larger m, either. We can stop the whole search. Let's try that:

def pp5(n)
  (2...n).each do |m|
    mpowk = m
    (2...n).each do |k|
      mpowk *= m
      if mpowk > n
        return if k == 2
        break
      end
      if mpowk == n
        return [m, k]
      end
    end
  end
  nil
end

This now does the 5000-test in about 0.07 seconds! We can even check all numbers up to 100000 in 6 seconds:

> puts Benchmark.measure { (1..100000).each { |n| pp5(n) } }
  5.891000   0.000000   5.891000 (  5.927859)

Anyway, let's look at the big picture. We're trying m = 2.. and for each m we try to find a k so that m**k == n. Hey, math has a solution for that! We can compute k as k=log_m(n). Let's do it:

def pp6(n)
  (2...n).each do |m|
    k = Math.log(n, m).round
    return if k < 2
    return [m, k] if m**k == n
  end
  nil
end

Measure again:

> puts Benchmark.measure { (1..100000).each { |n| pp6(n) } }
 28.797000   0.000000  28.797000 ( 28.797254)

Hmm, slower. Ok, another idea: Let the outer loop be for k instead of m. Now for given n and k, how do we find m such that m^k = n? Take the k-th root!

def pp7(n)
  (2...n).each do |k|
    m = (n**(1.0 / k)).round
    return if m < 2
    return [m, k] if m**k == n
  end
  nil
end

Measure again:

> puts Benchmark.measure { (1..100000).each { |n| pp7(n) } }
  0.828000   0.000000   0.828000 (  0.836402)

Nice. How about 400000, which my factorization solution in my other answer solved in 2.9 seconds?

> puts Benchmark.measure { (1..400000).each { |n| pp(n) } }
  3.891000   0.000000   3.891000 (  3.884441)

Ok that's a bit slower. But... with this solution here we can solve really large numbers:

pp7(1000000035000000490000003430000012005000016807)
=> [1000000007, 5]
pp7(908485319620418693071190220095272672648773093786320077783229)
=> [29, 41]
> pp7(57248915047290578345908234051234692340579013460954153490523457)
=> nil

And all these result appears immediately. The factorization solution solves the 29⁴¹ case quickly as well, but for the 1000000007⁵ case and the randomly-typed case at the end it's slow, because the factorization is slow.

---

P.S. Note that the logarithm and square root get us floating point numbers. That could lead to problems with very large numbers. For example:

irb(main):122:0> pp7(10**308 + 1)
=> nil
irb(main):123:0> pp7(10**309 + 1)
FloatDomainError: Infinity
        from (irb):82:in `round'
        from (irb):82:in `block in pp7'
        from (irb):81:in `each'
        from (irb):81:in `pp7'
        from (irb):123
        from C:/Ruby24/bin/irb.cmd:19:in `<main>'

In this case, that's because 10³⁰⁹ simply is too large for floats:

> (10**309).to_f
=> Infinity

Also, there could be accuracy problems with large enough numbers. Anyway, you can solve these issues by writing integer-versions for logarithm and root. But that's a whole other issue.

Answer 2

You could use the prime factorization:

require 'prime'

def pp(n)
  pd = n.prime_division
  k = pd.map(&:last).reduce(&:gcd)
  return if k < 2
  m = pd.map { |p, e| p**(e / k) }.reduce(:*)
  [m, k]
end

For example for n = 216 you get [[2, 3], [3, 3]], meaning 216 = 2³⋅3³. Then find the greatest common divisor of the exponents, which is the greatest possible exponent k. If it's less than 2, you lose. Otherwise, compute the base m from the pieces.

Yours takes my PC about 4.1 seconds to check the numbers from 2 to 200. Mine takes about 0.0005 seconds for that, and takes about 2.9 seconds to check the numbers 2 to 400000.