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

How high can you count on two hands?

How high can you count on two hands? The answer is 1023, if you use binary. I made the following video to demonstrate this to my students.

True story: This is a trick that I came up with when I was 10 years old. As is common in classrooms, my teacher had had enough disruptions in class, and told us students to put our heads on our desks in silence for 15 or 20 minutes as punishment. Naturally, I was trying to think of something to do to pass the time, and I somehow came up with the idea that I could keep myself entertained by counting in binary using my fingers.

When I was a kid, I could count to 1023 in about 5 minutes. But I was a lot more dextrous then, and so it takes me about 6 or 7 minutes today.

Binary

Source: http://www.xkcd.com/953/

Fun with Bases

Something I noticed last month:

10 in base ten…

is 101 in base three…

and 1010 in base two.

Notice that the representation changed by just adding an extra digit. Also, this is the maximum number of times that this could happen for 10; base two is the smallest base, while a two-digit representation is the shortest that could have a pattern like this (since 10 is represented as A for any base higher than ten).

Naturally, I’m curious if there’s another number like this. 64 comes close:

10 in base sixty-four…

100 in base eight…

1000 in base four…

1 000 000 in base two.

But the pattern breaks for base three.

How signed integers are represented using 16 bits

Source: http://www.xkcd.com/571/

This probably requires a little explanation with the nuances of how integers are stored in computers. A 16-bit signed integer simulates binary digits with 16 digits, where the first digit represents either positive ( $0$ ) or negative ( $1$ ). Because this first digit represents positive or negative, the counting system is a little different than regular counting in binary.

For starters,

$0000000000000000$ represents $0$

$0000000000000001$ represents $1$

$0000000000000010$ represents $2$

$\vdots$

$0111111111111111111$ represents $2^{16}-1 = 32767$

For the next number, $1000000000000000$ , there’s a catch. The first $1$ means that this should represent a negative number. However, there’s no need for this to stand for $-0$ , since we already have a representation for $0$ . So, to prevent representing the same number twice, we’ll say that this number represents $0 - 32768 = -32768$ , and we’ll follow this rule for all representations starting with $1$ . So

$0000000000000000$ represents $0-32768 = -32768$

$0000000000000001$ represents $1 - 32768 = -32767$

$0000000000000010$ represents $2 - 32768 = -32766$

$\vdots$

$0111111111111111111$ represents $32767-32768 = -1$

Because of this nuance, the following C computer program will result in the unexpected answer of $-37268$ (symbolized by the sheep going backwards in the comic strip).

main()

{

short x = 32767;

printf(“%d \n”, x + 1);

}

For more details, see http://en.wikipedia.org/wiki/Integer_%28computer_science%29

Why does 0.999… = 1? (Part 1)

Our decimal number system is so wonderful that it’s often taken for granted. (If you doubt me, try multiplying $12$ and $61$ or finding an $18\%$ tip on a restaurant bill using only Roman numerals.)

However, there’s one little quirk about our numbering system that some students find quite unsettling:

If a number has a terminating decimal representation, then the same number also has a second different terminating decimal representation. (However, a number that does not have a terminating decimal representation does not have a second representation.)

Stated another way, a decimal representation corresponds to a unique real number. However, a real number may not have a unique decimal representation.

Some (perhaps many) students find such equalities to be unsettling at first glance, and for good reason. They’d prefer to think that there is a one-to-one correspondence to the set of real numbers and the set of decimal representations. Stated more simply, students are conditioned to think that if two number look different (like $24$ and $25$ ), then they ought to be different.

However, there’s a subtle difference between a number and a numerical representation. The number $1$ is defined to be the multiplicative identity in our system of arithmetic. However, this number has two different representations in our numbering system: $1$ and $0.999\dots$ . (Not to mention its representation in the numbering systems of the ancient Romans, Babylonians, Mayans, etc.)

