Deciphering recommendation engines

From the video’s description: “Data scientist Cathy O’Neil provides a glimpse of the methods that Netflix, Google, and others apply to recommend or offer to users selections based on their apparent interests.” This is a non-intuitive but real application of linear algebra.

Preparation for Industrial Careers in the Mathematical Sciences: Finding the Safest Place to Store Nuclear Waste

The Mathematical Association of America recently published a number of promotional videos showing various mathematics can be used in “the real world.” Here’s the first pair of videos describing the process of mathematical modeling. From the YouTube descriptions:

Dr. Genetha Gray talks about her path and about a research problem that she worked on at Sandia National Laboratories. Using quite limited geological data, they had to create a groundwater flow computational model, with parameters to be determined, so that they could study the feasibility and safety of prospective subsurface nuclear waste storage sites.

Prof. Gwen Spencer of Smith College introduces the mathematics behind optimization, calibration, and the quantification of uncertainty in models and in the results that they give.

Arithmetic with big numbers: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on doing basic arithmetic with very large numbers that exceed the character displays of most calculators.

Part 1: Addition

Part 2: Multiplication

Part 3: Division

A clean computer programming joke

A programmer calls home. His wife says, “While you’re out, get some milk.” He never returns home.

Calculator Errors: When Close Isn’t Close Enough (Index)

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on how I remind students about Taylor series. I often use this series in a class like Differential Equations, when Taylor series are needed but my class has simply forgotten about what a Taylor series is and why it’s important.

Part 1: Propagation of small numerical errors.

Part 2: A tragedy during the 1991 Gulf War that was a direct result of calculator rounding.

Square roots and Logarithms Without a Calculator: Index

Part 1: Method #1: Trial and error.

Part 2: Method #2: An algorithm comparable to long division.

Part 3: Method #3: Introduction to logarithmic tables. At the time of this writing, this is the most viewed page on my blog.

Part 4: Finding antilogarithms with a table.

Part 5: Pedagogical and historical thoughts on log tables.

Part 6: Computation of square roots using a log table.

Part 7: Method #4: Slide rules

Part 8: Method #5: By hand, using a couple of known logarithms base 10, the change of base formula, and the Taylor approximation $ln(1+x) \approx x$ .

Part 9: An in-class activity for getting students comfortable with logarithms when seen for the first time.

Part 10: Method #6: Mentally… anecdotes from Nobel Prize-winning physicist Richard P. Feynman and me.

Part 11: Method #7: Newton’s Method.

Arithmetic with big numbers (Part 3)

In the previous two posts, we considered the use of base- $10^n$ arithmetic so that a calculator can solve addition and multiplication problems that it ordinarily could not handle. Today, we turn to division. Let’s now consider the decimal representation of $\displaystyle \frac{8}{17}$ .

There’s no obvious repeating pattern. But we know that, since 17 has neither 2 nor 5 as a factor, that there has to be a repeating decimal pattern.

So… what is it?

When I ask this question to my students, I can see their stomachs churning a slow dance of death. They figure that the calculator didn’t give the answer, and so they have to settle for long division by hand.

That’s partially correct.

However, using the ideas presented below, we can perform the long division extracting multiple digits at once. Through clever use of the calculator, we can quickly obtain the full decimal representation even though the calculator can only give ten digits at a time.

Let’s now return to where this series began… the decimal representation of $\displaystyle \frac{1}{7}$ using long division. As shown below, the repeating block has length $6$ , which can be found in a few minutes with enough patience. By the end of this post, we’ll consider a modification of ordinary long division that facilitates the computation of really long repeating blocks.

Because we arrived at a repeated remainder, we know that we have found the repeating block. So we can conclude that $\displaystyle \frac{1}{7} = 0.\overline{142857}$ .

Students are taught long division in elementary school and are so familiar with the procedure that not much thought is given to the logic behind the procedure. The underlying theorem behind long division is typically called the division algorithm. From Wikipedia:

Given two integers $a$ and $b$ , with $b \ne 0$ , there exist unique integers $q$ and $r$ such that $a = bq+r$ and $0 \le r < |b|$, where $|b|$ denotes the absolute value of $b$ .

