Sunday, June 15, 2014
Tuesday, June 10, 2014
Project Euler
I spent a lot of time being frustrated with Problem 472 . It seems like a problem that should admit to a nice closed form solution but solving it ended up being a (fun) pattern matching exercise.
The main thing to realize is that you are asked to sum the function $f$ over $10^{12}$ terms, but there is really no way to do that in under 1 minute of execution time. (Of course, I did not realize this until I had spent a great deal of time devising efficient algorithms for evaluating $f$ at a single value.)
You have to group the terms and add over the groups. One way yields about $\log N$ terms, which
brings the execution time down to < 0.1s.
It's all about pattern matching -- I guess....hacking + math = project euler
The main thing to realize is that you are asked to sum the function $f$ over $10^{12}$ terms, but there is really no way to do that in under 1 minute of execution time. (Of course, I did not realize this until I had spent a great deal of time devising efficient algorithms for evaluating $f$ at a single value.)
You have to group the terms and add over the groups. One way yields about $\log N$ terms, which
brings the execution time down to < 0.1s.
It's all about pattern matching -- I guess....hacking + math = project euler
Saturday, May 24, 2014
Paul Otlet, a great man way before his time
Otlet an idealistic, Belgian visionary thought that exposing the interconnectedness of the world's information would make it a more peaceful place. He could foresee a day when
He got all this funded to create an impressive operation called the Mundaneum but like any failed startup, his backers eventually refused to infuse more capital and the Mundaneum folded. He died mostly a forgotten man, although not soon thereafter, in 1945, Vannevar Bush wrote the seminal Atlantic article that in several ways presaged the WWW.
There is a new book about Otlet, but to get a really deep sense of who this man was and what he tried to do, I highly recommend wonderfully evocative online exhibit of Molly Springfield called Inside the Mundaneum.
All the things of the universe and all those of man would be registered from afar as they were produced. Thus the moving image of the world would be established—its memory, its true duplicate. From afar anyone would be able to read the passage, expanded or limited to the desired subject, that could be projected on his individual screen. Thus, in his armchair, anyone would be able to contemplate the whole of creation.Unfortunately, he lived from 23 August 1868 – 10 December 1944. He had no reasonable way to realize his vision. He thought of the world as a collection of Documents that needed to be classified and cross referenced. To this end he designed an extremely elaborate cataloging system called the Universal Decimal System that he then used to create a mammoth collection (12 million) of index cards.
He got all this funded to create an impressive operation called the Mundaneum but like any failed startup, his backers eventually refused to infuse more capital and the Mundaneum folded. He died mostly a forgotten man, although not soon thereafter, in 1945, Vannevar Bush wrote the seminal Atlantic article that in several ways presaged the WWW.
There is a new book about Otlet, but to get a really deep sense of who this man was and what he tried to do, I highly recommend wonderfully evocative online exhibit of Molly Springfield called Inside the Mundaneum.
Thoughts on Project Euler
Project Euler describes itself as a
The obvious difference between these problems and the brainteasers is that you are required to use some math (not advanced math, but math nonetheless). You end up looking up cool stuff on the wikipedia. A problem on prime numbers may have you reacquainting yourself with the Sieve of Eratosthenes as a fast way of generating prime numbers, and delving into the details of the Miller Rabin Primality Test for the first time. When I say "delving into the details" what I really mean is that you learn enough to be able to implement it in code. This isn't super deep but deeper than most of us would go if weren't focused on solving a concrete problem.
The problems that I like best follow a specific pattern: the setting involves a game or a process that can be easily simulated in a few lines of code. One is asked to compute some function, which again can be easily coded. But the kicker is that one has to provide the answer to the function for some gargantuan input like \(10^{12}\) and the nifty lines of code one has written so far would have to run for eternity to arrive at the answer. It is the process of rethinking one's approach so that the answer is computable in about a minute's worth of running time is what is most fun and rewarding about Project Euler.
An example of this (and one that I would rate as moderately hard on the "Euler Scale") is Problem 469, which concerns itself with knights sitting around a table. We have a round table with $n$ seats and Knights enter the room sequentially. The first knight picks any chair and blocks the seats to his immediate left and right. Then the next knight enters and picks one of the available seats uniformly at random. This goes on until a Knight cannot be seated. The question concerns the average fraction of seats that remain empty. Now for a small value of $n$ (say $1000$), this is not hard to compute. One simulates the knight seating process and estimates the average. But the problem asks to compute the answer for $10^{18}$ and it wants the answer to be correct to many significant digits. Well, what to do now? That is the typical kind of dilemma I face when attempting Euler problems.
When you do solve a problem correctly you get access to a terrific forum in which people post their code. I am constantly amazed at the range of approaches people from all over the world use in their solutions.
Bottom line, start solving these problems if you like math, brainteasers and have a basic knowledge of programming. You will lean a lot and have fun doing it!
series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.I've worked my through about 150 of the approximately 500 problems over the last few months, and it's been a lot of fun!
The obvious difference between these problems and the brainteasers is that you are required to use some math (not advanced math, but math nonetheless). You end up looking up cool stuff on the wikipedia. A problem on prime numbers may have you reacquainting yourself with the Sieve of Eratosthenes as a fast way of generating prime numbers, and delving into the details of the Miller Rabin Primality Test for the first time. When I say "delving into the details" what I really mean is that you learn enough to be able to implement it in code. This isn't super deep but deeper than most of us would go if weren't focused on solving a concrete problem.
The problems that I like best follow a specific pattern: the setting involves a game or a process that can be easily simulated in a few lines of code. One is asked to compute some function, which again can be easily coded. But the kicker is that one has to provide the answer to the function for some gargantuan input like \(10^{12}\) and the nifty lines of code one has written so far would have to run for eternity to arrive at the answer. It is the process of rethinking one's approach so that the answer is computable in about a minute's worth of running time is what is most fun and rewarding about Project Euler.
An example of this (and one that I would rate as moderately hard on the "Euler Scale") is Problem 469, which concerns itself with knights sitting around a table. We have a round table with $n$ seats and Knights enter the room sequentially. The first knight picks any chair and blocks the seats to his immediate left and right. Then the next knight enters and picks one of the available seats uniformly at random. This goes on until a Knight cannot be seated. The question concerns the average fraction of seats that remain empty. Now for a small value of $n$ (say $1000$), this is not hard to compute. One simulates the knight seating process and estimates the average. But the problem asks to compute the answer for $10^{18}$ and it wants the answer to be correct to many significant digits. Well, what to do now? That is the typical kind of dilemma I face when attempting Euler problems.
When you do solve a problem correctly you get access to a terrific forum in which people post their code. I am constantly amazed at the range of approaches people from all over the world use in their solutions.
Bottom line, start solving these problems if you like math, brainteasers and have a basic knowledge of programming. You will lean a lot and have fun doing it!
Thursday, November 3, 2011
The Importance of English
The China Conundrum - NYTimes.com:
Great article highlights the growth of middle class eager to enter the English speaking world....
"College officials and consultants say they are seeing widespread fabrication on applications, whether that means a personal essay written by an agent or an English proficiency score that doesn’t jibe with a student’s speaking ability. American colleges, new to the Chinese market, struggle to distinguish between good applicants and those who are too good to be true."
Saturday, October 29, 2011
Royal Society Opens Online Archive; Puts 60,000 Papers Online
Royal Society Opens Online Archive; Puts 60,000 Papers Online:
Maggie Koerth-Baker of BoingBoing writes:
60,000 peer-reviewed papers, including the first peer-reviewed scientific research journal in the world, are now available free online. The Royal Society has opened its historical archives to the public. Among the cool stuff you’ll find here: Issac Newton’s first published research paper and Ben Franklin’s write-up about that famous kite experiment. Good luck getting anything accomplished today. Or ever again. —
Newton’s telescope appears in the image above
Monday, October 24, 2011
Subscribe to:
Posts (Atom)