As usual, let $[0,1]$ be the set of real numbers from $0$ to $1$ (inclusive), and let $D$ be the set of decimal representations of the form $0.d_1 d_2 d_3 \dots$ . Then there’s clearly a function $f : D \to \mathbb{R}$ , defined by

$f(0.d_1 d_2 d_3\dots) = \displaystyle \sum_{i=1}^\infty \frac{d_n}{10^n}$

If I want to give my students a headache, I’ll ask, “In Calculus II, you saw that some series converge and some series diverge. So what guarantee do we have that this series actually converges?” (The convergence of the right series can be verified using the Direct Comparsion Test, the fact that $d_i \le 9$ , and the formula for an infinite geometric series.)

In the language of mathematics: Using the completeness axiom, it can be proven (though no student psychologically doubts this) that $f$ maps $D$ onto $[0,1]$ . In other words, every decimal representation corresponds to a real number, and every real number has a decimal representation. However, the function $f$ is a surjection but not a bijection. In other words, a real number may have more than one decimal representation.

This is a big conceptual barrier for some students — even really bright students — to overcome. They’re not used to thinking that two different decimal expansions can actually represent the same number.

The two most commonly shown equal but different decimal representations are $0.999\dots = 1$ . Other examples are

$0.125 = 0.124999\dots$

$3.458 = 3.457999 \dots$

In this series, I will discuss some ways of convincing students that $0.999\dots = 1$ . That said, I have met a few math majors within a semester of graduating — that is, they weren’t dummies — who could recite all of these ways and were perhaps logically convinced but remained psychologically unconvinced. The idea that two different decimal representations could mean the same number just remained too high of a conceptual barrier for them to hurdle.

Method #1. This first technique is accessible to any algebra or pre-algebra student who’s comfortable assigning a variable to a number. We convert the decimal representation to a fraction using something out of the patented Bag of Tricks. If students aren’t comfortable with the first couple of steps (as in, “How would I have thought to do that myself?”), I tell my usual tongue-in-cheek story: Socrates gave the Bag of Tricks to Plato, Plato gave it to Aristotle, it passed down the generations, my teacher taught the Bag of Tricks to me, and I teach it to my students.

Let $x =0.999\dots$ . Multiply $x$ by $10$ , and subtract:

$10x = 9.999\dots$

$x = 0.999\dots$

$\therefore (10-1)x = 9$

$x =1$

$0.999\dots = 1$

Thoughts on 1/7 and other rational numbers (Part 7)

In a previous post concerning roundoff error, I mentioned that the number $1/10$ equals

$\displaystyle \frac{1}{2^4} + \frac{1}{2^5} +\frac{1}{2^8} + \frac{1}{2^9} + \frac{1}{2^{12}} + \frac{1}{2^{13}} + \dots$

In other words, the binary expansion of $1/10$ is

$0.0001100110011001100110011001100....$

That’s the expansion of the fraction in base $2$ , as opposed to base $10$ .

In the previous post, I verified that the above infinite series actually converges to $1/10$ :

$S = \displaystyle \left(\frac{1}{2^4} + \frac{1}{2^5}\right) +\left(\frac{1}{2^8} + \frac{1}{2^9}\right) + \left(\frac{1}{2^{12}} + \frac{1}{2^{13}}\right) + \dots$

$S = \displaystyle \frac{3}{2^5} + \frac{3}{2^9} + \frac{3}{2^{13}} + \dots$

$S = \displaystyle \frac{\displaystyle \frac{3}{2^5}}{\quad \displaystyle 1 - \frac{1}{2^4} \quad}$

$S = \displaystyle \frac{\displaystyle \frac{3}{32}}{\quad \displaystyle \frac{15}{16} \quad}$

$S = \displaystyle \frac{3}{32} \times \frac{16}{15}$

$S = \displaystyle \frac{1}{10}$

Still, a curious student may wonder how one earth one could directly convert $1/10$ into binary without knowing the above series ahead of time.

