问题标签 [exponentiation]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
19 回答
242607 浏览

c - 实现基于整数的幂函数 pow(int, int) 的最有效方法

在 C 中将一个整数提高到另一个整数的幂的最有效方法是什么?

0 投票
10 回答
54464 浏览

c# - 你如何在 C# 中做 *integer* 幂运算?

Math.Pow().NET中的内置函数将double基数提高到double指数并返回double结果。

对整数做同样的事情的最好方法是什么?

补充:似乎可以将Math.Pow()结果转换为(int),但这总是会产生正确的数字并且没有舍入错误吗?

0 投票
4 回答
4071 浏览

math - 只需要前 k 位时的快速求幂?

这实际上是针对编程比赛的,但我已经非常努力地尝试了,甚至没有最微弱的线索如何做到这一点。

找到 n m的第一个和最后 k 个数字,其中 n 和 m 可以非常大 ~ 10^9。

对于最后 k 位,我实现了模幂运算。

对于第一个 k,我想使用二项式定理达到一定的幂,但这涉及到大量的阶乘计算,我不知道如何找到一个最佳点,在该点处 n^m 可以扩展为 (x+y)

那么有没有任何已知的方法可以在不执行整个计算的情况下找到前 k 位数字?

更新1 <= k <= 9 并且 k 将始终是 <= n m中的数字

0 投票
5 回答
10130 浏览

php - 在 PHP 中提升权力

好吧,我需要在 PHP 脚本中进行一些计算。我有一个表现错误的表达式。

输出 10

输出 0

输出 1

输出 1.000....

bcscale(100)用于 BCMath 计算。

Excel 和 Wolfram Mathematica 给出了 ~0,977237 的答案。

有什么建议么?

0 投票
2 回答
2331 浏览

math - SPARQL 中的幂(幂)和其他数学函数支持

我正在尝试编写一个 SPARQL 查询,我想在其中过滤某些东西的平方,但我根本无法弄清楚如何对一个数字(x 2)进行平方(当然,除非将它与自身相乘)。我猜想一个叫作有效的平方根函数math:sqrt(),但math:pow似乎不存在这样的东西。

如何在 SPARQL 中求平方,更重要的是,我在哪里可以了解它和其他数学函数(例如math:sqrtSPARQL)?

注意:这与我之前的问题有关:Reverse wikipedia geotagging lookup

0 投票
3 回答
32553 浏览

math - prolog中的幂函数

我的幂函数有什么问题?

0 投票
4 回答
7175 浏览

javascript - JavaScript 中最快的模幂运算

我的问题是(g^x) mod p在 JavaScript 中快速计算,^取幂mod是模运算。所有输入都是非负整数,x大约有 256 位,并且p是 2048 位的质数,g最多可以有 2048 位。

我发现的大多数可以在 JavaScript 中执行此操作的软件似乎都使用 JavaScript BigInt 库(http://www.leemon.com/crypto/BigInt.html)。在我的慢速浏览器(带有 SpiderMonkey 的 Firefox 3.0)上,用这个库进行一次这样大小的幂运算大约需要 9 秒。我正在寻找至少快 10 倍的解决方案。对于 2048 位数字来说,使用平方和乘法(通过平方求幂,http ://en.wikipedia.org/wiki/Exponentiation_by_squaring )的明显想法太慢了:它需要多达 4096 次乘法。

升级浏览器不是一种选择。使用另一种编程语言不是一种选择。将号码发送到 Web 服务不是一种选择。

是否有更快的替代方案实施?

更新:按照下面 outis 的回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf的建议,通过做一些额外的准备(即预先计算几百次幂) ,可以对 2048-位模幂运算最多仅使用 354 次模乘。(传统的平方和乘法方法要慢得多:它使用最多 4096 次模乘。)这样做在 Firefox 3.0 中将模幂运算速度提高了 6 倍,在 Google Chrome 中提高了 4 倍。我们没有得到 4096/354 的完全加速的原因是 BigInt 的模幂算法已经比平方和乘法更快,因为它使用了蒙哥马利归约 ( http://en.wikipedia.org/wiki/Montgomery_reduction ) .

更新:从 BigInt 的代码开始,似乎值得做两级手动优化(和内联)Karatsuba 乘法(http://en.wikipedia.org/wiki/Karatsuba_algorithm),然后才恢复到 base-32768 O( n^2) 在 BigInt 中实现的乘法。这将 2048 位整数的乘法速度提高了 2.25 倍。不幸的是,模运算并没有变得更快。

更新:使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和 Karatsuba 乘法和预计算幂(定义在http://www.ccrwest.org/gordon/ fast.pdf ),我可以在 Firefox 3.0 中将单次乘法所需的时间从 73 秒缩短到 12.3 秒。这似乎是我能做的最好的,但它仍然太慢。

更新:Flash Player 中的 ActionScript 2 (AS2) 解释器不值得使用,因为它似乎比 Firefox 3.0 中的 JavaScript 解释器慢:对于 Flash Player 9,它似乎慢 4.2 倍,对于 Flash Player 10,它似乎慢了 2.35 倍。有人知道 ActionScript2 和 ActionScript3 (AS3) 在数字处理方面的速度差异吗?

更新:Flash Player 9 中的 ActionScript 3 (AS3) 解释器不值得使用,因为它的速度与 JavaScript int Firefox 3.0 几乎相同。

更新:如果使用 Flash Player 10 中的 ActionScript 3 (AS3) 解释器int代替Number,并且Vector.<int>使用代替Array. 2048 位大整数乘法至少要快 2.41 倍。因此,可能值得在 AS3 中进行模幂运算,如果可用,在 Flash Player 10 中执行它。请注意,这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。有关各种编程语言和 JavaScript 实现的速度比较,请参阅http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 。

更新:有一个非常快速的 Java 解决方案,如果安装了 Java 插件,可以从浏览器的 JavaScript 调用。以下解决方案比使用 BigInt 的纯 JavaScript 实现快约 310 倍。

任何人都可以将此代码翻译成 Silverlight (C#) 吗?

0 投票
2 回答
1441 浏览

c++ - 快速求幂:real^real (C++ MinGW, Code::Blocks)

我正在编写一个应用程序,在某个块中,我需要将实数取幂大约 3*500*500 次。当我使用 exp(y*log(x)) 算法时,程序明显滞后。如果我使用基于处理数据类型的另一种算法,它会明显更快,但该算法不是很精确,尽管为模拟提供了不错的结果,而且它在速度方面仍然不是完美的。

有没有比 exp(y*log(x)) 更快的实际幂的精确求幂算法?

先感谢您。

0 投票
3 回答
1973 浏览

haskell - 在 Haskell 中使用带有列表列表的地图时出现问题

我正在使用 Haskell 解决 euler 项目中的问题 99,我必须从基本指数对列表中找到最大结果。

我想出了这个:

数字的形式为:

为什么这不起作用?我需要更改数字的格式吗?这里有没有我没有想到的简单优化,比如更有效的求幂方法?

0 投票
2 回答
1385 浏览

prolog - 序言统一决议

为什么会这样:

这会产生堆栈溢出异常吗?