Tuesday

July 7, 2015

July 7, 2015

Posted by **Julissa** on Sunday, December 7, 2008 at 6:29pm.

- Math 117 -
**Count Iblis**, Sunday, December 7, 2008 at 8:52pmLong division for numbers and polynomials are basically the same thing. I think that long division should not be taught in primary school as almost no students in primary school understand why it works.

Long division is only practical if you have paper and pencil. So, you wouldn't want do it if you are in a shop and need to do a quick approximate division in your head to compare prices.

I think that in today's world long division is only a practical technique for algebra and calculus problems involving polynomials or series expansions. And then only if you have to compute a few terms.

If you have to divide two numbers, then you can just use a calculator or a computer. If you happen to be somewhere where you don't have access to a calculator or computer, you usually do not have access a desk with paper and pencil on which you can do long division either.

So, this is why I really do not understand why long division is taught in primary school at all.

The long division process gives you decimal by decimal but that comes at the expense of the computational efficiency. In case of polynomials you get the correct coefficients one by one.

A more practical division algorithm uses the Newton's method. This works as follows. Suppose we want to compute

x = 1/q. Then x satisfies the equation:

1/x - q = 0

You can solve this equation by iteration using Newton's method, se here:

http://en.wikipedia.org/wiki/Newton's_method

So, we take

f(x) = 1/x - q

and then nth approximation of the zero is found by iteration:

x_{n+1} = x_{n} - f(x_n)/f'(x_n) =

x_{n} - (1/x_n - q)/(-1/(x_n)^2) =

2x_n -q x_n^2

The advantage of this algorithm is that, unlike in case of long division, the interation step here does not involve any (trial) divisions. Also, in each step the number of significant digits doubles, while in case of long division you only get one significant digit per step.

So, to compute a million digits only requires about twenty steps of the algorithm, if your first guess is accurate to one significant digit. In case of long division, you need to go through a million separate steps.

The algorithm also works in case of polynomials. If p(x) = 1/(q(x)), then the algorithm yields approximations

p_n(x):

P_{n+1}(x) = 2 P_{n}(x) - Q(x)(P_n(x))^2

The number of correct coefficients in the polynomial doubles in each interation. E.g., we can compute 1/(1-x) by putting Q(x) = 1-x. We take the first approximation to be P_0(x) = 1

We then get:

P_1(x) = 2 P_0(x)-(1-x) (P_0(x))^2=

2 - (1-x) = 1+x

P_2(x) = 2 P_1(x) - (1-x)(P_1(x))^2 =

2+2x - (1-x)(1+x)^2 =

2 + 2 x - (1-x^2)(1+x) =

2 + 2 x - 1 - x + x^2 + x^3 =

1 + x + x^2 + x^3

Efficient division algorithms such as this form the basis of computer algebra programs. They are used to compute seris expansions of functions. To see what use a division algorithm is, consider computing the series expansion of g(x) = Log(f(x)), where f(x) is a given function whose series expansion is known (e.g. f(x) could be cos(x)). The the derivative of g(x) is given by:

g'(x) = f'(x)/f(x)

So, you just need to compute 1/(f(x)) using the above division algorithm and then multiply that by f'(x). You then integrate the expansion term by term.

To compute g(x) = exp(f(x)), you simply solve the equation:

f(x) = Log(g(x))

by starting with a trial g(x) and using Newton's method again. Each step in that iteration then involves the above method of cmputing the logarithm which involves the division algorithm.

Like in case of the division algorithm, Newton's method to get an improved estimate x for the equation

y = Log(x) also does not involve any divisions:

x_(n+1) = x_n - x_n[Log(x_n) - y] =

(1+y)x_n - x_n Log(x_n)

So, both the logarithm and the exponential function can be computed very efficiently. And that's all you need in practice, because a large class of functions can be expressed using compositions of the logarithm and the exponential function only.

Computer algebra systems can the give you the billionth term of a series expansion of some complicated function in just a few dozen steps. Taylor's folmula for the term would involve the billkionth derivative. So, this means that you can use it to effienctly compute derivatives of functions. This is indeed how computer algebra systems compute high order derivatives of functions.

- Math 117 -
**Mrs. C.**, Friday, July 2, 2010 at 12:18amI don't think that it is about the math that is the reason children are taught math. I believe that it has to do with the part of the brain that working mathematical concepts come from. I also believe that it has something to do with "solving" which I believe also comes from the same part of the brain.