0
\$\begingroup\$

Why will this code work for a smaller multiple like 10 but time out for anything over 13? Can this code be revised to work for larger numbers?

(I have an alternate solution but wanted to see if this code could be fixed to work for more multiples.)

#2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

multiple = 10
y = multiple
hash = Hash.new(0)

loop do
    if hash.has_value?(multiple) || y == 0
        break
    end
    for x in 1..multiple do
        if y % x == 0
            hash[y] += 1
        end
    end
    y += multiple
end

puts "Smallest number = #{y - multiple}"
hash.has_value?(multiple)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ This code runs and has the correct output, it is just very, very slow \$\endgroup\$
    – Zack
    Dec 8, 2016 at 20:40
  • 1
    \$\begingroup\$ I don't think this should have been put on hold, it's working code and he's asking for a review to improve performance. \$\endgroup\$
    – user122352
    Dec 8, 2016 at 20:41
  • \$\begingroup\$ Can this code be revised to work for larger numbers? - I took this to mean that this code doesn't operate as such and you're asking about making that possible. \$\endgroup\$
    – Jamal
    Dec 8, 2016 at 21:03

1 Answer 1

1
\$\begingroup\$

Theoretical Code Evaluation

Let's do some math to see how many operations you are doing.

I'm going to use m as my variable for whatever value you assigned to multiple

You have a loop that for every multiple of m, it does m modulus tests. For m = 10, the correct answer is 2520, so we can calculate that you code did 2520/m*m = 2520 operations For m = 13 the correct answer is 360360, which is also the same number of operations performed. This doesn't seem too bad.

However you are also calling hash.has_value? every iteration. If you look at the source code for this, it loops through every value in the hash. This means that in the first iteration, the hash has one value and this is one operation. In the second iteration hash has two values (requiring two operations) but now we've done a total of three operations between the first and second iteration. In the third iteration there are three operations which makes for a combined total of 6 operations. After the fourth iteration we've done a total of 10 operations. This is a series of the sum of natural numbers and the formula for it is:

\frac{n(n+1)}{2}

So when m = 10 you do 2520 + (252 * 253 / 2) = 34,398 operations.

When m = 13 you do 360360 + (27720 * 27721 / 2) = 384,573,420 operations. This is not good.

Practical Code Evaluation

Now that we think we know what the code is doing, we can profile it to see what it is actually doing. I generated these numbers on your code using the ruby-prof gem after setting multiple = 13. (This is just a portion of the output)

Total: 165.979596

 %self      total      self      wait     child     calls  name
 56.63    165.679    93.988     0.000    71.690    27722   Hash#has_value?
 43.19     71.690    71.690     0.000     0.000 384240778   Fixnum#==
  0.13      0.215     0.215     0.000     0.000    27720   Range#each

We can see that it took 165 seconds to run on my computer. Almost all of that time was spent calling Hash.has_value?. Hash.has_value? was called 27722 times, which is 360360/13, the number of iterations in the loop (plus one or two more). There is also another function, Fixnum#== that was called many times. This is called from inside Hash.has_value? to compare each value in the hash to the value being searched for. It is also called as part of the modulus check and probably a few other places as well. The number is very close ot the number we predicted with the formula.

In summary, almost all of the processing time is taken by Hash.has_value? and its inner call to Fixnum#==.

Fixing The Code

Your bottleneck is in Hash.has_value? so we should get rid of it. All you are doing is checking if the test number is divisible by every number less than or equal to m. You store this in a hash, but never reference anything other than the current iteration. As such, you can get rid of the hash and use a simple counter instead.

multiple = 13
y = multiple

loop do
  counter = 0
  for x in 1..multiple do
    if y % x == 0
      counter += 1
    end
  end
  
  if counter == multiple || y == 0
    break
  end    
  
  y += multiple
end

puts "Smallest number = #{y - multiple}"

When we profile this code we get the following:

Total: 0.137014

 %self      total      self      wait     child     calls  name
 75.91      0.104     0.104     0.000     0.000    27720   Range#each

We now run over 1000 times faster, yay!

Cleaning up the Code

One of the reasons this question took so long to answer is that your original code is very hard to read. I'm going to keep your logic intact but clean it up some, just to make it look a little more rubyish.

def find_smallest_dividend(max_divisor)
  return 0 if max_divisor <= 0
  
  current_value = max_divisor
  loop do
    break if (1..max_divisor).all? { |n| (current_value % n).zero? }
    current_value += max_divisor
  end
  
  current_value
end

puts "Smallest number = #{find_smallest_dividend(13)}"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.