使用模块化幂运算，此脚本能否具有更好的性能? [英] Can this script have better performance using modular exponentiation?

问题描述

def f(a, b, c):
    return ((a ** b)-1) // c % b

此脚本可以某种方式更快吗? (我一直在寻找具有模幂的东西):

pow(a, b, c) == a ** b % c

，但是上面的脚本似乎不是那样完善的.有谁知道一种加快上述脚本速度的方法?预先感谢.

第二个脚本与第一个脚本完全不同，它只是用来说明我所考虑的优化类型.

我没有输入确切的方程式，因为我想要一个通用的案例解决方案， 是当a = 4且c = 3时发生的.这是否使它更容易?

我收到要求明确表示要先减去还是要先求幂的要求，我想先做我通过加方括号明确表示的求幂.

解决方案

请注意，a**b//c%d == a**b%(c*d)//c%d适用于任何正整数.这是正确的，因为存在一个正整数k，使得a**b == k*c*d + a**b%(c*d)成立，并且右侧的操作//c%d的结果不受任何k的影响. 根据这一事实，可以使用命令计算a**b//c%d

pow(a,b,c*d)//c%d

def f(a, b, c):
    return ((a ** b)-1) // c % b

Can this script be faster in some way? (I have been looking for something with modular exponentiation):

pow(a, b, c) == a ** b % c

but this above script doesn't seem to be improvable like that. Does anyone know a way to speedup the above script? Thanks in advance.

Edit:

The second script is not at all the same as the first one, it is just meant to show what kind of optimization I had in mind.

Edit:

I didn't put the exact equation in becouse I wanted a general case solution, the specfics are when a = 4 and c = 3. Does that make it easier?

Edit:

I got the request to make it clear if I want to subtract first or if I want to exponentiate first, I want to first do the exponentiation which I made clear by adding brackets.

解决方案

Note that a**b//c%d == a**b%(c*d)//c%d holds for any positive integers. This is true because there exists a positive integer k such that a**b == k*c*d + a**b%(c*d) holds and result of operation //c%d over right side is not affected by any k. According to this fact, a**b//c%d can be calculated using a command

pow(a,b,c*d)//c%d

这篇关于使用模块化幂运算，此脚本能否具有更好的性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！