2009-05-24

p-adic field in ruby

Teichmüller character(sgn)とexpとlogも．
x != 0 に対して，
x = p^ord(x) sgn(x) e^log(x)
となるようにlogを拡張してる．

class Adic < Numeric
  
  def initialize adic, precision, arg = 0, ord = 0
    @adic, @precision = adic, precision
    @modulus = adic ** precision
    @int, @ord = if arg.zero?
                   [0, :infty]
                 else
                   while arg % adic == 0
                     arg /= adic
                     ord += 1
                   end
                   [arg % modulus, ord]
                 end
  end

  attr_reader :adic, :precision, :modulus, :int, :ord

  def hash
    adic.hash ^ precision.hash ^ int.hash ^ ord.hash
  end

  def eql? b
    self.class.eql?(b.class) and
    adic.eql?(b.adic) and
    precision.eql?(b.precision) and
    int.eql?(b.int) and ord.eql?(b.ord)
  end

  def coerce b
    case b
    when self.class
      raise if adic != b.adic
      case
      when precision < b.precision
        [self.class.new(adic, precision, b.int, b.ord), self]
      when precision > b.precision
        [b, self.class.new(adic, b.precision, int, ord)]
      else
        [b, self]
      end
    when Integer
      [self.class.new(adic, precision, b), self]
    when Rational
      n, = coerce b.numerator
      d, = coerce b.denominator
      [n/d, self]
    else
      raise
    end
  end

  def == b
    case b
    when self.class, Rational, Integer
      b, a = coerce b
      a.eql? b
    else
      a, b = b.coerce self
      a == b
    end
  end

  def zero?
    int.zero? and ord == :infty
  end

  def zero
    self.class.new(adic, precision)
  end

  def unity
    self.class.new(adic, precision, 1)
  end

  def inspect
    x, s = int, []
    precision.times do
      x, a = x.divmod adic
      s << a
    end
    b, e = if ord.eql?(:infty)
             ['', 0]
           elsif ord >= 0
             ['0.1', ord]
           else
             ['10', -ord]
           end
    if adic <= 36 
      s[0].to_s(adic) + '.' + s[1..-1].map {|a| a.to_s(adic)}.join
    else
      s.inspect
    end +
    if e.zero?
      ''
    else
      ' * ' + b + if e == 1
                    ''
                  else
                    "^#{e}"
                  end
    end
  end

  alias to_s inspect

  def + b
    case b
    when self.class, Rational, Integer
      b, a = coerce b
      case
      when a.zero?
        b
      when b.zero?
        a
      when b == - a
        a.zero
      else
        a, b = b, a unless b.ord >= a.ord
        self.class.new(adic, a.precision, a.int + b.int * adic ** (b.ord - a.ord), a.ord)
      end
    else
      a, b = b.coerce(self)
      a + b
    end
  end

  def -@
    if zero?
      self
    else
      self.class.new(adic, precision, - int, ord)
    end
  end

  def - b
    self + (- b)
  end

  def * b
    case b
    when self.class, Integer, Rational
      b, a = coerce b
      if a.zero? or b.zero?
        a.zero
      else
        self.class.new(adic, a.precision, a.int * b.int, a.ord + b.ord)
      end
    else
      a, b = b.coerce(self)
      a * b
    end
  end

  def inverse
    raise ZeroDivisionError if zero?
    a, b, x, z = int, modulus, 1, 0
    until b.zero?
      q, r = a.divmod b
      a, b, x, z = b, r, z, x - q * z
    end
    self.class.new(adic, precision, x, - ord)
  end

  def / b
    case b
    when self.class, Rational, Integer
      b, a = coerce b
      a * b.inverse
    else
      a, b = b.coerce(self)
      a / b
    end
  end

  def ** b
    if b < 0
      b, s = -b, inverse
    else
      s = self
    end
    a = unity
    until b.zero?
      a *= s if b.odd?
      s *= s
      b >>= 1
    end
    a
  end

  def unit
    raise Errno::EDOM.new 'unit' if zero?
    self.class.new(adic, precision, int)
  end

  def sgn
    if zero?
      zero
    else
      r = unit
      (precision - 1).times {r **= adic}
      r
    end
  end

  def exp
    1 + exp0
  end

  def log
    r = unit / sgn
    - (1 - r).log0
  end

  def exp0
    raise Errno::EDOM.new 'exp' unless zero? or (adic - 1) * ord > 1
    r = self
    unless zero?
      n = 2
      t = r * r / n
      while t.ord < precision + ord
        r += t
        n += 1
        t *= self / n
      end
    end
    r
  end

  def log0
    raise Errno::EDOM.new 'log' unless zero? or ord > 0
    r = self
    unless zero?
      n = 2
      t = r * r / n
      while t.ord < precision + ord
        r += t
        t *= n
        n += 1
        t *= self / n
      end
    end
    r
  end

