tests/shootout_nsieve_bytes_alt.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 class Bitarray
  16
  17         var narr: Bytes
  18
  19         init do
  20                 for x in [0 .. narr.length[ do narr[x] = 0xFF
  21         end
  22
  23         fun [](pos: Int): Bool do
  24                 pos -= 2
  25                 return (narr[pos / 8] & (1 << (7 - pos % 8))) != 0
  26         end
  27
  28         fun []=(pos: Int, val: Bool) do
  29                 pos -= 2
  30                 if val then
  31                         narr[pos / 8] |= 1 << (7 - pos % 8)
  32                 else
  33                         narr[pos / 8] &= 0xFF - (1 << (7 - pos % 8))
  34                 end
  35         end
  36 end
  37
  38 fun nsieve(n: Int): Int
  39 do
  40         var count = 0
  41         var b_arrsz = ((n - 1).to_f / 8.0).ceil.to_i
  42         var bitarr = new Bitarray(new Bytes(new CString(b_arrsz), b_arrsz, b_arrsz))
  43         for i in [2 .. n[ do
  44                 # If self is already false, then no need to check for multiples
  45                 if not bitarr[i] then continue
  46                 count += 1
  47                 var j = i * i
  48                 while j < n do
  49                         bitarr[j] = false
  50                         j += i
  51                 end
  52         end
  53         return count
  54 end
  55
  56 fun test(n: Int)
  57 do
  58         var m = 10000 << n
  59         print("Primes up to {m} {nsieve(m)}")
  60 end
  61
  62 var n = 2
  63 if args.length == 1 then
  64         n = args.first.to_i
  65 end
  66
  67 test(n)
  68 if n >= 1 then
  69         test(n-1)
  70 end
  71 if n >= 2 then
  72         test(n-2)
  73 end