如何使用 (**) 运算符而不是 pow 实现相同的功能

Question

我正在尝试参与编码 challenge where for the large numbers I need to take a modulo with (10 ^ 9 + 7). Since the website support only ruby 2.3.1 version so I can't make use of pow() function。当我试图用 (**) 运算符解决同样的问题时。它给了我无限。所以，我的问题是

1) (**) 和 pow 运算符到底有什么区别

2) 我需要一种方法来实现 pow 运算符提供的相同功能

下面是程序

mod = ((10 ** 9) + 7)
q = gets.to_i
while q != 0 do
  n = gets.to_i
  if (n % 2 == 0 || n == 1)
    puts 0
  else
    val = (n - 3)/2
    puts 2.pow(val, mod)
    ### now If I do puts (2 ** ( val % mod)) it will give me infinite
  end
  q -= 1
end

输入 q = 3

n - 将是一个非常大的数字，例如 899187440761857221 或 889644209960741769

如果我运行在我的本地机器上安装程序，我可以运行因为我使用的是 ruby 最新版本，而在网站上他们支持 2.3.1版本

如有任何帮助，我们将不胜感激

Answer 1

不同之处正是您链接的文档所说的，没有模参数，结果与调用 base**exponent 相同，但是使用模参数，它将计算结果而不会溢出类型，这可以在使用 base 和 exponent 的大值进行直接模幂 (base ** exponent) % modulo 时会发生这种情况。

下面是基于https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method

的模幂运算的ruby实现

  def pow_with_modulus(base, exponent, modulus)
    return 0 if modulus == 1

    res = 1
    exponent.times do
      res = (res * base) % modulus
    end

    res
  end

从实现中可以看出，中间值永远不能大于 modulus * base，这使其低于溢出。 base * modulus溢出当然会溢出。

编辑：性能更高的版本，改编自 https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

  def pow_with_modulus(base, exponent, modulus)
    return 0 if modulus == 1

    res = 1
    base = base % modulus

    while exponent > 0
      res = (res * base) % modulus if exponent.odd?
      exponent = exponent >> 1
      base = (base * base) % modulus
    end

    res
  end

如何使用 (**) 运算符而不是 pow 实现相同的功能

How to achieve the same functionality with (**) operator instead of pow

ruby

modulo