an implementation of adeles

alg.rb

def not_implemented
  puts "#{inspect} : #{self.class}"
  raise NotImplementedError
end

$radix ||= 10    # 2 <= $radix <= 36
$adic  ||= 10**4 # 2 <= $adic
$delim ||= ','   # or '|', etc.
$type  ||= :arch # or :adic
$prec  ||= 4     # default precision
$term_order ||= :gr # or :lex

class Class
  def get *args, &block
    (new *args, &block).identity
  end
end

module Algebraic
  include Comparable

  @@pool = {}
  def identity
    @@pool[self] ||= self
  end
  def get *args
    self.class.get *args
  end

  def eql? a
    self.class.eql? a.class
  end
  def hash
    case self
    when Fixnum, Symbol, NilClass
      super
    else
      not_implemented
    end
  end

  def finalize
    self
  end

  def coerce a
    _ = self
    case a
    when NilClass
      _ = a
    when Adele
      _ = Adele.get a.n, _ * a.s, a.s
    else
      not_implemented
    end
    [a, _]
  end
  def cast a
    a, = coerce a
    a
  end
  
  def <=> a
    case a
    when Algebraic
      a, _ = coerce a
      _.compare a
    else
      _, a = a.coerce self
      _ <=> a
    end
  end
  def compare a
    not_implemented
  end

  def zero; 0; end
  def zero?; eql? zero; end
  def +@
    self
  end
  def + a
    case a
    when Algebraic
      a, _ = coerce a
      (_.add a).finalize # when respond_to? :add
    else
      _, a = a.coerce _
      _ + a
    end
  end
  def add a
    not_implemented
  end
  def -@
    not_implemented
  end
  def - a
    self + -a
  end
  def reside
    return if unit?
    Adele.get self, zero, unity
  end
  def % a
    self + a.reside
  end

  def unity; 1; end
  def unity?; eql? unity; end
  def * a
    case a
    when Algebraic
      a, _ = coerce a
      (_.mul a).finalize # when respond_to? :mul
    else
      _, a = a.coerce _
      _ * a
    end
  end
  def mul a
    not_implemented
  end
  def inverse
    return if zero?
    Adele.get zero, unity, self
  end
  def / a
    self * a.inverse
  end
  def ** a
    case a
    when Integer
      return inverse ** -a if a < 0
      _, r = self, unity
      until a.zero?
        r *= _ if (a&1).unity?
        _ *= _
        a >>= 1
      end
      r
    else # when respond_to? :log
      (log * a).exp
    end
  end
  
  def divmod a
    not_implemented
  end
  def div a; q, r = divmod a; q; end
  def mod a; q, r = divmod a; r; end
  def gcd a
    _ = self
    until a.zero?
      _, a = a, (_.mod a)
    end
    _
  end
  def lcm a
    (self * a).div gcd a
  end
  def inv a
    _, x, z = self, unity, zero
    until a.zero?
      q, r = _.divmod a
      _, a, x, z = a, r, z, x - q * z
    end
    x
  end
  def euclid a
    _, x, y, z, w = self, unity, zero, zero, unity
    until a.zero?
      q, r = _.divmod a
      _, a, x, y, z, w = a, r, z, w, x - q * z, y - q * w
    end
    [_, x, y]
  end
  def ub a = zero
    return [unit, body] if a.zero?
    u, b = self, unity
    while true
      _ = u.gcd a
      break if _.unity?
      u = u.div _
      b = b.mul _
    end
    [u, b]
  end

  def sgn; not_implemented; end
  def unit; not_implemented; end
  def abs
    return zero if zero?
    mul sgn.inverse
  end
  def body
    mul unit.inverse
  end
  def puni
    return unity if zero?
    unit.mul sgn.inverse
  end

  def sgn?;  eql? sgn;  end
  def abs?;  eql? abs;  end
  def unit?; eql? unit; end
  def body?; eql? body; end
  def puni?; eql? puni; end

  def nonzero?
    zero? ? nil : self
  end
end

