f# Power接受两个参数为大整型的问题

我目前正在尝试使用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#知识是阻碍我一点。是否有可能创建一个接受两个参数都为大整型的幂函数?

我现在有这个:

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

但是会抛出一个错误:零没有定义。所以我也做错了什么。不接受i作为替代品，因为它会给出以下错误:

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'语句。有别的解决办法吗?

提前感谢，请原谅我的长帖子。我只是尽可能清楚地表达我的"挑战"。

我不明白为什么你需要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)

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

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

问题是bigint.Zero是一个返回值的静态属性，但是模式只能包含(常量)字面值或f#活动模式。它们不能直接包含属性(或其他)调用。但是，如果您仍然喜欢match，则可以在where子句中编写额外的约束:

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时有效。

您不需要创建Pow函数。(**)操作符对bigint -> int -> bigint有重载。只有第二个参数应该是整数，但我不认为这对你的情况是一个问题。试试

bigint 10 ** 32;;

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

另一个选择是内联你的函数，这样它就可以与所有的数字类型(支持所需的运算符:(*), (-), get_One和get_Zero)一起工作。

let rec inline PowBigInt (x:^a) (y:^a) : ^a =  
  let zero = LanguagePrimitives.GenericZero 
  let one = LanguagePrimitives.GenericOne
  if y = zero then one
  else x * PowBigInt x (y - one) 
let x = PowBigInt 10 32     //int
let y = PowBigInt 10I 32I   //bigint
let z = PowBigInt 10.0 32.0 //float

我可能会推荐使用尾部递归，就像Tomas建议的那样。

相关内容

最新更新

热门标签：