F# 电源问题，它接受两个参数都是 bigint

Question

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

因此，我对 F# 缺乏了解(最有可能的是，编译器的工作原理)可能是我有时完全大吃一惊的原因。

例如，我编写了一个 C# 程序来确定完全数。它使用已知形式的欧几里得证明，即可以从梅森素数 2p-1(2p-1)(其中 2p-1 是素数，p 表示为 的幂)形成完全数。

由于 F# 的帮助说明 '**' 可用于计算幂，但使用浮点数，因此我尝试使用位移运算符 (<<<) 创建一个简单的函数(请注意，我已为指出需要):

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

但是，在运行测试并寻求性能改进时，我还尝试了一种我记得使用 Miranda(也是一种函数式编程语言)的形式，它使用递归和模式匹配器来计算幂。主要的好处是我可以将变量 y 用作 64 位整数，这在标准位移运算符中是不可能的。

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

事实证明，这个函数实际上更快，但我(还)无法理解原因。也许这是一个不太理智的问题，但我仍然很好奇。

第二个问题是，在计算完全数时，您会遇到这样一个事实，即 int64 在找到第 9 个完全数(由 31 的幂形成)后无法显示大数交叉。我试图找出您是否可以使用 BigInteger 对象(或 bigint 类型)，但在这里我对 F# 的了解有点阻碍我。是否可以创建一个接受两个参数都是 bigint 的幂函数？

我目前有这个:

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 .根据 this link ，已知最大的梅森数是 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)