Как добиться такой же функциональности с оператором (**) вместо pow - PullRequest
Новая
       24

Как добиться такой же функциональности с оператором (**) вместо pow

0 голосов
/ 10 марта 2020

Я пытаюсь участвовать в кодировании вызов , где для больших чисел мне нужно взять по модулю (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

input q = 3

n - будет очень большое число, например 899187440761857221 или 889644209960741769

Если я запускаю Программа на моем локальном компьютере Я могу запустить ее, потому что я использую ruby последнюю версию, тогда как на сайте они поддерживают версию 2.3.1

Любая помощь будет оценена

1 Ответ

1 голос
/ 10 марта 2020

Различие в том, что именно то, что вы указали в документах, без параметра по модулю результат такой же, как при вызове base**exponent, но с параметром по модулю он вычислит результат без переполнения типа, что может произойти при выполнении прямого модульное возведение в степень (base ** exponent) % modulo с большими значениями для base и exponent.

Ниже приведена ruby реализация модульного возведения в степень на основе https://en.wikipedia.org/wiki/Modular_exponentiation#Memory -efficient_method 

  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
...