class Numeric
  include Algebraic

  remove_method :eql?
  remove_method :<=>
  remove_method :zero?
  remove_method :+@
  remove_method :-@
  remove_method :divmod
  remove_method :div
  remove_method :modulo
  remove_method :quo
  remove_method :remainder
  remove_method :fdiv
  remove_method :floor
  remove_method :truncate
  remove_method :ceil
  remove_method :round
  remove_method :abs
  remove_method :nonzero?
  remove_method :integer?
  remove_method :step
  remove_method :to_int
  
  def coerce a
    _ = self
    case a
    when Numeric
      _, a = a.coerce _
    when Symbol, Term
      a = Poly.get a => 1
      _ = Poly.get 1 => _
    when Poly
      _ = Poly.get 1 => _
    else
      return super
    end
    [a, _]
  end
end

class Integer
  include Enumerable
  
  def eql? a
    super and
    (compare a).zero?
  end
  
  def coerce a
    _ = self
    case a
    when _.class
      [a, _]
    else
      super
    end
  end
  
  def inverse
    return self if eql? 1 or eql? -1
    super
  end
  def sgn
    compare 0
  end
  def abs
    mul sgn
  end
  def unit
    zero? ? unity : sgn
  end
  alias body abs

  def divmod a
    a.zero? ? [0, self] : (_divmod a)
  end

  def each
    (- self).times {|i| yield self + i } if self < 0
    times {|i| yield i }
  end
end
class Fixnum
  alias compare <=>
  alias add     +
  alias mul     *
  alias _divmod divmod
  alias _to_s   to_s
  
  remove_method :<=>
  remove_method :==
  remove_method :>=
  remove_method :<
  remove_method :<=
  remove_method :>

  remove_method :+
  remove_method :-
  remove_method :%

  remove_method :*
  remove_method :/

  remove_method :divmod
  remove_method :div
  remove_method :to_s
end
class Bignum
  alias compare <=>
  alias add     +
  alias mul     *
  alias _divmod divmod
  alias _to_s   to_s

  remove_method :<=>
  remove_method :==

  remove_method :+
  remove_method :-
  remove_method :%
  
  remove_method :*
  remove_method :/
  
  remove_method :divmod
  remove_method :div
  remove_method :to_s
end

class Charp < Numeric
  def initialize arg
    _ = arg.size - 1
    _ -= 1 while arg[_].zero? and ! _.zero?
    @arg = arg[0.._]
  end
  attr_reader :arg

  def eql? a
    super and
    arg.eql? a.arg
  end
  def hash
    arg.hash
  end

  def compare a
    arg <=> a.arg
  end

  def coerce a
    _ = self
    case a
    when _.class
      unless ec.eq? a.ec
        __ = (ec.cast a.ec).zero
        _ = get   arg.map {|c| c + __ }
        a = get a.arg.map {|c| c + __ }
      end
    when Integer
      a = a.to_a ec.ord
      a = get a.map {|c| c % ec.ord }
    else
      return super
    end
    [a, _]
  end

  def zero
    get [ec.zero]
  end
  def add a
    return a if zero?
    return self if a.zero?
    return a.add self if a.size > size
    get a.size.map {|i|
      arg[i] + a.arg[i]
    } + arg[a.size..-1]
  end
  def -@
    get arg.map {|_| -_ }
  end

  def unity
    get [ec.unity]
  end
  def mul a
    return zero if zero? or a.zero?
    _ = Array.new deg + a.size, ec.zero
    size.each {|i|
      a.size.each {|j|
        _[i + j] += arg[i].mul a.arg[j]
      }
    }
    get _
  end

  def divmod a
    q, r = zero, self
    unless a.zero?
      until r.size < a.size or r.zero?
        _ = lc / a.lc * adic**(r.size - a.size)
        q += _
        r -= a * _
      end
    end
    [q, r]
  end

  def sgn
    get [lc]
  end
  def unit
    zero? ? unity : sgn
  end
  alias puni unity

  def size
    arg.size
  end
  def deg
    size - 1
  end
  def lc
    arg[deg]
  end
  def ec
    arg[0]
  end
  def adic
    get [ec.zero, ec.unity]
  end
