Masalahnya adalah sebagai berikut.

Input: Bilangan bulatn

Output: Perdana terkecil lebih besar dari n.

Tantangannya adalah untuk memberikan kode tercepat yang dapat dilakukan. Saya akan menguji kode pada nilai mulai dari ukuran kira10^8 10^200 - kira dan menggandakan ukuran sampai dibutuhkan lebih dari satu menit 10 detik di komputer saya.

Kode yang menang akan menemukan perdana berikutnya untuk ukuran input terbesar.

Sebagai perbandingan, saringan sederhana yang ditulis dengan python mampu menemukan perdana berikutnya yang lebih besar dari 10^8pada sekitar20 hitungan detik.

Persyaratan bahwa saya dapat mengujinya pada komputer ubuntu RAM 4GB saya sangat ketat. Semua kode harus gratis (dalam kedua pengertian) dan jika menggunakan pustaka mereka juga harus bebas dan mudah diinstal. Setiap bilangan prima yang dilaporkan akan segera mendiskualifikasi pengajuan.

Saya akan memberikan pujian terpisah untuk pemenang dalam setiap bahasa pemrograman juga jika kode sepenuhnya ditulis dalam bahasa itu tanpa menggunakan perpustakaan eksternal. Saya juga akan membuat tabel berjalan dari waktu tercepat saat kompetisi berlangsung sehingga orang dapat melihat bagaimana kinerja mereka.

Meja sejauh ini

• Python. 357Digit prima yang menakjubkan 343239883006530485749095039954069660863471765007165270469723172959277159169882802606127982033072727748864815569574042901856099399985832190628701414555752857600000000000000000000000000000000000000002872284792758930912601189043411951050852357613658978971208596097634095500808832510259693761982135208603287199546795000697807728609476163156438356035166156820611adalah angka terakhir di bawah 10 detik menggunakan kode yang disediakan oleh primo. Adakah yang akan mengalahkan entri pertama ini?

Python ~ 451 digit

Ini adalah bagian dari perpustakaan yang saya tulis untuk masalah faktorisasi semiprime , dengan fungsi yang tidak perlu dihapus. Ia menggunakan tes primality Baillie-PSW , yang secara teknis merupakan tes probabilistik, tetapi hingga saat ini, tidak ada pseudoprim yang diketahui - dan bahkan ada hadiah uang tunai jika Anda dapat menemukannya (atau untuk memberikan bukti bahwa tidak ada) .

Sunting : Saya tidak menyadari bahwa Python memiliki eksponensial modular bawaan. Mengganti sendiri untuk hasil bawaan menghasilkan peningkatan kinerja sekitar 33%.

my_math.py

# legendre symbol (a|m)
# note: returns m-1 if a is a non-residue, instead of -1
def legendre(a, m):
  return pow(a, (m-1) >> 1, m)

# strong probable prime
def is_sprp(n, b=2):
  d = n-1
  s = 0
  while d&1 == 0:
    s += 1
    d >>= 1

  x = pow(b, d, n)
  if x == 1 or x == n-1:
    return True

  for r in range(1, s):
    x = (x * x)%n
    if x == 1:
      return False
    elif x == n-1:
      return True

  return False

# lucas probable prime
# assumes D = 1 (mod 4), (D|n) = -1
def is_lucas_prp(n, D):
  P = 1
  Q = (1-D) >> 2

  # n+1 = 2**r*s where s is odd
  s = n+1
  r = 0
  while s&1 == 0:
    r += 1
    s >>= 1

  # calculate the bit reversal of (odd) s
  # e.g. 19 (10011) <=> 25 (11001)
  t = 0
  while s > 0:
    if s&1:
      t += 1
      s -= 1
    else:
      t <<= 1
      s >>= 1

  # use the same bit reversal process to calculate the sth Lucas number
  # keep track of q = Q**n as we go
  U = 0
  V = 2
  q = 1
  # mod_inv(2, n)
  inv_2 = (n+1) >> 1
  while t > 0:
    if t&1 == 1:
      # U, V of n+1
      U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n
      q = (q * Q)%n
      t -= 1
    else:
      # U, V of n*2
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      t >>= 1

  # double s until we have the 2**r*sth Lucas number
  while r > 0:
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      r -= 1

  # primality check
  # if n is prime, n divides the n+1st Lucas number, given the assumptions
  return U == 0

# primes less than 212
small_primes = set([
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97,101,103,107,109,113,
  127,131,137,139,149,151,157,163,167,173,
  179,181,191,193,197,199,211])

