static void integer_divide_remainder(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs, uint64_t *div, uint64_t *rem) {
  if(is_smallint(lhs) && is_smallint(rhs)) {
    *div = pack_smallint(unpack_smallint(lhs) / unpack_smallint(rhs));
    *rem = pack_smallint(unpack_smallint(lhs) % unpack_smallint(rhs));
  } else {
    *div = pack_undefined();
    *rem = pack_undefined();
  }
}
static uint64_t integer_divide(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
  uint64_t div, rem;
  integer_divide_remainder(a, lhs, rhs, &div, &rem);
  return div;
}
static uint64_t integer_remainder(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
  uint64_t div, rem;
  integer_divide_remainder(a, lhs, rhs, &div, &rem);
  return rem;
}
static uint64_t integer_negate(uint64_t expr) {
  return (expr ^ INTEGER_NEG_FLAG_BIT);
}
static bool integer_is_negative(uint64_t expr) {
  return (expr & INTEGER_NEG_FLAG_BIT) == INTEGER_NEG_FLAG_BIT;
}
static uint64_t integer_absolute(uint64_t expr) {
  return (expr & ~INTEGER_NEG_FLAG_BIT);
}
static uint64_t integer_greatest_common_denominator(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
  uint64_t r;
  while(rhs != LITERAL_ZERO) {
    r = integer_remainder(a, lhs, rhs);
    lhs = rhs;
    rhs = r;
  }
  return integer_absolute(lhs);
}
uint64_t solver_Algebra_integer(struct solver_Algebra *a, int64_t value) {
  return pack_smallint(value);
}

static uint64_t embed_fraction(struct solver_Algebra *a, uint64_t numerator, uint64_t denominator) {
  assert(is_smallint(numerator));
  assert(is_smallint(denominator));
  if(denominator == LITERAL_ZERO) {
    return pack_undefined();
  }
  uint64_t div, rem;
  integer_divide_remainder(a, numerator, denominator, &div, &rem);
  if(rem == LITERAL_ZERO) {
    return div;
  }
  uint64_t g = integer_greatest_common_denominator(a, numerator, denominator);
  uint64_t values[2];
  if(integer_is_negative(denominator)) {
    values[0] = integer_divide(a, numerator, g);
    values[1] = integer_divide(a, denominator, g);
  } else {
    values[0] = integer_divide(a, integer_negate(numerator), g);
    values[1] = integer_divide(a, integer_negate(denominator), g);
  }
  uint32_t index = embed_values(a, 2, values);
  return pack_fraction(index);
}
uint64_t solver_Algebra_fraction(struct solver_Algebra *a, uint64_t numerator, uint64_t denominator) {
  return embed_fraction(a, numerator, denominator);
}

// returns ¯∞ up to 0 for for less than, 0 for equals, then up to ∞ for greater than
static int term_compare(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs);
static int term_compare_lists_from_end(struct solver_Algebra *a, uint32_t l, const uint64_t *lhs, uint32_t r, const uint64_t *rhs) {
  for(;; --l, --r) {
    if(l == 0) return 1;
    if(r == 0) return -1;
    int cmp = term_compare(a, lhs[l], rhs[r]);
    if(cmp != 0) {
      return cmp;
    }
  }
}
static bool term_compare_0(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs, int *result) {
  uint32_t l, r;
  const uint64_t *l_values, *r_values;
  
  if(is_product(lhs)) {
    l = get_list_count(lhs);
    l_values = a->values.data + get_list_index(lhs);
    if(is_product(rhs)) {
      r = get_list_count(rhs);
      r_values = a->values.data + get_list_index(rhs);
    } else if(is_power(rhs) || is_sum(rhs) || is_variable(rhs)) {
      r = 1;
      r_values = &rhs;
    } else {
      return false;
    }
    *result = term_compare_lists_from_end(a, l, l_values, r, r_values);
    return true;
  }
  if(is_power(lhs)) {
    l = 2;
    l_values = a->values.data + get_pair_index(lhs);
    if(is_power(rhs)) {
      r = 2;
      r_values = a->values.data + get_pair_index(rhs);
    } else if(is_sum(rhs) || is_variable(rhs)) {
      r = 1;
      r_values = &rhs;
    } else {
      return false;
    }
    *result = term_compare_lists_from_end(a, l, l_values, r, r_values);
    return true;
  }
  if(is_sum(lhs)) {
    l = get_list_count(lhs);
    l_values = a->values.data + get_list_index(lhs);
    if(is_sum(rhs)) {
      r = get_list_count(rhs);
      r_values = a->values.data + get_list_index(rhs);
    } else if(is_variable(rhs)) {
      r = 1;
      r_values = &rhs;
    } else {
      return false;
    }
    *result = term_compare_lists_from_end(a, l, l_values, r, r_values);
    return true;
  }
  return false;
}
static int term_compare(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
  if(is_number(lhs)) {
    if(is_number(rhs)) {
      return number_compare(a, lhs, rhs);
    } else {
      return -1;
    }
  } else if(is_number(rhs)) {
    return 1;
  }
  if(is_variable(lhs) && is_variable(rhs)) {
    return strcmp(unpack_variable(lhs), unpack_variable(rhs));
  }
  int result;
  if(term_compare_0(a, lhs, rhs, &result)) return result;
  if(term_compare_0(a, rhs, lhs, &result)) return -result;
  assert(false);
  return 0;
}