This can be addressed by using the principles that we’ve gleaned in this study of decimal representations, except translating this work into the language of base $2$ . In the following, I will use the subscripts $\hbox{ten}$ and $\hbox{two}$ so that I’m clear about when I’m using decimal and binary, respectively.

To begin, we note that $10_{\hbox{\scriptsize ten}} = 1010_{\hbox{\scriptsize two}} = 10_{\hbox{\scriptsize two}} \times 101_{\hbox{\scriptsize two}}$ . (In other words, ten is equal to two times five.) So, following Case 3 of the previous post, we will attempt to write the denominator in the form

$10_{\hbox{\scriptsize two}}^d \left(10_{\hbox{\scriptsize two}}^k - 1 \right)$ , or $2_{\hbox{\scriptsize ten}}^d \left(2_{\hbox{\scriptsize ten}}^k - 1 \right)$

If $k = 1_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^1 - 1 = 1_{\hbox{\scriptsize ten}}$ , but $1_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 2_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^2 - 1 = 3_{\hbox{\scriptsize ten}}$ , but $3_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 3_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^3 - 1 = 7_{\hbox{\scriptsize ten}}$ , but $7_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 4_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^4 - 1 = 15_{\hbox{\scriptsize ten}}$ . This time, $15_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}} = 3_{\hbox{\scriptsize ten}}$ . Written in binary,

$101_{\hbox{\scriptsize two}} \times 11_{\hbox{\scriptsize two}} = 1111_{\hbox{\scriptsize two}}$

We now return to the binary representation of $1/10_{\hbox{\scriptsize ten}} = 1/1010_{\hbox{\scriptsize two}}$ .

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = \displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} \times \frac{11_{\hbox{\scriptsize two}}}{11_{\hbox{\scriptsize two}}}$

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = \frac{11_{\hbox{\scriptsize two}}}{11110_{\hbox{\scriptsize two}}}$

Therefore, the binary representation has a delay of one digit and a repeating block of four digits:

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = 0.0\overline{0011}$

Naturally, this matches the binary representation given earlier.

Thoughts on 1/7 and other rational numbers (Part 1)

I’m guessing that not many people ever blocked time out of their busy schedules to purposefully memorize the decimal representation of a fraction. Nevertheless, in my experience, most math majors and math teachers can immediately convert, from memory, most (but not all — more on this later) fractions of the form $\displaystyle \frac{k}{n}$ into its decimal representation as long as the denominator $n$ is less than or equal to $10$ . They can also go the other direction, mentally recognizing a decimal expansion as a fraction of this form.

This memorization occurs not because of purposeful study but because these fractions arise so commonly from 6th grade through college that students can’t help but memorize them. They just come up so often that good students almost can’t help but memorize them.

Here are the decimal representations of $\displaystyle \frac{k}{n}$ , where the fraction is in lowest terms and $1 \le k < n \le 10$ .

$\displaystyle \frac{1}{2} = 0.5$

$\displaystyle \frac{1}{3} = 0.\overline{3} \quad \displaystyle \frac{2}{3} = 0.\overline{6}$

$\displaystyle \frac{1}{4} = 0.25 \quad \displaystyle \frac{3}{4} = 0.75$

$\displaystyle \frac{1}{5} = 0.2 \quad \displaystyle \frac{2}{5} = 0.4 \quad \displaystyle \frac{3}{5} = 0.6 \quad \displaystyle \frac{4}{5} = 0.8$

$\displaystyle \frac{1}{6} = 0.1\overline{6} \quad \displaystyle \frac{5}{6} = 0.8\overline{3}$

$\displaystyle \frac{1}{7} = 0.\overline{142857} \quad \displaystyle \frac{2}{7} = 0.\overline{285714} \quad \displaystyle \frac{3}{7} = 0.\overline{428571}$

$\displaystyle \frac{4}{7} = 0.\overline{571428} \quad \displaystyle \frac{5}{7} = 0.\overline{714285} \quad \displaystyle \frac{6}{7} = 0.\overline{857142}$

