Skip to content

Instantly share code, notes, and snippets.

@etale
Last active September 27, 2015 17:47
Show Gist options
  • Save etale/1308075 to your computer and use it in GitHub Desktop.
Save etale/1308075 to your computer and use it in GitHub Desktop.
an implementation of adeles
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment