1
\$\begingroup\$

for the following function

#!/usr/bin/ruby -w
e=0
g=0
h=1
while h < 10000000
    a = h
    f=0
    while f !=1 && f!= 89
        d=0
        f=0
        while a.to_s[d] != nil
            e = a.to_s[d]
            b = e.to_i
            f += b**2
            d+=1
        end
        a = f
        f = 89 if [4,16,37,58,20,42,145].include? f
    end
    h += 1
    g+=1 if f == 89
end
p g

this is a porject i'm working for a certain programming practice website which i will not mention by name so my solution can't be found on google, but it's the 92nd problem. it runs about three times slower than i would like, everything that i have tried to speed it up with ends up adding a few seconds instead of subtracting, and that icludes storing values in arrays for later comparisons, any suggestions? run time is 3:10 and the result is 8581146 the purpose of this code is to find square digit chains from one to ten thousand that either end up in one or eighty-nine and to run a count of how many end at eightnine and out put the total when the program finishes. i get the square digit result for a number by first converting it into a string and converting individual chars back into nums and running it repeatedly, i have an if statement to catch f if it hits any of the numbers on the eighty-nine loop so i can shave off a few cycles here and there.

\$\endgroup\$
2
\$\begingroup\$

In benchmarking various techniques for this question, I found the biggest speed boost was in abandoning string conversion in favor of %10 to get the individual digits - try using a method like this to get your sums:

def sum_square_digits(n)
  sum = 0
  until n == 0
    sum += (n % 10) ** 2
    n /= 10
  end
  sum
end
\$\endgroup\$
2
  • \$\begingroup\$ thanks, that cut down my code to 25 sec run time. i also ended up replacing f = 89 if [4,16,37,58,20,42,145].include? f with if f < 100 if [1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97].include? f f = 1 else f = 89 end end and it cut dow my code by another 6 seconds for a total of 19 \$\endgroup\$ – user24658 May 2 '13 at 15:28
  • 1
    \$\begingroup\$ to shave off additional picoseconds, use a hash instead of [].include?, i.e. : hash = Hash[ [1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97].map{|i|[i,true]} ] ; condition = hash.has_key?(f) . Hash key lookup is faster than traversing an array every time. \$\endgroup\$ – m_x May 2 '13 at 16:08

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.