F#Power问题接受两个参数都是bigints

Question

我目前正在试验F#.在互联网上找到的文章很有帮助,但作为一名C#程序员,我有时遇到我认为我的解决方案会有所帮助的情况,但它没有或只是部分帮助.

因此,我对F#缺乏了解(最有可能的是,编译器的工作方式)可能是我有时会非常惊讶的原因.

例如,我写了一个C#程序来确定完美的数字.它使用欧几里德证明的已知形式,可以从Mersenne Prime 2p-1(2p-1)(其中2p-1是素数,p表示为幂)形成完美数.

由于F#的帮助声明'**'可用于计算功率,但使用浮点,我试图用bitshift运算符创建一个简单的函数(<<<)(注意我编辑了这个代码指出需要):

 let PowBitShift (y:int32) = 1 <<< y;;

但是,在运行测试并寻找性能改进时,我还尝试了一种形式,我记得使用Miranda(一种函数式编程语言),它使用递归和模式匹配器来计算功率.主要的好处是我可以使用变量y作为64位整数,这对于标准的bitshift运算符是不可能的.

    let rec Pow (x : int64) (y : int64) = 
    match y with
        | 0L -> 1L
        | y -> x * Pow x (y - 1L);;

事实证明,这个功能实际上更快,但我不能(还)理解原因.也许这是一个不那么智力的问题,但我仍然很好奇.

那么秒的问题就是,当计算完美数字时,你会遇到这样一个事实:在找到第9个完美数字(由31的幂形成)之后,int64无法显示大数字交叉.我试图找出你是否可以使用BigInteger对象(或bigint类型),但在这里我对F#的了解阻止了我一点.是否有可能创建一个接受两个参数的幂函数？

我目前有这个:

let rec PowBigInt (x : bigint) (y : bigint) = 
    match y with
        | bigint.Zero -> 1I
        | y -> x * Pow x (y - 1I);;

但它抛出了bigint.Zero未定义的错误.所以我也在做错事.0I不被接受作为替代,因为它给出了这个错误:

Non-primitive numeric literal constants cannot be used in pattern matches because they    
can be mapped to multiple different types through the use of a NumericLiteral module.  
Consider using replacing with a variable, and use 'when <variable> = <constant>' at the 
end of the match clause.    

但模式匹配器不能使用'when'语句.还有其他解决办法吗？

在此先感谢,请原谅我的长篇文章.我只是尽力表达我的"挑战".

Answer 1

我不明白为什么你需要y成为一个int64或一个bigint.根据这个链接,最大的已知梅森数是一个p = 43112609,其中p确实在范围内int.

其y作为一个整数,你可以使用标准的运营商pown : ^T -> int -> ^T,而不是因为:

let Pow (x : int64) y = pown x y
let PowBigInt (x: bigint) y = pown x y

关于模式匹配的问题bigint,错误消息非常清楚地表明您可以通过when警卫使用模式匹配:

let rec PowBigInt x y = 
    match y with
    | _ when y = 0I -> 1I
    | _ -> x * PowBigInt x (y - 1I)

Answer 2

我认为最简单的定义方法PowBigInt是使用if而不是模式匹配:

let rec PowBigInt (x : bigint) (y : bigint) =  
  if y = 0I then 1I   
  else x * PowBigInt x (y - 1I) 

问题是这bigint.Zero是一个返回值的静态属性,但模式只能包含(常量)文字或F#活动模式.它们不能直接包含属性(或其他)调用.但是,where如果您仍然愿意,可以在子句中编写其他约束match:

let rec PowBigInt (x : bigint) (y : bigint) =  
  match y with 
  | y when y = bigint.Zero -> 1I 
  | y -> x * PowBigInt x (y - 1I)

作为旁注,你可以使用尾递归使函数更有效(想法是如果一个函数使递归调用成为最后一个东西,那么它可以更有效地编译):

let PowBigInt (x : bigint) (y : bigint) =   
  // Recursive helper function that stores the result calculated so far
  // in 'acc' and recursively loops until 'y = 0I'
  let rec PowBigIntHelper (y : bigint) (acc : bigint) =
    if y = 0I then acc 
    else PowBigIntHelper (y - 1I) (x * acc)
  // Start with the given value of 'y' and '1I' as the result so far
  PowBigIntHelper y 1I

关于PowBitShift功能 - 我不确定它为什么慢,但它绝对没有你需要的.使用位移来实现功率仅在基数为2时有效.

Answer 3

您无需创建Pow功能.(**)运算符对bigint有一个重载 - > int - > bigint.只有第二个参数应该是一个整数,但我认为这不是一个问题.试一试

bigint 10**32 ;;

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}