Feeds:
Posts

## Square Root Algorithm

The “Babylonian Algorithm” for approximating square roots is a great example of a recursive function or iterative calculation.  I first encountered this method in an undergraduate Real Analysis I took at University of Maine in 2002.  The basic idea is that we make a guess for the square root of a number (let’s say $\sqrt{60}$).  So we could guess $\sqrt{60} \approx 7.5$.  Then we divide $60 \div 7.5 = 8$ and then average our guess with the result of the division $\frac{7.5+8}{2} =7.75$ and then follow the process all over again $60 \div 7.75 \approx 7.742$ and $\frac{7.75+7.742}{2} \approx 7.746$ and continue this process until the desired accuracy is achieved.  $7.746$ is actually a pretty good result for $\sqrt{60}$.

I programmed this loop onto a TI84 calculator for fun and it works quite well. Pseudocode for this looks like:

Input A

A/2 = B

While abs(A-B^2) > 0.01 do

A/B=C

(B+C)/2=B

else

Display B

Then I wondered if I could do something similar for other roots.  I tried a fifth root program, but changed the “A/B = C” to “A/B^4=C” and tried to run the program, but it ended up in an infinite loop.  Somehow the process was skipping over the fifth root I was looking for.  I started with $\sqrt[5]{32}$ just to keep it simple.  The algorithm started with large values but as it got closer to 2, it failed converge on the desired answer.  Here’s the pseudocode for my first try:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(B+C)/2=B

else

Display B

If you try this algorithm starting with:

32/2.3^4 = 1.1435

(2.3+1.1435)/2 = 1.72175

So far so good, 1.72175 is closer than 1.1435, but when we do 32/1.72175^4 we get 3.6414 which is farther away than 2.3 was.  So I decided to take a weighted average and made the algorithm:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(4*B+C)/5=B

else

Display B

And it worked like a charm!  Then I extended this to other roots as:

Input A

Input R

(A+1)/2 = B

While abs(A-B^R) > 0.01 do

A/B^(R-1)=C

(R-1)*B+C)/R=B

else

Display B

And again – it works great!  I haven’t figured out the problem with the original fifth root algorithm I tried, but I think that the A/B^4 introduces something that throws it off.

## Integration and the AP test

I was perusing some old AP Calculus exams recently and ran across an interesting problem.  The free-response questions are an interesting bunch.  I won’t analyze or critique them too much except to say that they tend to be kind of the same, without much variety.

The question I was really drawn to presents the graph of a derivative function and asks a series of questions about the maximum/minimum values and points of inflection of the underlying function.  It says that if the graph below is $f(x)$ and $g(x)=\int_2^xf(x)\;dx$, then etc, etc.

The graph of the derivative looks like this:

The test questions based on the graph aren’t all that interesting, but I got really interested in wanting to see the original function.  I suppose you can integrate the piecewise derivative graph and use the identified points to build a piecewise function, but I did this geometrically, since these are all triangles.  Really I was just interested in what the original function looked like – which will appear after the jump for those of you who want to think about this for a minute…

## Isosceles Problems

One of my students gave me a problem last fall that was very interesting.

The problem is posed with the following diagram:

What is the measure of $\angle CDA$?  That is, what is the value of $x$?

I’ve given a similar problem in my trigonometry class for the past few years, except that version of the problem has a side length included and the triangle is not isosceles.

A pdf of this problem is linked below:

jun_7_mth_112_river_problem

Working from my experience with the other version of this problem, I began to write in values for the various unlabeled angles in the diagram – if we label the intersection of $\overline{AD}$ and $\overline{BC}$ as $K$, then $\angle CKD$ and $\angle AKB$ are both $70^{\circ}$, $\angle CKA$ and $\angle DKB$ are both $110^{\circ}$, which makes $\angle KCA$ $50^{\circ}$ and $\angle ADB$ is $40^{\circ}$.

I added in new variables and created a system of four equations with four unknowns, but it was a dependent system.

