- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
我的问题是在 JavaScript 中快速计算 (g^x) mod p
,其中 ^
是求幂,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 ),然后才恢复到在 BigInt 中实现的 base-32768 O(n^2) 乘法。这将 2048 位整数的乘法速度提高了 2.25 倍。不幸的是,模运算并没有变得更快。
更新:使用 http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf 和 Karatsuba 乘法和预计算幂(定义在 http://www.ccrwest.org/gordon/fast.pdf 中)中定义的修改后的 Barrett 缩减,我可以在 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 差不多。
更新:如果使用 int
代替 Number
并且使用 Vector.<int>
代替 Array
,Flash Player 10 中的 ActionScript 3 (AS3) 解释器可以比 Firefox 3.0 中的 JavaScript 解释器快 6.5 倍。 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 倍。
<body>hi0
<script type="text/javascript">
document.body.innerHTML += '<br>hi1';
if ('object'==typeof java) {
var x = new java.math.BigInteger("123456789123456789", 10);
var p = new java.math.BigInteger("234567891234567891", 10);
var g = new java.math.BigInteger("3", 10);
var v = x.modPow(x, p);
document.body.innerHTML += '<br>' + v.toString();
document.body.innerHTML += '<br>' + v.toString(16);
} else {
document.body.innerHTML += '<br>java plugin not installed';
}
</script></body>
最佳答案
其他一些可从 JS 调用的客户端技术,例如 Java 小程序或 Flash 电影,是否可以接受? BigInt 的 approach已经相当快了。您可以调整 BigInt,或者您可以尝试 different algorithm ,但你可能不会得到一个数量级的改进。
关于javascript - JavaScript 中最快的模幂运算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1450608/
什么是更快的安卓? Color.rgb(184, 134, 011); 或 Color.parseColor("#234181"); 还是别的什么? 答案:最快的似乎是: int mycolor =
没错, 基本上我需要计算出从服务器到最终用户的最短路线。我有 2 台服务器 - 一台在英国,一台在美国。 我需要根据最终用户的位置确定从哪个服务器加载内容。 我最初想使用 fsock/curl/fgc
我正在阅读固定宽度整数类型 ( cpp reference) 并遇到int_fast8_t、int_fast16_t、int_fast32_t 和 int_least8_t 类型,int_least1
Closed. This question is opinion-based。它当前不接受答案。 想改善这个问题吗?更新问题,以便editing this post用事实和引用来回答。 6年前关闭。
我有大量目录,我想尽快读取所有文件。我的意思是,不是 DirectoryInfo.GetFiles 快,而是“get-clusters-from-disk-low-level”快。 当然,.NET 2
我尝试寻找最小的可被1到n整除的数字,现在我正在寻求有关进一步压缩/使我的解决方案更有效的方法的建议。如果也有O(1)解决方案,那将非常酷。 def get_smallest_number(n):
有很多不同的方法可以在驱动程序之间选择元素。我想知道哪一个最快且最适合 native 应用程序(iOS 和 Android)。 Appium Driver 类有: findElementByAcces
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,
让矩阵 A 说 A = magic(100);。我见过两种计算矩阵 A 的所有元素之和的方法。 sumOfA = sum(sum(A)); 或者 sumOfA = sum(A(:)); 其中一个比另一
我想为玩具车在没有障碍物的平面 (2d) 上规划一条路线。玩具车应该从点 (p1x,p1y) 移动到 (p2x,p2y)(又名狄利克雷边界条件)。此外,玩具车在起点的速度是(v1x,v1y),终点处要
假设有 n 个 3 维对象(多面体)。最快的方法是计算所有对象的交集O(n^2)? 现在,我正在使用一个基本上强制 T(n) 等于 n ^ 2 的库: for each object: // ther
关闭。这个问题需要 details or clarity 。它目前不接受答案。 想改进这个问题吗? 添加细节并通过 editing this post 澄清问题。 关闭 5 年前。 Improve
在 c: 上,我有数以万计的 *.foobar 文件。它们在各种各样的地方(即子目录)。这些文件的大小大约为 1 - 64 kb,并且是纯文本。 我有一个 class Foobar(string fi
我的基本问题是有多个线程做一些事情,其中一些需要比其他线程更多的时间(20 倍甚至更多),他们需要的时间只取决于起始值,但不能从起始值预测单独他们需要多少时间。为了减少更快线程的空闲时间,我想通过
好的,我有一个疑问: select distinct(a) from mytable where b in (0,3) 什么会更快,上面的还是 select distinct(a) from myta
问题简介: 我正在开发一个生态生理模型,我使用了一个名为 S 的引用类列表。存储模型需要输入/输出的每个对象(例如气象、生理参数等)。 此列表包含 5 个对象(请参见下面的示例): - 两个数据帧,S
我有一个正在工作的问题陈述,但我仍然想知道更高效、更快,更重要的是正确设计来处理下面提到的场景。 我有一个 POJO 类 class A { String s; Double d; } 我正在
关闭。这个问题需要更多focused .它目前不接受答案。 想改进这个问题吗? 更新问题,使其只关注一个问题 editing this post . 关闭 3 年前。 Improve this q
关于 LLVM 如何优化代码,关于 SO 以及整个网络都有一些非常好的描述。但这些都无法回答我的具体问题。 在 Xcode 中,项目和目标设置中有各种代码优化选项。我理解在开发过程中不需要优化,但为什
我正在用 C# 开发一个服务器项目,在收到 TCP 消息后,它会被解析并存储在一个精确大小的 byte[] 中。 (不是固定长度的缓冲区,而是存储所有数据的绝对长度的字节[]。) 现在为了阅读这个 b
我是一名优秀的程序员,十分优秀!