时间戳

首页 > 解决方案 > 如何使用 (**) 运算符而不是 pow 实现相同的功能

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

问题描述

我正在尝试参加编码挑战，对于大数字我需要取模（10 ^ 9 + 7）。由于网站只支持 ruby​​ 2.3.1 版本，所以我不能使用 pow()函数。当我试图用 (**) 运算符解决同样的问题时。它给了我无限。所以，我的问题是

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 版本

任何帮助，将不胜感激

标签： rubymodulo

解决方案

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

下面是基于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

推荐阅读