11

我目前正在尝试使用 F#。在 Internet 上找到的文章很有帮助，但作为 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# 的了解有点阻碍我。是否可以创建一个接受两个参数都是 bigints 的 powerfunction？

我目前有这个：

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'语句。有另一种解决方案吗？

在此先感谢，请原谅我的长帖子。我只是想尽可能清楚地表达我的“挑战”。

4

4 回答 4

8

我不明白为什么你需要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)
于 2011-12-02T13:21:02.587 回答
5

我认为最简单的定义方法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 时，才使用位移位来实现功率。

于 2011-12-02T13:03:30.020 回答
5

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

大整数 10 ** 32 ;;

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}
于 2011-12-02T14:04:10.163 回答
3

另一种选择是内联您的函数，使其适用于所有数字类型（支持所需的运算符：、、、(*)和）。(-)get_Oneget_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 建议的那样，我可能会建议将其设为尾递归。

于 2011-12-02T15:24:32.990 回答