end

2009-04-29

Teichmüller representatives

2
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000

3
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.222222222222222222222222222222222222222222222222222222222222222

5
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.121342303220413240434041241411314142011332240424031240330300031
3.323102141224031204010403203033130302433112204020413204114144413
4.444444444444444444444444444444444444444444444444444444444444444

7
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.463026243445212146113502341343566222024066154123413403324445104
3.463026243445212146113502341343566222024066154123413403324445104
4.203640423221454520553164325323100444642600512543253263342221562
5.203640423221454520553164325323100444642600512543253263342221562
6.666666666666666666666666666666666666666666666666666666666666666

11
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.a49123978aa4665595763636a7759561973379552a008794726876536840707
3.01236a870639702081aa512817a3876314aa15825660a950506811802507240
4.795298078665557a535566629558391515066a6467117557494a7393760a29a
5.251785a3a801407560312956a5248a836938941917391397836091a97735196
6.8593250702a96a354a798154058620274172169193719713274a19013375914
7.315812a324455530575544481552719595a44046439935536160371734a0810
8.a9874023a4713a8a290059829307234796009528544a015a5a42992a85a386a
9.061987132006445515347474033515491377315580aa231638423457426a3a3
a.aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

13
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.62242587310ba70541161b132c38788264312c51bb513bc501b555513334a66
3.b69724488152a64aac93cb938a1c54374c63553b078a31191a29226cc29c101
4.b69724488152a64aac93cb938a1c54374c63553b078a31191a29226cc29c101
5.51055101886c63047450514b76a55596a625002b77075c3429672c7615053b0
6.19a35644136281c31766607b27bbcb739176a05076644292a28c48c48493c75
7.b3297688b96a4b09b5666c51a51101593b562c7c56688a3a2a4084084839057
8.7bc77bcb446069c8587c7b815627773626a7cca155c57098a365a056b7c791c
9.1635a8844b7a26822039013942b0789580697791c5429bb3b2a3aa600a30bcb
a.1635a8844b7a26822039013942b0789580697791c5429bb3b2a3aa600a30bcb
b.6aa8a7459bc125c78bb6b1b9a094544a689ba07b117b9107cb17777b9998266
c.ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

17
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.93c9e15a7a8a6g4gd6ab5925ea06d49047f9c5a92gb7d060d5e2bcff4396d84
3.d230b40a93g33bg5ab7e6c4db1de97d0d879de79f007cc815df6f584dfcafd8
4.2a5cgc8d3e0610f18e57ge15d965cgf9gecg1364af5gc21540f2be951bgf756
5.905g9151geg6cc67dbe8d8433dae6c3227e87f691d84ccged306f95b5c304e7
6.2e416237cc681aef2a97adea7bdbgbg1b533f1e344e4cgab2bf0g448dc1af04
7.42g1fe26c5g0gc81e25ed04f531583f0f07bac089197a0161d3a98aeacb551f
8.614f1g21a875c5c1bd7a5da236070c98e9e9bf05cd9d84a75fg4818bb52cd1f
9.afc1f0ef689b4b4f5396b36edag9g478272751gb43738c69b10c8f855be43f1
a.ce0f12ea4b0g048f2eb23gc1bdfb8d1g1g9564g87f796gfaf3d67862645bbf1
b.e2cfaed944a8f621e67963269535050f5bdd1f2dcc2c4065e51g0cc834f61gc
c.7gb07fbf020a44a9352838cdd362a4dee92891a7f38c44023dga17b5b4dgc29
d.e6b40483d2gafg1f82b902fb37ab40170240fdac61b04efbcg1e527bf5019ba
e.3edg5cg67d0dd50b6592a4c35f32793g389732971gg9448fb31a1b8c3146138
f.7d472fb69686a0c03a65b7eb26ga3c7gc9174b67e0593gag3b2e5411cd7a38c
g.ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg

