Project Euler - #5 smallest multiple (Ruby using a hash table)

Question

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)

• Zack: This code runs and has the correct output, it is just very, very slow
• user122352: 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.
• Jamal: 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.

Answer 1

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)}"