# speed up square digit function

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.

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

• 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 May 2 '13 at 15:28
• 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.
– m_x
May 2 '13 at 16:08