Logo Search packages:      
Sourcecode: mathomatic version File versions

super.c

/*
 * Algebraic manipulator simplifying and polynomial routines.
 * Includes polynomial and smart division,
 * polynomial factoring, etc.
 *
 * Copyright (c) 1996 George Gesslein II.
 */

#include "am.h"
#include "externs.h"

#define     DIVISOR_SIZE      (DEFAULT_N_TOKENS / 2)

/* For smart_div() and poly_div(): */
token_type  divisor[DIVISOR_SIZE];
int         n_divisor;
token_type  quotient[DIVISOR_SIZE];
int         n_quotient;

token_type  gcd_divisor[DIVISOR_SIZE];
int         len_d;

static int  do_gcd();
static int  pf_recurse();
static int  pf_sub();
static int  mod_recurse();
static int  polydiv_recurse();
static int  pdiv_recurse();
static int  poly_div_sub();
static int  sf_recurse();
static int  sf_sub();
static void group_recurse();

static int
vcmp(p1, p2)
sort_type   *p1, *p2;
{
      if (p2->count == p1->count) {
            if (p1->v < p2->v)
                  return -1;
            if (p1->v == p2->v)
                  return 0;
            return 1;
      }
      return(p2->count - p1->count);
}

/*
 * Factor polynomials.
 * Factors repeated factor polynomials (like (x+1)^5)
 * and symbolic factor polynomials (like (x+a)*(x+b)).
 *
 * Return true if equation side was modified.
 */
int
poly_factor(equation, np, symbolic_flag)
token_type  *equation;
int         *np;
int         symbolic_flag;    /* if true, do symbolic factoring, too */
{
      return pf_recurse(equation, np, 0, 1, symbolic_flag);
}

static int
pf_recurse(equation, np, loc, level, symbolic_flag)
token_type  *equation;
int         *np, loc, level;
int         symbolic_flag;
{
      int   modified;
      int   i;
      int   op;
      int   len;

      modified = false;
      op = 0;
      for (i = loc + 1; i < *np && equation[i].level >= level; i += 2) {
            if (equation[i].level == level) {
                  op = equation[i].token.operatr;
            }
      }
      len = i - loc;
      switch (op) {
      case PLUS:
      case MINUS:
            modified = pf_sub(equation, np, loc, len, level, symbolic_flag);
            break;
      }
      if (modified)
            return true;
      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  modified |= pf_recurse(equation, np, i, level + 1, symbolic_flag);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            }
            i++;
      }
      return modified;
}

/*
 * Remove level 1 trivial factors and divides from "tlhs".
 * Return true if result is (or will be after unfactoring)
 * a level 1 plus type expression.
 * If this returns false, nothing is removed.
 */
int
remove_factors(v)
long  v;
{
      int   i, j, k;
      int   plus_flag;
      int   divide_flag;
      int   vfound_flag;
      int   op;

      debug_string(3, "Entering remove_factors() with:");
      side_debug(3, tlhs, n_tlhs);
      do {
            simp_ssub(tlhs, &n_tlhs, 0L, 0.0, false, false, true, 0);
      } while (uf_power(tlhs, &n_tlhs));
#if   false
      if (n_tlhs > 1 && tlhs[0].level == 1 && tlhs[0].kind == CONSTANT
          && (tlhs[1].token.operatr == TIMES || tlhs[1].token.operatr == DIVIDE)) {
            tlhs[0].token.constant = 1.0;
      }
#endif
      plus_flag = false;
      divide_flag = false;
      vfound_flag = false;
      k = 0;
      for (i = 0, j = 0;; i++) {
            if (i >= n_tlhs) {
                  if ((v == 0L || vfound_flag) && plus_flag && !divide_flag) {
                        if (k > 0)
                              j--;
                        blt(&scratch[k], &tlhs[j], (i - j) * sizeof(token_type));
                        k += i - j;
                  }
                  if (k <= 0)
                        return false;
                  blt(tlhs, scratch, k * sizeof(token_type));
                  n_tlhs = k;
                  side_debug(3, tlhs, n_tlhs);
                  return true;
            }
            if (tlhs[i].kind == OPERATOR && tlhs[i].level == 1) {
                  op = tlhs[i].token.operatr;
                  if (op == PLUS || op == MINUS) {
                        plus_flag = true;
                        continue;
                  }
                  if (op != TIMES && op != DIVIDE)
                        return false;
                  if ((v == 0L || vfound_flag) && plus_flag && !divide_flag) {
                        if (k > 0)
                              j--;
                        blt(&scratch[k], &tlhs[j], (i - j) * sizeof(token_type));
                        k += i - j;
                  }
                  vfound_flag = false;
                  plus_flag = false;
                  divide_flag = (op == DIVIDE);
                  j = i + 1;
                  continue;
            }
            if (tlhs[i].kind == OPERATOR && tlhs[i].level == 2) {
                  op = tlhs[i].token.operatr;
                  if (op == PLUS || op == MINUS)
                        plus_flag = true;
            } else if (tlhs[i].kind == VARIABLE && tlhs[i].token.variable == v) {
                  vfound_flag = true;
            }
      }
}

/*
 * Return the number of level 1 additive type operators.
 */
int
level1_plus(p1, n1)
token_type  *p1;
int         n1;
{
      int   i;
      int   count;

      count = 0;
      for (i = 1; i < n1; i += 2) {
            if (p1[i].level == 1) {
                  switch (p1[i].token.operatr) {
                  case PLUS:
                  case MINUS:
                        count++;
                  }
            }
      }
      return count;
}

/*
 * Return the count of variables in an expression.
 */
int
var_count(p1, n1)
token_type  *p1;
int         n1;
{
      int   i;
      int   count;

      count = 0;
      for (i = 0; i < n1; i += 2) {
            if (p1[i].kind == VARIABLE) {
                  count++;
            }
      }
      return count;
}

/*
 * Polynomial factoring subroutine.
 * It can't factor everything,
 * but it usually can factor polynomials
 * if it will make the expression size smaller.
 */
