Author | Tim Chartier | |

Isbn | 9780691160603 | |

File size | 5MB | |

Year | 2014 | |

Pages | 152 | |

Language | English | |

File format | ||

Category | mathematics |

2
MATH BYTES
3
4
Copyright © 2014 by Princeton University Press
Published by Princeton University Press, 41 William Street,
Princeton, New Jersey 08540
In the United Kingdom: Princeton University Press,
6 Oxford Street, Woodstock, Oxfordshire, OX20 1TW
press.princeton.edu
All Rights Reserved
Library of Congress Cataloging-in-Publication Data
Chartier, Timothy P., 1969–
Math bytes : Google bombs, chocolate-covered pi, and other cool bits in
computing / Timothy P. Chartier.
pages cm
Includes bibliographical references and index.
ISBN 978-0-691-16060-3 (acid-free paper) 1. Mathematics–Popular works.
2. Mathematics–Data processing–Popular works.
3. Computer science–Popular works. I. Title.
QA93.C47 2014
510–dc23
2013025378
British Library Cataloging-in-Publication Data is available
This book has been composed in Minion Pro
Printed on acid-free paper ∞
Typeset by S R Nova Pvt Ltd, Bangalore, India
Printed in the United States of America
1 3 5 7 9 10 8 6 4 2
5
To Noah and Mikayla,
snuggle up close,
I have math-nificent stories to share
before this day ends,
and then may your dreams lead you
to explore what you learn in new ways.
I await your stories. …
6
CONTENTS
•••••••••••••••••
•••
Preface
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ix
Your First Byte
1
Deceiving Arithmetic
Two by Two
5
11
Infinite Detail
21
Plot the Course
32
Doodling into a Labyrinth
Obama-cize Yourself
54
Painting with M&Ms
Distorting Reality
42
61
73
A Pretty Mathematical Face
March MATHness
98
Ranking a Googol of Bits
A Byte to Go
105
124
Up to the Challenge
Bibliography
Index
133
Image Credits
86
125
131
135
7
PREFACE
••••••••••••••••••
•••
“WHY STUDY MATH?” can be a common question about
mathematics. While a variety of answers are possible, seeing
applications of math and how it relates to the world can be
inspiring, motivating, and eye opening. This book discusses
mathematical techniques that can recognize a disguised celebrity
and rank web pages with the roll of a pair of dice. Math also
helps us understand our world. How can poor reviews on Twitter
impact a big budget film’s poor showing on opening weekend?
How are fonts created by computers?
Mathematics has many applications, too many for any book.
The purpose here is to cover and introduce mathematical ideas
that use computing. Some of the ideas were developed by others,
like Google’s PageRank algorithm. Other ideas were developed
specifically for this book, like how to create mazes from
mathematical images created with TSP Art. The goal is to give
the reader a good taste for computing and mathematics (thus a
byte). Still, many ideas are not presented in their full depth with
the mathematical theory or most complex (and robust) approach
(thus a bit of math and computing).
This book is intended for broad audiences. It was developed in
this way. For example, Chapter 6 begins with math and doodling,
which is adapted from content taught to non-majors at Davidson
College. Later in the chapter, the content on the Traveling
Salesman Problem and TSP Art was developed from lectures to
math majors at Davidson College and the University of
Washington. The chapter concludes with the creation of mazes,
which is an application of these ideas developed specifically for
this book. Other chapters have been adapted from ideas
developed in my seminars with the Charlotte Teachers Institute.
As such, teachers should find ideas that align with their curricular
goals.
Some sections of this book have been used in my public
presentations in which audiences range from children to adults.
8
Other sections, like the later portions of Chapter 12 on the theory
of PageRank, tend to appeal to mathematicians. This multileveled
approach is intentional. Given the eclectic collection of ideas, I
imagine a reader can delve into what’s interesting and skim
sections of less interest. Throughout the development of this
book, readers have ranged from self-proclaimed “math haters” to
professors of mathematics. Wherever you, as a reader, fall in this
range, may you enjoy these applications of mathematics and
computing.
Throughout the book, you’ll find hands-on activities from using
chocolate to estimating π to computing a trajectory of flight in
Angry Birds. I expect such explorations to be a tasty byte of math
and computing for many readers. If you enjoy these
investigations, I encourage you to view the supplemental
resources for this book at the Princeton University Press website;
you’ll
find
such
materials
at
http://press.princeton.edu/titles/10198.html.
My hope is that this book will broaden a reader’s perspective
of how math can be used. So, when someone turns to you and
asks for a reason to study math, you’ll at least have one, if not
several, reasons. Math is used every day. Such applications can
be enjoyed and appreciated even if you simply consider a bit and
a byte of it.
Acknowledgments. First and foremost, I thank Tanya Chartier
who walks this journey with me and affirms choices that lead to
roads less travelled and sometimes possibly even untrodden.
Tanya encouraged me to write the first draft of this book when it
was clearest in my mind during my sabbatical at the University of
Washington in Seattle. Thank you, Tanya, for such wise counsel.
I’m grateful to Melody Chartier for being my first reader as her
input supplied great momentum and the ever-present goal of
reaching a broad audience. I also thank Ron Taylor, Brian McGue,
and Daniel Orr for their readings of the book. I enjoyed
developing the Jay Limo story and chocolate Calculus with Austin
Totty. I’m grateful for the various lunch conversations with Anne
Greenbaum that largely led to our coauthored text [18] but also
inspired a variety of ideas for this book. I appreciate Davidson
College’s Alan Michael Parker for encouraging me, when I thought
I was done with an earlier draft, to write “my book” with “my
9
voice.” Having studied mime with Marcel Marceau while I pursued
my doctorate in Applied Mathematics, it seems almost natural to
have written a book that computes π with chocolate, finds math
in a popular video game, and explores math in sports. As such, I
believe this book reflects my journey as a mathematician and
artist. I thank my parents who taught me to apply my learning
beyond preset boundaries and to look for connections in
unexpected areas. Finally, I appreciate the many ways Vickie
Kearn has supported me in this writing process and her guidance,
friendship, and encouragement. It is difficult, if not impossible, to
thank everyone who played a part in this book. To colleagues,
students, and friends, may you see your encouragement and the
results of conversations in these pages.
10
MATH BYTES
11
1••••••••••••••••••••
••••
12
Your First Byte
MATHEMATICS HELPS CREATE THE LANDSCAPES
on distant planets in the
movies. The web pages listed by a search engine are possible
through mathematical computation. The fonts we use in word
processors result from graphs of functions. These applications use
a computer although each is possible to perform by hand, at least
theoretically. Modern computers have allowed applications of
math to become a seamless part of everyday life.
Before the advent of the digital computer, the only computer
we had to rely on was a person’s mind. Few people possessed the
skill to perform complex computations quickly. Johan Zacharias
Dase (1824–1861) was noted for such skill and could mentally
multiply
in 54 seconds, two 20-digit numbers in six minutes, two 40-digit
numbers in 40 minutes, and two 100-digit numbers in 8 hours and
45 minutes. As another example, Leonhard Euler, the most
prolific mathematical writer of all time with over 800 published
papers, was renowned for his phenomenal memory. Such ability
became important during the productive last two decades of his
life, when he was totally blind. He once performed a calculation in
his head to settle an argument between students whose
computations differed in the fiftieth decimal place.
Multiprocessors, in a certain sense, also existed. Gaspard
Riche de Prony calculated massive logarithmic and trigonometric
tables by employing systematic division of mental labor. In one
step of the process, mathematically untrained hairdressers
unemployed after the French Revolution performed only additions
and subtractions. De Prony’s process of calculation inspired
Charles Babbage in the design of his difference engine, which was
an automatic, mechanical calculator operated by the turn of a
crank. The advent of computational machinery added a level of
certainty in comparison to hand calculations. Computing machines
13
could benefit from parallel calculations, seen in Figure 1.1, much
like de Prony’s calculations did from his team of hairdressers.
Algorithmic advances play a key role in the efficiency of
modern mathematical computing. Consider simulating a galaxy.
Prior to the 1970s, a computer simulating a cluster of 1,000 stars
would compute the attraction of each pair of stars on each other
resulting in 999,000 computations. The motion of a star is
determined by summing the 999 forces tugging on it by other
stars. If a computer calculates this for all 1,000 stars for many
instances in time, the motion of the cluster emerges and we see
how that galaxy evolves over time.
Figure 1.1. Early parallel computing? At least 30 workers at the
Computing Division, Veterans Bureau, in Washington, DC in the
early 1920s used Burroughs electric adding machines to compute
bonuses for World War I veterans.
In the 1970s, a cheaper computation was discovered. The
process begins by pairing each star with its nearest neighbor,
then grouping each pair with its closest pair, and subsequently
clustering each superpair with its nearest neighbor until a single
group remains. The forces are then computed for the groupings on
14
each level. For our galaxy of 1,000 stars this results in a
simulation that involves 10,000 computations at each step in
time.
SUPERCOMPUTING AND LINEAR SYSTEMS
The U. S. national laboratories house many of the world’s
fastest high performance computers. Such computers enable
scientists
to
simulate
complex
physical
phenomena,
sometimes involving billions of variables. One of the fastest
computers in the world (in fact the fastest in June 2010) is
Jaguar (pictured above) housed at Oak Ridge National
Laboratory that can perform 2.3 quadrillion floating-point
operations per second (flops). A flop is a measure of computer
performance
measuring
the
number of
floating-point
calculations performed per second, similar to the older, simpler
instructions per second.
Algorithmic improvements increase the speed of computation.
Improvements in processor speed make things even faster.
Before 1970, computers performed less than 1 million instructions
per second (MIPS). Today, laptops easily perform over 1,000
times as fast. The Intel®Core i7-990X chip, released in 2011,
operates at 3.46 GHz and reaches 159,000 MIPS. This means
what can be done in a second or less on a computer today would
have taken over 16 minutes by that 1975 mainframe. However,
this assumes we run the same algorithm on both computers.
Suppose we run our modern algorithm (which involves 1/100 as
many computations) and its slower counterpart on the older
mainframe. Now a simulation that takes 6 seconds of
computation on today’s computer would have taken over 2
15
months of constant computation on the 1975 mainframe.
These types of advances have led to the integral role of
computing in our world, from ATMs to digital watches to home
computers with internet browsers and word processing. In this
book, we’ll apply mathematics to a variety of topics. Computing
will play an important role, sometimes making the application
possible. In reading this book, you should get a taste of how
math and computing influences our world and culture.
16
2••••••••••••••••••••
•••••
17
Deceiving Arithmetic
ADDITION
enough. In fact, that is
largely what a computer does, and a computer only adds 1s and
0s. Yet, even this most foundational mathematical operation can
be tricky and require attention.
AND SUBTRACTION CAN SEEM EASY
Homer Simpson’s Method
In the 7th season of The Simpsons, Homer has a nightmare in
which he travels into 3D space. In this episode entitled
“Treehouse of Horror VI” as Homer struggles with this newfound
reality, an equation flies past 3D Homer that reads:
Simple enough, unless you happen to remember some fateful
words written in 1637.
It may have been a dark and dreary night in 1637 as Pierre de
Fermat delved deeply into the work Arithmetica written by
Diophantus some 2,000 years prior. Mathematical ideas swirled in
Fermat’s mind until suddenly the numbers fell into an
unmistakable, miraculous pattern. Quickly, he scratched into the
margin of his copy of the ancient work the statement that would
be forever linked with his name:
It is impossible to write a cube as a sum of two cubes, a
fourth power as a sum of two fourth powers, and, in general,
any power beyond the second as a sum of two similar powers.
For this, I have discovered a truly wondrous proof, but … the
margin is too small to contain it.
Let’s look at this statement carefully as it will help us understand
the humor and ingenuity of the equation in Homer’s 3D world. For
any two positive integers, if we take the first number raised to
the third power, then add it to the second number raised to the
18
third power it will never equal a positive integer raised to the
third power. Written mathematically:
For instance,
but the cube root of 35 is about 3.27, which isn’t an integer.
Fermat’s statement became known as his Last Theorem and is
stated mathematically as:
Fermat’s Last Theorem For n ≥ 3, there do not exist any
natural numbers x, y and z that satisfy the equation
What did Fermat actually “prove”? He was notorious for making
mathematical claims with little or no justification or proof. By the
1800s, all of Fermat’s statements had been resolved except the
last one written on that fateful night.
On another night in 1994 in New Jersey, Princeton University
professor Andrew Wiles discovered a proof of Fermat’s Last
Theorem. What kind of proof? It called on mathematics that had
not yet been discovered in Fermat’s time. He didn’t write it in the
margin … it took 130 pages.
Many brilliant minds worked on this problem and many
mathematical advances took place even with the failed attempts.
As more mathematicians failed to prove and disprove Fermat’s
statement, the “theorem” grew in its prestige. It turns out the
initial proof even had an error in it—that was corrected. It took
357 years, but Fermat’s Last Theorem was finally indeed proven
to be a theorem. The accomplishment was even headline news,
which is particularly newsworthy when the topic is mathematical.
Now, back to Homer’s dream. Did Homer dream up a counterexample to Fermat’s Last Theorem? Again, his world proposed
19
that
Will there be new headlines regarding Homer’s disproving Wiles’
accomplishment? Let’s wait a moment and look carefully at this
equation. Do you notice anything odd about it? Indeed, there is.
The left-hand side of the equation is the sum of an even number
(178212) and an odd number (184112), which will be an odd
number, whatever it happens to be. What about the right-hand
side of the equation? It will be even since it is an even number
raised to a power. Even Homer (hopefully) would recognize that a
number cannot be even and odd at the same time.
So, why include the equation? The humor is evident if you try
testing the equation on some calculators, especially those
available at the time the show originally aired. You can test the
equation by noting if 178212 + 184112 = 192212 then
So, what do you get? On many calculators and even some
computers that use mathematical software, you will find that
computing
results in an answer of 1922.0000000.
What happened? It becomes clearer if you can print out an
additional digit which uncovers that
equals
1921.99999996. Many calculators of the time would have
indicated the equality we just saw.
Pretty clever! Where is all this math coming from in The
Simpsons? It turns out that many of the writers have a
mathematical background. David S. Cohen (a.k.a. David X.
Cohen), writer for The Simpsons and head writer and executive
producer of Futurama, graduated magna cum laude with a
bachelor’s degree in physics from Harvard University and a
master’s degree in computer science from UC Berkeley. Watch
The Simpsons carefully and you’ll see bits of math appearing.
Futurama has even more references to mathematics. To read
about math appearing in these shows, visit [19].
Now, it is your turn with a challenge problem. They are posed
throughout the book with answers in the back. See how you do. If
20

