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.

## 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)$.

## 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 Many Solutions of the Population Equation

I never studied the logistic equation as a student.  I first encountered this relationship as an instructor in one of the College Algebra textbooks I was reviewing and/or teaching from and was intrigued by the application of this “growth with constraints” model to a natural resource.  In researching applying the logistic model to natural resource consumption, I immediately ran into M. King Hubbard’s work on Peak Oil.

Then, when I was teaching integral calculus last winter, we began a unit on separable differential equations.  I was poking around looking for good application problems that would utilize separable ODEs and ran into the fundamental population differential relationship $\frac{dP}{dt}=kP$, followed by the relationship I had used for the logistic $\frac{dP}{dt}=kP(1-\frac{P}{N})$ with $N$ defined as the “carrying capacity” or maximum growth for the population.

We went through the procedures for solving each of these ODEs (as well as the continuous mixing problems which follow a similar pattern) and then we moved on.

This year when I was teaching this topic again I was reminded of a paper my thesis advisor had given to me back in 2003 about the application of differential equations to modeling fish populations.  I was intrigued by the profusion of models that could be generated by changing the constraints for a given relationship.

Since I didn’t teach integral calculus for another 10 years after I read that paper, I had essentially forgotten most of the equations, formulas and relationships that generated the graphs that had stuck with me.  This year, while covering the separable ODEs with their applications, I began to look into the application of these relationships to fish populations and population in general.

I found two great resources that go through the set up of these relationships in a very clear manner, and each of them includes wonderful graphs showing the multiple solutions that result when the same differential relationship is solved with different initial conditions.

The opening section of Robert Borelli and Courtney Coleman’s Differential Equations: A Modeling Approach can be read here.

A student project from James Madison University written by Bailey Steinworth, Yuhui Wang and Xing Zhang can be read here.

## 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}$.

## Derivation of the Cross Product

A few weeks ago, my colleague who teaches Physics asked me about the derivation and justification of the cross-product formula.

The cross product for two vectors will find a third vector that is perpendicular to the original two vectors given.

The given vectors are assumed to be perpendicular (orthogonal) to the vector that will result from the cross product.  This means that the dot product of each of the original vectors with the new vector will be zero.

So, given two vectors $a=\begin{bmatrix} a_1\\ a_2\\ a_3 \end{bmatrix}$

and $b=\begin{bmatrix} b_1\\ b_2\\ b_3 \end{bmatrix}$

we want to find a third vector $n=\begin{bmatrix} n_1\\ n_2\\ n_3 \end{bmatrix}$

so that $n$ is perpendicular to both $a$ and $b$

As I mentioned above this means that we want the dot product of $n$ with each of the two original vectors to be zero.

$a \cdot n=a_1n_1+a_2n_2+a_3n_3=0$

and

$b \cdot n=b_1n_1+b_2n_2+b_3n_3=0$

This gives us two equations to work with.  Since we have three variables to solve for $(n_1, n_2, n_3)$, we’ll need another equation to work with.

The website Heaven’s in the backyard introduces a third constraint that the modulus of the cross product vector $n$ be equal to 1.

This creates a third equation $n_1^2+n_2^2+n_3^2=1$ and allows us to solve for $n_1, n_2,$ and $n_3$ in terms of $a_1, a_2, a_3, b_1, b_2$ and $b_3$

As mentioned above the web page Heaven’s in the backyard does a nice job with the derivation of the values for $n_1, n_2,$ and $n_3$ and ends up with the formula $n=\begin{bmatrix} a_2b_3-a_3b_2\\ a_3b_1-a_1b_3\\ a_1b_2-a_2b_1 \end{bmatrix}$.

I don’t see this mentioned in the derivation, but it appears that the $\sqrt{Z}$ term that is factored out and defined to make the derivation work more smoothly is actually the modulus of the cross product vector $n$.

Assuming that the cross product vector has a length of $1$ results in an answer that is multiplied by $\frac{1}{\sqrt{Z}}$, because the actual perpendicular $(n)$ has a modulus equal to $\sqrt{(a_2b_3-a_3b_2)^2+(a_3b_1-a_1b_3)^2+(a_1b_2-a_2b_1)^2}$ which is $\sqrt{Z}$.

After working through some of these ideas, I became interested in where the cross-product came from.

At Wikipedia, they mention that Joseph-Louis Lagrange, the French/Italian mathematician of the late 18th century provided a formula for this in a paper from 1773 that was focused on the properties of a tetrahedron.  The calculations related to the cross-product appear in the first few pages of the paper.  Lagrange posits 9 “quantités” $x, y, z, x', y', z', x'', y'', z''$ and then proceeds through a blizzard of calculations based on these quantities.

If each triplet of values $q=(x, y, z)$, $r=(x', y', z')$ and $s=(x'', y'', z'')$ is considered as the coordinates of a vector, then the first calculations are the cross-products of each vector with each of the others.  In Lagrange’s notation, we could identify each of the cross products as

$r \times s=\begin{bmatrix} \xi\\ \eta\\ \zeta \end{bmatrix}$, $q \times s=\begin{bmatrix} \xi'\\ \eta'\\ \zeta' \end{bmatrix}$, $q \times r=\begin{bmatrix} \xi''\\ \eta''\\ \zeta'' \end{bmatrix}$

On the following page Lagrange identifies the square of the modulus for each of the cross-product vectors as $\alpha$, $\alpha'$ and $\alpha''$

Several pages later Lagrange notes that the dot product of each original vector with the appropriate cross-product produces a zero result.

There are two things that fascinate me about this – (1) the depth of this seemingly simple question – how do you justify the cross-product formula? and (2) what was Lagrange up to in this paper? – what is the purpose of the multitude of calculations that he completes in the paper from 1773 (Solutions analytiques de quelques problèmes sur les pyramides triangulaires)?

## Income Inequality

Back in May of 2013, I did a presentation on income inequality that focused on how the Gini index is calculated.

Recently, I came across a graph that shows how the income growth during economic expansions has been distributed over the last 60 years.

It’s seems clear to me that the change in income tax rates during the Reagan years had a radical effect on income distribution in the US.

In his latest blog post, Robert Reich has a good analysis of some of the other issues that have led to the level of inequality we experience today.