nix-bigint/lib.nix

{ lib, ... }: with lib;
rec {
  # TODO: Changing the base currently requires more modifications to the code.
  #       The arithmetic works out, but `toBigInt` and `bigIntToString` does not.
  base = 10;

  # a -> Bool
  isBigInt = x: isAttrs x
             && x ? type
             && x.type == "bigint"
             && x ? isPositive
             && x ? digits;

  # Num -> BigInt
  toBigInt = num: {
    type = "bigint";
    isPositive = num >= 0;
    digits = pipe num [
      toString
      (removePrefix "-")
      stringToCharacters
      (map toInt)
    ];
  };

  # BigInt -> String
  bigIntToString = { isPositive, digits, ... }:
    (optionalString (!isPositive) "-") + (concatStringsSep "" (map toString digits));

  # https://silentmatt.com/blog/2011/10/how-bigintegers-work/

  # BigInt -> BigInt -> BigInt
  bigIntAdd = x: y:
    assert isBigInt x;
    assert isBigInt y;
  let
    # rem = lib.trivial.mod;
    # mod = a: b: a - b * (builtins.floor (a / b));
    repeat = item: times: map (const item) (range 1 times);
    zfill = len: el: xs: if length xs > len then xs else (repeat el (len - (length xs))) ++ xs;
    stripZeros = xs: if xs == [0] then [0]
                     else if head xs == 0 then stripZeros (tail xs)
                     else xs;

    addDigits = xs: ys: let
      addF = { fst, snd }: { carry ? false, digits ? [] }: let
        n = if carry then 1 + fst + snd else fst + snd;
      in {
        carry = n >= base;
        digits = [(mod n base)] ++ digits;
      };
      xs' = zfill (max (length xs) (length ys)) 0 xs;
      ys' = zfill (max (length xs) (length ys)) 0 ys;
      folded = foldr addF {} (zipLists xs' ys');
    in if folded.carry then [1] ++ folded.digits else folded.digits;

    subDigits = xs: ys: let
      subF = { fst, snd }: { borrow ? false, digits ? [] }: let
        n = if borrow then fst - snd - 1 else fst - snd;
        n' = if n < 0 then n + base else n;
      in {
        borrow = n < 0;
        digits = [n'] ++ digits;
      };
      xs' = zfill (max (length xs) (length ys)) 0 xs;
      ys' = zfill (max (length xs) (length ys)) 0 ys;
      folded = foldr subF {} (zipLists xs' ys');
    in stripZeros folded.digits;

  in if x.isPositive && y.isPositive then {
    type = "bigint";
    isPositive = true;
    digits = addDigits x.digits y.digits;
  }
  else if !x.isPositive && !y.isPositive then {
    type = "bigint";
    isPositive = false;
    digits = addDigits x.digits y.digits;
  }
  else if x.isPositive && !y.isPositive then rec {
    type = "bigint";
    isPositive = !(bigIntLessThan x (y // { isPositive = true; }));
    digits = if isPositive
               then subDigits x.digits y.digits
               else subDigits y.digits x.digits;
  }
  else /* !x.isPositive && y.isPositive */ rec {
    type = "bigint";
    isPositive = !(bigIntLessThan y (x // { isPositive = true; }));
    digits = if isPositive
               then subDigits y.digits x.digits
               else subDigits x.digits y.digits;
  };

  # BigInt -> BigInt -> BigInt
  bigIntSub = x: y@{ isPositive, ... }:
    bigIntAdd x (y // { isPositive = !isPositive; });

  # https://silentmatt.com/blog/2011/10/how-bigintegers-work-part-2-multiplication/

  # BigInt -> BigInt -> BigInt
  bigIntMultiply = x: y:
    assert isBigInt x;
    assert isBigInt y;
  let
    xor = a: b: (a && !b) || (!a && b);

    createPartial = y_digit: { carry ? 0, digits ? [] }: x_digit: let
      n = (x_digit * y_digit) + carry;
    in {
      carry = builtins.floor (n / base);
      digits = [(mod n base)] ++ digits;
    };

    partialProductDigits = let
      mapYs = i: y_digit: let
        partial = foldl (createPartial y_digit) { } ([0] ++ x.digits);
        partialWithCorrectPower = partial.digits ++ (builtins.genList (_: 0) i);
      in partialWithCorrectPower;
    in imap0 mapYs y.digits;

    partialProducts =
      map (digits: { type = "bigint"; isPositive = true; inherit digits; }) partialProductDigits;

  in foldl bigIntAdd (toBigInt 0) partialProducts // {
    isPositive = !(xor x.isPositive y.isPositive);
  };

  # BigInt -> BigInt -> BigInt
  bigIntEquals = x: y:
    assert isBigInt x;
    assert isBigInt y;
    x == y;

  # BigInt -> BigInt -> BigInt
  bigIntGreaterThan = x: y:
    assert isBigInt x;
    assert isBigInt y;
    if x.isPositive && !y.isPositive then true
    else if !x.isPositive && y.isPositive then false
    # Cheaper than the upcoming calculations
    else if bigIntEquals x y then false

    else if x.isPositive && y.isPositive then
      if length x.digits < length y.digits then false
      else if length x.digits > length y.digits then true
      else let
      compareDigits = xs: ys:
        if xs == [] then false
        else if (head xs) == (head ys) then compareDigits (tail xs) (tail ys)
        else head xs > head ys;
      in compareDigits x.digits y.digits

    /* !x.isPositive && !y.isPositive */
    else
      if length x.digits > length y.digits then false
      else if length x.digits < length y.digits then true
      else let
      compareDigits = xs: ys:
        if xs == [] then false
        else if (head xs) == (head ys) then compareDigits (tail xs) (tail ys)
        else head xs < head ys;
      in compareDigits x.digits y.digits;

  # BigInt -> BigInt -> BigInt
  bigIntLessThan = flip bigIntGreaterThan;

  # BigInt -> BigInt -> BigInt
  bigIntCmp = x: y: if bigIntEquals x y then 0 else
                    if bigIntGreaterThan x y then 1 else
                    -1;
}