Math Bytes: Google Bombs, Chocolate-Covered Pi, and Other Cool Bits in Computing by Tim Chartier


5958b814f95247c.jpeg Author Tim Chartier
Isbn 9780691160603
File size 5MB
Year 2014
Pages 152
Language English
File format PDF
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

Leave a Reply

Your email address will not be published. Required fields are marked *