2
\$\begingroup\$

My code is very slow to run, and I am trying to find a way to make it more efficient. I know there must be a better way than to write each modulo operation.

The goal of the script is to find the smallest possible number than can be divided by numbers 1 to 20 without a remainder.

def divide
  (2..Float::INFINITY).each do |x|
      if x % 2 == 0 && x % 3 == 0 && x % 4 == 0 && x % 5 == 0 && x % 6 == 0 && x % 7 == 0 && x % 8 == 0 && x % 9 == 0 && x % 10 == 0 && x % 11 == 0 && x % 12 == 0 && x % 13 == 0 && x % 14 == 0 && x % 15 == 0 && x % 16 == 0 && x % 17 == 0 && x % 18 == 0 && x % 19 == 0 && x % 20 == 0
        print x
        break
      end
  end
end

divide
\$\endgroup\$
5
  • \$\begingroup\$ What is the goal here? The variable test doesn't seem to be used, nor is there a purpose for z. \$\endgroup\$
    – MTarantini
    Apr 1 '16 at 15:23
  • \$\begingroup\$ @MTarantini The goal is to improve performance on the script, as it takes quite a while to run. I got rid of variables. \$\endgroup\$
    – tristan
    Apr 1 '16 at 15:28
  • \$\begingroup\$ Well of course the goal here is to improve performance, that's why you posted it ;-) I meant what is the purpose of the script, not your post. \$\endgroup\$
    – MTarantini
    Apr 1 '16 at 15:30
  • \$\begingroup\$ @MTarantini Well I misread that... The goal is o find the smallest possible number than can be divided by numbers 1 to 20 without a remainder. \$\endgroup\$
    – tristan
    Apr 1 '16 at 15:48
  • \$\begingroup\$ Check codereview.stackexchange.com/questions/26346/… \$\endgroup\$
    – tokland
    Apr 1 '16 at 15:51
2
\$\begingroup\$

Array provides lcm() which gives you the least common multiple of two numbers. You can apply this to an entire array by applying it to each result as you go through it. This is what reduce does.

puts (1..20).reduce{|m,n| m.lcm(n)}

or even shorter:

puts (1..20).reduce(:lcm)

Because most of the calculations are done in the ruby implementation (e.g. C for MRI), this will be fast.

\$\endgroup\$
0
\$\begingroup\$

all

Your if can become:

if (2..20).all? {|d| x % d == 0}

To avoid repetition.

all returns at the first false so this should be as fast as yours.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm afraid the speed difference is significant, the original conditional is considerably faster. I benchmarked the original at: 3.981697, while the benchmark with the all method: 33.40386 \$\endgroup\$
    – MTarantini
    Apr 1 '16 at 18:50
-1
\$\begingroup\$

I would start at 20 and increase the number by 20 each time it loops:

def divide
  (20..Float::INFINITY).step(20).each do |x|
    if x % 2 == 0 && x % 3 == 0 && x % 4 == 0 &&
      x % 5 == 0 && x % 6 == 0 && x % 7 == 0 &&
      x % 8 == 0 && x % 9 == 0 && x % 10 == 0 &&
      x % 11 == 0 && x % 12 == 0 && x % 13 == 0 &&
      x % 14 == 0 && x % 15 == 0 && x % 16 == 0 &&
      x % 17 == 0 && x % 18 == 0 && x % 19 == 0 && x % 20 == 0

      puts x
      break
    end
  end
end

puts divide

Since 20 is the smallest number it could possibly be, we start there, since we know that it has to be evenly divisible by 20, we can continue increasing the number by 20 until it finds the solution.

At first I tried replacing your large conditional with a loop that would go from 2 to 20, testing the remainder, but this was much slower than your conditional.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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