当前位置: 首页 > 编程语言 > C#

计算BigInteger的平方根(System.Numerics.BigInteger)分享

时间:2023-04-10 23:54:25 C#

计算BigInteger的平方根(System.Numerics.BigInteger).NET4.0为任何大整数提供了System.Numerics.BigInteger类型。我需要计算一个BigInteger平方根(或一个合理的近似值——例如,一个整数平方根)。所以我不必重新实现轮子,有没有人有扩展它的好方法?CheckifBigIntegerisaperfectsquare有计算JavaBigInteger整数平方根的代码。这里翻译成C#,作为扩展方法。publicstaticBigIntegerSqrt(thisBigIntegern){如果(n==0)返回0;如果(n>0){intbitLength=Convert.ToInt32(Math.Ceiling(BigInteger.Log(n,2)));BigIntegerroot=BigInteger.One=lowerBound&&n非正式测试表明,对于小整数,这比Math.Sqrt慢大约75倍。VS分析器将isSqrt中的乘法指向热点。我不确定牛顿法是否是计算bignum平方根的最佳方法,因为它涉及除法,这对于bignum来说很慢。您可以使用仅使用加法和移位(此处显示为无符号整数)的CORDIC方法staticuintisqrt(uintx){intb=15;//这是我们接下来要尝试的一点uintr=0;//r将包含结果uintr2=0;//这里我们保持r平方while(b>=0){uintsr2=r2;uintsr=r;//compute(r+(1x){r=sr;r2=sr2;}b--;}returnr;}有一个类似的方法只使用加法和移位,称为“DijkstrasSquareRoot”,例如在这里解释:计算任意精度平方根的最简单方法是牛顿法。您可以将其转换为您选择的语言和变量类型。这是JavaScript中的截断平方根(对我来说是新鲜的),它使用1+3+5...+nthoddNumber=n^2所有变量都是整数,只是加减法vartruncSqrt=function(n){v??aroddNumber=1;varresult=0;while(n>=oddNumber){n-=oddNumber;oddNumber+=2;result++;}returnresult;}`简短回答:(但请注意,请参阅下面的详细信息)Math.Pow(Math.E,BigInteger.Log(pd)/2)其中pd表示平方根运算在BigInteger上执行。长答案和解释:理解这个问题的另一种方法是理解平方根和对数的工作原理。如果你有等式5^x=25,要求解x我们必须使用对数。在这个例子中,我将使用自然对数(其他基地的日志是可能的,但自然对数是简单的方法)。5^x=25重写,我们有:x(ln5)=ln25为了隔离x,我们有x=ln25/ln5我们在x=2处看到这个结果。但是因为我们已经知道x(x=2,在5^2中),让我们改变我们不知道的东西并写一个新的方程并求解新的未知数。令x为平方根运算的结果。这给了我们2=ln25/lnx重写以隔离x,我们有lnx=(ln25)/2来删除日志,我们现在使用自然日志的特殊id和特殊编号e。具体来说,e^lnx=x。重写等式现在得到e^lnx=e^((ln25)/2)简化左侧,我们有x=e^((ln25)/2)其中x将是25的平方根.你也可以将这个想法扩展到任何根或数,x的y次根的通式就变成了e^((lnx)/y)。现在将其专门应用于C#、BigIntegers和这个问题,我们只需实施该公式。警告:虽然数学是正确的,但也有一些限制。这种方法只会让你四处走动,有一个很大的未知数(取决于你正在操纵的数字的大小)。也许这就是微软没有实现这种方法的原因。//Asamplegeneratedpublickeymodulusvarpd=BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727");varsqrt=Math.Pow(Math.E,BigInteger.Log(pd)/2);控制台.WriteLine(sqrt);注意:BigInteger.Log()方法返回一个双精度数,因此有两个问题。1)数字不精确,2)Log()可以处理BigInteger输入的内容有一个上限。要检查上限,我们可以查看自然对数的标准形式lnx=y。换句话说,e^y=x。由于double是BigInteger.Log()的返回类型,最大的BigInteger可以提升为double.MaxValue。在我的电脑上,这将是e^1.79769313486232E+308。不精确是不合适的。有人想实施BigDecimal并更新BigInteger.Log()吗?消费者要小心,但它会让你进入邻居,并且对结果进行平方会产生一个类似于原始输入的数字,最多那么多位数,并且不如RedGreenCode的答案那么精确。快乐(方形)生根!;)以上就是C#学习教程分享的全部内容:计算BigInteger(System.Numerics.BigInteger)的平方根。收藏不代表立场,如涉及侵权,请点击右侧联系管理员删除。如需转载请注明出处: