My off-hand Lua implementation of a solution to Exercise 1.22 in MIT SICP book. (see http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.22) In "reply" to https://github.com/aknrdureegaesr/sicp_clj/blob/master/chapter1/src/chapter1/AnswerToExercise_1_22.clj where some possible Java JIT effects were observed. Usefulness is probab…

AnswerToExercise_1_22.lua

require 'os'

-- reimplementation of SICP section 1.2.6
function smallest_divisor(n)
    return find_divisor(n,2)
end

function find_divisor(n, test_divisor)
    if (test_divisor * test_divisor > n) then
        return n
    else 
        if ((n % test_divisor) == 0) then
            return test_divisor
        else
            return find_divisor(n, test_divisor+1)
        end
    end
end


function is_prime(n)
    return n == smallest_divisor(n)
end


-- my own code for exercise 1.22 
-- (see http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.22)

function search_for_n_primes(larger_than, n)
    -- make sure to start with an odd number
    local candidate = larger_than
    if (candidate % 2 == 0) then
        candidate = candidate + 1
    end
  
    local str = ''    -- result string
    local i = 0       -- success counter
    local sum = 0     -- sum of elapsed times
    
     
    -- find n candidates
    while i < n do
        start_time = os.clock()
        if is_prime(candidate) then
            str = str .. string.format("%i", candidate) .. " " 
            -- keep track of elapsed time
            sum = sum + os.clock() - start_time
            i = i + 1
        end
        candidate = candidate+2
    end
    print(str)
    
    -- return average time used to find each of the three primes
    return sum/n
end
            
        

-- throwaway code for measuring runtime increase
oldavg = 0
i = 10

while i <= 1e+15 do
    avg = search_for_n_primes(i,3)
    if oldavg > 0 then
        print(string.format("runtime increased %f fold\n", avg/oldavg))
    end
    oldavg = avg
    i = i * 10
end


--[[
Unfortunately, os.clock only appears to have tens of milliseconds resolution.

# time lua AnswerToExercise_1_22.lua  
11 13 17 
101 103 107 
1009 1013 1019 
10007 10009 10037 
100003 100019 100043 
1000003 1000033 1000037 
10000019 10000079 10000103 
100000007 100000037 100000039 
1000000007 1000000009 1000000021 
10000000019 10000000033 10000000061 
runtime increased 2.500000 fold

100000000003 100000000019 100000000057 
runtime increased 2.800000 fold

1000000000039 1000000000061 1000000000063 
runtime increased 3.000000 fold

10000000000037 10000000000051 10000000000099 
runtime increased 3.119048 fold

100000000000031 100000000000067 100000000000097 
runtime increased 3.236641 fold

1000000000000037 1000000000000091 1000000000000159 
runtime increased 3.127358 fold

lua AnswerToExercise_1_22.lua  24.55s user 0.00s system 99% cpu 24.596 total


LuaJIT gives a speedup of about one order of magnitude for this task


# time luajit AnswerToExercise_1_22.lua 
11 13 17 
101 103 107 
1009 1013 1019 
10007 10009 10037 
100003 100019 100043 
1000003 1000033 1000037 
10000019 10000079 10000103 
100000007 100000037 100000039 
1000000007 1000000009 1000000021 
10000000019 10000000033 10000000061 
100000000003 100000000019 100000000057 
1000000000039 1000000000061 1000000000063 
runtime increased 2.500000 fold

10000000000037 10000000000051 10000000000099 
runtime increased 2.600000 fold

100000000000031 100000000000067 100000000000097 
runtime increased 3.461538 fold

1000000000000037 1000000000000091 1000000000000159 
runtime increased 3.088889 fold

luajit AnswerToExercise_1_22.lua  2.56s user 0.00s system 97% cpu 2.617 total
]]--