19
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.6e4edaeiggibcd8b28188af8ddhibe66i131i7a5c8b01520b6467bcb5g370bf
3.g78gif1i662348h253f3i4hi2e8a720fif6a2h39i80hc8a71c3h23aihd9ed9e
4.5hh56e012e36hc0e74197g1ad8646gfh3f021hbgg68bab88f3d98fb6e6f5607
5.33dbd7gh442fg27e7bgb7fd8g87a0h62ih9b16eebhbhddc7ci74ae3b4bd2e1b
6.c2heihgi6da84i0hd747d4f9fddh218d0dd46f8a67a07240648cecahb4221ei
7.f701i04b576ccidc4b4af9c8icg5877a17b9238a81f84821469d4628d895a0i
8.f701i04b576ccidc4b4af9c8icg5877a17b9238a81f84821469d4628d895a0i
9.1i2hc51i9a44g6h6g6d2hg1i8fhf91e6e94cb5hae407156agagfe9fdb71bb4c
a.h0g16dh098ee2c1c2c5g12h0a3139h4c49e67d184eibhdc8282349357bh77e6
b.3bih0ie7dbc66056e7e8396a062dabb8hb79gfa8ah3aeaghec95ecga5a9d8i0
c.3bih0ie7dbc66056e7e8396a062dabb8hb79gfa8ah3aeaghec95ecga5a9d8i0
d.6g140120c58ae0i15beb5e393551gha5i55ec3a8cb8ibgeicea646817eggh40
e.ff575b21eeg32gb4b727b35a2ab8i1cg0197hc447171556b60be84f7e75g4h7
f.d11dc4ihg4fc16i4beh9b2h85acec231f3igh1722ca787aa3f59a37c4c3dcib
g.2ba203h0ccgfea1gdf3f0e10g4a8bgi303c8g1f90ai16a8bh6f1gf801594594
h.c4e45840220765a7gahaa83a551074cc0hfh0b8d6a7ihdgi7cecb767d2fbi73
i.iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

23
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.blaf29c8idamhdajh3ihe43i7i43mem109m4df5f2mb3ch44ddef9cj1hm4901k
3.5hh7il7fci17cmma870m2jfce5f0g3hllgi38ggk9j4k870l2i729943i3a963m
4.lm478gm1m8h0mld4hk74fmej8g3bhii35bmb3j7j5a4d3f0bf86263d90mlmdli
5.12j829j77953621858fh058lfbe75547187laigce97h2f02fg9k32h5embaa3i
6.kfh1e7k1kl938a78ae8e3bf9ibamg9l1dl6i5d0fma1c5mekj96clam9ag9bf27
7.fj588fjbd2d0f06m1k521bh715ah69gb8gc458j173ej6h9ff0ljlladk27jbim
8.hhahjb334fadd8l2ea83dcjjlmbcjfablff2djam5demleb1ddd3412m1f3ibi0
9.7d17jfckm26ggdljb6ci8ae346ek48a78g02a3mmf55cb1cf4a5cbb100e1l1ck
a.b7lcmfhk5m2f384b8157me84b843df7dmk2ij2k9g11f56848779j0fhcblkb50
b.8ah33jma41cljah1ia67b3341a8j2i3gemhmhb7m1lj82h2673glg0k90bbif82
c.ec5jj30cila13c5l4cgfbjjilce3k4j680505bf0l13ek5kgfj616m2dmbb47ek
d.bf1a0752h0k7jeibelhf08eibeij97f902k43k2d6ll7hgeieffd3m75ab12bhm
e.f9lf37a20kg66913bga4ec8jig82iecfe6mkcj007hhabla7ichabblmm8l1la2
f.55c53bjji7c99e1k8cej9a3310ba37cb177k93c0h98018bl999jilk0l7j4b4m
g.73hee73b9k9m7mg0l2hklb5flhc5gd6be6aihe3lfj83g5d77m1311c92kf3b40
h.275l8f2l21djecfec8e8jb7d4bc06d1l91g4h9m70clah0823dga1c0dc6db7kf
i.lk3ekd3ffdhjgklehe75mhe17b8fhhiflef1c46a8df5k7mk76d2jk5h80bccj4
j.10ife60l0e5m019i52fi7083e6jb544jhb0bj3f3hci9j7mb7egkgj9dm010914
k.h55f41f7a4lfa00cefm0k37a8h7m6j51164je662d3i2efm1k4fkddij4jcdgj0
l.b1c7kdae49c059c35j458ij4f4ij080lmd0i97h7k0bja5ii9987da3l50idml2
m.mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

