baseの違うbignumの比較

integer_dup.rb

def string_radix(s)
  if s.match?(/0x/i)
    [16, 2]
  elsif s.match?(/0o/i)
    [8, 2]
  elsif s.match?(/0b/i)
    [2, 2]
  elsif s.start_with?('0')
    [8, 0]
  else
    [10, 0]
  end
end

def string_mod(s, m)
  ans = 0
  radix, i = string_radix(s)
  while i < s.size
    ans = (ans * radix + s[i].to_i(radix)) % m
    i += 1
  end
  ans
end

def string_pow(s, a, m)
  ans = 1
  radix, offset = string_radix(s)
  i = s.size - 1
  while i >= offset
    ans = ans * a.pow(s[i].to_i(radix), m) % m
    a = a.pow(radix, m)
    i -= 1
  end
  ans
end

def string_rsa_hash(s)
  # secret_p, secret_q = 300000047, 500000003
  n = 150000024400000141 # secret_p * secret_q # TODO: use larger prime
  string_pow(s, 2, n)
end

def string_dups(strings)
  groups = [strings]
  n = 2
  dups = []
  until groups.empty?
    new_groups = []
    groups.each do |list|
      max_size = list.map(&:size).max
      if n > max_size * 3 # radixによって違う・10進数で2.3くらいだったから雑に3にした。要検証
        dups << list
      else
        list.group_by { string_mod(_1, n) }.each do |_, group|
          new_groups << group if group.size >= 2
        end
      end
    end
    groups = new_groups
    n += 1
  end
  dups
end
n=rand(10**100)
m=rand(10**100)
numbers = [n, m].flat_map do
  [_1.to_s, "0x#{_1.to_s(16)}", "0o#{_1.to_s(8)}", "0b#{_1.to_s(2)}", "0#{_1.to_s(8)}"]
end.shuffle
string_dups(numbers).map(&:size)

numbers.group_by { string_rsa_hash(_1) }.transform_values(&:size)

integer_equal.rb

primes = {}
(2..).each do |n|
  # 2つの数値a,bが(a-b)%mod1==0 && (a-b)%mod2==0の時 (a-b)はlcm(mod1,mod2)の倍数
  n.prime_division.each do |prime, exp|
    primes[prime] = [(primes[prime] || 0), exp].max
  end
  # (2..n)で割った余りが0になる時、(a-b)===(2..nの最小公倍数の定数倍) なので
  # (2..nの最小公倍数)以下のa,bに対して正しく比較できる
  # 素数定理を元に、ある桁数の数に対してどのnまで試せばいいか見積もれるはず
  digits = primes.sum{|prime, exp| exp * Math.log10(prime)}
  p [n / digits, digits.floor] # 実験的には桁数の2.3倍くらいっぽい
end