Author Tim Chartier Isbn 9780691160603 File size 5MB Year 2014 Pages 152 Language English File format PDF Category Mathematics Book Description: FacebookTwitterGoogle+TumblrDiggMySpaceShare This book provides a fun, hands-on approach to learning how mathematics and computing relate to the world around us and help us to better understand it. How can reposting on Twitter kill a movie’s opening weekend? How can you use mathematics to find your celebrity look-alike? What is Homer Simpson’s method for disproving Fermat’s Last Theorem? Each topic in this refreshingly inviting book illustrates a famous mathematical algorithm or result–such as Google’s PageRank and the traveling salesman problem–and the applications grow more challenging as you progress through the chapters. But don’t worry, helpful solutions are provided each step of the way. Math Bytes shows you how to do calculus using a bag of chocolate chips, and how to prove the Euler characteristic simply by doodling. Generously illustrated in color throughout, this lively and entertaining book also explains how to create fractal landscapes with a roll of the dice, pick a competitive bracket for March Madness, decipher the math that makes it possible to resize a computer font or launch an Angry Bird–and much, much more. All of the applications are presented in an accessible and engaging way, enabling beginners and advanced readers alike to learn and explore at their own pace–a bit and a byte at a time. Download (5MB) Fractal Music, Hypercards and More A Java Library Of Graph Algorithms And Optimization Math Lab for Kids Cakes, Custard And Category Theory 50 Mathematics Ideas You Really Need To Know Load more posts