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.

## Mathematical Humor

Many years ago I picked up a copy of Martin Gardner’s book A Gardner’s Workout.  In his book, Gardner reviews a collection of writing by the late Ralph Boas, a former professor and department chair at Northwestern University.

In his review of of this collection, Gardner says:

In Princeton’s Fine Hall, Boas recalls, someone once posted a “Scale of Obviousness”:

If Wedderburn says it’s obvious, everybody in the room has seen it ten minutes ago.

If Bohnenblust says it’s obvious, it’s obvious.

If Bochner says it’s obvious, you can figure it out in half an hour.

If von Neumann says it’s obvious, you can prove it in three months if you’re a genius.

If Lefschetz says it’s obvious, it’s wrong.

What I love about this little bit of mathematical humor is that the idea of an “obvious” proposition in mathematics is so inherently subjective.  In fact, in grad school (when I first read this) we had our own joke, which was that if we didn’t know how to justify some part of the proof we were working on, we should just write “clearly.”  Or “the proof is left to the reader.”

On top of the humor is the historical nature of this little joke.  The people mentioned are all well-known mid-century mathematicians from Princeton University faculty.

## Elliptic Curve Cryptography and Finite Fields

Back around 2000, I found a copy of Neal Koblitz’s text A Course in Number Theory and Cryptography at the Borders bookstore in Bangor, Maine.  I only worked my way through the first chapter, but was fascinated with these ideas.  I found Professor Koblitz’s website which, at the time, had a tutorial section on finite fields and elliptic curve cryptography (this may have been on the Certicom website, I can’t remember now).  I moved on to other forms of digital cryptography, like the Diffie-Hellman Key Exchange and RSA Cryptosystem, but always appreciated Prof. Koblitz’s work.  Recently, we dressed up for Halloween as a number and I chose to be the number 4.  As part of my costume, I drew the addition table for the Galois Field of order 4$GF(4)=^{GF(2)[x]}/_{x^2+x+1}$, and did a lot of thinking that week about the element a, which was defined as the root of the equation $0=x^2+x+1$ in $GF(2)$

This past week, I decided to look at the mathematics behind Bitcoin and blockchain, and lo and behold, it is Finite Fields and Elliptic Curve Cryptography – I don’t know why it took me so long to find this out, but now I’m excited about these topics.  I am a little skeptical about the current “Bitcoin bubble.”  I’m not sure that these valuations are sustainable, but from everything I’ve read, the blockchain algorithm behind Bitcoin is revolutionary and the mathematics is “supercool.”

Here’s a graph of the equation $y=x+1$ in $GF(2)$.

## 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…

## Recipe for a Leibniz Quarter Pi

Ingredient: $\frac{1}{1+x^2}$

Divide gently in a long division sauce pan:

$\frac{1}{1+x^2}=1-x^2+x^4-x^6+x^8-x^{10}...$

Integrate briskly over a low flame:

$\int (1-x^2+x^4-x^6+x^8-x^{10}...)dx=$

$=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{11}}{11}+...$

Evaluate for $x=1$ and let stand at room temperature for 1000 terms for accuracy to three decimal places.

$=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\frac{1}{15}...$

But this doesn’t look like a pi! or taste like a pi!

or a quarter pi!

$\int \frac{1}{1+x^2}dx$

and make the trigonometric substitution $x=tan \theta$ so that $dx=sec^2 \theta d \theta$ then:

$\int \frac{1}{1+x^2}dx=\int \frac{1}{1+tan^2 \theta}sec^2 \theta d \theta$

and

$\int \frac{1}{1+tan^2 \theta}sec^2 \theta d \theta=\int \frac{1}{sec^2 \theta}sec^2 \theta d \theta$

$=\int d \theta=\theta$

which, if we return to the original substitution $x=tan \theta$, we see that $\tan^{-1} x=\theta$

So, $\int \frac{1}{1+x^2}dx=\tan^{-1}x$, which means that:

$\tan^{-1}x=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{11}}{11}+...$

and since $\tan^{-1}(1)=\frac{\pi}{4}$, then

$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\frac{1}{15}...$

## The (Google) Map and the Territory

There was an interesting article in the January 31, 2016 New York Times about the proliferation of fake locksmiths on Google.

I was really interested in this because I ran into this problem about four years ago when I locked my keys in my car (while it was running!) in Seaside.  I went into the office of the hotel where I was parked and used their internet connection to search for a locksmith in Seaside.  The one I called immediately started asking for personal information rather than the address where the car was.

I asked them where they were and it turned out they were in Salem.  It wasn’t clear to me how they were going to help me from Salem, so I hung up and found a phone book.  I called a local locksmith in Seaside listed in the (paper) yellow pages.  They showed up in ten minutes and got in my car for \$20.  Problem solved (for me).

This is why I was so interested to see this article in the NY Times about locksmith internet scams.  Apparently, the call centers that come up in a locksmith search farm the jobs out to independent contractors who often bait and switch by charging far more than the original quoted price.  They also are typically short-term temps who don’t care about their reputation.

Some of these scammers go so far as to create fake digital storefronts that show up on Google maps as if they were an actual local business.

The moral of all this is:

“DON’T MISTAKE THE MAP FOR THE TERRITORY.”

In other words don’t think that, because something exists in a mediated form, that it will necessarily exist in the physical world.  This problem has essentially no effect on Google’s revenue, so they have almost no interest in fixing or monitoring the problem.  The internet is a wonderful tool, but be aware of the REAL physical local businesses in your area and support them in the real world.