29
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.2qsjg5bdo16m7oo30rs940d801mqpcp456efqce30ef65sci06ncikhbf5pq8bq
3.gr03fra6ns12gcq3smq2r5ebgcg5pcqnb7oec9k15i57o9c4lk0c6k7msq9m5i9
4.8lg12ro0da856408ol0lfek5d8p93g2gsgm3hkjg3rs5krano6a0rbsojemmc4i
5.296i4ese7rg35a39f23fd7rj3djr38lnqc06dbhoe22k5h80lrj3de90bkfjerr
6.9k8eq0p49qhqo2l15o0nghn1kkjncihd9sads4o8oqgcl3ec6eo4c4cmh2sr9qk
7.m533al755811iijiefob9imgajor3edhj5dkec3g5bal6k1nprc7r4s84kccshp
8.ohmn9kgoga7j8rhe1f53b8lh8o76bbmkehesqohi57pfic15p2j3cjq5gjegp2f
9.9f8n9slr9qp06drkrjrg7iaio9j4o7m78p1np4k20aaagqf1h78n576k2e89qja
a.e7o55l26elpmjjc2jmqk7dnme1l5dpdjpppmkk1bsj4l30a0e2lfck3d07nr092
b.l6956f5f48c638b3gl9i54cb5202aok1nbge055l4dsbk6glo9dlhr8l4f3qp66
c.1c1igf39op3e0r8rqd21ogf2ho6mme8igdk5k79dmejki00q4ml12bb7a385nic
d.mqk3p8nen4jm4hp705lmdirs6prjhl7e4963hs8lk2a113aee084ro0saqojmq5
e.069jm8o43jgp106439rm5skbi5qse11sg26csphghps2kqrfqjo3db707b739ng
f.smj96k4op9c3rsmopj16n08han20err0cqmg03bcb30q821d294pfhlslhlpj5c
g.628p3k5e5o96ob3lsn76fa10m319b7leojmpb0k78qirrpieesko14s0i24962n
h.rgracdpj43pes1k12fqr4cdqb4m66ekacf8n8ljf6e98ass2o67rqhhlipkn5ag
i.7mjnmdndokgmpkhpc7janoghnqsqi48r5hcesnn7of0h8mc74jf7b1k7odp23mm
j.el4nn7qme73699gq9628lf56er7nf3f9333688rh09o7psiseq7dg8pfsl51sjq
k.jdk5j071j23smf18191claia4j9o4l6lk3r53o8qsiiic2drblk5nlm8qekj29i
l.4b65j8c4cil9k1berdnphk7bk4lmhh68ebe024banl3dagrn3q9pg92nc9ec3qd
m.6nppi7lnnkrraa9aed4hja6ci941pefb9nf8egpcnhi7m8r531gl1o0ko8gg0b3
n.j8ke2s3oj2b24q7rn4s5cb5r8895gabfj0if0o4k42cg7pegme4ogog6bq01j28
o.qjmaoe0el1cpnipjdqpdfl19pf91pk752gsmfhb4eqq8nbks719pfejsh8d9e11
p.k7crq14sfiknmosk47s7de8nfk3jpcqc0c6pb89cp10n81i54mis1h049e66goa
q.c1spd1im50rqcg2p062q1nehcgcn3g25hl4egj8rnanl4jgo78sgm8l602j6naj
r.q209cnhf4rm6l44ps10josfksr623g3onmed2gepsedmn0gasm5ga8bhdn32kh2
s.sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss

