tests: Shootout_nsieve now uses byte arrays instead of Buffers

Signed-off-by: Lucas Bajolet <r4pass@hotmail.com>

diff --git a/tests/sav/shootout_nsieve_bytes_alt.res b/tests/sav/shootout_nsieve_bytes_alt.res
new file mode 100644 (file)
index 0000000..d9e91fa
--- /dev/null
+++ b/tests/sav/shootout_nsieve_bytes_alt.res
@@ -0,0 +1,3 @@
+Primes up to 40000 4203
+Primes up to 20000 2262
+Primes up to 10000 1229

diff --git a/tests/shootout_nsieve.nit b/tests/shootout_nsieve.nit
index 2137a3a..109b70f 100644 (file)
--- a/tests/shootout_nsieve.nit
+++ b/tests/shootout_nsieve.nit
@@ -14,21 +14,44 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+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: Buffer = new FlatBuffer.with_capacity(n)
-       for i in [0..n[ do
-               array.chars[i] = 'o'
-       end
-       for i in [2..n[ do
-               if array.chars[i] == 'o' then
-                       var j = i * 2
-                       while j < n do
-                               array.chars[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

diff --git a/tests/shootout_nsieve_bytes_alt.nit b/tests/shootout_nsieve_bytes_alt.nit
new file mode 100644 (file)
index 0000000..ab5c703
--- /dev/null
+++ b/tests/shootout_nsieve_bytes_alt.nit
@@ -0,0 +1,73 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+class Bitarray
+
+       var narr: Bytes
+
+       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 b_arrsz = ((n - 1).to_f / 8.0).ceil.to_i
+       var bitarr = new Bitarray(new Bytes(new NativeString(b_arrsz), b_arrsz, 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
+
+fun test(n: Int)
+do
+       var m = 10000.lshift(n)
+       print("Primes up to {m} {nsieve(m)}")
+end
+
+var n = 2
+if args.length == 1 then
+       n = args.first.to_i
+end
+
+test(n)
+if n >= 1 then
+       test(n-1)
+end
+if n >= 2 then
+       test(n-2)
+end