快速生成Fibonacci素数

Question

不出所料，fibonacci素数是素数，也是斐波那契数。目前已知的Fibonacci素数有34个，另外还有15个可能的Fibonacci素数。为了解决这个问题，Fibonacci数是F_n定义为F_1 = 1、F_2 = 1和F_n = F_{n-1} + F_{n-2}的序列，如果一个数字通过了概率素数测试，并且不正确的概率小于2^{-32}，那么它就被认为是素数。例如，由于k圆Miller-Rabin测试的错误概率为4^{-k}，因此16轮Miller-Rabin测试足以证明该挑战的原素性。

提交：

这个挑战的目标是编写一个完整的程序，在斐波纳契级数中尽可能快地计算每个斐波纳契素数及其索引。

提交应是一个完整的程序，完整的说明，建设和运行它。提交必须以一种免费的语言提供给非商业用途，并且能够在Windows 10上运行，并且用户必须准备好为该语言提供安装说明。外部库是允许的，但也适用于语言。

素数将输出，方法是将它们写入基10整数，以格式按升序进行输出。

index,prime\n

其中\n是换行符。数字可以有额外的前导/尾随空格，而不是换行符。

评分

这些程序将在Intel(R) Core(TM) i5-8365U CPU上运行，具有8个线程、avx-2支持和24G内存。能在一分钟内正确到达的最大质数获胜。打破平局是达到最大价值所需的时间。篡改我的电脑或测试程序的程序将被取消资格。如果程序出现错误或无法产生正确的输出，将根据其失败前到达的最远斐波那契素数来判断。

结果

遗憾的是，让Anders的条目正确地构建起来比它所需要的要困难得多。

Results:
  anders_kaseorg:
    num: 27
    time: 44.6317962s
  aleph_alpha:
    num: 24
    time: 22.6188601s
  example:
    num: 12
    time: 23.2418081s

另见：A005478，A001605

测试程序可以找到这里。此外，还有一个示例程序这里。

Answer 1

Rust，F_{14431}在≈58 s

中

(基于预期CPU性能比的非官方估计。)

在特殊大小写F_3, F_4之后，使用GMP mpz_probab_prime_p函数测试每个素数索引的斐波纳契数，该函数执行贝利-PSW测试和rep - 24 米勒-拉宾迭代。由于Baillie没有经过验证的错误限制，所以我通过24 + 16来确保16次Miller-Rabin迭代.

使用cargo build --release构建并运行target/release/fibprimes。

Cargo.toml

[package]
name = "fibprimes"
version = "0.1.0"
edition = "2021"

[dependencies]
pariter = "0.5.1"
rug = { version = "1.16.0", features = ["integer"], default-features = false }

src/main.rs

use pariter::IteratorExt;
use rug::{integer::IsPrime, Integer};
use std::iter;

fn main() {
    println!("3,2");
    println!("4,3");

    let mut fib0 = Integer::from(1);
    let mut fib1 = Integer::from(2);
    let mut n = Integer::from(3);

    for (n, fib) in iter::from_fn(move || {
        let n1 = Integer::from(n.next_prime_ref());
        while n != n1 {
            fib0 += &fib1;
            fib1 += &fib0;
            n += 2;
        }
        Some((n.clone(), fib1.clone()))
    })
    .parallel_filter(|(_, fib)| fib.is_probably_prime(24 + 16) != IsPrime::No)
    {
        println!("{n},{fib}");
    }
}

Answer 2

C + 帕里/GP's C库，F_{9677} in 25s在我的计算机

上

#include <pari/pari.h>

void f(long n)
{
    GEN a = fibo(n);
    if (ispseudoprime(a, 16))
        pari_printf("%d,%Ps\n", n, a);
    return;
}

int main()
{
    pari_init(8000000, 500000);

    f(3);
    f(4);

    long n;
    forprime_t iter;
    u_forprime_init(&iter, 5, ULONG_MAX);

    while (n = u_forprime_next(&iter))
        f(n);

    return 0;
}

如果您正在使用Ubuntu或Debian，则需要安装包libpari-dev。对于Arch来说，pari-gp就足够了。

使用gcc -O3 filename.c -lpari编译。