The number $q$ is typically called the quotient, while the number $r$ is called the remainder.

Repeated application of this theorem is the basis for long division. For the example above:

Step 1.

$10 = 1 \times 7 + 3$ . Dividing by $10$ , $1 = 0.1 \times 7 + 0.3$

Step 2.

$30 = 4 \times 7 + 2$ . Dividing by $100$ , $0.3 = 0.04 \times 7 + 0.02$

Returning to the end of Step 1, we see that

$1 = 0.1 \times 7 + 0.3 = 0.1 \times 7 + 0.04 \times 7 + 0.02 = 0.14 \times 7 + 0.02$

Step 3.

$20 = 2 \times 7 + 6$ . Dividing by $1000$ , $0.02 = 0.002 \times 7 + 0.006$

Returning to the end of Step 2, we see that

$1 = 0.14 \times 7 + 0.02 = 0.14 \times 7 + 0.0002 \times 7 + 0.006 = 0.142 \times 7 + 0.006$

And so on.

By adding an extra zero and using the division algorithm, the digits in the decimal representation are found one at a time. That said, it is possible (with a calculator) to find multiple digits in a single step by adding extra zeroes. For example:

Alternate Step 1.

$1000 = 142 \times 7 + 6$ . Dividing by $1000$ , $1 = 0.142 \times 7 + 0.006$

Alternate Step 2.

$6000 = 587 \times 7 + 1$ . Dividing by $100000$ , $0.006 = 0.000587 \times 7 + 0.000001$

Returning to the end of Alternate Step 1, we see that

$1 = 0.142 \times 7 + 0.006= 0.142 \times 7 + 0.000587\times 7 + 0.000001 = 0.142857 \times 7 + 0.000001$

So, with these two alternate steps, we arrive at a remainder of $1$ and have found the length of the repeating block.

The big catch is that, if $a = 1000$ or $a = 6000$ and $b = 7$ , the appropriate values of $q$ and $r$ have to be found. This can be facilitated with a calculator. The integer part of $1000/7$ and $6000/7$ are the two quotients needed above, and subtraction is used to find the remainders (which must be less than $7$ , of course).

At first blush, it seems silly to use a calculator to find these values of $q$ and $r$ when a calculator could have been used to just find the decimal representation of $1/7$ in the first place. However, the advantage of this method becomes clear when we consider fractions who repeating blocks are longer than 10 digits.

Let’s now return to the question posed at the top of this post: finding the decimal representation of $\displaystyle \frac{8}{17}$ . As noted in Part 6 of this series, the length of the repeating block must be a factor of $\phi(17)$ , where $\phi$ is the Euler toitent function, or the number of integers less than $17$ that are relatively prime with $17$ . Since $17$ is prime, we clearly see that $\phi(17) = 16$ . So we can conclude that the length of the repeating block is a factor of $16$ , or either $1$ , $2$ , $4$ , $8$ , or $16$ .

Here’s the result of the calculator again:

We clearly see from the calculator that the repeating block doesn’t have a length less than or equal to $8$ . By process of elimination, the repeating block must have a length of $16$ digits.

Now we perform the division algorithm to obtain these digits, as before. This can be done in two steps by multiplying by $10^8 = 100,000,000$ .

So, by the same logic used above, we can conclude that

$\displaystyle \frac{8}{17} = 0.\overline{4705882352941176}$

In other words, through clever use of the calculator, the full decimal representation can be quickly found even if the calculator itself returns only ten digits at a time… and had rounded the final $2941176$ of the repeating block up to $3$ .

(Note: While this post continues exploring the unorthodox use of a calculator to handle arithmetic problems, it also appeared in a previous series on the decimal expansions of rational numbers.)

Arithmetic with big numbers (Part 2)

Ready for an elementary arithmetic problem? Here it is:

Nothing to it… just multiply the two numbers. Of course, we’d rather not multiply them by hand, so let’s use a calculator instead:

bigmult2

