Kim Walisch kimwalisch
kimwalisch
/ segmented_sieve1.cpp
Last active
March 4, 2018 18:47
Set the segment size in the segmented sieve of Eratosthenes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// Set your CPU's L1 data cache size (in bytes) here | |
| const int64_t L1D_CACHE_SIZE = 32768; | |
| /// Generate primes using the segmented sieve of Eratosthenes. | |
| /// This algorithm uses O(n log log n) operations and O(sqrt(n)) space. | |
| /// @param limit Sieve primes <= limit. | |
| /// | |
| void segmented_sieve(int64_t limit) | |
| { | |
| int64_t sqrt = (int64_t) std::sqrt(limit); |
kimwalisch
/ int128.h
Created
November 22, 2017 12:25
— forked from Bananattack/int128.h
A signed 128-bit integer type. Internally stores its data in Two's Complement within two unsigned 64-bit integer parts. Still needs more testing, but basic implementation is fairly complete.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef WIZ_UTILITY_INT128_H | |
| #define WIZ_UTILITY_INT128_H | |
| #include <cassert> | |
| #include <cstdint> | |
| #include <cstddef> | |
| #include <cstring> | |
| #include <cstdlib> | |
| #include <utility> | |
| #include <string> |
kimwalisch
/ stars.sh
Created
September 3, 2016 21:02
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/bin/sh | |
| total_stars=0 | |
| for i in {'primesieve','primecount','primesum','calculator'} | |
| do | |
| stars=$(curl --silent "https://api.github.com/repos/kimwalisch/$i" \ | |
| -H 'Accept: application/vnd.github.preview' \ | |
| | grep stargazers_count \ | |
| | cut -f2 -d':' \ |
kimwalisch
/ primesieve_ checksums.sh
Last active
February 11, 2019 09:38
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| e9d01635ae2313ea5d3b5bf2b8c204bac7932c68 primesieve-7.4.zip | |
| 72aa38a72a07a87e5fbf6aa1118fa1b1596a8fef primesieve-7.4.tar.gz | |
| 69f4916e8390a79db443d7842399251a5a54dbb8 primesieve-7.4-win64.zip | |
| d4b88dd6a83c82ac075494458d3c0e4cc19da425 primesieve-7.4-linux-x64.tar.xz | |
| 4095d6d2f88a71f8bf86cea1332b539025320bec primesieve-5.5.0-macOS-x64.zip | |
| 4f04d35d7cdb701ae142f7e286f1641590d9b4b2 primesieve-7.4-win64-console.zip | |
| f4d80d2bfd1d5db3fde4fd50737bf3e0d96e26d3 primesieve-7.4-linux-x64-console.tar.xz | |
| c1c7b6c5f078d51e7e09d67e3e091f3a14610ee3 primesieve-7.4-macOS-x64-console.zip | |
| da7a99173692da005ace827b0df17cb3e7ab1356 primesieve-3.6-win32.zip | |
| 9d16566558aee0b71139f5f95dff23d808d2d886 primesieve-3.6-win32-console.zip |
kimwalisch
/ primesieve_ checksums.sh
Created
August 23, 2016 19:23
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 45a20e525e3c19fc98e583101af166fd5e6b2324 primesieve-5.7.2.tar.gz | |
| 064b79afeff39866b3c17d390c790778460e5a1c primesieve-5.7.2.zip | |
| 6fd3e6d98a6d4bf7a7234279deaa4eff193235b9 primesieve-5.7.0-win64.zip | |
| c7f3e96c4e1a0e23131f6a39f4086d6d275b0b6c primesieve-5.7.0-win64-console.zip | |
| 8e3f62c850efe591286fcc2262a7f4af4cad285b primesieve-5.5.0-linux-x64.tar.gz | |
| 31215c1dcbc3899f4929b1291a0cb73522111b6d primesieve-5.7.0-linux-x64-console.tar.gz | |
| 4095d6d2f88a71f8bf86cea1332b539025320bec primesieve-5.5.0-macosx-x64.zip | |
| 7ea817d4555dc378e0abf9d14400af8de95dc9f7 primesieve-5.5.0-macosx-x64-console.zip | |
| da7a99173692da005ace827b0df17cb3e7ab1356 primesieve-3.6-win32.zip | |
| 9d16566558aee0b71139f5f95dff23d808d2d886 primesieve-3.6-win32-console.zip |
kimwalisch
/ compile.sh
Last active
August 23, 2016 18:11
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Compile using default C++ compiler | |
| c++ -O2 segmented_sieve.cpp -o segmented_sieve | |
| # Count the primes below 10^9 | |
| time ./segmented_sieve 1000000000 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <primesieve.h> | |
| #include <stdio.h> | |
| int main() | |
| { | |
| primesieve_iterator it; | |
| primesieve_init(&it); | |
| uint64_t prime; | |
| /* iterate over the primes below 10^6 */ |
kimwalisch
/ libdivide-without-power-of-2.cpp
Created
March 20, 2016 10:19
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct libdivide_u64_t libdivide_u64_gen(uint64_t d) { | |
| struct libdivide_u64_t result; | |
| const uint32_t floor_log_2_d = 63 - libdivide__count_leading_zeros64(d); | |
| uint64_t proposed_m, rem; | |
| uint8_t more; | |
| proposed_m = libdivide_128_div_64_to_64(1ULL << floor_log_2_d, 0, d, &rem); //== (1 << (64 + floor_log_2_d)) / d | |
| LIBDIVIDE_ASSERT(rem > 0 && rem < d); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ; primesieve inner sieving loop | |
| ; Uses only 11 instructions (x86-64) to cross-off the next 8 multiples | |
| .L99: | |
| andb $-3, (%rax) | |
| andb $-9, (%rax,%r14) | |
| andb $127, (%rax,%r12) | |
| andb $-33, (%rax,%rbp) | |
| andb $-2, (%rax,%r10) | |
| andb $-65, (%rax,%rbx) | |
| andb $-5, (%rax,%r9) |
kimwalisch
/ primes.cpp
Last active
August 14, 2017 09:01
Generate primes using the primesieve C++ library
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <primesieve.hpp> | |
| #include <iostream> | |
| int main() | |
| { | |
| primesieve::iterator it; | |
| uint64_t prime = it.next_prime(); | |
| // iterate over the primes below 10^6 | |
| for (; prime < 1000000; prime = it.next_prime()) |