Z.myr

   1 use std
   2
   3 use t
   4
   5 use "traits"
   6 use "bigint"
   7
   8 pkg yakmo =
   9         type Z = std.bigint
  10         impl disposable Z#
  11         impl division_struct Z#
  12         impl group_struct Z#
  13         impl ring_struct Z#
  14         impl abs_struct Z#
  15         impl gcd_struct Z#
  16         impl lcm_struct Z#
  17         impl real_struct Z#
  18         impl std.equatable Z#
  19         impl t.comparable Z#
  20         impl t.dupable Z#
  21
  22         generic Zfrom : (a : @a -> Z#) :: numeric,integral @a
  23
  24         /*
  25         trait Zlike @a =
  26                 Zfrom : (a : @a -> Z#)
  27         ;;
  28         impl Zlike @a :: numeric,integral @a
  29         impl Zlike Z#
  30         */
  31
  32         const ZfromS : (s : byte[:] -> std.result(Z#, byte[:]))
  33
  34         /* generic eqZ : (a : Z#, b : @i -> bool) :: Zlike @i */
  35         generic eqZ : (a : Z#, b : @i -> bool) :: numeric,integral @i
  36 ;;
  37
  38 const __init__ = {
  39         var z : Z#
  40         z = z
  41         std.fmtinstall(std.typeof(z), zfmt)
  42 }
  43
  44 const zfmt = {sb, ap, opts
  45         var z : Z# = std.vanext(ap)
  46         var bz : std.bigint# = (z : std.bigint#)
  47         std.sbfmt(sb, "{}", bz)
  48 }
  49
  50 impl disposable Z# =
  51         __dispose__ = {a
  52                 var ba : std.bigint# = (a : std.bigint#)
  53                 std.bigfree(ba)
  54         }
  55 ;;
  56
  57 impl division_struct Z# =
  58         div_maybe = {a, b
  59                 var ba : std.bigint# = (a : std.bigint#)
  60                 var bb : std.bigint# = (b : std.bigint#)
  61                 var q, r
  62                 (q, r) = std.bigdivmod(ba, bb)
  63                 if std.bigiszero(r)
  64                         std.bigfree(r)
  65                         -> `std.Some (q : Z#)
  66                 else
  67                         std.bigfree(r)
  68                         std.bigfree(q)
  69                         -> `std.None
  70                 ;;
  71         }
  72 ;;
  73
  74 impl group_struct Z# =
  75         gadd_ip = {a, b
  76                 var ba : std.bigint# = (a : std.bigint#)
  77                 var bb : std.bigint# = (b : std.bigint#)
  78                 std.bigadd(ba, bb)
  79         }
  80         gadd = {a, b
  81                 var g = t.dup(a)
  82                 gadd_ip(g, b)
  83                 -> g
  84         }
  85         gneg_ip = {a
  86                 var ba : std.bigint# = (a : std.bigint#)
  87                 ba.sign *= -1
  88         }
  89         gneg = {a
  90                 var g = t.dup(a)
  91                 gneg_ip(g)
  92                 -> g
  93         }
  94         gid = {
  95                 var id : std.bigint# = std.mkbigint(0)
  96                 -> (id : Z#)
  97         }
  98
  99         eq_gid = {z
 100                 -> std.bigiszero((z : std.bigint#))
 101         }
 102 ;;
 103
 104 impl ring_struct Z# =
 105         rid = {
 106                 var u : std.bigint# = std.mkbigint(1)
 107                 -> (u : Z#)
 108         }
 109         rmul_ip = {a, b
 110                 var ba : std.bigint# = (a : std.bigint#)
 111                 var bb : std.bigint# = (b : std.bigint#)
 112                 std.bigmul(ba, bb)
 113         }
 114         rmul = {a, b
 115                 var r = t.dup(a)
 116                 rmul_ip(r, b)
 117                 -> r
 118         }
 119 ;;
 120
 121 impl abs_struct Z# =
 122         abs_ip = {z;
 123                 var b : std.bigint# = (z : std.bigint#)
 124                 if !std.bigiszero(b)
 125                         b.sign = 1
 126                 ;;
 127         }
 128         abs = {z;
 129                 var ret = t.dup(z)
 130                 abs_ip(ret)
 131                 -> ret
 132         }
 133         cmp_zero = {z;
 134                 var b : std.bigint# = (z : std.bigint#)
 135                 if std.bigiszero(b)
 136                         -> `std.Equal
 137                 elif b.sign > 0
 138                         -> `std.After
 139                 else
 140                         -> `std.Before
 141                 ;;
 142         }
 143 ;;
 144
 145 impl gcd_struct Z# =
 146         gcd = {a : Z#, b : Z#
 147                 var ab : std.bigint# = (a : std.bigint#)
 148                 var bb : std.bigint# = (b : std.bigint#)
 149                 if std.bigiszero(bb)
 150                         var ret = t.dup(a)
 151                         abs_ip(ret)
 152                         -> ret
 153                 elif std.bigiszero(ab)
 154                         var ret = t.dup(b)
 155                         abs_ip(ret)
 156                         -> ret
 157                 ;;
 158
 159                 var t1 = std.bigdup(ab)
 160                 t1.sign = 1
 161                 var t2 = std.bigdup(bb)
 162                 t2.sign = 1
 163
 164                 while true
 165                         std.bigmod(t1, t2)
 166                         if std.bigiszero(t1)
 167                                 std.bigfree(t1)
 168                                 -> (t2 : Z#)
 169                         ;;
 170
 171                         std.bigmod(t2, t1)
 172                         if std.bigiszero(t2)
 173                                 std.bigfree(t2)
 174                                 -> (t1 : Z#)
 175                         ;;
 176                 ;;
 177
 178                 -> Zfrom(0)
 179         }
 180 ;;
 181
 182 impl lcm_struct Z# =
 183         lcm = {a : Z#, b : Z#
 184                 if std.bigiszero((a : std.bigint#)) && std.bigiszero((b : std.bigint#))
 185                         -> Zfrom(0)
 186                 ;;
 187
 188                 var d = yakmo.gcd(a, b)
 189                 auto d
 190                 match yakmo.div_maybe(a, d)
 191                 | `std.None: /* impossible */
 192                         -> Zfrom(0)
 193                 | `std.Some ab_over_d:
 194                         yakmo.rmul_ip(ab_over_d, b)
 195                         yakmo.abs_ip(ab_over_d)
 196                         -> ab_over_d
 197                 ;;
 198         }
 199 ;;
 200
 201 impl real_struct Z# =
 202         compconj_ip = {z;}
 203         compconj = {z; -> t.dup(z)}
 204 ;;
 205
 206 impl std.equatable Z# =
 207         eq = {a,b; -> std.bigeq((a : std.bigint#),(b : std.bigint#))}
 208 ;;
 209
 210 impl t.comparable Z# =
 211         cmp = {a,b; -> std.bigcmp((a : std.bigint#),(b : std.bigint#))}
 212 ;;
 213
 214 impl t.dupable Z# =
 215         dup = {a
 216                 var aa = std.bigdup((a : std.bigint#))
 217                 -> (aa : Z#)
 218         }
 219 ;;
 220
 221 generic eqZ = {a, b
 222         /*
 223         var bz = auto Zfrom(b)
 224         var abi : std.bigint# = (a : std.bigint#)
 225         var bbi : std.bigint# = (bz : std.bigint#)
 226         -> std.bigeq(abi, bbi)
 227         */
 228
 229         -> std.bigeqi((a : std.bigint#), b)
 230 }
 231
 232 /*
 233 impl Zlike @a :: numeric,integral @a =
 234         Zfrom = { a; -> (std.mkbigint(a) : Z#) }
 235 ;;
 236
 237 impl Zlike Z# =
 238         Zfrom = {a; -> t.dup(a)}
 239 ;;
 240 */
 241
 242 generic Zfrom = {a; -> (std.mkbigint(a) : Z#) }
 243
 244 const ZfromS = {s
 245         match std.bigparse(s)
 246         | `std.Some n: -> `std.Ok (n : Z#)
 247         | `std.None: -> `std.Err std.fmt("cannot parse \"{}\"", s)
 248         ;;
 249 }