end

# self == n \ r / s
#      == r % n / s
#      == r / s % n
class Adele
  include Algebraic
  
  def initialize n, r, s
    n = n.body
    u, s = s.ub n
    r = (r.mul u.inv n).mod n.mul s
    @n, @r, @s = n, r, s
  end
  attr_reader :n, :r, :s
  def _r
    return r if n.zero?
    r < n/2 ? r : r - n
  end
  
  def eql? a
    super and
    [n, r, s].eql? [a.n, a.r, a.s]
  end
  def hash
    [n, r, s].hash
  end
  
  def finalize
    return if n.unity? or s.zero?
    _ = r.gcd s
    _r = r.div _
    _s = s.div _
    return _r if n.zero? and _s.unity?
    get n, _r, _s
  end
  
  def coerce a
    _ = self
    case a
    when _.class
      _n = n.gcd a.n
      _u, _s =   s.ub _n
      au, as = a.s.ub _n
      s_ = _s.lcm as
      _r = (  r.mul _u.inv _n).mul s_.div _s
      ar = (a.r.mul au.inv _n).mul s_.div as
      _ = get _n, _r, s_
      a = get _n, ar, s_
    when Numeric
      a = get n, (a.mul s), s
    else
      return super
    end
    [a, _]
  end
  
  def compare a
    _r.compare a._r
  end

  def zero
    get n, r.zero, s
  end
  def add a
    get n, r + a.r, s
  end
  def -@
    get n, -r, s
  end
  def reside
    return if unit?
    u, _n = r.ub n
    get _n, _n.zero, _n.unity
  end

  def unity
    get n, s, s
  end
  def mul a
    get n, (r.mul a.r), (s.mul a.s)
  end
  def inverse
    return if zero?
    u, _s = r.ub n
    _r = s.mul u.inv n
    get n, _r, _s
  end

  def divmod a
    not_implemented
  end

  def sgn
    return self if zero?
    unit
  end
  def unit
    _r, b = r.ub n
    get n, _r, s
  end
  def abs
    return zero if zero?
    body
  end
  def body
    u, _r = r.ub n
    get n, _r, s
  end
  def puni
    unity
  end
end

# self == adic**ord * arg
#      == adic**nil * arg.unity
class Adic < Numeric
  def initialize ord, arg
    @ord, @arg = ord, arg
  end
  attr_reader :ord, :arg

  def eq? a
    arg.eq? a.arg
  end
  def eql? a
    super and
    arg.eql? a.arg and ord.eql? a.ord
  end
  def hash
    ord.hash ^ arg.hash
  end

  def compare a
    [a.ord, arg] <=> [ord, a.arg]
  end

  def coerce a
    _ = self
    case a
    when _.class
      unless eq? a
        aarg, _arg = arg.coerce a.arg
        _ = get   ord, _arg unless _arg.eq?  arg
        a = get a.ord, aarg unless _arg.eq? aarg
      end
    when Integer
      aord, aarg = a.orduni adic
      aarg = arg.cast aarg
      a = get aord, aarg
    when Adele
      ar = cast a._r
      as = cast a.s
      a = ar / as
    when Real
      a, _ = coerce a.to_rat
    when Arch
      not_implemented
    else
      return super
    end
    [a, _]
  end

  def zero
    get nil, arg.unity
  end
  def add a
    return a if zero?
    return self if a.zero?
    return a.add self unless ord > a.ord
    _ord, _arg = (arg + a.arg * adic**(ord - a.ord)).orduni adic
    get ord + _ord, _arg
  end
  def -@
    get ord, -arg
  end

  def unity
    get ord.zero, arg.unity
  end
  def mul a
    return zero if zero? or a.zero?
    get ord + a.ord, arg * a.arg
  end
  def inverse
    return if zero?
    get -ord, arg.inverse
  end

  def frob
    self ** adic
  end
  def sgn
    return self if zero?
    _ = unit 
    a = _.frob 
    _, a = a, a.frob until _.eql? a
    _
  end
  def abs;  mul sgn.inverse; end
  def unit; get ord.zero, arg; end
  def body; get ord, arg.unit; end
  def puni; unit.mul sgn.inverse; end
