#阶乘 #数论 #组合数学 #大数 #性能

sirp

计算阶乘、k-阶乘和SIRP的性质

2 个版本

0.1.1 2022年1月4日
0.1.0 2021年12月13日

#1813 in 数学

MIT 许可证

10KB
162

SIRP

这是一个新颖的数学包,可以计算大阶乘、k-阶乘和(连续)区间剩余乘积,直到(2^64-1)!。此外,它还包括对这些因数分解和日志的快速评估,而不依赖于直接计算。

它目前使用数论库进行任意精度算术。

注意,fast_log 和 fast_factor 没有保证准确性,仅适用于估算难以计算的极大值。然而,fast_log 在大多数情况下表现相当不错,误差小于一个数字。但是,fast_factor 使用基于几何级数和简单除法的估计,在大多数情况下表现都很差,除了1-阶乘,即使在这种情况下也不精确。

计算单个阶乘、双阶乘和SIRP的示例

   use sirp::Sirp;
   
   // the factorial, aka the product of all numbers in the interval 1..100
   
   let  factorial_100 = Sirp::new(1,100,1,0).unwrap() ; 
   
   // the double factorial 100!!
   
   let double_100 = Sirp::new(1,100,2,0).unwrap() ;
   
     // the product of all odd numbers in the interval 1..100
     
   let double_odd_100 = Sirp::new(1,100,2,1).unwrap();
   
    // the product of all odd numbers in the interval 50..100
    
   let sirp_50_100 = Sirp::new(50,100,2,1).unwrap();
   
    // generate the digits to display later
    
   factorial_100.gen_digits();
   
   // compute the logarithm near-exactly
   
    double_100.log(10);
    
   // compute the  exact factorization
   
   double_100_odd.factor()
   
   // constant-time (i.e nanosecond) estimate of logarithm 
   
   double_odd_100.fast_log(10);
   
   // Estimate of factor
   
   sirp_50_100.fast_factor()
     
   
    

等等。Sirp是一种更通用的方法,包括阶乘、阶乘的区间和k-阶乘。请参阅阶乘和SIRP,以了解该包的进一步讨论和一些使用的算法。

依赖项

~305KB