Hello,
In much of the software that resorts to segmentation, the Eratosthene sieve <N is determined by precalculating the prime numbers up to √N.
This prompted me to write the SieveRecur function that borrows this idea to evaluate the sieve recursively:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // calculate the sieve isPrime from isPrime [0] to isPrime [N] void SieveRecur (uint N, bool * isPrime) {// len (isPrime)> N // before the first call, isPrime [0..N] must be initialized to true if (N <= 3) {isPrime [0] = isPrime [1] = false; return;} uint R = sqrt (N); SieveRecur (R, isPrime); for (uint m, p = 2; p <= R; ++ p) if (isPrime [p]) {// p is prime { for (m = p * p; m <= N-p; m + = p) isPrime [m] = false; isPrime [m] = false; } } void Sieve0 (uint N, bool * isPrime) {// len (isPrime)> N isPrime [0] = isPrime [1] = false; memset (isPrime + 2, true, N-1); uint R = sqrt (N); for (uint p = 2; p <= R; ++ p) if (isPrime [p]) for (uint q = p, Q = N / p; q <= Q; ++ q) isPrime [p * q] = false; } // bool * EratoD (uint N, bool * isPrime) { isPrime [0] = false; isPrime [1] = false; memset (isPrime + 2, true, N-1); for (uint p = 2; p * p <= N; ++ p) if (isPrime [p]) for (uint q = N / p; q> = p; --q) if (isPrime [q]) isPrime [p * q] = false; return isPrime; } |
Unfortunately, the SieveRecur function is only slightly faster than Sieve0 described in my previous articles:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | SieveRecur: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 2 ms N = 10000000, n = 664579, t = 92 ms N = 100000000, n = 5761455, t = 1270 ms N = 1000000000, n = 50847534, t = 15607 ms Sieve0: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 3 ms N = 10000000, n = 664579, t = 100 ms N = 100000000, n = 5761455, t = 1347 ms N = 1000000000, n = 50847534, t = 16263 ms EratoD: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 3 ms N = 10000000, n = 664579, t = 39 ms N = 100000000, n = 5761455, t = 422 ms N = 1000000000, n = 50847534, t = 4868 ms |
What is already “not so bad”!
One can of course improve it by avoiding to treat the multiples of some small primes (2, 3, 5, ..).
As I pointed out before, segmentation is not strictly speaking an algorithm!
But rather a “simplification” of the management of virtual memory.
The day our computers will have “enough” (real) memory, the “segmentations” will no longer have any reason to be.
In the meantime, these ideas will encourage me to try to “segment” more powerful algorithms than those usually used!