static int
pf_sub(equation, np, loc, len, level, symbolic_flag)
token_type  *equation;
int         *np, loc, len, level;
int         symbolic_flag;
{
      token_type  *p1;
      int         modified, single_modified;
      int         i, j, k;
      long        v, v1, last_v;
      int         len_first;
      int         loc1;
      int         loc2, len2;
      int         loct, lent;
      int         count;
      int         gcd_count;
      jmp_buf           save_save;
      int         div_flag;
      int         vc, cnt;
      sort_type   va[MAX_VARS];
      double            d;
      int         three;

      debug_string(3, "Entering pf_sub().");
      modified = false;
      single_modified = false;
      loc1 = loc;
      len2 = 0;
      v = 0L;
      div_flag = 2;
      find_greatest_power(&equation[loc1], len, &v, &d, &j, &k, &div_flag);
      if (v == 0L)
            return false;
      blt(save_save, jmp_save, sizeof(jmp_save));
      if ((i = setjmp(jmp_save)) != 0) {
            blt(jmp_save, save_save, sizeof(jmp_save));
            debug_string(3, "Exception occurred in pf_sub().");
            if (i == 13) {
                  longjmp(jmp_save, i);
            }
            return(modified || single_modified);
      }
/* First factor polynomials with repeated factors. */
      for (count = 1;; count++) {
            blt(trhs, &equation[loc1], len * sizeof(token_type));
            n_trhs = len;
            uf_simp(trhs, &n_trhs);
            if (level1_plus(trhs, n_trhs) < 2)
                  goto skip_factor;
            vc = 0;
            last_v = 0;
            for (;;) {
                  v1 = -1;
                  for (i = 0; i < n_trhs; i += 2) {
                        if (trhs[i].kind == VARIABLE
                            && trhs[i].token.variable > last_v) {
                              if (v1 == -1 || trhs[i].token.variable < v1) {
                                    v1 = trhs[i].token.variable;
                                    cnt = 1;
                              } else if (trhs[i].token.variable == v1) {
                                    cnt++;
                              }
                        }
                  }
                  if (v1 == -1)
                        break;
                  last_v = v1;
                  if (vc >= ARR_CNT(va)) {
                        break;
                  }
                  va[vc].v = v1;
                  va[vc++].count = cnt;
            }
            side_debug(3, &equation[loc1], len);
            cnt = -1;
            if (v) {
                  if (!poly_in_v(trhs, n_trhs, v, true)) {
                        v = 0L;
                  }
            }
            for (i = 0; i < vc; i++) {
                  if ((va[i].v & VAR_MASK) <= SIGN) {
                        continue;
                  }
                  if (v == 0L) {
                        if (poly_in_v(trhs, n_trhs, va[i].v, true)) {
                              v = va[i].v;
                        }
                  }
                  if (cnt < 0 || va[i].count < cnt) {
                        cnt = va[i].count;
                  }
            }
            if (cnt <= 1 || v == 0L)
                  goto skip_factor;
            blt(tlhs, trhs, n_trhs * sizeof(token_type));
            n_tlhs = n_trhs;
            if (!differentiate(tlhs, &n_tlhs, v)) {
                  break;
            }
#if   !SILENT
            if (debug_level >= 3) {
                  list_var(v, false, false);
                  printf(_("Differentiation successful using variable (%s).\n"), var_str);
            }
#endif
            simp_loop(tlhs, &n_tlhs);
            if ((n_tlhs + 2) > min(DIVISOR_SIZE, n_tokens))
                  break;
            for (i = 0; i < n_tlhs; i++)
                  tlhs[i].level++;
            tlhs[n_tlhs].kind = OPERATOR;
            tlhs[n_tlhs].level = 1;
            tlhs[n_tlhs].token.operatr = TIMES;
            n_tlhs++;
            tlhs[n_tlhs].kind = VARIABLE;
            tlhs[n_tlhs].level = 1;
            tlhs[n_tlhs].token.variable = v;
            n_tlhs++;
            uf_simp(tlhs, &n_tlhs);
            if ((gcd_count = poly_gcd(&equation[loc1], len, tlhs, n_tlhs, v)) == 0)
                  break;
            if (!level1_plus(tlhs, n_tlhs))
                  break;
            save_factors(equation, np, loc1, len, level);
            loc1 += n_tlhs + 1;
            len = n_trhs;
            switch (count) {
            case 1:
#if   !SILENT
                  if (debug_level > 0) {
                        printf(_("Polynomial with repeated factor factored.  Difficulty = %d...\n"), gcd_count);
                  }
#endif
                  len_first = n_tlhs;
                  loc2 = loc1;
                  break;
            case 2:
                  len2 = n_tlhs;
                  break;
            }
            modified = true;
      }
/* Now try and factor polynomials with symbolic factors. */
      if (symbolic_flag && !modified) {
            last_v = 0L;
next_v:
            p1 = &equation[loc];
            blt(trhs, p1, len * sizeof(token_type));
            n_trhs = len;
            uf_simp(trhs, &n_trhs);
            for (;;) {
                  v = -1;
                  for (i = 0; i < len; i += 2) {
                        if (p1[i].kind == VARIABLE
                            && p1[i].token.variable > last_v) {
                              if (v == -1 || p1[i].token.variable < v) {
                                    v = p1[i].token.variable;
                              }
                        }
                  }
                  if (v == -1) {
                        break;
                  }
                  last_v = v;
                  three = 3;
                  if ((count = find_greatest_power(trhs, n_trhs, &v, &d, &j, &k, &three)) > 1) {
                        blt(tlhs, trhs, n_trhs * sizeof(token_type));
                        n_tlhs = n_trhs;
                        factorv(tlhs, &n_tlhs, v);
                        if ((i = find_greatest_power(tlhs, n_tlhs, &v, &d, &j, &k, &three)) != 1) {
                              continue;
                        }
                        blt(tlhs, &tlhs[j], k * sizeof(token_type));
                        n_tlhs = k;
#if   !SILENT
                        if (debug_level >= 3) {
                              printf(_("i = %d, trying factor: "), i);
                              list_proc(tlhs, n_tlhs, false);
                              printf("\n");
                        }
#endif
                        if ((gcd_count = poly_gcd(&equation[loc1], len, tlhs, n_tlhs, 0L)) == 0)
                              goto next_v;
                        if (!level1_plus(tlhs, n_tlhs))
                              goto next_v;
                        save_factors(equation, np, loc1, len, level);
#if   !SILENT
                        if (debug_level > 0) {
                              printf(_("Found polynomial factor.  Difficulty = %d...\n"), gcd_count);
                        }
#endif
                        loc1 += n_tlhs + 1;
                        len = n_trhs;
                        len_first = n_tlhs;
                        loc2 = loc1;
                        single_modified = true;
                        break;
                  }
            }
      }
skip_factor:
      blt(jmp_save, save_save, sizeof(jmp_save));
      if (modified || single_modified) {
            debug_string(3, "Derived factors are:");
            side_debug(3, equation, *np);
      }
      if (modified) {
/* Repeated factor was factored out. */
/* See if we can factor out more of the repeated factor. */
            if (len2) {
                  loct = loc2;
                  lent = len2;
            } else {
                  loct = loc;
                  lent = len_first;
            }
            if (poly_gcd(&equation[loc1], len, &equation[loct], lent, v)) {
                  save_factors(equation, np, loc1, len, level);
                  loc1 += n_tlhs + 1;
                  len = n_trhs;
            }
            if (len2) {
                  loc1 = loc2;
                  len = len2;
            }
            if (poly_gcd(&equation[loc], len_first, &equation[loc1], len, 0L)) {
                  save_factors(equation, np, loc, len_first, level);
            }
      }
      return(modified || single_modified);
}

save_factors(equation, np, loc1, len, level)
token_type  *equation;
int         *np, loc1, len, level;
{
      int   i, j;

      i = n_tlhs + 1 + n_trhs;
      if ((*np + (i - len)) > n_tokens)
            error_huge();
      blt(&equation[loc1+i], &equation[loc1+len], (*np - (loc1 + len)) * sizeof(token_type));
      *np += i - len;
      blt(&equation[loc1], tlhs, n_tlhs * sizeof(token_type));
      i = loc1 + n_tlhs;
      equation[i].level = 0;
      equation[i].kind = OPERATOR;
      equation[i].token.operatr = TIMES;
      i++;
      blt(&equation[i], trhs, n_trhs * sizeof(token_type));
      i += n_trhs;
      for (j = loc1; j < i; j++)
            equation[j].level += level;
}

/*
 * Euclidean GCD algorithm for polynomials.
 * Return number of iterations, if successful.
 * Return 0 on failure.
 */
static int
do_gcd(vp)
long        *vp;
{
      int   i;
      int   count;

      for (count = 1;; count++) {
            if (!poly_div(trhs, n_trhs, gcd_divisor, len_d, vp)) {
                  return 0;
            }
            if (n_trhs == 1 && trhs[0].kind == CONSTANT && trhs[0].token.constant == 0.0) {
                  break;
            }
            if (len_d > n_tokens || n_trhs > DIVISOR_SIZE)
                  return 0;
            blt(scratch, trhs, n_trhs * sizeof(token_type));
            blt(trhs, gcd_divisor, len_d * sizeof(token_type));
            blt(gcd_divisor, scratch, n_trhs * sizeof(token_type));
            i = n_trhs;
            n_trhs = len_d;
            len_d = i;
      }
      return count;
}

/*
 * Compute polynomial Greatest Common Divisor of "larger" and "smaller".
 * Return true if successful.
 * Return the GCD in "trhs".
 * Return "larger"/GCD in "tlhs".
 */
int
poly_gcd(larger, llen, smaller, slen, v)
token_type  *larger;    /* larger polynomial */
token_type  *smaller;   /* smaller polynomial */
int         llen, slen;
long        v;
{
      int         count;

      blt(trhs, larger, llen * sizeof(token_type));
      n_trhs = llen;
      if (slen > min(ARR_CNT(gcd_divisor), n_tokens))
            return 0;
      blt(tlhs, smaller, slen * sizeof(token_type));
      n_tlhs = slen;
      if (!remove_factors(0L))
            return 0;
      if (n_tlhs > ARR_CNT(gcd_divisor))
            return 0;
      blt(gcd_divisor, tlhs, n_tlhs * sizeof(token_type));
      len_d = n_tlhs;
      count = do_gcd(&v);
      if (count == 0)
            return 0;
      if (count > 1) {
            if (len_d > n_tokens)
                  return 0;
            blt(tlhs, gcd_divisor, len_d * sizeof(token_type));
            n_tlhs = len_d;
            if (!remove_factors(0L))
                  return 0;
            if (n_tlhs > ARR_CNT(gcd_divisor))
                  return 0;
            blt(gcd_divisor, tlhs, n_tlhs * sizeof(token_type));
            len_d = n_tlhs;
            if (!poly_div(larger, llen, gcd_divisor, len_d, &v)
                || n_trhs != 1 || trhs[0].kind != CONSTANT || trhs[0].token.constant != 0.0)
                  return 0;
      }
      if (len_d > n_tokens)
            return 0;
      blt(trhs, gcd_divisor, len_d * sizeof(token_type));
      n_trhs = len_d;
      uf_simp(tlhs, &n_tlhs);
      uf_simp(trhs, &n_trhs);
      debug_string(3, "poly_gcd() successful.");
      return(count);
}

/*
 * Compute polynomial Greatest Common Divisor of "larger" and "smaller".
 * Return true if successful.
 * Return "larger"/GCD in "tlhs".
 * Return "smaller"/GCD in "trhs".
 */
int
poly2_gcd(larger, llen, smaller, slen, v)
token_type  *larger;    /* larger polynomial */
token_type  *smaller;   /* smaller polynomial */
int         llen, slen;
long        v;
{
      int         count;

      debug_string(3, "Entering poly2_gcd():");
      side_debug(3, larger, llen);
      side_debug(3, smaller, slen);
      blt(trhs, larger, llen * sizeof(token_type));
      n_trhs = llen;
      if (slen > ARR_CNT(gcd_divisor))
            return 0;
      blt(gcd_divisor, smaller, slen * sizeof(token_type));
      len_d = slen;
      count = do_gcd(&v);
      if (count == 0)
            return 0;
      if (count > 1) {
            if (!poly_div(smaller, slen, gcd_divisor, len_d, &v)
                || n_trhs != 1 || trhs[0].kind != CONSTANT || trhs[0].token.constant != 0.0) {
#if   !SILENT
                  printf(_("WARNING: Polynomial GCD found, but smaller divide failed.\n"));
#endif
                  return 0;
            }
            blt(trhs, gcd_divisor, len_d * sizeof(token_type));
            n_trhs = len_d;
            if (n_tlhs > ARR_CNT(gcd_divisor))
                  return 0;
            blt(gcd_divisor, tlhs, n_tlhs * sizeof(token_type));
            len_d = n_tlhs;
            blt(tlhs, trhs, n_trhs * sizeof(token_type));
            n_tlhs = n_trhs;
            if (!poly_div(larger, llen, tlhs, n_tlhs, &v)
                || n_trhs != 1 || trhs[0].kind != CONSTANT || trhs[0].token.constant != 0.0) {
#if   !SILENT
                  printf(_("WARNING: Polynomial GCD found, but larger divide failed.\n"));
#endif
                  return 0;
            }
            blt(trhs, gcd_divisor, len_d * sizeof(token_type));
            n_trhs = len_d;
      } else {
            n_trhs = 1;
            trhs[0].level = 1;
            trhs[0].kind = CONSTANT;
            trhs[0].token.constant = 1.0;
      }
      uf_simp(tlhs, &n_tlhs);
      uf_simp(trhs, &n_trhs);
      return count;
}