31
0.000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000
2.cbqgje47dq2fo82h1cqp293f0cchlncjqqqnlsgff7ubtkbs341italcqhicu6s
3.keu2n1teqho32cgmn1r7c05ihnfa49o1n1r83qdjuleb43nd9qh3lmsm6e522br
4.h32f4o9opta8d1s6rgrit72patb2bjm92q36orelpt1cohbqf62op7pqenui0uh
5.eo8itrc9ekb2fefj499uujej5q98dbooo2tf2g6tsahui2j9309tcuio2enjqos
6.eo8itrc9ekb2fefj499uujej5q98dbooo2tf2g6tsahui2j9309tcuio2enjqos
7.relj2gpcgmel36qc9gak6ihom3lt97c99pfs7pe0tcqaf891a6r9ho56islp7rn
8.k8te4hme9b6aet918e543taqd8p8tk6njor0g5pa8mk6emuaaaal1mfdt6nlpqc
9.rmb6jqgnujcrfndecr6rc36bmk8m7if6d6k8buipbcro0j5e76cfs9dt797fe13
a.qp7muk15fjiooauukdsh6i8ro5boqglqpo81fbqnqu8i92ch6l7fgl0r6s5g1ig
b.din37946blptg7nj52785qji2221lq3jbkj31mtlnbsm8qkrpct2c1022lld8qa
c.7638j46csel8ij1hmpnc9rbbphnah93flk4p59c8b78u7nneap82f1m82fos0pd
d.nn4ca4r0i7ho7a5e1h65ef98jjrmqjq7ld7mr4mpcbpjksfdmeupet1hfue63i6
e.euk97imnlubo097fakiuetdop1suom81tudl3qhpardufkp5de8p0u1joe0pl2f
f.inqfso5fh5k2l89p5csh4fg4piisu1blhfruuupgislu5um3ukd1q90m8hamp1s
g.c74f26pfdpas9ml5pi2dqfeq5cc20tj9df30005ec290p08r0aht4lu8mdk85t2
h.g0alnc8790j6ulnfkac0g1h65t2068mt10h9r4d5k3h0fa5phgm5u0tb6gu59sf
i.77qikq3ucnd6nkpgtdopgflmbb384b4n9hn83q85ij5ba2fh8g05g1tdf0gorco
j.normbqoi2g9mcbtd857il3jj5d7kdlrf9aq5plimjnm0n77gk5msft8msf62u5h
k.hc7rnlqoj951en7bpsnmp4bcssst94rbjabrt8197j28m4a35i1situss99hm4k
l.45n80atpfbc66k00ah2docm36pj64e9456mtfj4740mclsido9nfe9u3o2petce
m.38job4e70bi3f7hgi3o3iroj8am8ncfohoamj0c5ji36ubpgnoif2lh1nlnfgtr
n.am1gqd8gljokg1ltmgpqr1k4hm5m1ao7b63uep5km8aog80kkkk9t8fh1o7954i
o.3g9bse5ie8g9ro4ilekaocd68r91lnill5f2n5gu1i4kfmltko3ld6poc295n37
p.g6mc13ilgajsfgfbqll00bgbp4lmhj666s1fseo12kd0csblrul1i0c6sg7b462
q.g6mc13ilgajsfgfbqll00bgbp4lmhj666s1fseo12kd0csblrul1i0c6sg7b462
r.drsfq6l651kmht2o3e3c1ns5k1jsjb8ls4ro63g951ti6dj4fos65n54g70cu0d
s.ag0s7t1g4d6rsie87t3niupcd7fkql6t7t3mr4hb09gjqr7hl4dr9828ogpssj3
t.ij4ebgqnh4sf6msdti45slrfuiid97ib444792effn0j1aj2rqtc1k9i4dci0o2
u.uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu