Integer # pow is recommended for iterative squares solving in Ruby

Introduction

The beginning of things

In Ruby, there is a dedicated method Integer # pow.

I tried it immediately. AtCoder Typical Contest 002 B - n^p mod m

pow.rb


n, m, p = gets.split.map(&:to_i)
puts n.pow(p, m)

zisaku.rb


n, m, p = gets.split.map(&:to_i)
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p % 2 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts mpow(n, p, m)
Integer#pow Self-made mpow
Code length(Byte) 50 183
Execution time(ms) 68 62
memory(KB) 14356 14356

AtCoder Regular Contest 066 C - Lining Up

pow.rb


n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
f = true
h.each do |k, v|
  if n.odd? && k == 0
    if v != 1
      f = false
      break
    end
  elsif v != 2
    f = false
    break
  end
end
MOD = 1_000_000_007
puts (f ? 2.pow(n / 2, MOD) : 0)
Integer#pow Self-made mpow
Code length(Byte) 305 438
Execution time(ms) 101 100
memory(KB) 22676 22488

Acing Programming Contest 2020

pow.rb


n = gets.to_i
x = gets.chomp
xs = x.to_i(2)
xc = x.count('1')
def mpow(n, p, mod)
  return 0 if mod.zero?
  n.pow(p, mod)
end
def popcount(u)
  return 0 if u.zero?
  a = u % u.to_s(2).count('1')
  1 + popcount(a)
end
xsp = mpow(xs, 1, xc + 1)
xsm = mpow(xs, 1, xc - 1)
n.times do |i|
  if x[i] == '0'
    y = xsp + mpow(2, n - i - 1, xc + 1)
    y = mpow(y, 1, xc + 1)
  elsif xc == 1
    puts '0'
    next
  else
    y = xsm - mpow(2, n - i - 1, xc - 1)
    y = mpow(y, 1, xc - 1)
  end
  puts popcount(y) + 1
end
Integer#pow Self-made mpow
Code length(Byte) 541 629
Execution time(ms) 421 625
memory(KB) 14704 15392

All of them were equal or better. The era of ruby has arrived.

Summary

Referenced site instance method Integer#**

Recommended Posts

Integer # pow is recommended for iterative squares solving in Ruby
ABC177 --solving E in Ruby
Integer unified into Integer in Ruby 2.4
[Ruby] What is `!!` used for?
Microbenchmark for integer power of floating point numbers in Ruby
Is there no type in Ruby?
[Technical memo] What is "include" in Ruby?
[Beginner] Various iterative processing for Ruby arrays
Tips for gRPC error handling in Ruby