/*
 * Return true if passed expression is entirely integer.
 *
 * Assuming the variables are integer, the result of evaluating
 * the expression must be integer if this returns true.
 */
int
is_integer_expr(equation, n)
token_type  *equation;
int         n;
{
      int   i2;
      double      d;

      for (i2 = 0; i2 < n; i2++) {
            if ((equation[i2].kind == OPERATOR
                && equation[i2].token.operatr == DIVIDE)
                || (equation[i2].kind == CONSTANT
                && fmod(equation[i2].token.constant, 1.0))
                || (equation[i2].kind == VARIABLE
                && var_is_const(equation[i2].token.variable, &d))) {
                  return false;
            }
      }
      return true;
}

/*
 * This routine is a modulus simplifier for equation sides.
 * It does polynomial division, so tlhs and trhs are wiped out.
 *
 * Return true if expression was modified.
 */
int
mod_simp(equation, np)
token_type  *equation;
int         *np;
{
      return mod_recurse(equation, np, 0, 1);
}

static int
mod_recurse(equation, np, loc, level)
token_type  *equation;
int         *np, loc, level;
{
      int   modified;
      int   i, j, k;
      int   i1, i2, i3, i4, i5;
      int   op;
      int   last_op2;
      int   len1, len2, len3;
      long  v;
      int   diff_sign;

      modified = false;
      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  modified |= mod_recurse(equation, np, i, level + 1);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            }
            i++;
      }
      if (modified)     /* make sure the deepest levels are completed, first */
            return true;
      for (i = loc + 1;; i += 2) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level == level) {
                  if (equation[i].token.operatr == MODULUS) {
                        for (k = i + 2;; k += 2) {
                              if (k >= *np || equation[k].level <= level)
                                    break;
                        }
                        len1 = k - (i + 1);
                        last_op2 = 0;
                        for (j = loc;; j++) {
                              if (j >= *np || equation[j].level < level)
                                    break;
                              if (equation[j].level == level && equation[j].kind == OPERATOR) {
                                    last_op2 = equation[j].token.operatr;
                                    continue;
                              }
                              if (last_op2 == MODULUS) {
                                    continue;
                              }
                              last_op2 = MODULUS;
                              op = 0;
                              for (k = j + 1;; k += 2) {
                                    if (k >= *np || equation[k].level <= level)
                                          break;
                                    if (equation[k].level == (level + 1)) {
                                          op = equation[k].token.operatr;
                                          i1 = k;
                                    }
                              }
                              len2 = k - j;
                              switch (op) {
                              case MODULUS:
                                    /* simplify (x%n)%n to x%n */
                                    len3 = k - (i1 + 1);
                                    if (se_compare(&equation[i+1], len1, &equation[i1+1], len3, &diff_sign)) {
                                          blt(&equation[i1], &equation[k], (*np - k) * sizeof(token_type));
                                          *np -= len3 + 1;
                                          return true;
                                    }
                                    break;
                              case TIMES:
                                    if (!is_integer_expr(&equation[j], len2))
                                          break;
                                    /* simplify (i%n*j)%n to (i*j)%n if j is integer */
                                    for (i2 = i1 = j + 1;; i1 += 2) {
                                          if (i1 >= k || equation[i1].level == (level + 1)) {
                                                for (; i2 < i1; i2 += 2) {
                                                      if (equation[i2].level == (level + 2)
                                                          && equation[i2].token.operatr == MODULUS) {
                                                            len3 = i1 - (i2 + 1);
                                                            if (se_compare(&equation[i+1], len1, &equation[i2+1], len3, &diff_sign)) {
                                                                  blt(&equation[i2], &equation[i1], (*np - i1) * sizeof(token_type));
                                                                  *np -= len3 + 1;
                                                                  return true;
                                                            }
                                                      }
                                                }
                                          }
                                          if (i1 >= k)
                                                break;
                                    }
                                    break;
                              case PLUS:
                              case MINUS:
                                    /* simplify (i%n+j)%n to (i+j)%n */
                                    /* and ((i%n)*j+k)%n to (i*j+k)%n, when j is integer */
                                    for (i2 = i1 = j + 1, i3 = j - 1;; i1 += 2) {
                                          if (i1 >= k || equation[i1].level == (level + 1)) {
                                                for (; i2 < i1; i2 += 2) {
                                                      if (equation[i2].level == (level + 2)) {
                                                            switch (equation[i2].token.operatr) {
                                                            case MODULUS:
                                                                  len3 = i1 - (i2 + 1);
                                                                  if (se_compare(&equation[i+1], len1, &equation[i2+1], len3, &diff_sign)) {
                                                                        blt(&equation[i2], &equation[i1], (*np - i1) * sizeof(token_type));
                                                                        *np -= len3 + 1;
                                                                        return true;
                                                                  }
                                                                  break;
                                                            case TIMES:
                                                                  i2 = i1 - 2;
                                                                  if (!is_integer_expr(&equation[i3+1], i1 - (i3 + 1))) {
                                                                        break;
                                                                  }
                                                                  for (i4 = i3 + 2; i4 < i1; i4 += 2) {
                                                                        if (equation[i4].level == (level + 3)
                                                                            && equation[i4].token.operatr == MODULUS) {
                                                                              for (i5 = i4 + 2; i5 < i1 && equation[i5].level > (level + 3); i5 += 2)
                                                                                    ;
                                                                              len3 = i5 - (i4 + 1);
                                                                              if (se_compare(&equation[i+1], len1, &equation[i4+1], len3, &diff_sign)) {
                                                                                    blt(&equation[i4], &equation[i5], (*np - i5) * sizeof(token_type));
                                                                                    *np -= len3 + 1;
                                                                                    return true;
                                                                              }
                                                                        }
                                                                  }
                                                                  break;
                                                            }
                                                      }
                                                }
                                                i3 = i1;
                                          }
                                          if (i1 >= k)
                                                break;
                                    }
                                    break;
                              }
                              /* remove integer*n multiples in x for x%n by doing */
                              /* polynomial division and replacing with remainder%n */
                              v = 0;
                              if (poly_div(&equation[j], len2, &equation[i+1], len1, &v)) {
                                    if (is_integer_expr(tlhs, n_tlhs)) {
#if   !SILENT
                                          for (k = 0; k < n_tlhs; k += 2) {
                                                if (tlhs[k].kind == VARIABLE) {
                                                      printf(_("Modulus simplification made some variables integer only.\n"));
                                                      break;
                                                }
                                          }
#endif
                                          for (k = 0; k < n_trhs; k++)
                                                trhs[k].level += level;
                                          if ((*np + (n_trhs - len2)) > n_tokens)
                                                error_huge();
                                          blt(&equation[j+n_trhs], &equation[j+len2], (*np - (j + len2)) * sizeof(*equation));
                                          *np += n_trhs - len2;
                                          blt(&equation[j], trhs, n_trhs * sizeof(token_type));
                                          return true;
                                    }
                              }
                        }
                  } else
                        break;
            }
      }
      return modified;
}

/*
 * This routine is a division simplifier for equation sides.
 *
 * Return true if a Greatest Common Divisor was found and
 * the expression was simplified by dividing the numerator
 * and denominator by the GCD.
 */
int
polydiv_simp(equation, np)
token_type  *equation;
int         *np;
{
      return polydiv_recurse(equation, np, 0, 1);
}

