Friday, October 08, 2010

Remembering Prime Numbers Fast; Dividing with Less Guessing

Edit: This is a shorthand form of the Sieve of Eratosthenes.

Way back in high school, I thought I was a genius. In my naivety, I thought I could solve the great prime number problem--that is, to find a pattern in prime numbers that predicts them without having to check via factoring.

At the time, I knew very little about proofs or logic or induction. I did, however, know how to write programs in QBasic, so I wrote a factoring program. Then I wrote a program that generated lists of prime numbers, and I let one run for two days, giving me a data set containing all prime numbers through the 2 millions.

I tried different approaches to analysis. I arranged and displayed the numbers in different ways. I never found the pattern. If I had, I'd be a millionaire right now, and that would be pretty cool.

I'm not a millionaire though; I'm studying for the GRE--the general GRE. Now, you may scoff at that, and perhaps you're worthy of that great privilege. I'm not. I scoffed at the SATs, and that bit me in the ass. I doubt I did more than an hour of studying for them. I did fine--it got me into college--but I'm sure I could have nailed them with some more practice.

Lesson learned, here I am. After four years of Physics, I'm drilling basic algebra. Why? When you're doing a Physics problem, you have hours to do algebra. You can space out and happily meander through mathematical meadows. You re-derive all the theorems of algebra that you'd forgotten because you don't want to memorize a few formulae. When you're doing a GRE problem, you have two minutes flat to determine unwavering truth. The mindset's different; it takes a little practice and memorization to adapt.

Every practice test I've taken has turned up at least one problem where prime numbers are involved. The first few are easy to recall: 2, 3, 5, 7, 11, 13, 17, and 19. Those appear so frequently that it's hard to forget them. But what about the others? What about numbers that are far larger--say, 153--but not too big to be on the GRE?

I remembered one of the optimistic results I had during my prime number function hunting days. I'll first write it in the form I remember it in, then explain that:
The left is the ten's column. The right contains entries from the ones columns that are, in fact, prime when combined with that tens column. So, the rows above say,
11, 13, 17, 19
23, 29
31, 37

If we keep this going through one hundred, it looks something like this,
This looks discouraging--there's all those holes in the pattern!

Let's take a look at the exceptions:
49 = 7 x 7
77 = 7 x 11
91 = 7 x 13

In fact, what I'd developed was a sieve. It's an incomplete one, but a sieve nevertheless. It seems to eliminate all numbers that have factors of 2, 3, or 5; these three factors make the sieve loop every 30 integers. I haven't proven it rigorously, though I can make a few hand-wavy arguments.

By inspection, it obviously eliminates anything with a factor of two or five. Anything that's a multiple of two is even; its first digit is an even number, and there are none of those caught by the sieve. There's a similar argument for five; any multiple of five's first digit is 0 or 5, and none of those are present.

As far as threes go, in the first row of the sieve, all multiples of three are even or divisible by five--12, 15, 18--leaving all four possible first digits. In the second row, the multiples of three are 21, 24, and 27, so only 3 and 9 remain to be prime. On the third row, multiples of three actually begin with three--33, 36, 39--so 3 and 9 are dropped, leaving 1 and 7.

How is this useful if there are exceptions? There's not that many of them--only three less than 100, only one, 91, that made me double-take. Looking at whether or not a sieve catches a particular number gives you a lot of information and can take a lot of the guess work out of division.

In fact, it comes in really handy when factoring. Factoring by random guesswork is tedious, but this can cut your guess time down dramatically.

Take, for example, 153. The sieve doesn't cut it out, and it's not divisible two or five, so it's obviously divisible three--the only other factor the sieve eliminates. 150/3 = 50, and 3/3 = 1, so its factors are 3 and 51. 51 is not blocked out by the sieve and not a multiple of 2 or 5, so it too is divisible by three. 51 = 30 + 21, so 51/3 = 30/3 + 21/3 = 17. So the factors of 153 are 3, 3, and 17.

Being able to factor speeds up any type of division. It eliminates a lot of the guess work, saving time. Saved time on the GRE effectively means a higher score because it leaves you more time to think.

That, and I really hate doing guess work. When I was in fifth grade, I remember being taught to "guess and check," and I thought it was the biggest waste of time. I still think that, because if I wanted to guess and check, I'd make a computer do it for me. Division, though, remains a guess and check problem, and on a test where I can't use a calculator, I'll take all the help I can get.

Wednesday, October 06, 2010

Browser Diversity: The Internet's Condom

For the first time since the 90's, Microsoft Internet Explorer does not hold the majority of the browser market.

It's about time. The browser doesn't fully comply with W3C standards that say what an internet browser ought to do. I don't think it ever has, and they didn't try that hard to do so because they, at one point, controlled 95% of the market share. Why comply with standards when your browser is the standard?

This ends up being a huge pain in the ass for web designers. Take, for example, this game I've been developing. The part of the interface I've developed so far draws a map using 5x5 icons. Each of the icons is absolutely positioned using CSS. In Firefox and Chrome, the map renders properly:

This is what happens in IE:

IE, in one form or another, ignores the style sheets. It's rather insulting, really.

Once the Internet at large had enough, Firefox liberated us. It was the first browser capable of putting a significant punch into IE's market share, and more importantly, it introduced the idea that the browser you use is a choice. People using Windows had stuck with the default browser, but Firefox presented--for the first time--a viable option to switch to. Having changed before, users become slightly bolder to change again; the idea of changing browsers was no longer foreign.