end

# self == arg / 2**ord
class Real < Numeric
  def initialize ord, arg
    @ord, @arg = ord, arg
  end
  attr_reader :ord, :arg

  def eq? a
    ord.eql? a.ord
  end
  def eql? a
    super and
    eq? a and arg.eql? a.arg
  end
  def hash
    ord.hash ^ arg.hash
  end

  def compare a
    arg.compare a.arg
  end

  def coerce a
    _ = self
    case a
    when _.class
      case ord.compare a.ord
      when  1
        _ = get a.ord, arg >> ord - a.ord
      when -1
        a = get ord, a.arg >> a.ord - ord
      end
    when Integer
      a = get ord, a << ord
    when Adele
      a = get ord, ((a._r << ord).div a.s)
    when Adic
      a, _ = coerce a.to_rat
    else
      return super
    end
    [a, _]
  end

  def zero
    get ord, 0
  end
  def add a
    get ord, arg + a.arg
  end
  def -@
    get ord, -arg
  end

  def unity
    get ord, 1 << ord
  end
  def mul a
    get ord, arg * a.arg >> ord
  end
  def inverse
    return if zero?
    get ord, ((1 << ord * 2).div arg)
  end

  def sgn; get ord, arg.sgn << ord; end
  def abs; get ord, arg.abs; end
  def unit; not_implemented; end
  def body; not_implemented; end
  def puni; not_implemented; end

  def log
    return if zero?
    _ = self
    return (- _).log if _ < zero
    if _ > 2 or _ < unity
      e = 0
      e, _ = e + 1, _ / 2 while _ > 2
      e, _ = e - 1, _ * 2 while _ < 1
      _.log + e * 2.log
    else
      _ = x = unity - inverse
      t = unity
      i, r = unity, zero
      until t.zero?
        r += t
        i += unity
        _ *= x
        t = _ / i
      end
      r
    end
  end
  def exp
    t = self
    i, r = unity, unity
    until t.zero?
      r += t
      i += unity
      t *= self / i
    end
    r
  end

  def half
    get ord, arg >> 1
  end
end

# self == e^{ord + 2\pi i arg}
#      == e^{nil + 2\pi i zero}
class Arch < Numeric
  def initialize ord, arg
    @ord, @arg = ord, arg
  end
  attr_reader :ord, :arg

  def eq? a
    arg.eq? a.arg
  end
  def eql? a
    super and ord.eql? a.ord and arg.eql? a.arg
  end
  def hash
    ord.hash ^ arg.hash
  end

  def compare a
    return 0 if zero? and a.zero?
    return _arg.unit <=> 0 if a.zero?
    return 0 <=> a._arg.unit if zero?
    [_arg, ord] <=> [a._arg, a.ord]
  end

  def coerce a
    _ = self
    case a
    when _.class
      case arg.ord <=> a.arg.ord
      when  1
        _ord = a.arg.cast ord
        _arg = a.arg.cast arg
        _ = get _ord, _arg
      when -1
        _ord = arg.cast a.ord
        _arg = arg.cast a.arg
        a = get _ord, _arg
      end
    when Integer
      a =
      case a <=> 0
      when  0
        zero
      when  1
        get (arg.cast a).log, arg.zero
      when -1
        get (arg.cast a).log, arg.unity.half
      end
    when Adele
      a = (cast a._r) / (cast a.s)
    when Adic
      a = cast a.to_rat
    else
      return super
    end
    [a, _]
  end

  def zero
    get nil, arg.zero
  end
  def add a
    return a if zero?
    return self if a.zero?
    return zero if eql? -a
    mul (self/a).succ
  end
  def -@
    get ord, arg + 1/2
  end

  def unity
    get ord.zero, arg.zero
  end
  def mul a
    return zero if zero? or a.zero?
    get ord + a.ord, arg + a.arg
  end
  def inverse
    return if zero?
    get -ord, -arg
  end

  def sgn; zero? ? zero : unit; end
  def abs; zero? ? zero : body; end
  def unit; zero? ? unity : (get arg.zero, arg); end
  def body; zero? ? zero  : (get ord, arg.zero); end
  def puni; not_implemented; end