static int
polydiv_recurse(equation, np, loc, level)
token_type  *equation;
int         *np, loc, level;
{
      int   modified;
      int   i, j, k;
      int   op;
      int   last_op2;
      int   len1, len2;
      int   found_plus;

      modified = false;
      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  modified |= polydiv_recurse(equation, np, i, level + 1);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            }
            i++;
      }
      for (i = loc + 1;; i += 2) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level == level) {
                  if (equation[i].token.operatr == DIVIDE) {
                        op = 0;
                        found_plus = false;
                        for (k = i + 2;; k += 2) {
                              if (k >= *np || equation[k].level <= level)
                                    break;
                              switch (equation[k].token.operatr) {
                              case PLUS:
                              case MINUS:
                                    found_plus = true;
                                    break;
                              }
                              if (equation[k].level == level + 1) {
                                    op = equation[k].token.operatr;
                                    if (op == POWER && equation[k+1].level == (level + 1)
                                        && equation[k+1].kind == CONSTANT
                                        && fmod(equation[k+1].token.constant, 1.0) == 0.0
                                        && found_plus) {
                                          op = PLUS;
                                    }
                              }
                        }
                        if (op != PLUS && op != MINUS)
                              continue;
                        len1 = k - (i + 1);
                        last_op2 = 0;
                        for (j = loc;; j++) {
                              if (j >= *np || equation[j].level < level)
                                    break;
                              if (equation[j].level == level && equation[j].kind == OPERATOR) {
                                    last_op2 = equation[j].token.operatr;
                                    continue;
                              }
                              if (last_op2 == DIVIDE) {
                                    continue;
                              }
                              last_op2 = DIVIDE;
                              op = 0;
                              found_plus = false;
                              for (k = j + 1;; k += 2) {
                                    if (k >= *np || equation[k].level <= level)
                                          break;
                                    switch (equation[k].token.operatr) {
                                    case PLUS:
                                    case MINUS:
                                          found_plus = true;
                                          break;
                                    }
                                    if (equation[k].level == level + 1) {
                                          op = equation[k].token.operatr;
                                          if (op == POWER && equation[k+1].level == (level + 1)
                                              && equation[k+1].kind == CONSTANT
                                              && fmod(equation[k+1].token.constant, 1.0) == 0.0
                                              && found_plus) {
                                                op = PLUS;
                                          }
                                    }
                              }
                              if (op == MINUS)
                                    op = PLUS;
                              if (op != PLUS) {
                                    continue;
                              }
                              len2 = k - j;
                              if (poly2_gcd(&equation[i+1], len1, &equation[j], len2, 0L)) {
store_code:
                                    for (k = 0; k < n_tlhs; k++)
                                          tlhs[k].level += level;
                                    for (k = 0; k < n_trhs; k++)
                                          trhs[k].level += level;
                                    if (((*np + (n_trhs - len2)) > n_tokens)
                                        || ((*np + (n_trhs - len2) + (n_tlhs - len1)) > n_tokens))
                                          error_huge();
                                    blt(&equation[j+n_trhs], &equation[j+len2], (*np - (j + len2)) * sizeof(*equation));
                                    *np += n_trhs - len2;
                                    if (i > j)
                                          i += n_trhs - len2;
                                    blt(&equation[j], trhs, n_trhs * sizeof(token_type));
                                    blt(&equation[i+n_tlhs+1], &equation[i+1+len1], (*np - (i + 1 + len1)) * sizeof(*equation));
                                    *np += n_tlhs - len1;
                                    blt(&equation[i+1], tlhs, n_tlhs * sizeof(*equation));
                                    debug_string(1, "Found polynomial Greatest Common Divisor.");
                                    return true;
                              }
                              if (poly2_gcd(&equation[j], len2, &equation[i+1], len1, 0L)) {
                                    k = j - 1;
                                    j = i + 1;
                                    i = k;
                                    k = len1;
                                    len1 = len2;
                                    len2 = k;
                                    goto store_code;
                              }
                        }
                  } else if (equation[i].token.operatr != TIMES)
                        break;
            }
      }
      return modified;
}

/*
 * This routine is a division simplifier for equation sides.
 * Check for divides and do polynomial and smart division.
 * Return true if expression was simplified.
 */
int
div_remainder(equation, np, poly_flag, quick_flag)
token_type  *equation;
int         *np;
int         poly_flag;
int         quick_flag;
{
      int   rv;

      if (quick_flag)
            group_proc(equation, np);
      rv = pdiv_recurse(equation, np, 0, 1, poly_flag);
      if (quick_flag)
            organize(equation, np);
      return rv;
}

static int
pdiv_recurse(equation, np, loc, level, code)
token_type  *equation;
int         *np, loc, level, code;
{
      int   modified;
      int   i, j, k;
      int   op;
      int   last_op2;
      int   len1, len2;
      int   real_len1;
      long  v;
      int   rv;
      int   flag;
      int   power_flag;
      int   do_again;
      int   rem_zero;

      modified = false;
      for (i = loc + 1;; i += 2) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level == level) {
                  if (equation[i].token.operatr == DIVIDE) {
                        for (k = i + 2;; k += 2) {
                              if (k >= *np || equation[k].level <= level)
                                    break;
                        }
                        real_len1 = k - (i + 1);
                        last_op2 = 0;
                        for (j = loc;; j++) {
                              if (j >= *np || equation[j].level < level)
                                    break;
                              if (equation[j].level == level && equation[j].kind == OPERATOR) {
                                    last_op2 = equation[j].token.operatr;
                                    continue;
                              }
                              if (last_op2 == DIVIDE) {
                                    continue;
                              }
                              last_op2 = DIVIDE;
                              op = 0;
                              for (k = j + 1;; k += 2) {
                                    if (k >= *np || equation[k].level <= level)
                                          break;
                                    if (equation[k].level == level + 1)
                                          op = equation[k].token.operatr;
                              }
                              if (op != PLUS && op != MINUS) {
                                    continue;
                              }
                              len2 = k - j;
                              flag = code;
                              len1 = real_len1;
                              do_again = false;
#if   true
                              if (real_len1 > 2 && equation[i+real_len1-1].kind == OPERATOR
                                  && equation[i+real_len1-1].level == (level + 1)
                                  && equation[i+real_len1-1].token.operatr == POWER
                                  && equation[i+real_len1].level == (level + 1)
                                  && equation[i+real_len1].kind == CONSTANT
                                  && equation[i+real_len1].token.constant > 1.0) {
                                    do_again = true;
                              }
#endif
next_thingy:
                              power_flag = do_again;
                              if (power_flag) {
                                    len1 = real_len1 - 2;
                              } else {
                                    len1 = real_len1;
                              }
                              v = 0;
                              if (flag || power_flag) {
                                    rv = poly_div(&equation[j], len2, &equation[i+1], len1, &v);
                              } else {
                                    rv = smart_div(&equation[j], len2, &equation[i+1], len1);
                              }
                              rem_zero = (rv > 0 && n_trhs == 1 && trhs[0].kind == CONSTANT
                                  && trhs[0].token.constant == 0.0);
                              if (power_flag && !rem_zero) {
                                    rv = 0;
                              }
                              if (rv > 0 && (n_tlhs + 2 + n_trhs + len1) <= n_tokens) {
                                    for (k = 0; k < n_tlhs; k++)
                                          tlhs[k].level++;
                                    tlhs[n_tlhs].level = 1;
                                    tlhs[n_tlhs].kind = OPERATOR;
                                    tlhs[n_tlhs].token.operatr = PLUS;
                                    n_tlhs++;
                                    for (k = 0; k < n_trhs; k++)
                                          trhs[k].level += 2;
                                    blt(&tlhs[n_tlhs], trhs, n_trhs * sizeof(token_type));
                                    n_tlhs += n_trhs;
                                    tlhs[n_tlhs].level = 2;
                                    tlhs[n_tlhs].kind = OPERATOR;
                                    tlhs[n_tlhs].token.operatr = DIVIDE;
                                    n_tlhs++;
                                    k = n_tlhs;
                                    blt(&tlhs[n_tlhs], &equation[i+1], len1 * sizeof(token_type));
                                    n_tlhs += len1;
                                    for (; k < n_tlhs; k++)
                                          tlhs[k].level += 2;
                                    side_debug(3, &equation[j], len2);
                                    side_debug(3, &equation[i+1], len1);
                                    simpb_side(tlhs, &n_tlhs, 3);
                                    side_debug(3, tlhs, n_tlhs);
                                    if (power_flag) {
                                          k = (var_count(tlhs, n_tlhs) <= var_count(&equation[j], len2));
                                    } else {
                                          k = (var_count(tlhs, n_tlhs) <= (var_count(&equation[j], len2) + var_count(&equation[i+1], len1)));
                                    }
                                    if (k) {
                                          if (power_flag) {
                                                if ((*np - len2 + n_tlhs) > n_tokens)
                                                      error_huge();
                                          } else {
                                                if ((*np - (len1 + 1 + len2) + n_tlhs) > n_tokens)
                                                      error_huge();
                                          }
                                          for (k = 0; k < n_tlhs; k++)
                                                tlhs[k].level += level;
                                          if (power_flag) {
                                                equation[i+real_len1].token.constant -= 1.0;
                                          } else {
                                                blt(&equation[i], &equation[i+1+len1], (*np - (i + 1 + len1)) * sizeof(token_type));
                                                *np -= len1 + 1;
                                                if (i < j) {
                                                      j -= len1 + 1;
                                                }
                                          }
                                          blt(&equation[j+n_tlhs], &equation[j+len2], (*np - (j + len2)) * sizeof(token_type));
                                          *np -= len2 - n_tlhs;
                                          blt(&equation[j], tlhs, n_tlhs * sizeof(token_type));
#if   !SILENT
                                          if (flag || power_flag) {
                                                printf(_("Polynomial division successful.\n"));
                                          } else {
                                                printf(_("Smart division successful.\n"));
                                          }
#endif
                                          return true;
                                    }
                              }
                              if (do_again) {
                                    do_again = false;
                                    goto next_thingy;
                              }
                              if (flag == code) {
                                    flag = !flag;
                                    goto next_thingy;
                              }
                        }
                  } else if (equation[i].token.operatr != TIMES)
                        break;
            }
      }
      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  modified |= pdiv_recurse(equation, np, i, level + 1, code);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            }
            i++;
      }
      return modified;
}

/*
 * Do polynomial division.
 * Returns true if successful.
 * Quotient is returned in "tlhs" and remainder in "trhs".
 *
 * If "*vp" is 0, automatically select the best base variable,
 * and return it in "*vp".
 */
int
poly_div(d1, len1, d2, len2, vp)
token_type  *d1;        /* pointer to dividend */
int         len1;       /* length of dividend */
token_type  *d2;        /* pointer to divisor */
int         len2;       /* length of divisor */
long        *vp;        /* variable pointer to base variable */
{
      int         i, j;
      int         old_partial;
      jmp_buf           save_save;

      old_partial = partial_flag;
      partial_flag = false;
      blt(save_save, jmp_save, sizeof(jmp_save));
      if ((i = setjmp(jmp_save)) != 0) {
            blt(jmp_save, save_save, sizeof(jmp_save));
            partial_flag = old_partial;
            if (i == 13) {
                  longjmp(jmp_save, i);
            }
            return false;
      }
      j = poly_div_sub(d1, len1, d2, len2, vp);
      blt(jmp_save, save_save, sizeof(jmp_save));
      partial_flag = old_partial;
      return j;
}

