6个稳定版本
1.3.0 | 2024年6月27日 |
---|---|
1.2.2 | 2023年10月6日 |
1.2.1 | 2023年9月9日 |
1.2.0 | 2023年7月1日 |
1.0.0 | 2023年4月24日 |
#175 in 数学
66 每月下载次数
用于 2 个Crate(通过 数论)
1.5MB
17K SLoC
Machine prime是一个简单的64位整数素性检验,以可重复的方式构建,使用了F-Analysis库和Feitsma/Galway的2的底数伪素数表。它可以在crates.io上获得。
提供了两个具有C风格API的函数,以便在其他语言中调用。
- is_prime
- is_prime_wc (最坏情况)
is_prime针对平均情况进行了优化,并用作通用素性检验。is_prime_wc针对最坏情况进行了优化,并用于已怀疑为素数的数字的函数中。例如,在已经执行了试除法的因式分解中。它执行绝对最小的检查,并允许有少量已知的失败点,留给用户决定是否需要付出代价来检查它们。
此函数API将永远不会改变。is_prime将始终正确评估任何64位整数,但is_prime_wc的失败点可能会更改。
这些函数提供了三种模式,默认、小型和微型。随着每个后续模式的内存使用减少,复杂性增加。
默认模式使用大型散列表,并通过素数逆乘以进行试除法
- is_prime复杂度:最坏情况2.23 * Fermat检验,平均情况0.28 * Fermat检验
- is-prime_wc复杂度:最坏情况1.95 * Fermat检验,平均情况1.2* fermat检验
- is_prime_wc失败:在0处恐慌,将1标记为素数,将2标记为合数
- 由f-analysis的
to_hashtable(Some(262144),Some(1276800789),Some(65535))
构建散列表。计算到Feitsma表的EPF伪素数,并应用散列表方法来重现使用的散列表。请参阅f-analysis中的"散列表"示例以获取显式实现。 - 总内存:526464字节
SSMR与默认值相同,但对于小于2^40的整数将分支到使用SSMR算法
- 参数和失败情况与SSMR存储库相同
- 由于分支、缓存利用和计算修改,它比SSMR存储库慢
- 只有当SSMR存储库不提供足够大的区间时才使用此变体
Small省略了散列表,但仍使用试除法
- is_prime复杂度:最坏情况2.8 * Fermat测试,平均情况<0.567 * Fermat测试
- is-prime_wc复杂度:最坏情况2.5 * Fermat测试,平均情况<1.31 * Fermat测试
- is_prime_wc失败:在0处恐慌,将1标记为素数,将2标记为合数,1194649和12327121无限循环
- 除了最初的Fermat测试外,还使用修改后的Lucas序列测试
Tiny仅使用Small中实现的Fermat基,因此is_prime和is_prime_wc之间唯一的区别是后者省略了任何额外的检查以确保正确性。它比Small节省一小部分内存。
请注意,所有失败在调试模式下都将导致恐慌,但被优化覆盖,Makefile生成的动态库不会对任何情况恐慌。
用法
由于编译无标准库存在一些障碍,crates.io和存储库中的版本略有不同,尽管使用的是完全相同的算法。crates.io版本是为稳定的编译器配置的,而存储库是为夜间编译器配置的,因为目的是用它来构建动态库。
要从crates.io使用,只需在cargo.toml文件中包含它,并使用“small”或“tiny”功能(如果您想使用这些版本)。默认值将是最快的,具有散列表。
要作为动态库使用,请确保您正在运行rustc夜间版本; git clone
此存储库并运行make
以编译默认模式,make small
以编译Small模式,make tiny
以编译Tiny模式。这将创建库,并且make install
将安装到/lib/libprime.so
。 (确保您是超级用户)。安装库是推荐的,但不是绝对必要的。如果您使用gcc,请使用-lprime
链接到它。
请参阅存储库中的"binding"文件夹中的各种语言绑定。支持包括Ada、C、Fortran、Julia和Python在内的几种语言。
目的
许多数论函数要么需要素性测试,要么使用素性测试以提高效率。例如,勒让德符号和分解。虽然素性测试很少是这些函数的瓶颈,但它是在高度优化的计算中的限制因素。通过提供一种快速的开源实现,该实现可以在许多语言和架构中调用,可以最小化构建此类函数的工作。
注意事项
此素性测试的目的不是在所有区间中都是最快的,而是在一般情况下更快,平均情况更快。有些小测试对于32位来说更快,然而这个区间如此之小,以至于为它们进行分支将导致总体效率降低。有关基准测试和与其他高效素性测试的比较,请参阅性能。
存在一些用于优化内存的快速函数。然而,它们使用了浮点数运算。该库的目的是实现极高的速度,同时足够灵活,以便在只支持整数运算时也能使用。因此,没有使用浮点数运算、内联汇编和SIMD。此外,这也是为什么提供低内存版本的原因,因为并非每个人都能或愿意使用超过500千字节的内存。
二进制动态库的大小因编译器而异,但以下是一些合理的估计:默认-542.4kb,小型-18.1kb,微型-14kb
对于嵌入式系统的构建尚未经过测试,但尚未发现导致失败的原因。
此软件属于公共领域,所有值都可以使用开源的可审计的f-analysis库进行确定性重新计算。