end

class NilClass
  include Algebraic
  
  def coerce a; [self, self]; end
  def compare a; 0; end
  def zero; self; end
  def add a; self; end
  def -@; self; end
  def reside; self; end
  def unity; self; end
  def mul a; self; end
  def inverse; self; end
  def ** a; self; end
  def divmod a; [self, self]; end
  def sgn; self; end
  def unit; self; end
  def abs; self; end
  def body; self; end
  def puni; self; end
end

class Symbol
  include Algebraic

  def coerce a
    _ = self
    case _
    when Integer
      _ = Poly.get _ => 1
      a = Poly.get 1 => a
    end
    [a, _]
  end
      
  def compare a
    to_s <=> a.to_s
  end
  def add a
    _ = Poly.get self => 1
    a = Poly.get a => 1
    _.add a
  end
  def -@
    Poly.get self => -1
  end
  def mul a
    _ = Term.get self => 1
    a = Term.get a => 1
    _.mul a
  end
  def ** a
    Term.get self => a
  end
  def divmod a
    if eql? a
      [1, 0]
    else
      [0, self]
    end
  end
  def sgn;  1;    end
  def unit; 1;    end
  def abs;  self; end
  def body; self; end
  def puni; self; end
end

class Term
  include Algebraic
end

class Poly
  include Algebraic
end

class Array
  def sum;     reduce 0, :+; end
  def xor;     reduce 0, :^; end
  def product; reduce 1, :*; end

  def to_num prec = 0, a = $adic
    (reverse.inject {|s, i| s * a + i } || 0) / a ** prec
  end
  def pair_to_s adic = $adic, radix = $radix, delim = $delim
    delim = adic > radix ? delim : ''
    map {|a|
      a.map {|i|
        i._to_s radix
      }.join delim
    }.join '.'
  end
  
  def to_rat
    reverse.inject {|_, a| 1 / _ + a } || 0
  end
end

class X
  include Algebraic
  
  def initialize
  end
  attr_reader :ord, :arg
  
  def eql? a
    not_implemented
  end
  def hash
    not_implemented
  end
  
  def finalize
    super
  end
  
  def coerce a
    _ = self
    case a
    when _.class
    when Integer
      not_implemented
    when Adele
      not_implemented
    else
      return super
    end
    [a, _]
  end
  
  def compare a
    not_implemented
  end

  def zero
    not_implemented
  end
  def add a
    not_implemented
  end
  def -@
    not_implemented
  end
  def reside
    return if unit?
    Adele.get self, zero, unity
  end

  def unity
    not_implemented
  end
  def mul a
    not_implemented
  end
  def inverse
    return if zero?
    Adele.get zero, unity, self
  end
  def ** a
    super
  end

  def divmod a
    not_implemented
  end

  def sgn
    not_implemented
  end
  def unit
    not_implemented
  end
  def abs
    return zero if zero?
    mul sgn.inverse
  end
  def body
    mul unit.inverse
  end
  def puni
    return unity if zero?
    unit.mul sgn.inverse
  end
end

module Algebraic; def inspect; to_s; end; end

class Integer
  def to_a a
    _, arr = abs, []
    until _.zero?
      _, i = _.divmod a
      arr << i
    end
    arr
  end
  def size a
    (to_a a).size
  end

  def to_s adic = $adic, type = $type, radix = $radix, delim = $delim
    return '-' + ((- self).to_s adic, type, radix, delim) if self < 0
    s = (to_a adic).map {|i| i._to_s radix }
    s << '0' if zero?
    delim = adic > radix ? delim : ''
    case type
    when :arch
      s.reverse * delim
    when :adic
      s[0] + '.' + s[1..-1] * delim
    end
  end
end

class Adele
  def inspect
#    "#{n}\\#{r}/#{s}"
    ((n.zero? or $hide_mod) ? '' : "#{n}\\") + "#{r}" + (s.unity? ? '' : "/#{s}")
  end
end