[Shootout-list] Tcl : nsieve

[Simon Geard]

This is a multi-part message in MIME format.
--------------090403040900030702010303
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Robert Seeger wrote:

>I updated the Tcl implementation of the nsieve test. It now uses
>lists, since they are closer to a C array than Tcl arrays are.
>However, even with N = 3, it takes over 2 minutes to complete on my
>system :(
>
>Rob Seeger
>
>  
>
<snip>

I've tweaked your code (attached). It now runs ok:

[simon@localhost nsieve]$ time -p tclsh nsieve.tcl 3
Primes up to    80000     7837
Primes up to    40000     4203
Primes up to    20000     2262
real 0.34
user 0.29
sys 0.00

Simon Geard

--------------090403040900030702010303
Content-Type: text/x-tcl;
 name="nsieve.tcl"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="nsieve.tcl"

package require Tcl 8.4

proc main {n} {
    foreach value [list $n [incr n -1] [incr n -1]] {
        set num [expr { int(pow(2, $value) * 10000) }]
        puts [format "Primes up to %8d %8d" $num [nsieve $num]]
    }
}

proc nsieve {n} {
    set data {}
    for {set i 0} {$i <= $n} {incr i} {
        lappend data 1
    }

    set count 0
    for {set i 2} {$i <= $n} {incr i} {
        if { [lindex $data $i] } {
            for {set j [expr {$i + $i}]} {$j <= $n} {incr j $i} {
                lset data $j 0
            }
            incr count
        }
    }
    
    return $count
}

main [lindex $argv 0]


--------------090403040900030702010303--