Merge: doc: fixed some typos and other misc. corrections

[nit.git] / tests / shootout_nsieve.nit

diff --git a/tests/shootout_nsieve.nit b/tests/shootout_nsieve.nit
index a9a3923..1e7eda6 100644 (file)
--- a/tests/shootout_nsieve.nit
+++ b/tests/shootout_nsieve.nit
@@ -14,29 +14,52 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-meth nsieve(n: Int): Int
+import c
+
+class Bitarray
+
+       var narr: CByteArray
+
+       init do
+               for x in [0 .. narr.length[ do narr[x] = 0xFFu8
+       end
+
+       fun [](pos: Int): Bool do
+               pos -= 2
+               return (narr[pos / 8] & (1u8 << (7 - pos % 8))) != 0u8
+       end
+
+       fun []=(pos: Int, val: Bool) do
+               pos -= 2
+               if val then
+                       narr[pos / 8] |= 1u8 << (7 - pos % 8)
+               else
+                       narr[pos / 8] &= 0xFFu8 - (1u8 << (7 - pos % 8))
+               end
+       end
+end
+
+fun nsieve(n: Int): Int
 do
        var count = 0
-       var array = new String.with_capacity(n)
-       for i in [0..n[ do
-               array[i] = 'o'
-       end
-       for i in [2..n[ do
-               if array[i] == 'o' then
-                       var j = i * 2
-                       while j < n do
-                               array[j] = 'x'
-                               j = j + i
-                       end
-                       count = count + 1
+       var b_arrsz = ((n - 1).to_f / 8.0).ceil.to_i
+       var bitarr = new Bitarray(new CByteArray(b_arrsz))
+       for i in [2 .. n[ do
+               # If self is already false, then no need to check for multiples
+               if not bitarr[i] then continue
+               count += 1
+               var j = i * i
+               while j < n do
+                       bitarr[j] = false
+                       j += i
                end
        end
        return count
 end
 
-meth test(n: Int)
+fun test(n: Int)
 do
-       var m = 10000.lshift(n)
+       var m = 10000 << n
        print("Primes up to {m} {nsieve(m)}")
 end