15,671,318 members
Home / Discussions / Algorithms

Algorithms

 Data Consistency Patje27-Nov-08 5:53 Patje 27-Nov-08 5:53
 Re: Data Consistency Luc Pattyn27-Nov-08 10:34 Luc Pattyn 27-Nov-08 10:34
 Re: Data Consistency Patje27-Nov-08 23:36 Patje 27-Nov-08 23:36
 Re: Data Consistency Alan Balkany1-Dec-08 3:46 Alan Balkany 1-Dec-08 3:46
 [Message Deleted] AliN136221-Nov-08 21:51 AliN1362 21-Nov-08 21:51
 Re: RRT Arash Partow22-Nov-08 1:25 Arash Partow 22-Nov-08 1:25
 Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult21-Nov-08 10:58 PIEBALDconsult 21-Nov-08 10:58
 I've been working on improving my Sieve of Eratosthenes routine ever since I first had to write one in Pascal way back in college (well, not constantly), always trying to reach a higher maximum. I just got around to writing one in C#. I was reading up on Wheel Factorization (at least the type described on Wikipedia) as a way to extend my reach while using the same amount of memory. It turns out that, because I consider only the odd integers, I am already using a simple form of Wheel Factorization. Now I'm interested in getting to the next step, but I'm stumped by the statement: " The remaining numbers in the wheel contain mostly prime numbers. Use other methods such as Sieve of Eratosthenes to remove the remaining non-primes. " -- Wikipedia When I look at the example given, I don't see how Sieve of Eratosthenes can be successfully applied to each spoke separately. It appears I have to allocate memory for all the spokes I need to check (1 and 5) and sieve them concurrently, which won't extend the range (for a given amount of memory) as much as I was hoping. Let's say I want to allocate only enough memory for twelve flags. (1) With a one-spoke wheel we get the classic Sieve: 1 2 3 4 5 6 7 8 9 10 11 12 (2) But we know we don't need to check the even numbers, so we can use those twelve flags to represent only the odd numbers and thereby double our reach: 1 3 5 7 9 11 13 15 17 19 21 23 (3) If we use a fully-allocated two-spoke wheel we still only reach 12, which gains us nothing: 1 3 5 7 9 11 2 4 6 8 10 12 (4) But we don't need to allocate spoke 2, so we can use that memory to double our reach: 1 3 5 7 9 11 13 15 17 19 21 23 2 4 6 8 10 12 14 16 18 20 22 24 << not allocated It should be apparent that (4) is equivalent to (2), notice that the sieve can successfully be applied to spoke 1. (5) When we get to a 6-spoke wheel we can have it fully-allocated, which is little better than (3): 1 7 2 8 3 9 4 10 5 11 6 12 (6) Or, preferably, only allocate one spoke at a time as I did in (4): 1 7 13 19 25 31 37 43 49 55 61 67 2 8 14 20 26 32 38 44 50 56 62 68 << not allocated 3 9 15 21 27 33 39 45 51 57 63 69 << not allocated 4 10 16 22 28 34 40 46 52 58 64 70 << not allocated 5 11 17 23 29 35 41 47 53 59 65 71 << to be allocated later 6 12 18 24 30 36 42 48 54 60 66 72 << not allocated In theory, this will extend the reach by a factor of six; in practice it won't, because 25 and 55 appear in spoke 1 while their factors are in spoke 5. Unlike (4) we can't successfully apply Sieve of Eratosthenes to each spoke separately. (7) So we have to allocate both spoke 1 and spoke 5, yielding only a tripling of our reach: 1 7 13 19 25 31 2 8 14 20 26 32 << not allocated 3 9 15 21 27 33 << not allocated 4 10 16 22 28 34 << not allocated 5 11 17 23 29 35 6 12 18 24 30 36 << not allocated And then we have to be able to apply Sieve of Eratosthenes to both spokes concurrently. Which is where I'm at now. I see how it can be done, but I suspect that the calculations involved may not be worth the trouble. Have any of you done this?
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn21-Nov-08 17:43 Luc Pattyn 21-Nov-08 17:43
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult22-Nov-08 3:29 PIEBALDconsult 22-Nov-08 3:29
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn22-Nov-08 4:24 Luc Pattyn 22-Nov-08 4:24
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult22-Nov-08 7:34 PIEBALDconsult 22-Nov-08 7:34
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes [modified] PIEBALDconsult26-Nov-08 8:42 PIEBALDconsult 26-Nov-08 8:42
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn26-Nov-08 11:16 Luc Pattyn 26-Nov-08 11:16
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult26-Nov-08 13:02 PIEBALDconsult 26-Nov-08 13:02
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn26-Nov-08 13:12 Luc Pattyn 26-Nov-08 13:12
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult26-Nov-08 17:56 PIEBALDconsult 26-Nov-08 17:56
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn26-Nov-08 18:48 Luc Pattyn 26-Nov-08 18:48
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn26-Nov-08 15:14 Luc Pattyn 26-Nov-08 15:14
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult26-Nov-08 18:49 PIEBALDconsult 26-Nov-08 18:49
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult14-Jan-09 17:50 PIEBALDconsult 14-Jan-09 17:50
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn15-Jan-09 1:11 Luc Pattyn 15-Jan-09 1:11
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes PIEBALDconsult15-Jan-09 6:12 PIEBALDconsult 15-Jan-09 6:12
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Luc Pattyn15-Jan-09 6:28 Luc Pattyn 15-Jan-09 6:28
 Re: Wheel Factorization to simplify a Sieve of Eratosthenes Member 419459328-Nov-08 9:03 Member 4194593 28-Nov-08 9:03
 Last Visit: 31-Dec-99 18:00     Last Update: 8-Jun-23 19:02 Refresh ᐊ Prev1...168169170171172173174175176177 Next ᐅ