general.myr

   1 use std
   2
   3 use t
   4
   5 use "traits"
   6 use "Z"
   7
   8 pkg yakmo =
   9         /*
  10            Suffixes like _a, _c mean that certain properties of some
  11            object are required. Given an argument that doesn't satisfy
  12            those properties, all bets are off.
  13          */
  14
  15         /* Compute a + a + ... + a, for @a with an associative, commutative "+" */
  16         generic gpow_ac : (a : @a, n : Z# -> @a) :: disposable @a, group_struct @a
  17
  18         /* Compute a · a · ... · a, for @a with an associative, commutative "·" */
  19         generic fpow_ac : (a : @a, n : Z# -> std.result(@a, byte[:])) :: disposable @a, field_struct @a, ring_struct @a
  20 ;;
  21
  22 generic gpow_ac = {a, n
  23         var nb : std.bigint# = std.bigdup((n : std.bigint#))
  24         var then_negate : bool = false
  25
  26         if std.bigiszero(nb)
  27                 std.bigfree(nb)
  28                 -> gid()
  29         elif std.bigeqi(nb, 1)
  30                 std.bigfree(nb)
  31                 -> t.dup(a)
  32         elif std.bigeqi(nb, 2)
  33                 std.bigfree(nb)
  34                 -> gadd(a, a)
  35         else
  36                 then_negate = nb.sign < 0
  37                 nb.sign = 1
  38         ;;
  39
  40         var res : @a = rid()
  41         var double : @a = t.dup(a)
  42
  43         while !std.bigiszero(nb)
  44                 if !std.bigiseven(nb)
  45                         gadd_ip(res, double)
  46                 ;;
  47
  48                 gadd_ip(double, double)
  49                 std.bigshri(nb, 1)
  50         ;;
  51
  52         std.bigfree(nb)
  53         __dispose__(double) // TODO: recognize "disposable" trait
  54
  55         if then_negate
  56                 gneg_ip(res)
  57         ;;
  58         -> res
  59 }
  60
  61 generic fpow_ac = {a, n
  62         var nb : std.bigint# = std.bigdup((n : std.bigint#))
  63         var then_invert : bool = false
  64
  65         if std.bigiszero(nb)
  66                 std.bigfree(nb)
  67                 -> `std.Ok rid()
  68         elif std.bigeqi(nb, 1)
  69                 std.bigfree(nb)
  70                 -> `std.Ok t.dup(a)
  71         elif std.bigeqi(nb, 2)
  72                 std.bigfree(nb)
  73                 -> `std.Ok rmul(a, a)
  74         else
  75                 then_invert = nb.sign < 0
  76                 nb.sign = 1
  77         ;;
  78
  79         var res : @a = rid()
  80         var double : @a = t.dup(a)
  81
  82         while !std.bigiszero(nb)
  83                 if !std.bigiseven(nb)
  84                         rmul_ip(res, double)
  85                 ;;
  86
  87                 rmul_ip(double, double)
  88                 std.bigshri(nb, 1)
  89         ;;
  90
  91         std.bigfree(nb)
  92         __dispose__(double) // TODO: recognize "disposable" trait
  93
  94         if then_invert
  95                 match finv(res)
  96                 | `std.Some resi:
  97                         __dispose__(res)
  98                         -> `std.Ok resi
  99                 | `std.None: -> `std.Err std.fmt("cannot invert {}^{} = {}", a, n, res)
 100                 ;;
 101         ;;
 102
 103         -> `std.Ok res
 104 }