From: Jano Svitok <jan.svitok@...>
Date: 2007-07-26T16:32:58+09:00
Subject: Re: Efficiency/runtime trouble - may not be Ruby-specific

On 7/25/07, Kaldrenon <kaldrenon@gmail.com> wrote:
> On Jul 25, 2:42 pm, "Jano Svitok" <jan.svi...@gmail.com> wrote:
> > 1. Move things out of cycle if it doesn't depend on the inner variable.
>
> I try to do this in general, but am I correct in my thinking that it's
> not applicable to this script?

In your script Math.sqrt was computed inside an each loop. Now it's
not there anymore, so it's fixed.

> > 2. Cache hard-to-compute expressions, especially those involving floats.
>
> I'm still very much a novice - could you explain to me in simple terms
> what you mean, or point me to a document/resource on this topic?

For this I meant n.to_f/d that was there three times. I'm not sure if
ruby reuses the value or computes it three times.

> > 3. Use Set instead of array.
>
> Had a BIG impact on run-time, thank you!
>
> > 4. Move easy-to-compute conditions (<, >) before the hard ones (hcf)
>
> This is something I feel dumb for not remembering myself - although
> some of these other things are new material for me, this is something
> I've dealt with before. Thanks for the reminder. Also had a big impact
> on time.
>
> > 5. Optimize the ranges of your loops
>
> As with tip #1, is there a way this technique can improve this script?
> I know it's wise in general.

require 'mathn'
MAX_D = 1000
red_prop_fract = 0
for n in 2...(MAX_D/2).ceil do
 lower = n*2+1
 upper = [n*3-1,MAX_D].min
 for d in lower..upper do
   if n.gcd2(d) == 1
     red_prop_fract += 1
   end
 end
end

> > 6. Try to avoid sqrt and floats as much as possible.
>
> Like #1 and #5, I think - Can I really avoid floats, since I need to
> get a number that's between two floats?

As morton said, instead of checking a/b > c/d you can do a*d > b*c.
And even in case of storing the fractions you can encode them into a
Fixnum: (n<<16 + d)

You can optimize sqrt when you know you are iterating over a range:

sqrt =1
sqr = 1
for n in 1...10000
  if n > sqr
    sqr += 2*sqrt + 1
    sqrt += 1
  end
  # now sqrt == Math.sqrt(n).ceil
  #.... do whatever you need with sqrt
end

When looking at the source of Mathn.gcd2,  (and after profiling) we
can see that most of the script is spent inside Prime.succ, so another
way to get a little gain is to copy the code, and replace

  def prime_division
    raise ZeroDivisionError if self == 0
    ps = Prime.new
    value = self
    pv = []
    for prime in ps

with

  def prime_division
    value = self
    pv = []
    for prime in Primes_under_100

(we can skip the zero check, as we do not send zero)

But for me gcd is still faster (there we can get a little gain as well
if we drop the .abs calls)

The last thing I could do is to skip over when both n and d are even -
it's a fast check that avoids expensive gcd check

Inlining the function also helps a bit.
This is my version:
t = Time.now
MAX_D = 1000
red_prop_fract = 0
for n in 2...(MAX_D/2).ceil do
 lower = n*2+1
 upper = [n*3-1,MAX_D].min
 for d in lower..upper do
   next if (d|n) & 1 == 0
   min = n
   max = d
   while min > 1
     tmp = min
     min = max % min
     max = tmp
   end
   if min == 1
     red_prop_fract += 1
   end
 end
end
p red_prop_fract
p Time.now-t