Manual for SAINT

Manual for SAINT

Table of Contents

1 Introduction

SAINT (S ymbolic A utomatic INT egrator) is a program that models how humans solve problems by making educated guesses about which strategies are likely to work.

The program is built to solve calculus problems, but the principles involved are general and don't require mathematical expertise. SAINT has sophisticated techniques for analyzing a problem to see what strategies might work; SAINT can rearrange a problem so as to see it from a different point of view; and SAINT can tentatively try out solutions, switching strategies whenever forward progress seems unlikely.

1.1 How SAINT works

SAINT solves problems using a combination of sure-fire tricks and heuristic guesses.

  • Like most students, SAINT has memorized the answers to a few simple problems. When presented with such a simple, SAINT will provide the solution immediately. (For those who know calculus, these simple problems include integral forms such as \(\int e^x\; dx = e^x\) which calculus students learn by heart.)
  • When the integral is too complicated to solve immediately, SAINT knows some sure-fire tricks that are guaranteed to simplify the problem, or to break it apart into several simpler subproblems. (Specifically, these tricks include breaking apart sums (“the integral of a sum is the sum of the integrals”), changing the variable through linear substitution, and the obscure technique of polynomial division—among others.)
  • When the problem is too complex and none of the sure-fire tricks can be used to simplify the problem, SAINT (like any student) must guess how to proceed. These are educated guesses; SAINT knows a variety of useful techniques that are often helpful — techniques such as using trigonometric identities to replace sine and cosine with tan and sec. And SAINT will first examine the problem carefully to decide which technique to try, so as to avoid doing unnecessary work. Often, SAINT's hunches pay off; SAINT's guesses only rarely lead to dead ends.

SAINT is a program that shows off the power of using trees to represent goals and subgoals, and the power of using pattern-matching both to analyze mathematical expressions, and to match up problems with likely solution strategies.

1.2 Problems to try

Look at the web demo here, or download and open SAINT on your own computer to try it out. SAINT can solve many different kinds of integrals, solving them step-by-step. In addition to Slagle's original thesis, we have written a special solution engine which attempts to describe its problem-solving process in a human-like way. You can try out some of the following problems, for example:

$$\int \frac{z(z+1)(z+2)}{z+4}\; dz$$

"(integral z (/ (* z (+ z 1) (+ z 2)) (+ z 4)))"

$$\int \sin{(4+3y)}\sec{(4+3y)}\;dy$$

"(integral y (* (sin (+ 4 (* 3 y))) (sec (+ 4 (* 3 y)))))"

Notice that you enter the expressions into SAINT using prefix notation, rather than calculator (infix) notation. The first item in parentheses is the integral operator, followed by the variable of integration, followed by the expression to be integrated (the integrand).

1.3 What to build next

There are many more kinds of knowledge and tricks which you could add to SAINT's toolkit. To add another standard form, you can simply add another entry to the list std_rules of known integrals. (For example, you could enable SAINT to integrate inverse trigonometric functions.) To add another surefire trick or heuristic guess method, you can modify the list alg_rules of tentative, goal-altering strategies. (For example, one useful strategy could be integration by parts.)

More generally, SAINT provides the general structure of a problem-solver. By entirely replacing the standard rules and heuristic techniques, you can create a version of SAINT which solves problems in some entirely different domain! (Perhaps SAINT could help pick the next move to make in chess, for example.)

2 Details of SAINT's problem-solving

2.1 Standard formulas can be solved immediately

The simplest kinds of integrals have solutions that can be looked up in a table. For example, the integrals of trigonometric functions, or exponentials, or logarithms all have simple solutions.