# pre-calced sieve of eratosthenes for n = 2, 3, 5, 7
indices = [
    1, 11, 13, 17, 19, 23, 29, 31, 37, 41,
   43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
   89, 97,101,103,107,109,113,121,127,131,
  137,139,143,149,151,157,163,167,169,173,
  179,181,187,191,193,197,199,209]

# distances between sieve values
offsets = [
  10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
   6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
   2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
   4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2]

max_int = 2147483647

# an 'almost certain' primality check
def is_prime(n):
  if n < 212:
    return n in small_primes

  for p in small_primes:
    if n%p == 0:
      return False

  # if n is a 32-bit integer, perform full trial division
  if n <= max_int:
    i = 211
    while i*i < n:
      for o in offsets:
        i += o
        if n%i == 0:
          return False
    return True

  # Baillie-PSW
  # this is technically a probabalistic test, but there are no known pseudoprimes
  if not is_sprp(n): return False
  a = 5
  s = 2
  while legendre(a, n) != n-1:
    s = -s
    a = s-a
  return is_lucas_prp(n, a)

# next prime strictly larger than n
def next_prime(n):
  if n < 2:
    return 2
  # first odd larger than n
  n = (n + 1) | 1
  if n < 212:
    while True:
      if n in small_primes:
        return n
      n += 2

  # find our position in the sieve rotation via binary search
  x = int(n%210)
  s = 0
  e = 47
  m = 24
  while m != e:
    if indices[m] < x:
      s = m
      m = (s + e + 1) >> 1
    else:
      e = m
      m = (s + e) >> 1

  i = int(n + (indices[m] - x))
  # adjust offsets
  offs = offsets[m:]+offsets[:m]
  while True:
    for o in offs:
      if is_prime(i):
        return i
      i += o

Contoh skrip uji:

from time import clock
from my_math import *

n = i = 317**79
while True:
  i *= 317
  time1 = clock()
  n, o = next_prime(i), n
  span = clock()-time1
  if span > 10:
    break
  print(len(str(n)), span)
print(o)

Faktor 317 dipilih, karena kira-kira akar kuadratnya 10000, menambahkan sekitar 2,5 digit per iterasi (dan karena penggandaan terlalu lambat untuk diduduki). Output menunjukkan jumlah digit saat ini, dan waktu yang dibutuhkan.

Hasil sampel:

201 0.13121248650317288
203 0.059535499623555505
206 0.9157767258129175
208 0.2583420518529589
211 0.15367400046653978
213 0.32343915218274955
216 1.3962866788935466
218 0.5986165839513125
221 0.973842206202185
223 2.346910291671148
...
428 0.932809896229827
431 4.345940056627313
433 9.511724255457068
436 6.089835998709333
438 1.3793498894412721
441 4.290633027381972
443 3.5102506044762833
446 3.1629148397352083
448 3.364759208223404
451 7.34668009481652
1551197868099891386459896063244381932060770425565921999885096817830297496627504652115239001983985153119775350914638552307445919773021758654815641382344720913548160379485681746575245251059529720935264144339378936233043585239478807971817857394193701584822359805681429741446927344534491412763713568490429195862973508863067230162660278070962484418979417980291904500349345162151774412157280412235743457342694749679453616265540134456421369622519723266737913

Semua kode sekarang kompatibel dengan python.

C ++ dengan GMP: 567 digit

Menggunakan implementasi Miller-Rabin di GMP. Ini mungkin mengembalikan positif palsu, tetapi keberuntungan benar-benar memukul seseorang dengan probabilitas 2 ^ -200.

#include <gmp.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

double time() {
  struct timeval t;
  gettimeofday(&t, NULL);
  return t.tv_usec  * 1e-6 + t.tv_sec;
}

int main(int argc, char *argv[]) {
  mpz_t n, m;
  mpz_init_set_ui(n, 10);
  mpz_pow_ui(n, n, 200);
  mpz_init(m);
  for (int i = 0; true; i++, mpz_mul_ui(n, n, 2)) {
    double start = time();
    for (mpz_add_ui(m, n, 1); !mpz_millerrabin(m, 100); mpz_add_ui(m, m, 2)) ;
    double t = time() - start;
    gmp_printf("%d %Zd %f\n", i, m, t);
    if (t > 10.0) break;
  }
}

Menemukan yang terbaik 10^200 * 2^1216 + 361(567 digit) sebelum berjalan dari waktu ke waktu di laptop lambat saya.

