Initial commitHEADmaster

Sieve of Eratosthenes
- simple implementation and optimized versions
- Segmented sieve with pthreaded version

1 files changed, 97 insertions, 0 deletions

diff --git a/test.cc b/test.cc
new file mode 100644
index 0000000..ab31ba6
--- /dev/null
+++ b/test.cc
@@ -0,0 +1,97 @@
+#include "sieve.hh"
+#include <chrono>
+#include <functional>
+#include <gtest/gtest.h>
+#include <iostream>
+
+using ::testing::Combine;
+using ::testing::Values;
+
+TEST(Eratosthenes, isPrime) {
+  EXPECT_FALSE(isPrime(4));
+  EXPECT_FALSE(isPrime(9409));
+  EXPECT_TRUE(isPrime(9973));
+  EXPECT_FALSE(isPrime(53033));
+}
+
+constexpr auto sz = 1024 * 1024;
+static const auto n = sieve1(sz);
+
+TEST(Eratosthenes, validate) {
+  EXPECT_EQ(n[0], 2);
+
+  for (size_t i = 0; i < n.size(); ++i)
+    EXPECT_TRUE(isPrime(n[i])) << n[i];
+}
+
+typedef std::function<std::vector<int>(std::size_t)> SieveFunction;
+
+class SieveFunctionFixture
+    : public ::testing::TestWithParam<std::tuple<SieveFunction, std::string>> {
+public:
+  void SetUp() override {
+    sieve = std::get<SieveFunction>(GetParam());
+    sieve_name = std::get<std::string>(GetParam());
+  }
+
+protected:
+  SieveFunction sieve;
+  std::string sieve_name;
+};
+
+TEST_P(SieveFunctionFixture, validate) {
+  const auto begin = std::chrono::system_clock::now();
+  const auto r = sieve(sz);
+  const auto end = std::chrono::system_clock::now();
+
+  const auto ut =
+      std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
+  const auto nt =
+      std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
+
+  std::cout << sieve_name << '\n'
+            << "run time: " << ut << '\n'
+            << "prime count: " << r.size() << '\n'
+            << "time per prime: " << nt / r.size() << std::endl;
+
+  EXPECT_EQ(n.size(), r.size());
+  for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
+    EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
+  }
+}
+
+INSTANTIATE_TEST_SUITE_P(
+    Eratosthenes, SieveFunctionFixture,
+    Values(std::make_tuple(&sieve1, "sieve1"),
+           std::make_tuple(&sieve2, "sieve2"),
+           std::make_tuple(&sieve3, "sieve3"),
+           std::make_tuple(&segmentedSieve, "segmented sieve"),
+           std::make_tuple(&pthreadSieve, "threaded sieve")));
+
+TEST(benchmark, segmentedSieve) {
+  const auto begin = std::chrono::system_clock::now();
+  const auto r = segmentedSieve(1024 * sz);
+  const auto end = std::chrono::system_clock::now();
+
+  const auto t =
+      std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
+  std::cout << r.size() << " values in " << t << std::endl;
+
+  for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
+    EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
+  }
+}
+
+TEST(benchmark, threadedSieve) {
+  const auto begin = std::chrono::system_clock::now();
+  const auto r = pthreadSieve(1024 * sz);
+  const auto end = std::chrono::system_clock::now();
+
+  const auto t =
+      std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
+  std::cout << r.size() << " values in " << t << std::endl;
+
+  for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
+    EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
+  }
+}