static int
poly_div_sub(d1, len1, d2, len2, vp)
token_type  *d1;
int         len1;
token_type  *d2;
int         len2;
long        *vp;
{
      int         i;
      int         t1, len_t1;
      int         t2, len_t2;
      int         sign;
      int         divide_flag;
      double            last_power;
      double            divisor_power;
      int         sum_size;
      double            d;
      int         last_count, count;

      if (len1 > n_tokens || len2 > n_tokens)
            return false;
      if (trhs != d1) {
            blt(trhs, d1, len1 * sizeof(token_type));
            n_trhs = len1;
      }
      if (tlhs != d2) {
            blt(tlhs, d2, len2 * sizeof(token_type));
            n_tlhs = len2;
      }
      uf_simp(trhs, &n_trhs);
      uf_simp(tlhs, &n_tlhs);
      if (*vp == 0) {
            if (find_highest_count(trhs, n_trhs, tlhs, n_tlhs, vp) <= 0)
                  return false;
      }
#if   !SILENT
      if (debug_level >= 3) {
            list_var(*vp, false, false);
            printf(_("poly_div starts using variable (%s):\n"), var_str);
            side_debug(3, trhs, n_trhs);
            side_debug(3, tlhs, n_tlhs);
      }
#endif
      divide_flag = 2;
      last_count = find_greatest_power(trhs, n_trhs, vp, &last_power, &t1, &len_t1, &divide_flag);
      find_greatest_power(tlhs, n_tlhs, vp, &divisor_power, &t2, &len_t2, &divide_flag);
      if (divisor_power <= 0 || last_power < divisor_power) {
            divide_flag = !divide_flag;
            last_count = find_greatest_power(trhs, n_trhs, vp, &last_power, &t1, &len_t1, &divide_flag);
            find_greatest_power(tlhs, n_tlhs, vp, &divisor_power, &t2, &len_t2, &divide_flag);
            if (divisor_power <= 0 || last_power < divisor_power) {
                  return false;
            }
      }
      n_quotient = 1;
      quotient[0].level = 1;
      quotient[0].kind = CONSTANT;
      quotient[0].token.constant = 0.0;
      if (n_tlhs > ARR_CNT(divisor))
            return false;
      blt(divisor, tlhs, n_tlhs * sizeof(token_type));
      n_divisor = n_tlhs;
      sum_size = n_trhs + n_quotient;
      for (;;) {
            sign = PLUS;
            if (t1 > 0 && trhs[t1-1].token.operatr == MINUS)
                  sign = MINUS;
            if (t2 > 0 && divisor[t2-1].token.operatr == MINUS) {
                  if (sign == MINUS)
                        sign = PLUS;
                  else
                        sign = MINUS;
            }
            if ((len_t1 + len_t2 + 1) > n_tokens)
                  return false;
            blt(tlhs, &trhs[t1], len_t1 * sizeof(token_type));
            n_tlhs = len_t1;
            for (i = 0; i < n_tlhs; i++)
                  tlhs[i].level++;
            tlhs[n_tlhs].level = 1;
            tlhs[n_tlhs].kind = OPERATOR;
            tlhs[n_tlhs].token.operatr = DIVIDE;
            n_tlhs++;
            blt(&tlhs[n_tlhs], &divisor[t2], len_t2 * sizeof(token_type));
            i = n_tlhs;
            n_tlhs += len_t2;
            for (; i < n_tlhs; i++)
                  tlhs[i].level++;
            if (!simp_loop(tlhs, &n_tlhs))
                  return false;
            if ((n_quotient + 1 + n_tlhs) > min(ARR_CNT(quotient), n_tokens))
                  return false;
            for (i = 0; i < n_tlhs; i++)
                  tlhs[i].level++;
            quotient[n_quotient].level = 1;
            quotient[n_quotient].kind = OPERATOR;
            quotient[n_quotient].token.operatr = sign;
            n_quotient++;
            blt(&quotient[n_quotient], tlhs, n_tlhs * sizeof(token_type));
            n_quotient += n_tlhs;
            if ((n_trhs + n_tlhs + n_divisor + 2) > n_tokens)
                  return false;
            blt(&trhs[t1+1], &trhs[t1+len_t1], (n_trhs - (t1 + len_t1)) * sizeof(token_type));
            n_trhs -= len_t1 - 1;
            trhs[t1].level = 1;
            trhs[t1].kind = CONSTANT;
            trhs[t1].token.constant = 0.0;
            for (i = 0; i < n_trhs; i++)
                  trhs[i].level++;
            trhs[n_trhs].level = 1;
            trhs[n_trhs].kind = OPERATOR;
            if (sign == PLUS)
                  trhs[n_trhs].token.operatr = MINUS;
            else
                  trhs[n_trhs].token.operatr = PLUS;
            n_trhs++;
            blt(&trhs[n_trhs], tlhs, n_tlhs * sizeof(token_type));
            i = n_trhs;
            n_trhs += n_tlhs;
            for (; i < n_trhs; i++)
                  trhs[i].level++;
            trhs[n_trhs].level = 2;
            trhs[n_trhs].kind = OPERATOR;
            trhs[n_trhs].token.operatr = TIMES;
            n_trhs++;
            i = n_trhs;
            blt(&trhs[n_trhs], divisor, t2 * sizeof(token_type));
            n_trhs += t2;
            trhs[n_trhs].level = 1;
            trhs[n_trhs].kind = CONSTANT;
            trhs[n_trhs].token.constant = 0.0;
            n_trhs++;
            blt(&trhs[n_trhs], &divisor[t2+len_t2], (n_divisor - (t2 + len_t2)) * sizeof(token_type));
            n_trhs += (n_divisor - (t2 + len_t2));
            for (; i < n_trhs; i++)
                  trhs[i].level += 2;
            side_debug(3, trhs, n_trhs);
/*          uf_repeat(trhs, &n_trhs); */
            uf_tsimp(trhs, &n_trhs);
            side_debug(4, trhs, n_trhs);
            count = find_greatest_power(trhs, n_trhs, vp, &d, &t1, &len_t1, &divide_flag);
            if (d < divisor_power) {
                  blt(tlhs, quotient, n_quotient * sizeof(token_type));
                  n_tlhs = n_quotient;
                  side_debug(3, tlhs, n_tlhs);
                  side_debug(3, trhs, n_trhs);
                  if (n_trhs == 1 && trhs[0].kind == CONSTANT && trhs[0].token.constant == 0.0)
                        return true;
                  if ((n_trhs + n_quotient) >= (sum_size /* - (sum_size / 10) */)) {
                        if ((n_trhs + 1) > sum_size
                            && n_trhs > n_divisor)
                              return -2;
                        else
                              return -1;
                  }
                  return true;
            } else if (d < last_power) {
                  last_power = d;
                  last_count = count;
            } else if (d > last_power) {
                  return false;
            } else {
                  if (count >= last_count) {
                        return false;
                  }
                  last_count = count;
            }
      }
}

#define     MAX_TRIES   100

/*
 * Do smart division.
 *
 * Smart division is heuristic division much like polynomial division,
 * however instead of basing the division on the highest powers,
 * every term in the dividend is tried, and if a trial makes the
 * expression smaller, we go with that.
 *
 * Only one term in the divisor is tried, to save time.
 * Currently, the divisor term used is the one with the least number
 * of variables, not including any terms with no variables.
 *
 * Returns true if successful.
 * Quotient is returned in "tlhs" and remainder in "trhs".
 */