The solution for this problem that was devised by the student who gave it to me is after the jump…

## On the Importance of Algebra

About fifteen years ago, when the WorldWideWeb was still text-based, I came across some of the writings of Professor Richard Mitchell (1929-2002).  Mitchell was a Professor of English and Classics at Glassboro State College in New Jersey, now known as Rowan University.  Although he was a specialist in grammar, literature and the humanities in general, he had a tremendous appreciation for mathematics and a deep and penetrating understanding of what constitutes mathematics and what it’s good for.  These short excerpts below come from his two essays, “The Uses of Audacity” and “Wise Choices in Peoria.”

From “The Uses of Audacity”

Algebra is a world of principle, and a dramatic revelation of the power of principle. In fact, algebra, and even algebra alone, could provide a true and sufficient education out of which to understand the worth of living by principle…

…[Y]ou will have it in your mind that you can know something–truly know it, and not just believe it, or be informed of it–and maybe, since that is so, you can truly know something else. It’s interesting to wonder what such a something else might be.

…You will find that algebra shows you some truths. The first great truth is that there can be something real, and complete, and harmonious, and even, in some strange way, absolutely perfect right in your own mind, and made by you alone. You will see that you have a wonderful freedom not mentioned in the Bill of Rights, the freedom to decide what your mind will contain and how it will work.  You don’t have to copy the rest of the world.

Algebra tells sad truths too. Where there is no balance, there is no truth. What is equal is equal, and between the equal and the unequal there is no conference table, no convenient compromise. In this terrible law there is a hinting question for all of life…

Algebra will show you the inexorable, the endless and permanent chain of consequence, the dark thread of necessity that brought you to a wrong answer because of a tiny little mistake back in the second line. I know how unfair that seems, and how scary that what seems unfair is nevertheless justice. Is life like that too, as all of nature seems to be? How then shall we live? What are the laws of the algebra of our living, and where do they exist, where created? Who can show us how to learn them?

It takes some serious living to see the truth hidden in algebra…

From “Wise Choices in Peoria”

[Some people]…assume that things like geometry and the multiplication table are taught in schools only out of tradition, and they are easily seduced into believing that such arts are useless to those who aren’t going to make some money from them.

But in fact the mathematical arts are the best studies in which to learn certain truths that are essential to the making of wise choices. It is in mathematics that we most readily see that the permanent relationship between principle and necessity is not subject to appeal, that every particular is a local manifestation of some universal, that there is a demonstrable difference between what we believe and what we know, and that experience can never do the work of logic. It is in mathematical studies that a child … can have his first inkling of Justice and Truth…

## Education Reform

The Education Reform movement has been ubiquitous nationwide since at least 2010.  The Common Core standards and the testing that goes along with them is a part of this movement, as are charter schools, vouchers, Teach for America, VAM methods of evaluating teachers, MOOCs and a variety of other disruptive innovations in education.  I just read an article by Jill Lepore in the New Yorker from June 2014.  It was linked from the website of Diane Ravitch who has been blogging about Education Reform for quite some time now.

The paragraphs that are quoted on Diane Ravitch’s web page and which I think really get at the issue are as follows:

…Innovation and disruption are ideas that originated in the arena of business but which have since been applied to arenas whose values and goals are remote from the values and goals of business. People aren’t disk drives. Public schools, colleges and universities, churches, museums, and many hospitals, all of which have been subjected to disruptive innovation, have revenues and expenses and infrastructures, but they aren’t industries in the same way that manufacturers of hard-disk drives or truck engines or drygoods are industries. Journalism isn’t an industry in that sense, either.

Doctors have obligations to their patients, teachers to their students, pastors to their congregations, curators to the public, and journalists to their readers—obligations that lie outside the realm of earnings, and are fundamentally different from the obligations that a business executive has to employees, partners, and investors…

At the University of Amsterdam, staff and faculty have joined the students in protests against recent actions taken by the institution.  Jerome Roos of the European University Institute connects the events in Amsterdam to a world wide crisis in higher education:

