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