Click here to Skip to main content
15,070,974 members
Home / Discussions / Algorithms
   

Algorithms

 
QuestionData Consistency Pin
Patje27-Nov-08 5:53
MemberPatje27-Nov-08 5:53 
GeneralRe: Data Consistency Pin
Luc Pattyn27-Nov-08 10:34
sitebuilderLuc Pattyn27-Nov-08 10:34 
GeneralRe: Data Consistency Pin
Patje27-Nov-08 23:36
MemberPatje27-Nov-08 23:36 
AnswerRe: Data Consistency Pin
Alan Balkany1-Dec-08 3:46
MemberAlan Balkany1-Dec-08 3:46 
Question[Message Deleted] Pin
AliN136221-Nov-08 21:51
MemberAliN136221-Nov-08 21:51 
AnswerRe: RRT Pin
Arash Partow22-Nov-08 1:25
MemberArash Partow22-Nov-08 1:25 
AnswerRe: RRT Pin
Paul Conrad22-Nov-08 13:45
professionalPaul Conrad22-Nov-08 13:45 
QuestionWheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult21-Nov-08 10:58
professionalPIEBALDconsult21-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?
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn21-Nov-08 17:43
sitebuilderLuc Pattyn21-Nov-08 17:43 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult22-Nov-08 3:29
professionalPIEBALDconsult22-Nov-08 3:29 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn22-Nov-08 4:24
sitebuilderLuc Pattyn22-Nov-08 4:24 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult22-Nov-08 7:34
professionalPIEBALDconsult22-Nov-08 7:34 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes [modified] Pin
PIEBALDconsult26-Nov-08 8:42
professionalPIEBALDconsult26-Nov-08 8:42 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn26-Nov-08 11:16
sitebuilderLuc Pattyn26-Nov-08 11:16 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult26-Nov-08 13:02
professionalPIEBALDconsult26-Nov-08 13:02 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn26-Nov-08 13:12
sitebuilderLuc Pattyn26-Nov-08 13:12 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult26-Nov-08 17:56
professionalPIEBALDconsult26-Nov-08 17:56 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn26-Nov-08 18:48
sitebuilderLuc Pattyn26-Nov-08 18:48 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn26-Nov-08 15:14
sitebuilderLuc Pattyn26-Nov-08 15:14 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult26-Nov-08 18:49
professionalPIEBALDconsult26-Nov-08 18:49 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult14-Jan-09 17:50
professionalPIEBALDconsult14-Jan-09 17:50 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn15-Jan-09 1:11
sitebuilderLuc Pattyn15-Jan-09 1:11 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
PIEBALDconsult15-Jan-09 6:12
professionalPIEBALDconsult15-Jan-09 6:12 
GeneralRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Luc Pattyn15-Jan-09 6:28
sitebuilderLuc Pattyn15-Jan-09 6:28 
AnswerRe: Wheel Factorization to simplify a Sieve of Eratosthenes Pin
Member 419459328-Nov-08 9:03
MemberMember 419459328-Nov-08 9:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.