Line data    Source code

       1             : import 'dart:math' as math;
       2             : import 'package:logger/logger.dart';
       3             : 
       4           3 : var _log = Logger(
       5           1 :   printer: SimplePrinter(printTime: true),
       6             : );
       7             : 
       8             : enum ExprStyle {
       9             :   normalStyle,
      10             :   textStyle,
      11             :   displayStyle,
      12             : }
      13             : 
      14             : extension Compare<T> on Comparable<T> {
      15           0 :   bool operator <=(T other) => compareTo(other) <= 0;
      16           0 :   bool operator >=(T other) => compareTo(other) >= 0;
      17           0 :   bool operator <(T other) => compareTo(other) < 0;
      18           0 :   bool operator >(T other) => compareTo(other) > 0;
      19             : }
      20             : 
      21             : class Fraction implements Comparable<Fraction> {
      22             :   BigInt num, den;
      23           3 :   Fraction(this.num, this.den);
      24             : 
      25           0 :   static Fraction pi = fromDouble(math.pi);
      26           0 :   static Fraction e = fromDouble(math.e);
      27             : 
      28           1 :   static Fraction _fromDoubleSub(List<BigInt> v) {
      29           3 :     Fraction res = Fraction(BigInt.one, BigInt.one);
      30           2 :     for (var vv in v.reversed) {
      31           4 :       res = res.inv() + Fraction(vv, BigInt.one);
      32             :     }
      33           1 :     res.fix();
      34             :     return res;
      35             :   }
      36             : 
      37           1 :   static Fraction fromDouble(double v, {double precision = 1e-9}) {
      38             :     var cur = v;
      39           1 :     List<BigInt> stk = [];
      40             :     while (true) {
      41           1 :       var flr = BigInt.from(cur);
      42           3 :       _log.d("$v -> cur=$cur, flr=$flr");
      43           1 :       stk.add(flr);
      44           2 :       cur -= flr.toDouble();
      45           1 :       cur = 1 / cur;
      46           1 :       var res = _fromDoubleSub(stk);
      47           3 :       _log.d("test $v =?= $res");
      48           4 :       if ((res.toDouble() - v).abs() < precision) {
      49           3 :         _log.d("result: $res");
      50             :         return res;
      51             :       }
      52             :     }
      53             :   }
      54             : 
      55           1 :   static Fraction fromDouble2(double v, {double precision = 1e-12}) {
      56           5 :     var ret = Fraction(BigInt.from(v / precision), BigInt.from(1 / precision));
      57           1 :     ret.fix();
      58             :     return ret;
      59             :   }
      60             : 
      61           2 :   static Fraction fromBigInt(BigInt v) {
      62           4 :     return Fraction(v, BigInt.one);
      63             :   }
      64             : 
      65           1 :   static Fraction fromInt(int v) {
      66           3 :     return Fraction(BigInt.from(v), BigInt.one);
      67             :   }
      68             : 
      69           3 :   static Fraction _fromString(String s) {
      70           3 :     var idx = s.indexOf(".");
      71           6 :     if (idx == -1) {
      72           9 :       return Fraction(BigInt.parse(s), BigInt.one);
      73             :     }
      74           5 :     var n1 = BigInt.parse(s.substring(0, idx) + s.substring(idx + 1));
      75           3 :     var l = (s.length - idx) - 1;
      76           3 :     var n2 = BigInt.parse('1${"0"*l}');
      77           1 :     var ret = Fraction(n1, n2);
      78           1 :     ret.fix();
      79             :     return ret;
      80             :   }
      81             : 
      82           3 :   static Fraction fromString(String s) {
      83           3 :     var idx = s.indexOf("/");
      84           6 :     if (idx == -1) {
      85           3 :       return _fromString(s);
      86             :     }
      87           2 :     var x1 = _fromString(s.substring(0, idx));
      88           3 :     var x2 = _fromString(s.substring(idx + 1));
      89           1 :     return x1 / x2;
      90             :   }
      91             : 
      92           3 :   void fix() {
      93           9 :     var n = num.gcd(den);
      94           6 :     if (n != BigInt.one) {
      95           4 :       num ~/= n;
      96           4 :       den ~/= n;
      97             :     }
      98           9 :     if (den.sign < 0) {
      99           0 :       den = -den;
     100           0 :       num = -num;
     101             :     }
     102             :   }
     103             : 
     104           0 :   bool isNegative() {
     105           0 :     return num.isNegative ^ den.isNegative;
     106             :   }
     107             : 
     108           1 :   Fraction abs() {
     109           5 :     return Fraction(num.abs(), den.abs());
     110             :   }
     111             : 
     112           2 :   double toDouble() {
     113           6 :     return num / den;
     114             :   }
     115             : 
     116           1 :   BigInt toBigInt() {
     117           3 :     return num ~/ den;
     118             :   }
     119             : 
     120           3 :   @override
     121             :   String toString() {
     122           3 :     fix();
     123           9 :     if (den == BigInt.one) {
     124           4 :       return num.toString();
     125             :     } else {
     126           9 :       return "$num/$den";
     127             :     }
     128             :   }
     129             : 
     130           1 :   String toString2() {
     131           1 :     fix();
     132           3 :     BigInt n1 = num ~/ den;
     133           4 :     BigInt n2 = (num % den).abs();
     134           2 :     if (n2 == BigInt.zero) {
     135           0 :       return "$n1";
     136             :     } else {
     137           2 :       return "$n1+$n2/$den";
     138             :     }
     139             :   }
     140             : 
     141             :   Map<ExprStyle, String> stylemap = {
     142             :     ExprStyle.normalStyle: "frac",
     143             :     ExprStyle.textStyle: "tfrac",
     144             :     ExprStyle.displayStyle: "dfrac",
     145             :   };
     146             : 
     147           3 :   String toExpr([ExprStyle style = ExprStyle.normalStyle]) {
     148           3 :     fix();
     149           9 :     if (den == BigInt.one) {
     150           4 :       return num.toString();
     151             :     } else {
     152           4 :       var s = stylemap[style]!;
     153           6 :       return "\\$s{$num}{$den}";
     154             :     }
     155             :   }
     156             : 
     157           2 :   String toExpr2([ExprStyle style = ExprStyle.normalStyle]) {
     158           2 :     fix();
     159           6 :     BigInt n1 = num ~/ den;
     160           8 :     BigInt n2 = (num % den).abs();
     161           4 :     if (n1 == BigInt.zero) {
     162           0 :       return toExpr(style);
     163           4 :     } else if (n2 == BigInt.zero) {
     164           1 :       return "$n1";
     165             :     } else {
     166           4 :       var s = stylemap[style]!;
     167           4 :       return "$n1\\$s{$n2}{$den}";
     168             :     }
     169             :   }
     170             : 
     171           0 :   @override
     172             :   int compareTo(Fraction other) {
     173           0 :     fix();
     174           0 :     other.fix();
     175           0 :     _log.d("compareTo: $this $other");
     176           0 :     if (other.num == num && other.den == den) {
     177             :       return 0;
     178             :     }
     179           0 :     if ((num / den) < (other.num / other.den)) {
     180           0 :       return -1;
     181             :     }
     182             :     return 1;
     183             :   }
     184             : 
     185           0 :   Fraction operator %(Fraction other) {
     186           0 :     BigInt n = den.gcd(other.den);
     187           0 :     BigInt n1 = other.den ~/ n;
     188           0 :     BigInt n2 = den ~/ n;
     189           0 :     var ret = Fraction(num * n1, den * n1);
     190           0 :     ret.num %= other.num * n2;
     191             :     return ret;
     192             :   }
     193             : 
     194           2 :   Fraction operator *(Fraction other) {
     195          14 :     return Fraction(num * other.num, den * other.den);
     196             :   }
     197             : 
     198           0 :   Fraction square() {
     199           0 :     return Fraction(num * num, den * den);
     200             :   }
     201             : 
     202           3 :   Fraction operator +(Fraction other) {
     203           9 :     BigInt n = den.gcd(other.den);
     204           6 :     BigInt n1 = other.den ~/ n;
     205           6 :     BigInt n2 = den ~/ n;
     206          15 :     var ret = Fraction(num * n1, den * n1);
     207          12 :     ret.num += other.num * n2;
     208             :     return ret;
     209             :   }
     210             : 
     211           2 :   Fraction operator -(Fraction other) {
     212           6 :     BigInt n = den.gcd(other.den);
     213           4 :     BigInt n1 = other.den ~/ n;
     214           4 :     BigInt n2 = den ~/ n;
     215          10 :     var ret = Fraction(num * n1, den * n1);
     216           8 :     ret.num -= other.num * n2;
     217             :     return ret;
     218             :   }
     219             : 
     220           3 :   Fraction operator /(Fraction other) {
     221          21 :     var ret = Fraction(num * other.den, den * other.num);
     222             :     return ret;
     223             :   }
     224             : 
     225           1 :   bool operator <(Fraction other) {
     226           3 :     BigInt n = den.gcd(other.den);
     227           2 :     BigInt n1 = other.den ~/ n;
     228           2 :     BigInt n2 = den ~/ n;
     229           5 :     return (num * n1) < (other.num * n2);
     230             :   }
     231             : 
     232           0 :   bool operator <=(Fraction other) {
     233           0 :     BigInt n = den.gcd(other.den);
     234           0 :     BigInt n1 = other.den ~/ n;
     235           0 :     BigInt n2 = den ~/ n;
     236           0 :     return (num * n1) <= (other.num * n2);
     237             :   }
     238             : 
     239           0 :   bool operator >=(Fraction other) {
     240           0 :     BigInt n = den.gcd(other.den);
     241           0 :     BigInt n1 = other.den ~/ n;
     242           0 :     BigInt n2 = den ~/ n;
     243           0 :     return (num * n1) >= (other.num * n2);
     244             :   }
     245             : 
     246           1 :   bool operator >(Fraction other) {
     247           3 :     BigInt n = den.gcd(other.den);
     248           2 :     BigInt n1 = other.den ~/ n;
     249           2 :     BigInt n2 = den ~/ n;
     250           5 :     return (num * n1) > (other.num * n2);
     251             :   }
     252             : 
     253           0 :   @override
     254           0 :   int get hashCode => num.hashCode ^ den.hashCode;
     255             : 
     256           1 :   @override
     257             :   bool operator ==(Object other) {
     258           1 :     if (other is Fraction) {
     259           1 :       fix();
     260           1 :       other.fix();
     261           6 :       return num == other.num && den == other.den;
     262           0 :     } else if (other is BigInt) {
     263           0 :       fix();
     264           0 :       return num == other && den == BigInt.one;
     265           0 :     } else if (other is int) {
     266           0 :       fix();
     267           0 :       return num.toInt() == other && den == BigInt.one;
     268           0 :     } else if (other is double) {
     269           0 :       return toDouble() == other;
     270             :     }
     271             :     return false;
     272             :   }
     273             : 
     274           2 :   Fraction operator <<(int n) {
     275           8 :     return Fraction(num << n, den);
     276             :   }
     277             : 
     278           2 :   Fraction operator >>(int n) {
     279           8 :     return Fraction(num, den << n);
     280             :   }
     281             : 
     282           2 :   Fraction operator -() {
     283           8 :     return Fraction(-num, den);
     284             :   }
     285             : 
     286           1 :   Fraction log() {
     287           3 :     return Fraction.fromDouble(math.log(toDouble()));
     288             :   }
     289             : 
     290           1 :   Fraction log2() {
     291           3 :     return log() / Fraction.fromDouble(math.ln2);
     292             :   }
     293             : 
     294           0 :   Fraction log10() {
     295           0 :     return log() / Fraction.fromDouble(math.ln10);
     296             :   }
     297             : 
     298           0 :   Fraction logN(double n) {
     299             :     // returns log_n(this)
     300           0 :     return log() / fromDouble(math.log(n));
     301             :   }
     302             : 
     303           0 :   Fraction log2slow([double precision = 1e-10]) {
     304             :     // returns log_2(this)
     305           0 :     var res = Fraction(BigInt.from(0), BigInt.one);
     306           0 :     var x = Fraction(num, den);
     307           0 :     var one = Fraction(BigInt.one, BigInt.one);
     308           0 :     var two = Fraction(BigInt.two, BigInt.one);
     309             :     // int part
     310           0 :     while (x < one) {
     311           0 :       res -= one;
     312           0 :       x <<= 1;
     313             :     }
     314           0 :     while (x >= two) {
     315           0 :       res += one;
     316           0 :       x >>= 1;
     317             :     }
     318             :     // float part
     319           0 :     var fp = Fraction(BigInt.one, BigInt.one);
     320           0 :     var prec = Fraction.fromDouble(precision);
     321           0 :     while (fp.den <= prec.den) {
     322           0 :       fp >>= 1;
     323           0 :       x = x.square();
     324           0 :       if (x.num ~/ x.den >= BigInt.two) {
     325           0 :         x >>= 1;
     326           0 :         res += fp;
     327             :       }
     328             :     }
     329             :     return res;
     330             :   }
     331             : 
     332           0 :   Fraction pow(Fraction other) {
     333             :     // returns this ** other
     334           0 :     return fromDouble(math.pow(toDouble(), other.toDouble()).toDouble());
     335             :   }
     336             : 
     337           1 :   Fraction sqrt([double precision = 1e-10]) {
     338             :     // returns sqrt(this)
     339             :     // simple sqrt algo
     340           3 :     _log.d("sqrt $this");
     341           1 :     var prec = fromDouble(precision);
     342           3 :     var r = Fraction(num, den);
     343           4 :     while ((this - r * r).abs() > prec) {
     344           2 :       r = (r + this / r);
     345           3 :       r.den *= BigInt.from(2);
     346             :     }
     347           3 :     _log.d("result $r");
     348             :     return r;
     349             :   }
     350             : 
     351           0 :   Fraction exp() {
     352             :     // returns e ** this
     353           0 :     return e.pow(this);
     354             :   }
     355             : 
     356           1 :   Fraction inv() {
     357           3 :     return Fraction(den, num);
     358             :   }
     359             : }