BitSieve


1   /*
2    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
3    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
4    */
5   
6   /*
7    * @(#)BitSieve.java    1.10 03/12/19
8    */
9   
10  package java.math;
11  
12  /**
13   * A simple bit sieve used for finding prime number candidates. Allows setting
14   * and clearing of bits in a storage array. The size of the sieve is assumed to
15   * be constant to reduce overhead. All the bits of a new bitSieve are zero, and
16   * bits are removed from it by setting them.
17   *
18   * To reduce storage space and increase efficiency, no even numbers are
19   * represented in the sieve (each bit in the sieve represents an odd number).
20   * The relationship between the index of a bit and the number it represents is
21   * given by
22   * N = offset + (2*index + 1);
23   * Where N is the integer represented by a bit in the sieve, offset is some
24   * even integer offset indicating where the sieve begins, and index is the
25   * index of a bit in the sieve array.
26   *
27   * @see     BigInteger
28   * @version 1.10, 12/19/03
29   * @author  Michael McCloskey
30   * @since   1.3
31   */
32  class BitSieve {
33      /**
34       * Stores the bits in this bitSieve.
35       */
36      private long bits[];
37  
38      /**
39       * Length is how many bits this sieve holds.
40       */
41      private int length;
42  
43      /**
44       * A small sieve used to filter out multiples of small primes in a search
45       * sieve.
46       */
47      private static BitSieve   smallSieve = new BitSieve  ();
48  
49      /**
50       * Construct a "small sieve" with a base of 0.  This constructor is 
51       * used internally to generate the set of "small primes" whose multiples
52       * are excluded from sieves generated by the main (package private)
53       * constructor, BitSieve(BigInteger base, int searchLen).  The length
54       * of the sieve generated by this constructor was chosen for performance;
55       * it controls a tradeoff between how much time is spent constructing
56       * other sieves, and how much time is wasted testing composite candidates
57       * for primality.  The length was chosen experimentally to yield good
58       * performance.
59       */
60      private BitSieve() {
61          length = 150 * 64;
62          bits = new long[(unitIndex(length - 1) + 1)];
63  
64          // Mark 1 as composite
65          set(0);
66          int nextIndex = 1;
67          int nextPrime = 3;
68  
69          // Find primes and remove their multiples from sieve
70          do {
71              sieveSingle(length, nextIndex + nextPrime, nextPrime);
72              nextIndex = sieveSearch(length, nextIndex + 1);
73              nextPrime = 2*nextIndex + 1;
74          } while((nextIndex > 0) && (nextPrime < length));
75      }
76  
77      /**
78       * Construct a bit sieve of searchLen bits used for finding prime number
79       * candidates. The new sieve begins at the specified base, which must
80       * be even.
81       */
82      BitSieve(BigInteger   base, int searchLen) {
83          /*
84           * Candidates are indicated by clear bits in the sieve. As a candidates
85           * nonprimality is calculated, a bit is set in the sieve to eliminate
86           * it. To reduce storage space and increase efficiency, no even numbers
87           * are represented in the sieve (each bit in the sieve represents an
88           * odd number).
89           */
90          bits = new long[(unitIndex(searchLen-1) + 1)];
91          length = searchLen;
92          int start = 0;
93          
94          int step = smallSieve.sieveSearch(smallSieve.length, start);
95          int convertedStep = (step *2) + 1;
96  
97          // Construct the large sieve at an even offset specified by base
98          MutableBigInteger   r = new MutableBigInteger  ();
99          MutableBigInteger   q = new MutableBigInteger  ();
100         do {
101             // Calculate base mod convertedStep
102             r.copyValue(base.mag);
103             r.divideOneWord(convertedStep, q);
104             start = r.value[r.offset];
105 
106             // Take each multiple of step out of sieve
107             start = convertedStep - start;
108             if (start%2 == 0)
109                 start += convertedStep;
110             sieveSingle(searchLen, (start-1)/2, convertedStep);
111 
112             // Find next prime from small sieve
113             step = smallSieve.sieveSearch(smallSieve.length, step+1);
114             convertedStep = (step *2) + 1;
115         } while (step > 0);
116     }
117         
118     /**
119      * Given a bit index return unit index containing it.
120      */
121     private static int unitIndex(int bitIndex) {
122         return bitIndex >>> 6;
123     }
124 
125     /**
126      * Return a unit that masks the specified bit in its unit.
127      */
128     private static long bit(int bitIndex) {
129         return 1L << (bitIndex & ((1<<6) - 1));
130     }
131 
132     /**
133      * Get the value of the bit at the specified index.
134      */
135     private boolean get(int bitIndex) {
136         int unitIndex = unitIndex(bitIndex);
137         return ((bits[unitIndex] & bit(bitIndex)) != 0);
138     }
139 
140     /**
141      * Set the bit at the specified index.
142      */
143     private void set(int bitIndex) {
144         int unitIndex = unitIndex(bitIndex);
145         bits[unitIndex] |= bit(bitIndex);         
146     }
147 
148     /**
149      * This method returns the index of the first clear bit in the search
150      * array that occurs at or after start. It will not search past the
151      * specified limit. It returns -1 if there is no such clear bit.
152      */
153     private int sieveSearch(int limit, int start) {
154         if (start >= limit)
155             return -1;
156         
157         int index = start;
158         do {
159             if (!get(index))
160                 return index;
161             index++;
162         } while(index < limit-1);
163         return -1;
164     }
165 
166     /**
167      * Sieve a single set of multiples out of the sieve. Begin to remove
168      * multiples of the specified step starting at the specified start index,
169      * up to the specified limit.
170      */
171     private void sieveSingle(int limit, int start, int step) {
172         while(start < limit) {
173             set(start);
174             start += step;
175         }
176     }
177 
178     /**
179      * Test probable primes in the sieve and return successful candidates.
180      */
181     BigInteger   retrieve(BigInteger   initValue, int certainty) {
182         // Examine the sieve one long at a time to find possible primes
183         int offset = 1;
184         for (int i=0; i<bits.length; i++) {
185             long nextLong = ~bits[i];
186             for (int j=0; j<64; j++) {
187                 if ((nextLong & 1) == 1) {
188                     BigInteger   candidate = initValue.add(
189                                            BigInteger.valueOf(offset));
190                     if (candidate.primeToCertainty(certainty))
191                         return candidate;
192                 }
193                 nextLong >>>= 1;
194                 offset+=2;
195             }
196         }
197         return null;
198     }
199 }
200
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags