lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Try this simplified version (same algorithm you used):

--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--
max = arg[1]
prime = {} -- true when prime

-- marks all as prime
for k = 1, max do
    prime[k] = true
end

-- mark multiples of primes as not prime
for k = 2, math.sqrt(max) do
    if prime[k] then
        for kk = k*2, max, k do
            prime[kk] = false
        end
    end
end

---[[ prints the primes
for k, isprime in ipairs(prime) do
    if isprime and k ~= 1 then
        print(k)
    end
end
--]]
--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--~~--

Additionally I'd deactive any use of prints when meassuring
perfomance. I/O is so slow compared to anything else it will make most
speed advantages/disadvantages to tiny differences.


On Fri, Jan 21, 2011 at 8:12 AM, Steve Litt <slitt@troubleshooters.com> wrote:
> On Friday 21 January 2011 01:52:40 Alexander Gladysh wrote:
>> On Fri, Jan 21, 2011 at 09:47, Steve Litt <slitt@troubleshooters.com> wrote:
>> > A few weeks ago I wrote a Lua prime number generator. Today, to test Lua
>> > 5.1.4 vs LuaJIT 1.1.6 I ran the prime numbers between 1 and 50 million,
>> > writing all numbers to /dev/null to minimize I/O time. Lua took typically
>> > around 48 seconds and LuaJIT took around 34 seconds. Is this typical of a
>> > CPU/memory bound process?
>>
>> Why do you try LJ 1.1.6? Try LuaJIT 2! :-)
>
> Is it significantly faster than 1.1.6? I just took the stable one.
>
>>
>> Also, you may want to show us the benchmark code.
>
> Attached. Please don't laugh too hard -- I'd had about 3 days of Lua
> experience when I wrote it. Writing that program so easily and having it run
> so quickly was one of the things that made me decide to look more deeply into
> Lua.
>
> In case your list doesn't allow attachments, I've printed it at the bottom of
> this email.
>
> Thanks
>
> SteveT
>
> Steve Litt
> Recession Relief Package
> http://www.recession-relief.US
> Twitter: http://www.twitter.com/stevelitt
>
> #!/usr/bin/lua
>
> --[[
> Copyright (c) 2010 by Steve Litt
>
> Permission is hereby granted, free of charge, to any person obtaining a copy
> of this software and associated documentation files (the "Software"), to deal
> in the Software without restriction, including without limitation the rights
> to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
> copies of the Software, and to permit persons to whom the Software is
> furnished to do so, subject to the following conditions:
>
> The above copyright notice and this permission notice shall be included in
> all copies or substantial portions of the Software.
>
> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
> AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
> OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
> THE SOFTWARE.
> ]]
>
>
> function mark_multiples(primes)
>        local multiple=primes["candidate"]
>        while multiple <= primes["upto"] do
>                multiple = multiple + primes["candidate"]
>                -- print(string.format("dia multiple=%d", multiple))
>                primes[multiple] = 0
>        end
> end
>
>
> function find_next_candidate(primes)
>        primes["candidate"] = primes["candidate"] + 1
>        while primes[primes["candidate"]] == 0 do
>                primes["candidate"] = primes["candidate"] + 1
>        end
>
> end
>
>
> function print_primes(primes)
>        for i=1, primearray["upto"] do
>                if primearray[i] == 1 then
>                        print(i)
>                end
>        end
> end
>
>
> function print_array(primes)
>        for i=1, primearray["upto"] do
>                print(string.format("%d     %d", i, primearray[i]))
>        end
> end
>
>
> function mark_all_as_prime(primes)
>        for i=1, primearray["upto"] do primearray[i]=1 end
> end
>
>
> function main()
>        primearray={
>                upto=arg[1] + 0,
>                candidate=2,
>                maxcandidate=math.sqrt(arg[1])
>        }
>
>        mark_all_as_prime(primes)
>
>        while primearray["maxcandidate"] > primearray["candidate"] do
>                mark_multiples(primearray)
>                find_next_candidate(primearray)
>        end
>
>        print_primes(primearray)
>        -- print_array(primearray)
> end
>
> main()
>