Where's the bottleneck? performance disparities... (Project Euler #12)

Question

The following is my solution for Project Euler question #12:

def factor this_number, number=nil, *factors
  number = this_number if number.nil?
  m=2
  loop do 
    break factors << m if number % m == 0
    m+=1
  end
  arr = factors.flatten
  arr.inject(:*) != this_number ? factor(this_number, (number/factors.last), factors) : arr.uniq.collect {|k| arr.count(k)+1 }.inject(:*)
end

def highly_divisible_triangular_number number
  n = 2
  loop do
    num = (n*(n+1)/2)
    r = factor(num)
    break num if (r >= number)
    n+=1
  end
end

puts Benchmark.measure { p highly_divisible_triangular_number(n) }

This solution is courtesy of Zachary Denton:

require 'mathn' 

class Integer 
  def divisors
    return [1] if self == 1
    primes, powers = self.prime_division.transpose 
    exponents = powers.map{|i| (0..i).to_a} 
    divisors = exponents.shift.product(*exponents).map do |powers| 
      primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) 
    end 
    divisors.sort.map{|div| [div, self / div]} 
  end
end

triangles = Enumerator.new do |yielder|
  i = 1
  loop do
    yielder.yield i * (i + 1) / 2
    i += 1
  end
end

puts Benchmark.measure { p triangles.detect { |t| t.divisors.count > n } }

Benchmark results:

__projecteuler: ruby 'problem_12a.rb' 100
73920
  0.010000   0.000000   0.010000 (  0.009514) [MINE]
73920
  0.020000   0.000000   0.020000 (  0.028339)

__projecteuler: ruby 'problem_12a.rb' 200
2031120
  0.120000   0.000000   0.120000 (  0.123996) [MINE]
2031120
  0.250000   0.010000   0.260000 (  0.251311)

__projecteuler: ruby 'problem_12a.rb' 300
2162160
  0.120000   0.000000   0.120000 (  0.122242) [MINE]
2162160
  0.260000   0.000000   0.260000 (  0.259200)

__projecteuler: ruby 'problem_12a.rb' 400
17907120
  0.730000   0.000000   0.730000 (  0.725883) [MINE]
17907120
  1.050000   0.000000   1.050000 (  1.057079)

__projecteuler: ruby 'problem_12a.rb' 500
76576500
  2.650000   0.010000   2.660000 (  2.657921) [MINE]
76576500
  2.790000   0.000000   2.790000 (  2.795859)

__projecteuler: ruby 'problem_12a.rb' 600
103672800
  3.470000   0.010000   3.480000 (  3.484551) [MINE]
103672800
  3.420000   0.000000   3.420000 (  3.419714)

__projecteuler: ruby 'problem_12a.rb' 700
236215980
  7.430000   0.010000   7.440000 (  7.438317) [MINE]
236215980
  6.020000   0.020000   6.040000 (  6.046869)

__projecteuler: ruby 'problem_12a.rb' 800
842161320
 24.040000   0.020000  24.060000 ( 24.062911) [MINE]
842161320
 14.780000   0.000000  14.780000 ( 14.781805)

Question

As you can see from the benchmark results my solution is faster up to N 500 but gets annihilated with >N. Can someone help me understand why?

Update For those who think that the bottleneck is related to recursion, well try again. factor method without recursion the and benchmark does not show improvement:

__projecteuler: ruby 'problem_12a.rb' 800
842161320
 24.960000   0.020000  24.980000 ( 24.973017) [MINE (w/o recursion)]
842161320
 14.780000   0.030000  14.810000 ( 14.807774)


def factor this_number
  number,arr=this_number,[]

  done = false
  until done
    m=2
    loop do 
      break arr << m if number % m == 0
      m+=1
    end
    arr.inject(:*) != this_number ? number = number/arr.last : done = true
  end

  arr.uniq.collect {|k| arr.count(k)+1 }.inject(:*)
end

Answer 1

Your bottleneck is in your factorization method. (Your highly_divisible_triangular_number loop and his triangles.detect loop are basically identical.)

Where your factorization could be computationally faster

(Sorry, I just had to refactor your code. Everything is still computationally the same.)

def num_factors(number, dividend=nil, prime_factors_found=[])
  dividend = number if dividend.nil?

  smallest_prime_factor = (2..dividend).find { |divisor| dividend % divisor == 0 } # 1.
  prime_factors_found << smallest_prime_factor

  all_prime_factors_found = prime_factors_found.inject(:*) == number
  if !all_prime_factors_found
    return num_factors(number, dividend / prime_factors_found.last, prime_factors_found)
  end

  prime_factor_powerset_size = prime_factors_found.uniq.map do |prime_factor|
    prime_factors_found.count(prime_factor) + 1                                    # 2.
  end.inject(:*)

  return prime_factor_powerset_size
end

1. You don't need to check every number. You can check 2 once and then start skipping even numbers. You can then check 3 once after that to only check 2 out of every 6 numbers.
   You're also re-computing a lot of numbers here. For example, every time divisor is a 11 (a prime number), you'll run through the full loop only to discover once again that 11 is indeed a prime number. Worst-case, for n primes, you'll count up to n^2 to verify all of them.
2. The map is one full pass through the array of prime factors. But each pass, the count operation also requires takes a pass through the array. This means for an array of 10 items (O(n)), you look up values in the array 100 times (O(n^2)). Checking for occurrences can be done in a single pass instead.

Where his factorization saves computation (and where it doesn't)

You might be wondering why his code is faster then, since it contains the following nested loop:

divisors = exponents.shift.product(*exponents).map do |powers| 
  primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) 
end

In the same vein as your #2, he has linear pass work done for each element inside another linear pass, i.e. this part of the computation is also O(n^2). He wastes computation by actually computing all the divisors when all that's needed is the total number there will be in the end. But anyway in the end, it appears that this section is equal in asymptotic performance.

It turns out that the difference between your versions that lets him break ahead in the end is #1 - the prime tester/generator. While you have a custom loop that checks every single number over and over again, he's used a prime tester/generator in the Ruby library. If you'd like to see how it's implemented, you can find the source on your computer where ruby is installed at <ruby root>/lib/ruby/<version>/prime.rb.

Here is a version of your code that uses the prime_division method:

require 'prime'
def num_factors2(number, dividend=nil, prime_factors_found=[])
  dividend = number if dividend.nil?

  smallest_prime_factor = dividend.prime_division.first.first    # this is the only change
  prime_factors_found << smallest_prime_factor

  all_prime_factors_found = prime_factors_found.inject(:*) == number
  if !all_prime_factors_found
    return num_factors2(number, dividend / prime_factors_found.last, prime_factors_found)
  end

  prime_factor_powerset_size = prime_factors_found.uniq.map do |prime_factor|
    prime_factors_found.count(prime_factor) + 1
  end.inject(:*)

  return prime_factor_powerset_size
end

And the benchmarks on my system:

Benchmark.measure { (2..50000).map { |i| num_factors(i) } }
 =>  17.050000   0.020000  17.070000 ( 17.079428)
Benchmark.measure { (2..50000).map { |i| num_factors2(i) } }
 =>   2.630000   0.010000   2.640000 (  2.672317)

Extra

Using a combination of your two methods, I found a cool way to express the problem as a one-liner in ruby! (That's also really fast!)

n = (2..(1.0/0)).find { |i| (i*(i+1)/2).prime_division.inject(1) { |p,i| p*i[1]+p } > 500 }

Where n is the nth triangular number, i.e. triangle(n) = n * (n + 1) / 2.

Answer 2

Ruby is notorious for performing bad with recursion. You could perhaps read this post to get a few pointers on how to solve it.