A standard solution consists of five parts:

  1. A mathematical formula describing the rule.
  2. A natural language description of how to recognize when the rule applies.
  3. A predicate which determines whether an integrand matches the rule. The predicate is a function of the integrand e and the variable of integration v.
  4. A function which takes in the variable of integration and the integrand and produces the solved integral.
  5. A function which produces a verbose description of how the rule applies, suitable for teaching it to a student.
 std_rules.push(["\\int c dv = c\\cdot v",
                 "Integrand is constant; the variable does not appear.",
                 function(v,e){return constant(v,e);},
                 function(v, e){return product([e, v])},
                 function(v, e) {
                     var s = "We can solve the integral in one step:  \\("+notate(e)+"\\) is a constant";
                     s += "&mdash;<i>"+v+"</i> doesn't appear in it&mdash;";
                     s += "so we can solve the integral immediately using the one-step pattern \\(\\int c dv = c\\cdot v\\).";
                     return s;
                 }
                ]);

 std_rules.push(["\\int e^v dv = e^v",
                "Integrand is the number <i>e</i> raised to the variable ",
                 function(v,e){return is_expt(e) && same_variable("e",e[1]) && same_variable(v, e[2])},
                 function(v, e){return e;},
                 function(v, e) {
                     var s = "We can solve the integral in one step: the one-step rule for the integral of an exponential is \\("+notate(integral(v,e))+" = "+notate(e) + "\\).";
                     return s;
                 }
                ]);

 std_rules.push(["\\int c^v dv = c^v / \\ln{c}",
                "Integrand is any constant raised to the variable",
                 function(v,e){return is_expt(e) && constant(v,e[1]) && same_variable(v, e[2])},
                 function(v, e){return quotient(e,log(e[1]));},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "Since "+notate(e[1])+" is a constant (<i>"+notate(v)+"</i> doesn't appear in it), we can solve the integral immediately using the one-step rule for constant exponentials \\("+notate(integral(v,e))+" = "+notate(quotient(e,log(e[1]))) + "\\).";
                     return s;
                 }
                ]);

 std_rules.push(["\\int \\ln{v}\\, dv = v\\ln{v} - v",
                "Integrand is the natural log of the variable",
                 function(v,e){return is_log(e) && same_variable("e",e[1]) && same_variable(v, e[2])},
                 function(v, e){return sum([product([v, log(v)]),
                                            product([-1, v])]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step, using the rule for natural logs: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate( sum([product([v, log(v)]),
                                            product([-1, v])])) + "\\).";
                     return s;
                 }
                ]);

 std_rules.push(["\\int \\log_c{v}\\; dv = v\\ln{v} - v/\\ln(c)",
                "Integrand is some logarithm of the variable",
                 function(v,e){return is_log(e) && constant(v,e[1]) && same_variable(v, e[2])},
                 function(v, e){return sum([product([v, log(e[1],v)]),
                                            quotient(v, -1, log(e[1]))]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step, using the rule for logarithms: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(sum([product([v, log(e[1],v)]),
                                            quotient(v, -1, log(e[1]))])) + "\\).";
                     return s;
                 }
                ]);

 std_rules.push(["\\int \\sin{v}\\; dv = -\\cos{v}",
                "Integrand is the sine of the variable",
                 function(v,e){return is_sin(e) && same_variable(v,e[1])},
                 function(v, e){return product([-1, cosine(e[1])]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate( product([-1, cosine(e[1])]))+ "\\).";
                     return s;
                 }
                ]);
 std_rules.push(["\\int \\cos{v}\\; dv = \\sin{v}",
                "Integrand is the cosine of the variable",
                 function(v,e){return is_cos(e) && same_variable(v,e[1])},
                 function(v, e){return sine(e[1]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(sine(e[1]))+ "\\).";
                     return s;
                 }
                ]);

std_rules.push(["\\int \\tan{v}\\; dv = \\ln{\\sec{v}}",
                "Integrand is the tangent of the variable",
                 function(v,e){return is_op("tan",e) && same_variable(v,e[1])},
                 function(v, e){return log(["sec",v]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(log(["sec",e[1]]))+ "\\).";
                     return s;
                 }
                ]);

std_rules.push(["\\int \\cot{v}\\; dv = \\ln{\\sin{v}}",
                "Integrand is the cotangent of the variable",
                 function(v,e){return is_op("cot",e) && same_variable(v,e[1])},
                 function(v, e){return log(["sin",v]);},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(log(["sin",e[1]]))+ "\\).";
                     return s;
                 }
                ]);

std_rules.push(["\\int \\sec{v}\\; dv = \\ln{\\sec{v}+\\tan{v}}",
                "Integrand is the secant of the variable",
                 function(v,e){return is_op("sec",e) && same_variable(v,e[1])},
                 function(v, e){return log(sum([["sec",v],["tan",v]]));},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(log(sum([["sec",v],["tan",v]])))+ "\\).";
                     return s;
                 }
                ]);




 std_rules.push(["\\int dv/v = \\ln{v}",
                "Integrand is the reciprocal of the variable",
                function(v,e){return is_quotient(e) && e[1] == 1 && same_variable(v, e[2])},
                function(v, e){return log(v);},
                 function(v, e) {
                     var s = "We can solve the integral in one step: ";
                     s += "\\("+notate(integral(v,e))+" = "+notate(log(v))+ "\\).";
                     return s;
                 }
                ]);

std_rules.push(["\\int v^c dv = v^{c+1} / (c+1)",
                "Integrand is the variable raised to a constant power (&ldquo;the power rule&rdquo;)." ,
                 function(v,e){return same_variable(v,e) || (is_expt(e) && same_variable(v,e[1]) && constant(v, e[2]))},
                function(v, e){
                    if(same_variable(v,e)){return quotient(expt(v,2),2);}
                    return quotient(expt(e[1],sum([e[2],1])),sum([e[2],1]));},

                function(v, e) {
                     var s = "We can solve the integral in one step using the power rule, since the exponent is constant (<i>"+v+"</i> doesn't appear in it)."
                     return s;
                }
               ]);

2.2 Transformation rules modify the problem

There are three surefire transformation rules used by this implementation of SAINT — although you could easily add more. These three rules are:

  1. Extraction of constant factors from integrals.
  2. Splitting apart of sums within integrals
  3. Linear substitution

The components of a transformation rule are similar to the components of a standard formula, with some slight differences.

  1. A mathematical description of the rule.
  2. A natural language description of the rule.
  3. A predicate for determining if the rule applies. The predicate is a function of the integrand and the variable of integration.
  4. A function which transforms the current goal, producing a modified goal.
alg_rules.push(["\\int c\\cdot g(v) dv = c \\int g(v)dv",
                   "Factor out constants" , // Linearity I
                    function(v,e){
                        var q = extract_constants(v,e);
                        return product(q["constants"]) != 1;
                        return count(q["constants"])>0;
                    },
                   function(g) {
                       var v = g.problem[1];
                       var e = g.problem[2];

                       var q = extract_constants(v,e);
                       var subgoal = new Goal("", integral(v, product(q["vars"])));
                       subgoal.aux = product(q["constants"]);
                       subgoal.component = "CONSTANT";
                       g.addChild(subgoal);

                       return g;

                   },
                    function(v, e){
                        var q = extract_constants(v,e);
                        e = integral(v, product(q["vars"]));

                        return product([product(q["constants"]),e]);

                   }]);

    alg_rules.push(["\\int \\sum_i g_i(v) dv = \\sum_i \\int g_i(v)dv",
                    "Split apart sums",//"The integral of a sum is the sum of integrals" ,
                    function(v,e){return is_sum(e);},
                    function(g) {
                        var v = g.problem[1];
                        var e = g.problem[2];
                        var subproblems = map(function(x){return integral(v,x);}, e.slice(1));

                        for(var i=0; i<subproblems.length;i++) {
                            var x = new Goal("", subproblems[i]);
                            x.component = "SUMMAND";
                            g.addChild(x);
                        }
                        return g;

                    }


                   ]);


 alg_rules.push(["\\int f(c_1 + c_2 v) dv = \\int \\frac{1}{c_2} f(u)du",
                    "Linear substitution",//"The integral of a sum is the sum of integrals" ,
                    function(v,e){return ls("u", v, e);},
                    function(g) {
                        var u = "u";
                        var v = g.problem[1];
                        var e = g.problem[2];
                        var q = ls(u, v, e);

                        var subproblem = integral(u, q.form);

                        var x = new Goal("", integral(u, product([quotient(q.coeffs[1]),q.form])));
                        x.component = "USUB";
                        x.aux = q.coeffs;
                        g.addChild(x);
                        return g;

                    }


                   ])

3 Appendix

3.1 Sequence manipulation

function identity(x){return x;}
function is_array(x) {
    return (x instanceof Array);
}

function is_empty(coll) {
    return (coll == null || coll.length == 0);
}

function count(coll) {
    if(coll == null) {
        return 0;
    }
    return coll.length;
}

function rest(coll) {
    if(is_empty(coll)){[]}
    else{return coll.slice(1);}
}

function some(pred, coll) {
    if( is_empty(coll) ) {
        return null;
    }
    else {
        var y = pred(coll[0]);
        return y ? y : some(pred, rest(coll));
    }
}

function every(pred, coll) {
    return !some(function(x){return !pred(x);}, coll);
}

function filter(pred, coll) {
    if(is_empty(coll)) {
        return coll;
    }
    else {
        var y = filter(pred, rest(coll));
        if(pred(coll[0])) {
            y.unshift(coll[0]);
        }
        return y;
    }
}
function remove(pred, coll) {
    if(is_empty(coll)) {
        return coll;
    }
    else {
        var y = remove(pred, rest(coll));
        if(!pred(coll[0])) {
            y.unshift(coll[0]);
        }
        return y;
    }
}

function as_pairs(m) {
    var ret = [];
    var i = 0;
    for(var k in m) {
        ret[i] = [k, m[k]];
        i++;
    }
    return ret;
}
function map(f, coll) {
    var colls = Array.prototype.slice.call(arguments, 1);

    // colls = map(function(x){
    //  if(is_array(x)){return x;}
    //  else {return as_pairs(x);}
    // }, colls);

    var ret = [];
    while(!some(is_empty, colls)) {
        var args = []
        for(var i=0; i<colls.length;i++) {
            args.push(colls[i].shift());
            ret.push(f.apply(null, args));
        }
    }
    return ret;
}

function keys(m) {
    var ret = []
    for(k in m){ret.push(k);}
    return ret;
}
function vals(m) {
    var ret = []
    for(k in m){ret.push(m[k]);}
    return ret;
}
function merge_with(f, m) {
    var ms = Array.prototype.slice.call(arguments, 1);
    while(ms.length > 1) {
        for(var k in ms[1]) {
            if(ms[0][k]){
                ms[1][k] = f(ms[0][k],m[1][k]);
            }
            else {
                ms[1][k] = ms[1][k];
            }
        }
        ms.shift();
    }
    return ms[0];
}


function reduce(f, coll) {
    if(is_empty(coll)){return [];}
    var ret = coll.slice(0);
    while(ret.length > 1) {
        ret[1] = f(ret[0], ret[1]);
        ret.shift();
    }
    return ret;
}

function concat() {
    if(arguments.length == 0){[]}
    var args = Array.prototype.slice.call(arguments, 0);


    while(args.length > 1) {
        if(args[0] == null){args[0] = []}
        if(args[1] == null){args[1] = []}
        while(args[0].length > 0) {
            args[1].unshift(args[0].pop());
        }
        args.shift();
    }
    return args[0];

}

function mapcat(f, coll) {
    return reduce(function(a,b){return concat(a,b);},
                  map(f, coll));
}

function conj(coll, x) {
    // var coll2 = coll.slice(1);
    // coll2.push(x);
    // return coll2;
    if(is_empty(coll)){
        return [x];
    }

    coll.unshift(x);
    return coll;
    return ["x", "y", "z"]
}

function dissoc(m, k) {
     var ks = Array.prototype.slice.call(arguments, 1);
     var ret = $.extend({}, m);
     for(var i=0; i< ks.length;i++) {
        delete ret[ks[i]];
     }
     return ret;
}

3.2 Building symbolic expressions

A symbolic expression is usually a list where the first item is an operator (such as + or × or ∫), and the rest of the items are the argumens of that operator. In other words, these expressions are written in prefix notation.

Numbers are represented using ordinary Javascript numbers. Variables and operators are represented as strings.

function is_number(x) {
    return $.isNumeric(x);
}
function is_int(x) {
    return is_number(x) && (x % 1 == 0);
}

function depth(expr) {
    if(!is_array(expr)) {
        return 0;
    }
    else {
        return 1 + Number(reduce(function(a,b){return a > b ? a : b;}, 
                                 map(depth, expr.slice(0))));
    }
}

function op(symbol, coll) {
    var x = coll.slice(0);
    x.unshift(symbol);
    return x;
}
function is_op (symbol, expr) {
    // determine whether the expression is 
    // an n-ary relation of type symbol.
    return is_array(expr) && expr[0] == symbol;
}

function is_variable(x) {
    return !is_array(x) && !is_number(x);
}
function same_variable(v, w) {
    return is_variable(v) && is_variable(w) && v == w;
}

function terms(x) {
    if(is_sum(x) || is_product(x) || is_expt(x)) {
        return x.slice(1);
    }
    return [x];
}

function has_variable(v, x) {
    if(is_number(x)) {
        return false;
    }
    else if(is_variable(x)) {
        return same_variable(v,x);
    }
    else if(is_array(x)){
        // except for caveat about cancelling
        return some(function(y){return has_variable(v,y);}, x.slice(1));
    }

    return true;
}
function constant(v, c) {
    return !has_variable(v,c);
}

function gather_vars(coll) {
    // create a map from variables to a list of their literal instances in coll
    // also include an "other" category, for nonvariables
    var obj = new Object();
    for(var i=0; i< coll.length; i++) {
        var x = coll[i];
        if(!is_variable(x)) {
            obj["other"] = conj(obj["other"], x);
        }
        else {
            obj[x] = conj(obj[x], x);
        }
    }
    return obj;
}

function is_op(symbol, x) {
    return is_array(x) && x[0] == symbol;
}

function is_integral(x){return is_op("integral",x);}
function is_sum(x) {return is_op("+", x);}
function is_product(x) {return is_op("*", x);}
function is_expt(x){return is_op("expt",x);}
function is_quotient(x) {return is_op("/", x);}
function is_log(x) {return is_op("log", x);}
function is_sin(x) {return is_op("sin", x);}
function is_cos(x) {return is_op("cos", x);}
function is_tan(x) {return is_op("tan", x);}

function simplify(x) {
    if(is_sum(x)) {
        var y = sum(map(simplify, x.slice(1)));
        return y;
    }
    else if(is_product(x)) {
        return product(map(simplify, x.slice(1)));
    }
    else if(is_integral(x)){
        return [x[0], x[1], simplify(x[2])];
    }
    else if(is_log(x)){
        return log(x[1],x[2]);
    }
    else if(is_quotient(x)) {
        return quotient.apply(null,x.slice(1));
    }

    //debug(x[0]);
    return x;
}

Wrapper functions allow you to build expressions without referring to their underlying list-like representation. These builder functions also perform (slight) simplifications, e.g. by eliminaing all ones from products, or by replacing a product containing zero with zero.

function integral(v,e) {
    return ["integral", v, e];
}



function simplify_number(e) {
// if e is a composite of only numbers,
// evaluate it and return the number
// otherwise return nil
    if(is_number(e)) {
        return e;
    }
    else if(is_array(e)) {
        var e2 = e.slice(0);
        for(var i=1; i<e2.length;i++) {
            e2[i] = simplify_number(e2[i]);
            if(e2[i] == null){return null;}
        }
        return simplify(e2);
    }
    return null;
}
var product = function(factors) {
    factors = factors.slice(0);

    if(is_empty(factors)) {
        return 1;
    }
    else if(factors.length == 1) {
        return factors[0];
    }
    else if(some( function(x){return x == 0}, factors)) {
        return 0;
    }
    else if(some( function(x){return x == 1}, factors)) {
        return product(remove(function(x){return x == 1;}, factors));
    }
    else if(false && !some(function(x){return simplify_number(x) == null}, factors)){
        var ns = map(simplify_number, factors.slice(0));
    }
    else if( 
        count(filter(is_number, factors)) > 1 || 
        (count(filter(is_number, factors)) == 1 && !is_number(factors[0]))
    ) {

        var y = remove(is_number, factors);
        var z = reduce(function(a,b){return a*b;},
                       filter(is_number, factors));

        return product(conj(y,z));
    }
    else if(count(filter(function(x){return is_product(x);}, factors)) > 0) {
        // compositions of products are products
        var ps = [];
        for(var i=0; i<factors.length;i++) {
            if(is_product(factors[i])) {
                ps = concat(ps, factors[i].slice(1));
            }
            else {
                ps.push(factors[i]);
            }
        }
        return product(ps);
    }
    else if(count(filter(function(x){return is_quotient(x);}, factors)) > 0) {
        // compositions of products are products
        var ns = [];
        var ds = [];
        for(var i=0; i<factors.length;i++) {
            if(is_quotient(factors[i])) {
                ns.push(factors[i][1]);
                ds.push(factors[i][2]);
            }
            else {
                ns.push(factors[i]);
            }
        }
        //debug(factors.join("++"));
        //debug("qinp-1: "+ns.join(":"));
        //debug("qinp-2: "+ds.join(":"));
        //debug("");
        return quotient(product(ns),product(ds));
    }    
    else {
        var pred = function(x) {
            return is_number(x) || (is_quotient(x) && is_number(x[1]) && is_number(x[2]));
        };
        var p = filter(pred, factors);
        var q = remove(pred, factors);
        if(count(p) > 1) {
            q.unshift(single_fraction(p));
            return product(q);
        }
        else {
        // combine repeated factors into exponents
            var freq = gather_vars(factors);
            if(count(keys(dissoc(freq,"other"))) > 0
               && some(function(x){return x > 1;},
                       map(count, 
                           vals(dissoc(freq,"other"))))
              ){
                var ret = map(function(x){
                    return expt(x[0],count(x[1]));
                }, as_pairs(dissoc(freq,"other")));

                if(!freq["other"]){freq["other"] = [];}

                //return product(ret);
                return product(concat(freq["other"], ret));

            }
        }

        factors.unshift("*");
        return factors;

    } 

}

function single_fraction(factors) {
    // return a single quotient equal to the product of factors.
    var q = map(
        function(x){
            if(is_quotient(x)){
                return x[2];
            }else{
                return x;
            };},
        factors);


    return quotient(1,product(q));
}

var sum = function(sumds) {
    if(is_empty(sumds)) {
        return 0;
    }
    else if(count(sumds) == 1) {
        return sumds[0];
    }
    else if(some( function(x){return x == 0}, sumds)) {

        return sum(remove(function(x){return x == 0;}, sumds));
    }
    else if( 
        // if more than one coefficient, or not all coefficients at the front
        // then consolidate all coefficients at the front
        count(filter(is_number, sumds))>1 || 
            (count(filter(is_number, sumds)) == 1 && !is_number(sumds[0]))
    ) {
        var y = remove(is_number, sumds);
        var z = reduce(function(a,b){return Number(a)+Number(b);},
                       filter(is_number, sumds));

        return sum(conj(y,z));
    }
    else if(count(filter(function(x){return is_sum(x);}, sumds)) > 0) {
        // compositions of sums are sums
        var ps = [];
        for(var i=0; i<sumds.length;i++) {
            if(is_sum(sumds[i])) {
                ps = concat(ps, sumds[i].slice(1));
            }
            else {
                ps.push(sumds[i]);
            }
        }
        return sum(ps);
    }
    else {
        var freq = gather_vars(sumds);

        if(count(keys(dissoc(freq,"other"))) > 0
           && some(function(x){return x > 1;},
                   map(count, 
                       vals(dissoc(freq,"other"))))
          ){
            var ret = map(function(x){
                return product([count(x[1]), x[0]]);
            }, as_pairs(dissoc(freq,"other")));

            return sum(concat(freq["other"], ret));

        }
        sumds.unshift("+");
        return sumds;

    } 
}

function expt(base,exp) {
    if(base == null){
        base = "e";
    }
    if(exp == -1) {
        return quotient(base);
    }
    else if(exp == 1) {
        return base;
    }
    else if(exp == 0) {
        return 1;
    }
    else if(base == 1) {
        return 1;
    }
    else if(base == 0) {
        return 0;
    }
    return ["expt", base, exp];
}
function quotient(num) {
    var denoms = Array.prototype.slice.call(arguments, 1);

    if(denoms.length == 0){return quotient(1,num);}
    else if (num == 0){return 0}
    else if (is_number(num) && every(is_number, denoms) && is_int(num / reduce(function(a,b){return a*b}, denoms))) {
        return num / reduce(function(a,b){return a*b}, denoms);
    }
    else {
        p = product(denoms);
        if( p == 1) {return num;}
        else {
            var ns = is_product(num) ? num.slice(1) : [num];
            var ds = is_product(p) ? p.slice(1) : [p];

            if(is_product(num) || is_product(p)) {
                var cancel = {};

                for(var i=0; i< ns.length;i++) {
                    cancel[ns[i]] |= 0;
                    cancel[ns[i]] ++;
                }
                for(var i=0; i< ds.length;i++) {
                    cancel[ds[i]] |= 0;
                    cancel[ds[i]] --;
                }

                var is_cancelled = some(function(k){return cancel[k]==0;}, keys(cancel));


                if(is_cancelled) {

                    terms = concat(ns, ds);
                    ns = [];
                    ds = [];
                    for(var i=0; i<terms.length;i++) {
                        var k = terms[i];
                        if(cancel[k] > 0) {
                            ns.push(expt(k, cancel[k]));
                        }
                        else if(cancel[k] < 0){
                            ds.push(expt(k, -cancel[k]));
                        }
                        cancel[k] = 0;
                    }

                    return quotient(product(ns),product(ds));
                }

            }

            // remove nested fractions
            var ns = is_product(num) ? num.slice(1) : [num];
            var ds = is_product(p) ? p.slice(1) : [p];

            if(is_quotient(num) || is_quotient(p) 
               || (is_product(num) && some(is_quotient, num)) 
               || (is_product(p) && some(is_quotient, p))
              ) {
                var xs = [];
                var ys = [];

                for(var i=0; i< ns.length; i++) {
                    if(is_quotient(ns[i])) {
                        xs.push(ns[i][1]);
                        ys.push(ns[i][2]);
                    }
                    else {
                        xs.push(ns[i]);
                    }
                }
                for(var i=0; i< ds.length; i++) {
                    if(is_quotient(ds[i])) {
                        xs.push(ds[i][2]);
                        ys.push(ds[i][1]);
                    }
                    else {
                        ys.push(ds[i]);
                    }
                }

                return quotient(product(xs), product(ys));
            }


            return ["/", num, p];
        }
    }
}

function log(base, arg) {
    if(typeof arg === "undefined") {
        return log("e", base);
    }
    if(arg == 1){
        return 0;
    }
    else if (arg == base) {
        return 1;
    }
    else if(is_expt(arg) && arg[1] == base) {
        return arg[2];
    }
    return ["log", base, arg];
}

function sine(x) {return ["sin", x];}
function cosine(x) {return ["cos", x];}
function tangent(x) {return ["tan", x];}

3.3 Polynomial arithmetic

SAINT requires methods for recognizing and manipulating polynomials, especially for performing the heuristic trick of polynomial division. For ease of calculation, polynomials are often converted from the nested symbolic representation (as defined in the previous section) into a coefficient list expression.

For example, the polynomial \(9x^2 + 2x^1 + 8x^0\) would be represented in a nested symbolic expression as

["+", ["*", 9, ["expt", "x",2]], ["*", 2, ["expt", "x", 1]], ["*", 8, ["expt", "x", 0]]]

or more succinctly as a coefficient list:

[8, 2, 9]

In this representation, the coefficients are listed in order from smallest degree to largest degree, and missing terms are filled in with zero coefficients, so that, for example, \(9x^3\) is represented as1

[0, 0, 0, 9]

The following subroutines perform various operations on polynomials represented in this convenient coefficient form. These subroutines convert polynomials between the nested expression representation and the coefficient list representation. They also perform arithmetic operations, such as addition, multiplication, and (using a clever algorithm) polynomial division.

function coeffs_to_poly(v, coeffs) {
    var P = 0;
    for(var i=0; i<coeffs.length;i++) {
        P = sum([P, product([(coeffs[i] ? coeffs[i] : 0),expt(v,i)])]);
    }
    return P;
}
function poly(v, coeffs) {
    var P = 0;
    var co = coeffs.slice(0);
    var c;
    while(c = co.pop()) {
        P = product([P, v]);
        if(c){P = sum([P,c])}
    }
    //P = product([P, v]);
    return P;
    //return sum([coeffs[0], product([coeffs[1], v])]);
}

function poly_add(coeffs1, coeffs2) {
    var coeffs = [];
    for(var i=0; i< coeffs1.length || i<coeffs2.length; i++) {
        coeffs[i] |= 0;
        if(coeffs1[i]){
            coeffs[i] = sum([coeffs[i], coeffs1[i]]);
        }
        if(coeffs2[i]){
            coeffs[i] = sum([coeffs[i], coeffs2[i]]);
        }
    }
    return coeffs;
}

function poly_sub(coeffs1, coeffs2) {
    var coeffs = [];
    for(var i=0; i< coeffs1.length || i<coeffs2.length; i++) {
        coeffs[i] |= 0;
        if(coeffs1[i]){
            coeffs[i] = sum([coeffs[i], coeffs1[i]]);
        }
        if(coeffs2[i]){
            coeffs[i] = sum([coeffs[i],product([-1, coeffs2[i]])]);
        }
    }
    return coeffs;
}


function poly_mult(coeffs1, coeffs2) {
    var coeffs = [];
    for(var i=0; i<coeffs1.length; i++) {
        for(var j=0; j<coeffs2.length; j++) {
            if(coeffs1[i] && coeffs2[j]) {
                coeffs[i+j] |= 0;
                coeffs[i+j] = sum([coeffs[i+j], product([coeffs1[i],coeffs2[j]])]);             
            }
        }
    }
    return coeffs;
}

function deg(coeffs) {
    // return the degree of the polynomial represented by the coeffs
    var i = coeffs.length-1;

    while(i >= 0) {
        if((coeffs[i] | 0) != 0) {
            return i;
        }
        i--;
    }
    return 0;
}



function poly_div(coeffs1, coeffs2) {
    return (function divide(P, Q, R) {
        var m = deg(P);
        var n = deg(Q);
        //debug = function(x){return x;};

        //debug("degrees: "+m+" "+n);
        if(m < n) {
            while(P[P.length-1] == 0){P.pop();}
            return {"quotient" : R,
                    "rem-num" : P,
                    "rem-den" : Q}; 
        }
        else {
            var highest_order = [];
            highest_order[m-n] = quotient(P[m], Q[n]);
            // debug(highest_order[m-n]);
            // debug(poly_mult(Q, highest_order).join("||"));
            // debug(poly_sub(P, poly_mult(Q, highest_order)).join("||"));
            // debug(poly_add(R, highest_order));
            return divide(poly_sub(P, poly_mult(Q, highest_order)),
                          Q,
                          poly_add(R, highest_order));
        }
    })( coeffs1, coeffs2, []);

}

3.4 The user interface

function ui_add_row() {
    return $("<tr/>").appendTo(".columnar").append("<td/>").append("<td/>").append("<td/>");
}
function ui_left(x) {
    var $td = $(".columnar").children().children("tr").last().children("td").slice(0,1);
    if(x){$(x).appendTo($td);}
    return $td;
}
function ui_right(x) {
    var $td = $(".columnar").children().children("tr").last().children("td").slice(1,2);
    return $td;
}

var autoplay = false;
function next_step(f) {
    $ws = ui_right();
    var $o = $("<a/>",{"class":"next-step","href":"#", "html":"Next step &raquo;"});
    $o.appendTo($ws);
    $o.bind("click",function(){$o.mouseover();return false;});

    var g = function(){
        $o.hide("fast");
        f($o);

        $o.unbind("mouseover");
        if(!autoplay){
            $("html, body").animate({ scrollTop: $(document).height()}, 500);
        }
        return false;
    };



    if(autoplay){g();}
    else {
        setTimeout(function(){$o.bind("mouseover", g);}, 400);
    }
    rf();
}

function tabulate_all_subgoals($root, g, complete) {
    var x;

    var prob;
    var soln;

    var $table = $root.addClass("subgoals");
    var $tr = $("<tr/>").prependTo($table);

    if(!g.parent){
        prob = g.problem;
        soln = g.solution;

        $("<td/>").html("Solve").appendTo($tr);
        $tr.append($("<td/>",{"class":"sub"}).html("\\("+notate(prob)+(soln ? "\\,=\\,"+notate(soln) : "")+"\\)"));
        if(complete){$tr.addClass("final")}
    }
    else {

        $("<td/>").html("Solve "+typeset(g.parent.problem)+" by solving "+(g.parent.children.length > 1 ? "these" : "this")+":").appendTo($tr);
        var xs = g.parent.children;
        for(var i=0; i< xs.length;i++) {
            prob = xs[i].problem;
            soln = xs[i].solution;
            $tr.append($("<td/>",{"class":"sub"}).html("\\("+notate(prob)+(soln ? "\\,=\\,"+notate(soln) : "")+"\\)"));
        }
        if(complete) {
            $("<td/>",{"html":"&nbsp;","colspan":10}).appendTo($tr);
            $tr.addClass("final");
            complete = false;
        }
        else {
            $table.find("td.sub").slice(g.index(),1+g.index()).addClass("highlight");
        }
        tabulate_all_subgoals($root, g.parent, false)
    }

    $table = $("<table/>");
    return $table;
}

function tabulate_subgoals($root,g) {
    var x;
    var $table = $("<table/>",{"class":"subgoals"}).appendTo($root);
    var $tr = $("<tr/>").appendTo($table);

    $("<td/>").html("Solve "+typeset(g.problem)+" by solving these:").appendTo($tr);

    for(var i=0; i<g.children.length;i++) {
        x = g.children[i].problem;
        var soln = g.children[i].solution;
        $tr.append($("<td/>",{"class":"sub"}).html("\\("+notate(x)+(soln ? "\\,=\\,"+notate(soln) : "")+"\\)"));
    }
    return $table;
}
function tabulate_array($root, classname, array) {
    // pretty-print a table of options (strategies, etc.)
    var $table = $("<table/>",{"class":"rules "+classname}).appendTo($root);
    var label = {"std-rules" : "K",
                "alg-rules" : "T"};
    for(var i in array) {
        var $tr = $("<tr/>").appendTo($table);
        $("<td/>").html(label[classname]+(1+Number(i))+".").appendTo($tr);
        $("<td/>").appendTo($tr).html('\\('+array[i][0]+'\\)');
        $("<td/>",{"class":"smaller"}).appendTo($tr).html(array[i][1]);
    }
    return $table;
}



function aside(plain, whisper) {
    return $("<div/>",{"html":plain, "class":"aside"}).append($("<span/>",{"html":whisper, "class":"whisper"}));
}

Footnotes:

1

\(9x^3 = 9x^3 + 0x^2 + 0x^1 + 0x^0\).

Author: Dylan Holmes

Created: 2015-06-30 Tue 19:20

Emacs 24.5.1 (Org mode 8.3beta)

Validate