int
smart_div(d1, len1, d2, len2)
token_type  *d1;        /* pointer to dividend */
int         len1;       /* length of dividend */
token_type  *d2;        /* pointer to divisor */
int         len2;       /* length of divisor */
{
      int         i, j, k;
      int         t1, len_t1;
      int         t2, len_t2;
      int         sign;
      int         old_n_quotient;
      int         trhs_size;
      int         term_size, term_count;
      int         term_pos, skip_terms[MAX_TRIES];
      int         skip_count;
      token_type  *qp;
      int         q_size;
      int         sum_size;
      int         count;
      int         dcount;           /* divisor term count */
      int         vflag;

      blt(trhs, d1, len1 * sizeof(token_type));
      n_trhs = len1;
      blt(tlhs, d2, len2 * sizeof(token_type));
      n_tlhs = len2;
      uf_simp_no_repeat(trhs, &n_trhs);
      uf_simp_no_repeat(tlhs, &n_tlhs);
      debug_string(3, "smart_div() starts:");
      side_debug(3, trhs, n_trhs);
      side_debug(3, tlhs, n_tlhs);
      dcount = 0;
      for (i = 0, j = 0, k = 0, len_t2 = 0, vflag = false;; i++) {
            if (i >= n_tlhs || (tlhs[i].kind == OPERATOR && tlhs[i].level == 1
                && (tlhs[i].token.operatr == PLUS || tlhs[i].token.operatr == MINUS))) {
                  dcount++;
                  if (vflag) {
                        if (len_t2 == 0 || var_count(&tlhs[j], i - j) < k) {
                              len_t2 = i - j;
                              t2 = j;
                              k = var_count(&tlhs[t2], len_t2);
                        }
                  }
                  vflag = false;
                  j = i + 1;
            } else if (tlhs[i].kind == VARIABLE
                && (tlhs[i].token.variable & VAR_MASK) > SIGN) {
                  vflag = true;
            }
            if (i >= n_tlhs)
                  break;
      }
      if (len_t2 <= 0)
            return false;
      n_quotient = 1;
      quotient[0].level = 1;
      quotient[0].kind = CONSTANT;
      quotient[0].token.constant = 0.0;
      if (n_tlhs > ARR_CNT(divisor))
            return false;
      blt(divisor, tlhs, n_tlhs * sizeof(token_type));
      n_divisor = n_tlhs;
try_one:
      trhs_size = n_trhs;
      skip_count = 0;
      for (count = 0;;) {
            sum_size = n_trhs + n_quotient;
            for (term_count = 1, q_size = 0;; term_count++) {
                  if (!get_term(trhs, n_trhs, term_count, &t1, &len_t1))
                        break;
                  j = false;
                  for (i = 0; i < skip_count; i++) {
                        if (skip_terms[i] == t1) {
                              j = true;
                              break;
                        }
                  }
                  if (j)
                        continue;
                  if ((len_t1 + len_t2 + 1) > n_tokens)
                        return false;
                  blt(tlhs, &trhs[t1], len_t1 * sizeof(token_type));
                  n_tlhs = len_t1;
                  for (i = 0; i < n_tlhs; i++)
                        tlhs[i].level++;
                  tlhs[n_tlhs].level = 1;
                  tlhs[n_tlhs].kind = OPERATOR;
                  tlhs[n_tlhs].token.operatr = DIVIDE;
                  n_tlhs++;
                  blt(&tlhs[n_tlhs], &divisor[t2], len_t2 * sizeof(token_type));
                  i = n_tlhs;
                  n_tlhs += len_t2;
                  for (; i < n_tlhs; i++)
                        tlhs[i].level++;
                  if (!simp_loop(tlhs, &n_tlhs))
                        continue;
                  if (basic_size(tlhs, n_tlhs) <= basic_size(&trhs[t1], len_t1)) {
                        q_size = n_tlhs;
                        term_pos = t1;
                        term_size = len_t1;
                        break;
                  }
            }
            if (q_size <= 0) {
                  if (count <= 0) {
                        if (dcount > 1) {
                              dcount = 1;
                              t2 = 0;
                              len_t2 = n_divisor;
                              goto try_one;
                        }
                        return false;
                  }
end_div:
                  if (dcount > 1) {
                        i = n_quotient + n_trhs;
                        if (i >= trhs_size + 1) {
                              return false;
                        }
                  }
end_div2:
                  blt(tlhs, quotient, n_quotient * sizeof(token_type));
                  n_tlhs = n_quotient;
                  side_debug(3, tlhs, n_tlhs);
                  side_debug(3, trhs, n_trhs);
                  return true;
            }
            t1 = term_pos;
            len_t1 = term_size;
            sign = PLUS;
            if (t1 > 0 && trhs[t1-1].token.operatr == MINUS)
                  sign = MINUS;
            if (t2 > 0 && divisor[t2-1].token.operatr == MINUS) {
                  if (sign == MINUS)
                        sign = PLUS;
                  else
                        sign = MINUS;
            }
            if ((len_t1 + len_t2 + 1) > n_tokens)
                  return false;
            blt(tlhs, &trhs[t1], len_t1 * sizeof(token_type));
            n_tlhs = len_t1;
            for (i = 0; i < n_tlhs; i++)
                  tlhs[i].level++;
            tlhs[n_tlhs].level = 1;
            tlhs[n_tlhs].kind = OPERATOR;
            tlhs[n_tlhs].token.operatr = DIVIDE;
            n_tlhs++;
            blt(&tlhs[n_tlhs], &divisor[t2], len_t2 * sizeof(token_type));
            i = n_tlhs;
            n_tlhs += len_t2;
            for (; i < n_tlhs; i++)
                  tlhs[i].level++;
            simp_loop(tlhs, &n_tlhs);
            if ((n_quotient + 1 + n_tlhs) > min(ARR_CNT(quotient), n_tokens))
                  return false;
            for (i = 0; i < n_tlhs; i++)
                  tlhs[i].level++;
            old_n_quotient = n_quotient;
            quotient[n_quotient].level = 1;
            quotient[n_quotient].kind = OPERATOR;
            quotient[n_quotient].token.operatr = sign;
            n_quotient++;
            qp = &quotient[n_quotient];
            q_size = n_tlhs;
            blt(&quotient[n_quotient], tlhs, n_tlhs * sizeof(token_type));
            n_quotient += n_tlhs;
            if ((n_trhs + q_size + n_divisor + 2) > n_tokens)
                  return false;
            blt(tlhs, trhs, n_trhs * sizeof(token_type));
            n_tlhs = n_trhs;
            blt(&trhs[t1+1], &trhs[t1+len_t1], (n_trhs - (t1 + len_t1)) * sizeof(token_type));
            n_trhs -= len_t1 - 1;
            trhs[t1].level = 1;
            trhs[t1].kind = CONSTANT;
            trhs[t1].token.constant = 0.0;
            for (i = 0; i < n_trhs; i++)
                  trhs[i].level++;
            trhs[n_trhs].level = 1;
            trhs[n_trhs].kind = OPERATOR;
            if (sign == PLUS)
                  trhs[n_trhs].token.operatr = MINUS;
            else
                  trhs[n_trhs].token.operatr = PLUS;
            n_trhs++;
            blt(&trhs[n_trhs], qp, q_size * sizeof(token_type));
            i = n_trhs;
            n_trhs += q_size;
            for (; i < n_trhs; i++)
                  trhs[i].level++;
            trhs[n_trhs].level = 2;
            trhs[n_trhs].kind = OPERATOR;
            trhs[n_trhs].token.operatr = TIMES;
            n_trhs++;
            i = n_trhs;
            blt(&trhs[n_trhs], divisor, t2 * sizeof(token_type));
            n_trhs += t2;
            trhs[n_trhs].level = 1;
            trhs[n_trhs].kind = CONSTANT;
            trhs[n_trhs].token.constant = 0.0;
            n_trhs++;
            blt(&trhs[n_trhs], &divisor[t2+len_t2], (n_divisor - (t2 + len_t2)) * sizeof(token_type));
            n_trhs += (n_divisor - (t2 + len_t2));
            for (; i < n_trhs; i++)
                  trhs[i].level += 2;
            side_debug(3, trhs, n_trhs);
            uf_tsimp(trhs, &n_trhs);
            side_debug(4, trhs, n_trhs);
            if (n_trhs == 1 && trhs[0].kind == CONSTANT && trhs[0].token.constant == 0.0)
                  goto end_div2;
            if (dcount > 1) {
                  if ((n_trhs + n_quotient) >= sum_size) {
                        if (skip_count >= ARR_CNT(skip_terms)) {
                              if (count == 0) {
                                    return false;
                              } else {
                                    n_quotient = old_n_quotient;
                                    blt(trhs, tlhs, n_tlhs * sizeof(token_type));
                                    n_trhs = n_tlhs;
                                    goto end_div;
                              }
                        }
                        skip_terms[skip_count] = term_pos;
                        skip_count++;
                        n_quotient = old_n_quotient;
                        blt(trhs, tlhs, n_tlhs * sizeof(token_type));
                        n_trhs = n_tlhs;
                        debug_string(3, "Skipping last operation.");
                        continue;
                  }
            }
            if (n_trhs == 1 && trhs[0].kind == CONSTANT)
                  goto end_div;
            skip_count = 0;
            count++;
      }
}

/*
 * Return the size of a subexpression,
 * minus any constant multiplier.
 */
int
basic_size(p1, len)
token_type  *p1;
int         len;
{
      int   i, j;
      int   level;
      int   rv;
      int   constant_flag;

      rv = len;
      constant_flag = true;
      level = min_level(p1, len);
      for (i = 0, j = -1; i < len; i++) {
            if (p1[i].kind == OPERATOR) {
                  if (p1[i].level == level
                      && (p1[i].token.operatr == TIMES || p1[i].token.operatr == DIVIDE)) {
                        if (constant_flag) {
                              rv -= i - j;
                        }
                        j = i;
                        constant_flag = true;
                  }
            } else if (p1[i].kind != CONSTANT)
                  constant_flag = false;
      }
      if (constant_flag) {
            rv -= i - j;
      }
      return rv;
}

int
get_term(p1, n1, count, tp1, lentp1)
token_type  *p1;
int         n1;
int         count;
int         *tp1, *lentp1;
{
      int   i, j;
      int   no;

      for (no = 0, i = 1, j = 0;; i += 2) {
            if (i >= n1 || (p1[i].level == 1
                && (p1[i].token.operatr == PLUS
                || p1[i].token.operatr == MINUS))) {
                  no++;
                  if (no >= count) {
                        *tp1 = j;
                        *lentp1 = i - j;
                        return true;
                  }
                  j = i + 1;
            }
            if (i >= n1)
                  return false;
      }
}

/*
 * This routine automatically finds the best variable to do
 * polynomial division with.
 *
 * Returns 0 if nothing was found, otherwise variable is returned
 * in "*vp1".
 */