I was a Firefox fan for a long time. Yesterday, I switched to Chrome. Why? I'd tinkered with it briefly and saw it going good places. Google is right about the speed too--it does things faster. I felt a little guilty about leaving my liberator and hero, but I realized it wasn't such a bad thing. As more people move on or move around, it'll make us all safer.

This seems a little counterintuitive--that as people spread out across multiple browsers, it will make everyone safer. After all, having one browser with all of the security flaws worked out sounds safer than many browsers with smaller teams working on the same problems, leaving potentially more flaws out in the open.

No matter how hard a team of developers works, every browser has security flaws. Sure, updates bring the number closer to zero, but they can never quite reach it. There will always be holes. If there's one browser, then that flaw leaves room for more damage--at IE's peak, 95% of users were at risk.

It reminds me of the cordyceps fungus:
When one browser is hegemonic--like a single insect in the jungle having an edge--a single security flaw affects every user of the Internet. It brings everyone down.

A lot of the exploitation of browsers flaws comes from the fact that it can be profitable. Let's say an unscrupulous developer decides to write a script that forwards a user to a crappy search engine. The script makes it appear that the user clicked an advertising link for that search engine, and the unscrupulous developer gets paid for it.

In browser hegemony, it becomes very profitable for the unscrupulous developers to look for as many flaws as possible in those browsers. The resulting rate of return is very high, so even if those holes are hard to find, the yield makes them worth searching for.

On an Internet with browser diversity--the one we've started transitioning to--exploiting a single security flaw has a much lower rate of return, and doing so for profit is much more difficult. As a result, it's plausible that the business of exploiting browsers for profit could diminish. I don't think it will go away, but the increased difficulty will make it subside. Finding a security flaw in Firefox, at this point, gives you a 30% share of the market; IE, only 49%.

That's a much smaller incentive and, in the long run, makes things safer for everyone.

Monday, October 04, 2010

Moon of the Month: Enceladus

Saturn has a lot of moons. About two-hundred have been observed, and it's suspected there are more. Most of these are tiny and orbit on very irregular orbits; astronomers only consider twenty-four of them regular satellites. Those we know much about are fascinating--each in a different way. Very little was known about any of them until the Voyager probes looked at them close-up in the early 1980's.

Before then, Saturn's moons were just dots. William Herschel--the same guy who discovered Uranus--first spotted Enceladus in 1789. Enceladus was the second moon in Saturnian system discovered despite only being the sixth-largest. Part of this was because William Herschel was a badass--he was, after all, the first guy to discover a planet that wasn't visible to the naked eye. On the other hand, Herschel had a little help from Enceladus and its albedo.

No, that has nothing to do with libido--unless you have an albino fetish. Albedo--particularly, Bond albedo--is the measure of "whiteness" of something, coming from the Latin "alba," meaning "white." Effectively, Bond albedo measures how much light a body reflects back into space divided by the amount it receives. Earth has an albedo of 0.29--that is, it reflects 29% of the light it receives back into outer space. Dark colored oceans, asphalt, and other things absorb the remaining 71%, which lingers as heat.

Most solar system objects are about where earth is, plus or minus 5%. Mars reflects about 25%; Saturn about 34%. Venus--with its notoriously thick sky that lights up evening and morning skies on Earth when its visible--reflects 75%.

Enceladus reflects 99%--nearly all light that hits it bounces off. The surface is pure white, covered completely in relatively new surface ice, laid down by active ice volcanoes--that's right, volcanoes that spray ice into space. Scientists were stunned when these were discovered, just as they were when Io's volcanoes were discovered. When Mars was found geologically dead, it was suspected most of the outer solar system was as well. Io came as a surprise; Enceladus, even more so. Io was much easier to explain; it's close to Jupiter and experiences tidal heating. Enceladus, on the other hand, was more difficult.

What fuels the volcanoes? Something has to keep the ice under Enceladus' surface a liquid. So, to look at the question differently, what is heating Enceladus? Enceladus reflects nearly all of the light that hits it back out into space, so clearly, the sun is not warming Enceladus. Tidal heating is suspected, but Enceladus' neighbors that are closer to Saturn are more geologically dead than Enceladus, so that's not the whole answer.

To make up the difference, It's suspected that the other portion of Enceladus' heat comes from one of the same sources as Earth--radioactive decay. Like on Earth, radioactive elements deep inside Enceladus break down slowly over time. These breakdowns release energy that warms Enceladus, eventually warming the thick layer of ice on surface, melting it, increasing its pressure, and forcing it to erupt. These "cryo-volcanoes" result.

The effects of Enceladus' volcanoes aren't just local. It's suspected--in conjunction with meteorite impacts--that they replenish Saturn's large, diffuse E-ring. Calculations have shown that particles in the E-ring ought to dissipate after millions of years--assuredly a long time, but short on the scale of the solar system. If they'd been around at the beginning of the solar system and not been replenished, they would have assuredly disappeared. Enceladus' eruptions--perpetually pumping particles into space--explain the continued existence of the ring.

Scientists have discussed exploring Enceladus further--however, exploration of Europa, it's been decided, is more important. As cool as Enceladus is, I agree. It's easier to get Jupiter, and Europa's about due for drilling.