Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 00004 #include "utils/preconditions/preconditions.h" 00005 #include "utils/assert/integer_overflow.h" 00006 #include <limits> 00007 00008 namespace math { 00009 namespace prime_sieve { 00010 00019 class EratosthenesBasic { 00021 // Note: using upper-half of the range of SizeType is ok 00022 // as in this class we won't use difference type. 00023 typedef std::vector<bool>::size_type SizeType; 00024 00025 public: 00032 template <typename T> 00033 void initialize(T t_size) { 00034 STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>(); 00035 SizeType size = (SizeType) t_size; 00036 Preconditions::check(size > 2); 00037 // because of j = 2 * i 00038 Preconditions::check(size < std::numeric_limits<SizeType>::max() / 2, 00039 "Out of range for computation, there will be overflow"); 00040 // and now we are ready to go 00041 data.resize(size); 00042 data[0] = false; 00043 data[1] = false; 00044 for (SizeType i = 2; i < size; i++) { 00045 data[i] = true; 00046 } 00047 00048 for (SizeType i = 2; i < size; i++) if (data[i]) { 00049 for (SizeType j = 2 * i; j < size; j += i) 00050 data[j] = false; 00051 } 00052 } 00053 00058 template <typename T> 00059 bool isPrime(T p) { 00060 STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>(); 00061 Preconditions::checkRange((SizeType) p, data.size()); 00062 return data[(SizeType) p]; 00063 } 00064 00065 private: 00066 std::vector<bool> data; 00067 }; 00068 00069 } // namespace prime_sieve 00070 } // namespace math