Perl dengan modul GMP, 1300 digit

Menggunakan modul saya Math :: Prime :: Util dan bagian belakang GMP -nya . Titik potong yang tepat akan tergantung pada komputer Anda dan apakah Anda memiliki perpustakaan GMP terbaru. Semua kode gratis (modul-modulnya ada di github dan CPAN, dan GMP tersedia secara bebas). Saya sudah menjalankannya di AWS's Ubuntu dan juga desktop Ubuntu (dan Fedora, dan AIX, dan NetBSD, dll.).

Kode inti dalam C dan C + GMP. next_prime dari MPU melihat jumlahnya terlalu besar dan meneruskannya ke bagian belakang GMP (atau kode Perl murni jika bagian belakang tidak diinstal). Itu menguatkan dan mengkonversi ke mpz, dan akan mengubah hasilnya kembali menjadi tipe objek input atau Math :: BigInt. next_prime sendiri tidak:

• roda mod 30
• melacak sisa mod 23 # sehingga dapat melakukan modulos asli untuk primes hingga 23
• kemungkinan ujian utama pada hal-hal yang lulus ini.

Kemungkinan ujian utama adalah:

• periksa pembagi kecil menggunakan mpz_gcd_ui (dalam 64-bit dua dari ini periksa hingga 101)
• periksa pembagi kecil menggunakan primorial tunggal yang dihitung sendiri. Ini bisa berupa bilangan prima hingga 10k atau 40k tergantung pada ukuran input.
• untuk nilai yang lebih besar dari 2 ^ 1600, lakukan pembagian percobaan lebih lanjut menggunakan pohon-pohon. Ini bisa dilakukan dengan lebih efisien.
• akhirnya, ES BPSW dilakukan (uji Miller-Rabin dengan basis 2 diikuti oleh uji Lucas yang sangat kuat ).

Segala sesuatu sebelum ES BPSW hanyalah optimasi, yang tentu saja kita inginkan untuk next_prime. next_prime juga diimplementasikan dalam Perl menggunakan modul Math :: BigInt (pada intinya dengan Pari opsional dan ujung belakang GMP). Itu memang AES BPSW (seperti Pari) tetapi tidak dioptimalkan.

Saya telah memikirkan manfaat versi berbasis saringan parsial, menggunakan kisaran, misalnya, 2 manfaat. Saya hanya tidak yakin apakah ini akan benar-benar lebih baik, karena sebagian besar waktu kita akan melakukan penyaringan yang tidak perlu karena celahnya kecil, dan kadang-kadang untuk celah yang besar kita harus mengulanginya berkali-kali.

Perpustakaan mengimplementasikan ECPP (termasuk sertifikat) sehingga kami dapat menjalankan bukti pada hasilnya, tetapi 1200 digit benar-benar terlalu besar untuk kumpulan standar kecil dari polinomial yang disertakan (ada metode untuk mengunduh set yang lebih besar - bukti akan sedikit di bawah 15 menit yang sedikit lebih cepat dari APR-CL Pari tetapi sedikit lebih lambat dari mpz_aprcl WraithX). Satu kelemahan ECPP vs APR-CL adalah varians waktunya lebih banyak sehingga ada kemungkinan lebih dari 10 detik untuk beberapa angka sebelum waktu rata-rata tiba di sana. Dengan bukti saya pikir kami terbatas pada sesuatu dalam kisaran 400 digit kecuali kami mengizinkan perangkat lunak multi-threaded.

#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util ":all";
use Math::Prime::Util::GMP;  # Barf if the backend isn't installed
use Time::HiRes qw(gettimeofday tv_interval);
use Math::GMP;

my $n = Math::GMP->new(10) ** 200;
while (1) {
  my $start = [gettimeofday];
  my $np = next_prime($n);
  my $sec = tv_interval($start);
  my $len = length($n);
  die "next_prime $len = +",$np-$n," in $sec seconds\n" if $sec > 10;
  warn "  next_prime $len = +",$np-$n," in $sec seconds\n";
  $n *= 10;
}

Saya memutuskan untuk mencoba dengan urutan yang sama yang digunakan oleh primo. Ia mencapai 1191 digit, karena di situlah kami mencapai celah 18.138. Saya juga menguji kode primo menggunakan my_math.py terbaru. Ia mencapai 630 digit dengan urutan 10 ^ dan 641 dengan urutannya. Sangat mengesankan untuk kode semua-Python yang ringkas tanpa banyak pretest.