65.9K
CodeProject 正在变化。 阅读更多。
Home

F# 中的大整数平方根

rickoshay
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.23/5 (6投票s)

2011年10月10日

CPOL

5分钟阅读

viewsIcon

40969

downloadIcon

370

使用 F# 确定 BigInteger 的平方根

引言

我一直在 F# 中摸索 BigInteger 类型，并注意到 .NET 没有为该类型提供整数平方根函数。因此，我构建了一个平方根函数，它接受一个 BigInteger 并返回一个 BigInteger。用 F# 的说法，它是 BigInteger -> BigInteger。我在此代码中的目标之一是仅使用 BigInteger 类型。原因在于，如果您使用其他类型，例如 float，那么您将限制该函数适用的数字的大小。

我也关注了性能，因为 BigInteger 数学以速度慢而闻名。我使用牛顿-拉夫逊方法收敛到结果（这并不意外）。真正的性能提升在于我如何计算第一个猜测值来为牛顿-拉夫逊方法提供种子。

和你们许多人一样，我对 F# 也是新手；因此，任何关于改进代码或以更函数式的方式编写的建设性建议都欢迎。

SqrtMainWindow.PNG

背景

平方根函数在各种数学计算中都是一个常用的函数，从勾股定理中求斜边到在网格上求两点之间的距离。它有很多用途。它为什么会被遗漏在库之外，谁也猜不到。也许它最终会被添加到 .NET 库中。

整数平方根的定义是：给定一个正整数 S，返回一个正整数 R，R 是小于或等于 S 的平方根的最大整数。

这本质上说明，如果 S 不是完全平方数，则答案将被截断到最接近的整数。如果 S 是完全平方数，则您将获得精确答案。例如，25 的整数平方根是 5，26 的整数平方根也是 5。

Using the Code

我们将从在 F# 中构建牛顿-拉夫逊方法开始。这是被许多计算器广泛使用的标准函数。我不会解释求根的牛顿-拉夫逊方法；有很多其他网站对此有很好的解释。该方法的复杂度是 O(Log n) 级别，即以 10 为底的对数；而二分法求根的复杂度是以 2 为底的对数级别。这是代码的主要部分。

let bigintSqrt(bigNum : BigInteger) =
    let rec converge prevGuess =
        let nextGuess = (bigNum / prevGuess + prevGuess) >>> 1
        match BigInteger.Abs (prevGuess - nextGuess) with
        | x when x < 2I -> nextGuess
        | _ -> converge nextGuess
    if bigNum.Sign = -1 then
        failwith "Square root of a negative number is not defined."
    else
        let root = converge (sqrtRoughGuess bigNum)
        if root * root > bigNum then
            root - 1I
        else
            root

我使用右移运算符 (>>>) 而不是除以 2 来获得稍好的执行性能。我添加最后一个 if 语句（在最后四行中）的原因是它在执行整数平方根。所以答案必须小于或等于小数平方根。由于此循环将在误差为 1 的情况下收敛，因此我可能只需要将其更改 1。另请注意，名为 converge 的内部函数是尾递归的，因此堆栈溢出不是问题。（递归调用后不再发生其他处理。）

现在剩下的是创建用于为平方根函数播种的 sqrtRoughGuess 函数。由于我们正在处理 BigInteger 类型，输入数字可能有数百甚至数千位数字，或者更多。在这种情况下，以 1 作为第一个猜测值将是一个非常糟糕的猜测。或者，以我们原始数字 S 或 S/2 作为第一个猜测值会太高。虽然任何大于零的数字都可以，但第一个猜测值越接近最终答案，converge 内部函数执行的迭代次数就越少。

为了获得良好的第一个猜测值，我在以下公式中使用了简单的对数恒等式。

Sqrt(x) = b(1/2 * log(x)) ，其中 b 是该公式中对数的底。在这个公式中，我将使用 b = 10 作为底数，以简化计算。

以下是我为获得接近的第一个猜测值所做的尝试。

let sqrtRoughGuess (num : BigInteger) =
    let log10x = log10 (num + 1I)
    let halfLog = (log10x + 1I) >>> 1  
    (power10 halfLog)

我没有在这篇文章中展示 power10 函数的代码。但您可以从上面的链接下载代码进行检查。该函数接收 10，并将其提高到给定参数的幂。power10 函数也具有 BigInteger -> BigInteger 的签名。

现在，为了满足仅使用 BigInteger 类型的要求，我将创建一个以 10 为底的对数函数。这是因为 BigInteger 类型上的静态 Log10 方法返回一个 float，而我们的目标是仅使用 BigInteger 类型。

let ten = 10I  // 10^1 
let tenBillion = 10000000000I // 10^10
let googol = 100000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000I // 10^100
let googolToTenth = googol * googol * googol * googol * googol * 
googol * googol * googol * googol * googol // 10^10000

//*************************************************************************************
let private log10 theNumber =
    if theNumber <= 0I then
        failwith "Logarithm of a non-positive number is not defined."
    // this inner functions counts the number of times divisor will divide num
    let rec divisions count (num : BigInteger) divisor =
        match num with
        | x when x < divisor -> count, num
        | _ -> divisions (count + 1I) (num / divisor) divisor
    let thousandsCount, rem1 = divisions 0I theNumber googolToTenth
    let hundredsCount, rem2 = divisions 0I rem1 googol
    let tensCount, rem3 = divisions 0I rem2 tenBillion
    1000I * thousandsCount + 100I * hundredsCount + ten * tensCount + 
		fst(divisions 0I rem3 10I)

log10 函数，由于它是一个整数对数函数，它会回退到计算整数参数可被 10 整除的次数。有了这个函数，我们就有了平方根函数，它只使用接受 BigInteger 类型的函数。因此，输入整数大小的唯一限制就是您计算机的能力。

关注点

对于习惯于面向对象编程且不熟悉函数式风格的人来说，F# 是一种有趣的语言。递归是比 for / while 循环更受青睐的循环形式。并且为了防止堆栈溢出错误，尾递归是必需的。在这篇文章的递归函数中，我使用了参数列表中的累加器来避免递归调用后的其他处理。您也可以使用续延来确保尾递归，但我将留给读者自行研究。

我也喜欢我可以在一个解决方案中混合使用 .NET 语言。这个 WinForms 应用程序的 GUI 是用 C# 编写的。

历史

  • 2011 年 10 月 10 日 - 首次发布
  • 2011 年 10 月 19 日 - 包含可执行文件下载
© . All rights reserved.