Uh oh… the calculator doesn’t give the complete answer. It does return the first nine significant digits, but it doesn’t return all 16 digits. Indeed, we can’t be sure that the final 5 in the answer is correct because of rounding.

So now what we do (other than buy a more expensive calculator)?

In yesterday’s post, I posed a similar problem involving addition. Adding two big numbers by hand is no big deal. However, multiplying two big numbers, one digit at time, would be tedious!

When I pose this question to students, the knee-jerk reaction is to groan when facing the prospect of multiplying these two big numbers by hand. However, it is possible to use modern technology to make ordinary grade-school multiplication move a lot quicker. Perhaps the fastest way to do this is to split the numbers into block of five digits instead of the usual three:

Now we proceed as if each block of five digits was a single digit. We begin with the last block of digits on the second row, which is 48974. First, we multiply 6797 and 48974 using a calculator. Because most modern scientific calculators have a 10-digit display, we can be assured that the complete answer will be shown. (This is why I chose to divide the numbers using block of five digits and not six or more.) The last five digits in the answer are written down; the more significant digits are carried.

Next, we multiply 2236 and 48974 and then add the number that was carried.

bigmult4 We then repeat using 2449, the next (and final) block of digits on the second row. First, we multiply 6797 and 2449 using a calculator. The last five digits in the answer are written down; the more significant digits are carried.

Next, we multiply 2236 and 2449 and then add the number that was carried.

Finally, it remains to add these two partial products to obtain the final product. For this problem, this can be accomplished with only a single addition: the block of digits 76278 simply carry down to the final answer, and so we can start by adding the second and third blocks of digits. As this sum is less than $10^{10}$ , there is no digit to carry, and so the leading 54 also carries down to the final answer.

The above technique is logically equivalent to using base 100,000 as opposed to the customary use of base 10 arithmetic. So while multiplying two numbers in the billions still takes some time, judiciously using a calculator makes this exercise go a lot quicker than the ordinary grade-school method of multiplying one digit at a time.

Arithmetic with big numbers (Part 1)

Ready for an elementary arithmetic problem? Here it is:

Nothing to it… just add the two numbers. Of course, we’d rather not add them by hand, so let’s use a calculator instead:

bigadd5

So now what we do (other than buy a more expensive calculator)?

When I pose this question to students, the knee-jerk reaction is to just start adding one digit at a time. Though that’s not the worst possible response, it is possible to use modern technology to make ordinary grade-school addition move a lot quicker. One way to do this is to take three digits at a time while using a calculator:

Notice that the 1 in 1369 gets carried over to the next block of three digits in much the same way that a sum greater than 10 has the tens digit carried over to the next digit. Continuing:

This is logically equivalent to using base 1000 to add these two numbers (as opposed to base 10) and is certainly a lot faster than using only one digit at a time. Of course, it’d go even faster if we use up to nine digits a time (which is equivalent to using base one billion).

Inverse Functions: Logarithms and Complex Numbers (Part 30)

Ordinarily, there are no great difficulties with logarithms as we’ve seen with the inverse trigonometric functions. That’s because the graph of $y = a^x$ satisfies the horizontal line test for any $0 < a < 1$ or $a > 1$ . For example,

$e^x = 5 \Longrightarrow x = \ln 5$ ,

and we don’t have to worry about “other” solutions.

However, this goes out the window if we consider logarithms with complex numbers. Recall that the trigonometric form of a complex number $z = a+bi$ is

$z = r(\cos \theta + i \sin \theta) = r e^{i \theta}$

where $r = |z| = \sqrt{a^2 + b^2}$ and $\tan \theta = b/a$ , with $\theta$ in the appropriate quadrant. This is analogous to converting from rectangular coordinates to polar coordinates.

Over the past few posts, we developed the following theorem for computing $e^z$ in the case that $z$ is a complex number.

Definition. Let $z = r e^{i \theta}$ be a complex number so that $-\pi < \theta \le \theta$ . Then we define

$\log z = \ln r + i \theta$ .

Of course, this looks like what the definition ought to be if one formally applies the Laws of Logarithms to $r e^{i \theta}$ . However, this complex logarithm doesn’t always work the way you’d think it work. For example,