$\displaystyle \frac{1}{8} = 0.125 \quad \displaystyle \frac{3}{8} = 0.375 \quad \displaystyle \frac{5}{8} = 0.625 \quad \displaystyle \frac{7}{8} = 0.875$

$\displaystyle \frac{1}{9} = 0.\overline{1} \quad \displaystyle \frac{2}{9} = 0.\overline{2} \quad \displaystyle \frac{4}{9} = 0.\overline{4} \quad \displaystyle \frac{5}{9} = 0.\overline{5} \quad \displaystyle \frac{7}{9} = 0.\overline{7} \quad \displaystyle \frac{8}{9} = 0.\overline{8}$

$\displaystyle \frac{1}{10} = 0.1 \quad \displaystyle \frac{3}{10} = 0.3 \quad \displaystyle \frac{7}{10} = 0.7 \quad \displaystyle \frac{9}{10} = 0.9$

Like I said, most (but not all) of these have been memorized by math majors and math teachers. The exceptions, not surprisingly, are the fractions with a denominator of $7$ .

When I was a child, I read somewhere the following rule for memorizing the decimal expansion of $\displaystyle \frac{k}{7}$ . I must have been lucky, because I have yet to meet a student that also saw this rule. The following is not a formal proof of the rule, but it does work for the purposes of memorization.

Step 1. Let’s begin with $\displaystyle \frac{1}{7}$ . The decimal expansion can be remembered by repeating “3, 2, 6” along with repeating “up, down.” Repeating both patterns, we get

up 3

down 2

up 6

down 3

up 2

down 6

So,

Start at $1$ :

up 3: $\quad 1 + 3 = 4$

down 2: $\quad 4 - 2 = 2$

up 6: $\quad 2 + 6 = 8$

down 3: $\quad 8 - 3 = 5$

up 2: $\quad 5 + 2 = 7$

down 6: $\quad 7 - 6 = 1$

The pattern returns back to $1$ , and the digits repeat. That’s the decimal expansion:

$\displaystyle \frac{1}{7} = 0.142857142857\dots$

Steps 2-6. For $\displaystyle \frac{2}{7}, \dots, \frac{6}{7}$ , the digits repeat in the same pattern as $\displaystyle \frac{1}{7}$ , just starting at a different place. For example:

For $\displaystyle \frac{2}{7}$ , the second smallest of the digits $1, 4, 2, 8, 5, \hbox{~and~} 7$ is $2$ . So we’ll drop the first $1$ and $4$ and start on $2$ :

$\displaystyle \frac{1}{7} = 0.2857142857\dots = 0.\overline{285714}$

For $\displaystyle \frac{4}{7}$ , the fourth smallest of the digits $1, 4, 2, 8, 5, \hbox{~and~} 7$ is $5$ . So we’ll drop the first $1$ , $4$ , $2$ , and $8$ and start on $5$ :

$\displaystyle \frac{4}{7} = 0.57142857\dots = 0.\overline{571428}$

P.S. Plenty of math majors (though perhaps not a majority) have also memorized the decimal expansions of $\displaystyle\frac{k}{11}$ and $\displaystyle \frac{k}{12}$ . For $11$ , the rule is multiply $k$ by $9$ to form the two-digit repeating block. In other words:

$4 \times 9 = 36$ , and so $\displaystyle \frac{4}{11} = 0.\overline{36}$

$8 \times 9 = 72$ , and so $\displaystyle \frac{8}{11} = 0.\overline{72}$

$1 \times 9 = 9$ , and so $\displaystyle \frac{1}{11} = 0.\overline{09}$

For $12$ , the only lowest-term fractions are $\displaystyle \frac{1}{12}$ , $\displaystyle \frac{5}{12}$ , $\displaystyle \frac{7}{12}$ , and $\displaystyle \frac{11}{12}$ . To begin, the first should be memorized: