Why method "div" is faster thant "div2"?-CodePudding

Im trying to decipher why the div method is faster than the div2 method, and I cant find the reason.

def div2(num)
  [*1..num].select do |n|
    n if num % n == 0
  end
end

 p div2(58463982)

def div(num)
 result = []
 (1..num).each do |n|
   break if result.include?(num / n)
   result.concat([n, num / n]).uniq! if num % n == 0
 end
 result.sort!
end

p div(58463982)

CodePudding user response：

I will let others explain why div is faster than div2. I want to show how to compute the factors of the given natural number in a way that is considerably faster.

Every integer can be expressed as the product of a collection of prime numbers, each taken to a power of one more. We can use the method Prime::prime_division to obtain those prime numbers and powers. For example,

require 'prime'

arr = Prime.prime_division(58463982)
  #=> [[2, 1], [3, 2], [53, 1], [61283, 1]]

This means that:

(2**1) * (3**2) * (53**1) * (61283**1)
  #=> 58463982

One of those prime divisors of 58463982 equals, for example:

(2**1) * (3**2) * (53**0) * (61283**1)
  #=> 2 * 9 * 1 * 61283
  #=> 1103094

To confirm:

58463982 % 1103094
  #=> 0

Another would be

(2**0) * (3**1) * (53**1) * (61283**0)
  #=> 1 * 3 * 53 * 1
  #=> 159

We find that all factors of a given number can be computed (combinatorially) as follows, using the methods Array#product and Enumerable#reduce (a.k.a. inject):

def all_factors(n)
  primes, exponents = Prime.prime_division(n).transpose
  first_exp_range, *rest_exp_range = exponents.map { |e| [*0..e] }
  first_exp_range.product(*rest_exp_range).map do |exps| 
    primes.zip(exps).reduce(1) { |t,(p,e)| t*(p**e) }
  end.sort
end

Depending on requirements, .sort at the end may not be required.

We may test:

require 'time'

t = Time.now
all_factors(58463982)
p Time.now - t
  #=> [1, 2, 3, 6, 9, 18, 53, 106, 159, 318, 477, 954, 61283, 122566,
  #    183849, 367698, 551547, 1103094, 3247999, 6495998, 9743997,
  #    19487994, 29231991, 58463982]
  #
  #=> 0.001405 (seconds)

By constrast, computing the factors of 58463982 with div2 and div required 4.467112 and 0.021103 seconds, respectively.

This is clearly much faster than div and div2.

We may step through the example to view the calculations being performed.

n = 58463982

then

primes, exponents = Prime.prime_division(n).transpose
  #=> [[2, 3, 53, 61283], [1, 2, 1, 1]]

primes
  #=> [2, 3, 53, 61283]
exponents
  #=> [1, 2, 1, 1]

Then,

first_exp_range, *rest_exp_range = exponents.map { |e| [*0..e] }
  #=> [[0, 1], [0, 1, 2], [0, 1], [0, 1]]

first_exp_range
  #=> [0, 1]
rest_exp_range
  #=> [0, 1, 2], [0, 1], [0, 1]

Then

a = first_exp_range.product(*res_exp_range)
  #=> [[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1],
  #    [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1],
  #    [0, 2, 0, 0], [0, 2, 0, 1], [0, 2, 1, 0], [0, 2, 1, 1],
  #    [1, 0, 0, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 0, 1, 1],
  #    [1, 1, 0, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 1],
  #    [1, 2, 0, 0], [1, 2, 0, 1], [1, 2, 1, 0], [1, 2, 1, 1]]

Then,

 b = a.map { |exps| primes.zip(exps).reduce(1) { |t,(p,e)| t*(p**e) } }
   #=> [1, 61283, 53, 3247999, 3, 183849, 159, 9743997, 9, 551547,
   #    477, 29231991, 2, 122566, 106, 6495998, 6, 367698, 318,
   #    19487994, 18, 1103094, 954, 58463982]

To view the result sorted,

b.sort
  #=> [1, 2, 3, 6, 9, 18, 53, 106, 159, 318, 477, 954, 61283, 122566,
  #    183849, 367698, 551547, 1103094, 3247999, 6495998, 9743997,
  #    19487994, 29231991, 58463982]

CodePudding user response：

The div2 method create a list from 1 to num then iterates over all of the elements in it.

The div method can break early, and so does not have to iterate as many times.