int
find_highest_count(p1, n1, p2, n2, vp1)
token_type  *p1;        /* dividend expression */
int         n1;         /* length of dividend */
token_type  *p2;        /* divisor expression */
int         n2;         /* length of divisor */
long        *vp1;       /* variable pointer */
{
      int         i;
      int         vc, cnt;
      long        v1, last_v;
      sort_type   va[MAX_VARS];
      int         divide_flag;
      int         t1, len_t1;
      int         t2, len_t2;
      double            d1, d2;
      int         try_sign;
      int         count1, count2;

      vc = 0;
      last_v = 0;
      for (;;) {
            v1 = -1;
            for (i = 0; i < n1; i += 2) {
                  if (p1[i].kind == VARIABLE
                      && p1[i].token.variable > last_v) {
                        if (v1 == -1 || p1[i].token.variable < v1) {
                              v1 = p1[i].token.variable;
                              cnt = 1;
                        } else if (p1[i].token.variable == v1) {
                              cnt++;
                        }
                  }
            }
            if (v1 == -1)
                  break;
            last_v = v1;
            if (vc >= ARR_CNT(va)) {
                  break;
            }
            va[vc].v = v1;
            va[vc++].count = cnt;
      }
      if (vc <= 0)
            return 0;
      qsort((char *) va, vc, sizeof(*va), vcmp);
      try_sign = false;
do_again:
      for (i = 0; i < vc; i++) {
            if ((va[i].v & VAR_MASK) <= SIGN) {
                  if (!try_sign)
                        continue;
            } else {
                  if (try_sign)
                        continue;
            }
            *vp1 = va[i].v;
            divide_flag = 2;
            count1 = find_greatest_power(p1, n1, vp1, &d1, &t1, &len_t1, &divide_flag);
            count2 = find_greatest_power(p2, n2, vp1, &d2, &t2, &len_t2, &divide_flag);
            if (d2 <= 0 || d1 < d2 || count2 > count1) {
                  divide_flag = !divide_flag;
                  count1 = find_greatest_power(p1, n1, vp1, &d1, &t1, &len_t1, &divide_flag);
                  count2 = find_greatest_power(p2, n2, vp1, &d2, &t2, &len_t2, &divide_flag);
                  if (d2 <= 0 || d1 < d2 || count2 > count1) {
                        continue;
                  }
            }
            return va[i].count;
      }
      if (!try_sign) {
            try_sign = true;
            goto do_again;
      }
      return 0;
}

#define     VALUE_CNT   3

term_value(dp, p1, n1, loc)
double            *dp;
token_type  *p1;
int         n1, loc;
{
      int   i, j, k;
      int   divide_flag;
      int   level, div_level;
      double      d, sub_count, sub_sum;

      for (i = 0; i < VALUE_CNT; i++)
            dp[i] = 0.0;
      divide_flag = false;
      for (i = loc; i < n1; i++) {
            level = p1[i].level;
            if (p1[i].kind == VARIABLE) {
                  if (divide_flag) {
                        dp[0] -= 1.0;
                        dp[1] -= p1[i].token.variable;
                        dp[2] -= p1[i].token.variable;
                  } else {
                        dp[0] += 1.0;
                        dp[1] += p1[i].token.variable;
                        dp[2] += p1[i].token.variable;
                  }
            } else if (p1[i].kind == OPERATOR) {
                  if (level == 1 && (p1[i].token.operatr == PLUS || p1[i].token.operatr == MINUS))
                        break;
                  if (p1[i].token.operatr == DIVIDE) {
                        if (divide_flag && level >= div_level)
                              continue;
                        div_level = level;
                        divide_flag = true;
                  } else if (divide_flag && level <= div_level) {
                        divide_flag = false;
                  }
            }
      }
      divide_flag = false;
      for (j = loc + 1; j < i; j += 2) {
            level = p1[j].level;
            if (p1[j].token.operatr == DIVIDE) {
                  if (divide_flag && level >= div_level)
                        continue;
                  div_level = level;
                  divide_flag = true;
            } else if (divide_flag && level <= div_level) {
                  divide_flag = false;
            }
            if (p1[j].token.operatr == POWER && level == p1[j+1].level
                && p1[j+1].kind == CONSTANT) {
                  d = p1[j+1].token.constant - 1.0;
                  sub_count = 0.0;
                  sub_sum = 0.0;
                  for (k = j - 1; k >= loc && p1[k].level >= level; k--) {
                        if (p1[k].kind == VARIABLE) {
                              sub_count += 1;
                              sub_sum += p1[k].token.variable;
                        }
                  }
                  if (divide_flag) {
                        dp[0] -= d * sub_count;
                        dp[2] -= d * sub_sum;
                  } else {
                        dp[0] += d * sub_count;
                        dp[2] += d * sub_sum;
                  }
            }
      }
}

/*
 * This routine finds the additive term raised the highest power,
 * with ordering and much flexibility.
 *
 * The number of terms raised to the highest power is returned.
 */
int
find_greatest_power(p1, n1, vp1, pp1, tp1, lentp1, dcodep)
token_type  *p1;        /* expression */
int         n1;         /* length of expression */
long        *vp1;       /* variable pointer */
double            *pp1;
int         *tp1, *lentp1;
int         *dcodep;    /* divide flag pointer indicates if term is a denominator */
                        /* for example: for x^5 it is false, for 1/x^5 it is true */
{
      int         i, j, k;
      int         ii;
      int         flag;
      double            d;
      int         divide_flag;
      int         div_level;
      int         level;
      long        v;
      int         was_power;
      double            last_va[VALUE_CNT];
      double            va[VALUE_CNT];
      int         rv;
      int         count;

      *pp1 = 0.0;
      *tp1 = -1;
      v = 0;
      was_power = false;
      rv = *dcodep;
      count = 0;
      if (n1 < 1)
            return count;
      divide_flag = false;
      for (j = 0, i = 1;; i += 2) {
            if (i >= n1 || ((p1[i].token.operatr == PLUS || p1[i].token.operatr == MINUS) && p1[i].level == 1)) {
                  divide_flag = false;
                  if (!was_power && *pp1 <= 1.0) {
                        for (k = j; k < i; k++) {
                              if (p1[k].kind == VARIABLE) {
                                    if (*dcodep <= 1 && *dcodep != divide_flag)
                                          continue;
                                    if (*vp1) {
                                          if (p1[k].token.variable == *vp1) {
                                                term_value(va, p1, n1, j);
                                                flag = (*pp1 == 1.0 && (rv > divide_flag));
                                                if (*pp1 == 1.0 && rv == divide_flag) {
                                                      if (*tp1 != j)
                                                            count++;
                                                      for (ii = 0; ii < ARR_CNT(va); ii++) {
                                                            if (va[ii] == last_va[ii])
                                                                  continue;
                                                            if (va[ii] < last_va[ii])
                                                                  flag = true;
                                                            break;
                                                      }
                                                } else if (*pp1 < 1.0 || flag) {
                                                      count = 1;
                                                }
                                                if (*pp1 < 1.0 || flag) {
                                                      blt(last_va, va, sizeof(last_va));
                                                      *pp1 = 1.0;
                                                      *tp1 = j;
                                                      rv = divide_flag;
                                                }
                                                break;
                                          }
                                    } else {
                                          v = p1[k].token.variable;
                                          *pp1 = 1.0;
                                          *tp1 = j;
                                          rv = divide_flag;
                                          break;
                                    }
                              } else if (p1[k].kind == OPERATOR) {
                                    if (p1[k].token.operatr == DIVIDE) {
                                          if (divide_flag && p1[k].level >= div_level)
                                                continue;
                                          div_level = p1[k].level;
                                          divide_flag = true;
                                    } else if (divide_flag && p1[k].level <= div_level) {
                                          divide_flag = false;
                                    }
                                    if (p1[k].token.operatr == POWER) {
                                          level = p1[k].level;
                                          do {
                                                k += 2;
                                          } while (k < i && p1[k].level > level);
                                          k--;
                                    }
                              }
                        }
                  }
                  if (i >= n1)
                        break;
                  j = i + 1;
                  was_power = false;
                  divide_flag = false;
                  continue;
            }
            level = p1[i].level;
            if (p1[i].token.operatr == DIVIDE) {
                  if (divide_flag && level >= div_level)
                        continue;
                  div_level = level;
                  divide_flag = true;
            } else if (divide_flag && level <= div_level) {
                  divide_flag = false;
            }
            if (p1[i].token.operatr == POWER && p1[i+1].kind == CONSTANT
                && (*vp1 || level == p1[i+1].level)) {
                  if (*dcodep <= 1 && *dcodep != divide_flag)
                        continue;
                  d = p1[i+1].token.constant;
                  for (k = i;;) {
                        if (p1[k-1].kind == VARIABLE) {
                              if (*vp1) {
                                    if (p1[k-1].token.variable == *vp1) {
                                          was_power = true;
                                          term_value(va, p1, n1, j);
                                          flag = (d == *pp1 && (rv > divide_flag));
                                          if (d == *pp1 && rv == divide_flag) {
                                                if (*tp1 != j)
                                                      count++;
                                                for (ii = 0; ii < ARR_CNT(va); ii++) {
                                                      if (va[ii] == last_va[ii])
                                                            continue;
                                                      if (va[ii] < last_va[ii])
                                                            flag = true;
                                                      break;
                                                }
                                          } else if (d > *pp1 || flag) {
                                                count = 1;
                                          }
                                          if (d > *pp1 || flag) {
                                                blt(last_va, va, sizeof(last_va));
                                                *pp1 = d;
                                                *tp1 = j;
                                                rv = divide_flag;
                                          }
                                          break;
                                    }
                              } else {
                                    was_power = true;
                                    if (d > *pp1) {
                                          v = p1[k-1].token.variable;
                                          *pp1 = d;
                                          *tp1 = j;
                                          rv = divide_flag;
                                    }
                                    break;
                              }
                        }
                        k -= 2;
                        if (k <= j)
                              break;
                        if (p1[k].level <= level)
                              break;
                  }
            }
      }
      if (*vp1 == 0)
            *vp1 = v;
      if (*tp1 >= 0) {
            for (i = *tp1 + 1; i < n1; i += 2) {
                  if ((p1[i].token.operatr == PLUS || p1[i].token.operatr == MINUS)
                      && p1[i].level == 1) {
                        break;
                  }
            }
            *lentp1 = i - *tp1;
      }
      if (*dcodep == 2)
            *dcodep = rv;
      return count;
}