Structurally underfunded, severely over-financialized and profoundly undemocratic, universities everywhere are increasingly abandoning their most crucial social functions of yore — to produce high-quality research and educate the next generation of skilled, conscious citizens — and devolving ever more into quasi-private companies run by an utterly detached managerial elite.

To make matters worse, these managers…are actually being paid six-sum figures to push around insane amounts of pointless paperwork, forcing destructive workloads and unrealistic expectations onto increasingly precarious staff, treating students like simple-minded consumers and impersonal statistics, and putting immense pressure on highly talented researchers to spew out mind-numbing amounts of nonsensical garbage just to meet rigid quantitative publication quotas….

The protesters at UvA thus find themselves at the front-line of what is essentially a global fightback against the commodification of higher education and the steady reduction of knowledge and learning to an increasingly unaffordable consumer good. In many countries, this neoliberal logic has resulted in dramatic tuition hikes and budget cuts, combined with the metastization of a culture of top-down managerialism, creeping bureaucratization and the systematic precarization of academic labor — with all the attendant consequences of rising student indebtedness, the proliferation of work floor bullying, and deepening anxiety, depression and burnout among university staff.

## Combinatorics

Yesterday in Pre-Calculus class we were discussing combinatorics and came across a series of questions on how many ways can a best 2 out of 3 sets tennis match be won and how many ways can a best 3 out of 5 tennis match be won.

For a 2 out of 3 scenario there are six possibilities (AA, ABA, BAA, BB, BAB, ABB) and for the 3 out of 5 scenario there are 20 possibilities (AAA, BAAA, ABAA, AABA, BBAAA, BABAA, BAABA, ABBAA, ABABA, AABBA and ten more in which B wins).

The question then came up of how to generalize these results.  The way I approached this was to consider how many ways one of the players could win and then double the answer to include the scenarios in which the other won.

One of the issues in this type of problem is that once the winner has won the required number of games the match ends, so that a best 2 out of 3 match could never end AAB, for instance.  Another issue is that each of the possibilities of winning in a different number of sets should be considered separately.  That is, winning in the minimum number of sets, then winning after having lost one set and so forth.

Taking all of these issues into account for a competition in which the winner must win $\frac{n+1}{2}$ out of $n$ leads to a general formula of $2*\displaystyle \sum_{k=0}^{\frac{n-1}{2}}{_\frac{n+2k-1}{2}}C_{k}$.

Or – if the winner must win $g$ out of $2g-1$ then the formula would be $2*\displaystyle \sum_{k=0}^{g-1}{_{g+k-1}}C_{k}$.

## Reliance on Technology in Mathematics

I read a very interesting article today from the Notices of the American Mathematical Society (AMS) about the intelligent use of technology in mathematics.  This article, titled “The Misfortunes of a Trio of Mathematicians Using Computer Algebra Systems. Can We Trust in Them?” describes the experiences of these three researchers in using the mathematical software packages Mathematica and Maple.  The details of their research are interesting but the important point for students of mathematics is to be aware of the limitations of the technology you use.  A key quote from the article is:

…even more dramatically, his algorithm yielded different outputs given the same inputs.

A more detailed explanation of what was going wrong:

…given the same matrix, the determinant function can give different values!

The authors do give credit to technology as a groundbreaking aid in modern mathematical research, but as is true in other research disciplines, they recommend using multiple sources.  In this case, checking the results of one mathematical software package against another software package to compare the results:

Having made this criticism, let us stress that software systems have proved very useful to research mathematicians.  Some well-known instances are the proof of the four-color problem by Kenneth Appel and Wolfgang Haken and the Kepler conjecture by Thomas Hales….Software bugs should not prevent us from continuing this mutually beneficial relationship in the future.  However, for the time being, when dealing with a problem whose answer cannot be easily verified without a computer, it is highly advisable to perform the computations with at least two computer algebra systems.

And, for students of mathematics, I would add,

– When dealing with a problem whose answer CAN be easily verified without a computer, do so!