P_P

SoE segmented

P_P
Mar 18th, 2018
580
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //    https://codereview.stackexchange.com/q/189083
  2.  
  3. //    https://pastebin.com/0F6fiEAD
  4.  
  5. /*                    old-ns-new               old-s-new
  6.       primes <   25     47    47    p < 2^31   7.0   2.0
  7.                  50     62    63        2^32  15.0   4.2
  8.                 100     78    78
  9.                 200    141   110         1e9         0.9
  10.                 400    218   187         2e9         1.8
  11.                 800    406   344         4e9         3.9
  12.                1600    718   639
  13.                3200   1435  1295
  14.                6400   2855  2590                            */
  15.  
  16. //    https://pastebin.com/xK6c0EVc
  17. //    ~ 10 % faster (not for small limits ;)
  18.  
  19. #include "stdafx.h"
  20. #include <vector>
  21. #include <iostream>
  22. #include <ctime>
  23. #include <Windows.h>
  24. using namespace std;
  25. typedef unsigned int u32;
  26. vector<u32> x; vector<u32> p;
  27.  
  28. void buildX(u32 m)  // mark odd composites
  29. {
  30.     m -= m / ~0u; m += m & 1; m >>= 1;
  31.     u32 r0, r1 = 0, a = 1, b = 1, c = 1, d = m >> 5;
  32.     x.resize(d + 1); x[0] = 0x9b4b3491;
  33.     for (;;)                                      // 3x23 3x25 3x27 ...
  34.     {
  35.         if (a > d) break; x[a++] = 0x24924924;
  36.         if (a > d) break; x[a++] = 0x49249249;
  37.         if (a > d) break; x[a++] = 0x92492492;
  38.     }
  39.     for (;;)                                      // 5x13 5x15 5x17 ...
  40.     {
  41.         if (b > d) break; x[b++] |= 0x42108421;
  42.         if (b > d) break; x[b++] |= 0x10842108;
  43.         if (b > d) break; x[b++] |= 0x84210842;
  44.         if (b > d) break; x[b++] |= 0x21084210;
  45.         if (b > d) break; x[b++] |= 0x08421084;
  46.     }
  47.     for (;;)                                      // 7x11 7x13 7x15 ...
  48.     {
  49.         if (c > d) break; x[c++] |= 0x08102040;
  50.         if (c > d) break; x[c++] |= 0x40810204;
  51.         if (c > d) break; x[c++] |= 0x04081020;
  52.         if (c > d) break; x[c++] |= 0x20408102;
  53.         if (c > d) break; x[c++] |= 0x02040810;
  54.         if (c > d) break; x[c++] |= 0x10204081;
  55.         if (c > d) break; x[c++] |= 0x81020408;
  56.     }
  57.     while ((r0 = r1) < m)  // L1 cache 64 KB / 2 = 0x40000
  58.     {
  59.         if ((r1 += 0x40000) > m) r1 = m;
  60.         for (a = 11, b = 60, c = 20; b < r1; a += 2, b += c += 4)
  61.             if ((x[a >> 6] & 1 << (a >> 1)) == 0)
  62.             {
  63.                 if ((d = b) < r0)
  64.                 {
  65.                     d += (r0 - d) / a * a;
  66.                     if (d < r0) d += a;
  67.                 }
  68.                 while (d < r1) { x[d >> 5] |= 1 << d; d += a; }
  69.             }
  70.     }
  71.     x[m >> 5] |= ~0u << m;
  72. }
  73.  
  74. void countPrimes()
  75. {
  76.     u32 c = 1; int i = x.size() - 1;
  77.     while (i >= 0) c += __popcnt(~x[i--]);
  78.     p.resize(c);
  79. }
  80.  
  81. void primes(u32 m)  // primes <= m
  82. {
  83.     if (m > 1)
  84.     {
  85.         buildX(m); countPrimes(); p[0] = 2;
  86.         u32 u = ~0u, v = ~0u, xi; DWORD tz;
  87.         for (int i = 0, n = 1, c = p.size(); n < c; v = u += 64)
  88.             for (xi = ~x[i++]; xi; p[n++] = v += (tz + 1) << 1)
  89.             {
  90.                 _BitScanForward(&tz, xi); xi >>= tz; xi >>= 1;
  91.             }
  92.     }
  93. }
  94.  
  95. int main()
  96. {
  97.     primes(1000);
  98.     for (u32 m = 25; m < 6401; m <<= 1)  // for (u32 m = 0; m < 9; m++)
  99.     {
  100.         primes(m);
  101.         if (m > 1)
  102.         {
  103.             u32 maxP = p[p.size() - 1];
  104.             cout << "largest prime <= " << m << ": " << maxP << "  ";
  105.         }
  106.         clock_t clock0 = clock();
  107.         for (int i = 1000000; i; i--)
  108.         {
  109.             x.resize(0); p.resize(0); primes(m);
  110.         }
  111.         cout << clock() - clock0 << " ns: ";
  112.         cout << p.size() << " primes" << endl << endl;
  113.     }
  114.     x.resize(0); p.resize(0); u32 m = (u32)~0u >> 0;
  115.     clock_t clock0 = clock(); primes(m);
  116.     cout << clock() - clock0 << " ms: ";
  117.     cout << p.size() << " primes <= " << m;
  118.     for (int j = p.size(), i = j - 5; i < j;) cout << endl << p[i++];
  119.     getchar();
  120. }
  121.  
  122.  
  123. //  void buildX(u32 m) {
  124. //      m -= m / ~0u; m += m & 1; m >>= 1;
  125. //      u32 r0, r1 = 0, a = 1, b = 1, c = 1, d = m >> 5;
  126. //      x.resize(d + 1); x[0] = 0x9b4b3491;
  127. //  L0: if (a > d) goto L1; x[a++] = 0x24924924;;
  128. //      if (a > d) goto L1; x[a++] = 0x49249249;;
  129. //      if (a > d) goto L1; x[a++] = 0x92492492;; goto L0;
  130. //  L1: if (b > d) goto L2; x[b++] |= 0x42108421;
  131. //      if (b > d) goto L2; x[b++] |= 0x10842108;
  132. //      if (b > d) goto L2; x[b++] |= 0x84210842;
  133. //      if (b > d) goto L2; x[b++] |= 0x21084210;
  134. //      if (b > d) goto L2; x[b++] |= 0x08421084; goto L1;
  135. //  L2: if (c > d) goto L3; x[c++] |= 0x08102040;
  136. //      if (c > d) goto L3; x[c++] |= 0x40810204;
  137. //      if (c > d) goto L3; x[c++] |= 0x04081020;
  138. //      if (c > d) goto L3; x[c++] |= 0x20408102;
  139. //      if (c > d) goto L3; x[c++] |= 0x02040810;
  140. //      if (c > d) goto L3; x[c++] |= 0x10204081;
  141. //      if (c > d) goto L3; x[c++] |= 0x81020408; goto L2;
  142. //  L3: if ((r0 = r1) == m) { x[m >> 5] |= ~0u << m; return; }
  143. //      if ((r1 += 0x40000) > m) r1 = m;
  144. //      for (a = 9, b = 60, c = 20; b < r1; b += c += 4)
  145. //          if ((x[(a += 2) >> 6] & 1 << (a >> 1)) == 0) {
  146. //              if ((d = b) < r0) d += (r0 - d + a ^ 1) / a * a;
  147. //              while (d < r1) { x[d >> 5] |= 1 << d; d += a; }
  148. //          } goto L3;
  149. //  }
  150.  
  151. //  void countPrimes() {
  152. //      u32 c = 1, xi;
  153. //      for (int i = x.size() - 1; i >= 0; i--)
  154. //          for (xi = ~x[i]; xi; xi &= xi - 1) c++;
  155. //      p.resize(c);
  156. //  }
RAW Paste Data