/*
 * Combine denominators in equation side.
 * This means converting "a/b+c/d" to "(a*d+c*b)/b/d".
 * Return true if equation side was modified.
 */
int
super_factor(equation, np, start_flag)
token_type  *equation;
int         *np;
int         start_flag;
{
      int   rv;

      group_proc(equation, np);
      rv = sf_recurse(equation, np, 0, 1, start_flag);
      organize(equation, np);
      return rv;
}

static int
sf_recurse(equation, np, loc, level, start_flag)
token_type  *equation;
int         *np, loc, level;
int         start_flag;
{
      int   modified;
      int   i, j, k;
      int   op;
      int   len1, len2;

      if (!start_flag) {
            for (i = loc + 1;; i += 2) {
                  if (i >= *np || equation[i].level < level)
                        break;
                  if (equation[i].level == level
                      && (equation[i].token.operatr == DIVIDE
                      || equation[i].token.operatr == POWER)) {
                        start_flag = true;
                        break;
                  }
            }
      }
      modified = false;
      op = 0;
      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  modified |= sf_recurse(equation, np, i, level + 1, start_flag);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            } else if (equation[i].kind == OPERATOR) {
                  op = equation[i].token.operatr;
            }
            i++;
      }
      if (modified)
            return true;
      switch (op) {
      case PLUS:
      case MINUS:
            break;
      default:
            return modified;
      }
      if (!start_flag)
            return modified;
sf_again:
      i = loc;
      for (k = i + 1;; k += 2) {
            if (k >= *np || equation[k].level <= level)
                  break;
      }
      len1 = k - i;
      for (j = i + len1 + 1;; j += len2 + 1) {
            if (j >= *np || equation[j-1].level < level)
                  break;
            for (k = j + 1;; k += 2) {
                  if (k >= *np || equation[k].level <= level)
                        break;
            }
            len2 = k - j;
            if (sf_sub(equation, np, loc, i, len1, j, len2, level + 1)) {
                  modified = true;
                  goto sf_again;
            }
      }
      return modified;
}

static int
sf_sub(equation, np, loc, i1, n1, i2, n2, level)
token_type  *equation;
int         *np, loc, i1, n1, i2, n2, level;
{
      int   i, j, k;
      int   b1, b2;
      int   len;
      int   e1, e2;
      int   op1, op2;
      int   div_flag1, div_flag2;

      div_flag1 = false;
      div_flag2 = false;
      e1 = i1 + n1;
      e2 = i2 + n2;
      op2 = equation[i2-1].token.operatr;
      if (i1 <= loc) {
            op1 = PLUS;
      } else
            op1 = equation[i1-1].token.operatr;
      for (i = i1 + 1;; i += 2) {
            if (i >= e1)
                  break;
            if (equation[i].level == level && equation[i].token.operatr == DIVIDE) {
                  div_flag1 = true;
                  break;
            }
      }
      b1 = i + 1;
      if (div_flag1) {
            for (i += 2; i < e1; i += 2) {
                  if (equation[i].level == level)
                        break;
            }
      }
      for (j = i2 + 1;; j += 2) {
            if (j >= e2)
                  break;
            if (equation[j].level == level && equation[j].token.operatr == DIVIDE) {
                  div_flag2 = true;
                  break;
            }
      }
      b2 = j + 1;
      if (div_flag2) {
            for (j += 2; j < e2; j += 2) {
                  if (equation[j].level == level)
                        break;
            }
      }
      if (!div_flag1 && !div_flag2)
            return false;
      if (n1 + n2 + (i - b1) + (j - b2) + 8 > n_tokens) {
            error_huge();
      }
      if (!div_flag1) {
            for (k = i1; k < e1; k++)
                  equation[k].level++;
      }
      if (!div_flag2) {
            for (k = i2; k < e2; k++)
                  equation[k].level++;
      }
      len = (b1 - 1) - i1;
      blt(scratch, &equation[i1], len * sizeof(*equation));
      if (op1 == MINUS) {
            scratch[len].level = level;
            scratch[len].kind = OPERATOR;
            scratch[len].token.operatr = TIMES;
            len++;
            scratch[len].level = level;
            scratch[len].kind = CONSTANT;
            scratch[len].token.constant = -1.0;
            len++;
      }
      if (div_flag1) {
            blt(&scratch[len], &equation[i], (e1 - i) * sizeof(*equation));
            len += e1 - i;
      }
      if (div_flag2) {
            scratch[len].level = level;
            scratch[len].kind = OPERATOR;
            scratch[len].token.operatr = TIMES;
            len++;
            blt(&scratch[len], &equation[b2], (j - b2) * sizeof(*equation));
            len += j - b2;
      }
      for (k = 0; k < len; k++)
            scratch[k].level += 2;
      scratch[len].level = level + 1;
      scratch[len].kind = OPERATOR;
      if (op2 == MINUS)
            scratch[len].token.operatr = MINUS;
      else
            scratch[len].token.operatr = PLUS;
      len++;
      k = len;
      blt(&scratch[len], &equation[i2], (b2 - i2 - 1) * sizeof(*equation));
      len += b2 - i2 - 1;
      if (div_flag2) {
            blt(&scratch[len], &equation[j], (e2 - j) * sizeof(*equation));
            len += e2 - j;
      }
      if (div_flag1) {
            scratch[len].level = level;
            scratch[len].kind = OPERATOR;
            scratch[len].token.operatr = TIMES;
            len++;
            blt(&scratch[len], &equation[b1], (i - b1) * sizeof(*equation));
            len += i - b1;
      }
      for (; k < len; k++)
            scratch[k].level += 2;
      scratch[len].level = level;
      scratch[len].kind = OPERATOR;
      scratch[len].token.operatr = DIVIDE;
      len++;
      k = len;
      if (div_flag1) {
            blt(&scratch[len], &equation[b1], (i - b1) * sizeof(*equation));
            len += i - b1;
      }
      if (div_flag1 && div_flag2) {
            scratch[len].level = level;
            scratch[len].kind = OPERATOR;
            scratch[len].token.operatr = TIMES;
            len++;
      }
      if (div_flag2) {
            blt(&scratch[len], &equation[b2], (j - b2) * sizeof(*equation));
            len += j - b2;
      }
      for (; k < len; k++)
            scratch[k].level++;
      if (*np + len - n1 - (n2 + 1) > n_tokens) {
            error_huge();
      }
      if (op1 == MINUS) {
            equation[i1-1].token.operatr = PLUS;
      }
      blt(&equation[i2-1], &equation[e2], (*np - e2) * sizeof(*equation));
      *np -= n2 + 1;
      blt(&equation[i1+len], &equation[e1], (*np - e1) * sizeof(*equation));
      *np += len - n1;
      blt(&equation[i1], scratch, len * sizeof(*equation));
      return true;
}

/*
 * This function is the guts of the "group" command.
 */
group_sub(n)
int   n;
{
      elim_loop(lhs[n], &n_lhs[n]);
      make_fractions(lhs[n], &n_lhs[n]);
      group_proc(lhs[n], &n_lhs[n]);

      elim_loop(rhs[n], &n_rhs[n]);
      make_fractions(rhs[n], &n_rhs[n]);
      group_proc(rhs[n], &n_rhs[n]);
}

/*
 * Group denominators.
 * Grouping here means converting "a/b/c" to "a/(b*c)".
 */
group_proc(equation, np)
token_type  *equation;
int         *np;
{
      group_recurse(equation, np, 0, 1);
}

static void
group_recurse(equation, np, loc, level)
token_type  *equation;
int         *np, loc, level;
{
      int         i;
      int         len;
      int         di, edi;
      int         grouper;
      int         e1;

      for (i = loc;;) {
            if (i >= *np || equation[i].level < level)
                  break;
            if (equation[i].level > level) {
                  group_recurse(equation, np, i, level + 1);
                  i++;
                  for (; i < *np && equation[i].level > level; i += 2)
                        ;
                  continue;
            }
            i++;
      }
      e1 = i;
      di = -1;
      edi = *np;
      grouper = false;
      for (i = loc + 1; i < e1; i += 2) {
            if (equation[i].level == level) {
                  if (equation[i].token.operatr == DIVIDE) {
                        if (di < 0)
                              di = i;
                        else {
                              grouper = true;
                              for (len = i + 2; len < e1; len += 2) {
                                    if (equation[len].level == level
                                        && equation[len].token.operatr != DIVIDE)
                                          break;
                              }
                              len -= i;
                              if (edi == *np) {
                                    i += len;
                                    edi = i;
                                    continue;
                              }
                              blt(scratch, &equation[i], len * sizeof(*equation));
                              blt(&equation[di+len], &equation[di], (i - di) * sizeof(*equation));
                              blt(&equation[di], scratch, len * sizeof(*equation));
                              edi += len;
                              i += len - 2;
                        }
                  } else if (equation[i].token.operatr == TIMES) {
                        if (di >= 0 && edi == *np)
                              edi = i;
                  } else
                        break;
            }
      }
      if (di < 0 || !grouper) {
            return;
      }
      di++;
      for (i = di; i < edi; i++) {
            if (equation[i].level == level && equation[i].kind == OPERATOR)
                  equation[i].token.operatr = TIMES;
            equation[i].level++;
      }
}

Generated by  Doxygen 1.6.0   Back to index