Archive for the ‘Technology’ Category

Functional Programming and F#: Newton Basin Fractal Example Code

Thursday, August 28th, 2008

I think the best way to appreciate how efficient F# is, especially for numerical analysis, is to show an implementation of a short program. The following is a bare-bones application which computes the basins of attraction for a Newton fixed point iteration which finds the roots of a polynomial in the complex plane. This computation is threaded across all available processors, and is a stand alone (albeit absolutely minimal) Windows application. The entire program is less than 50 lines, a testament to F# with respect to numerics and the .NET framework with respect to the GUI.

Briefly, Newton’s method is an iterative way to solve for the zeros of nonlinear functions. You start with an initial guess, and based on the local slope of the function, you make a refined guess for the root by following the slope all the way to zero. Unless the function really is a line this guess will be wrong, of course, but hopefully a little more accurate than where you started. If you start close enough to a root, repeated applications of the approximation will end up converging to the correct answer to arbitrary precision. If you start far away from one, however, you could end up at a root far away from your starting point, or you might never converge. It turns out that the map of where you end up as a function of where you start is a fractal, and a rather beautiful one for many equations. Below is a screen shot of the final program. Visible in the task manager is the nearly full usage of both cores of the processor during the render. (Click for a bigger version.)

Screenshot of Newton Basin application, showing the nearly full use of both cores during the render.

Screenshot showing the nearly full use of both cores during the render.

The program below will iterate through up to 32 steps of Newton’s method on an arbitrary polynomial, starting at a grid of points in the complex plane. It shades each point based on the location of the final root found, with the hue determined by which root is converged to and with the brightness determined by how many steps were required. I’ll go through most of the functions, explaining each and pointing out how functional programming techniques are used. I do not claim this program is a highly efficient implementation! The main point was to illustrate several aspects of F#. It is however, pretty fast and makes use of multiple threads. In fact, the ease with which this program was parallelized is one of the main points I am trying to illustrate, and is made possible by the immutability of data in F# (and the Flying Frog Numerics library, a review of the which will be the subject of my final post on F#).

(more…)

Functional programming and F#: Introduction

Tuesday, August 26th, 2008

Computer programmers sometimes mistake brevity for elegance, especially when discussing the relative merits of programming languages. Haskel partisans, for example, love to show how one can implement QuickSort in one line of inscrutable gibberish that looks like somebody had an epileptic seizure with the caps lock on. Haskell is a great language, but not because it saves you some typing. If being concise is really all that important, one might as well define a new programming language called ZipC, whose “compiler” is defined as “gunzip -c $1 | gcc”. You’ll get some really concise and “elegant” programs out of that, I’m sure! I’m usually pretty wary of academic languages like Lisp and ML, which often put computer science orthodoxy above usability. I’m just not interested in investing the time to learn a new language just so that I can save some typing and use cute tricks. The time saved is likely to be more than offset by the inefficiency of maintaining competence in multiple special purpose languages.

F#, however, is the first new language in a long time that I’ve felt is worth taking the time to learn. Developed by Microsoft research in England, F# is a functional language with roots in ML. Unlike many academic functional languages, however, F# is a pragmatic mix of imperative object oriented programming and functional constructs. Instead of forcing a paradigm on you, it simply makes several available. It can also leverage the full .NET framework, and is thus just as capable of implementing a GUI as it is an abstract recursive algorithm. It produces code that’s about as fast as C#, and it should only get faster with improvements in its CLR compiler and in .NET’s JIT compiler. A novel aspect of F# (in the context of .NET languages) is that it can be used as an interactive scripting language from within Visual Studio, allowing for interactive data visualization.

After working with it for a month or so, I find it to be a highly productive and expressive language, especially for numerical algorithms. It manages to be concise and high-level while maintaining coherence and readability. Well-written functions in F# are easier to follow and debug, relative to C++ or C#, and there are fewer opportunities for bugs to begin with. More than just cute syntax, it’s a language that actually encourages you to think differently. Programs implemented well in F# are a closer representation of the underlying concept and thinking, and are less obscured with with mundane details. Perhaps the best argument of all is empirical: the test program I wrote to compute fractal Newton basins worked the first time I compiled it, something that virtually never happens to me with C or C++.

In this post, I’ll provide a rough overview of functional programming and F#. There are much better introductions out there, but I nonetheless wanted to write this as a way to help myself learn about functional programming. I also figure F# is new enough that many of the people who read this blog might have not yet heard of it, and any small additional exposure this great language gets is worth it. This is not meant to provide a tutorial that will bring you up to speed on F#, but is intended to give you enough of an idea about it that you can decide whether or not you want to learn more.

In a follow up article, I’ll step through a short program in F# which uses some of the example functions I define below to implement a parallel computation of some pretty fractals generated by running Newton’s method for polynomial roots in the complex plane. In a third post, I’ll talk about some of the libraries available to speed up F# development. Because of the functional nature of F#, libraries written for F# can do some pretty impressive things. For example, the fractal generator detailed in the next post uses a third-party library function that handles all the details of multithreaded task parallelization through the surprisingly simple use of higher-order functions. In fact, parallelizing the program required typing exactly nine characters.

(more…)

Remote test post from iPhone

Wednesday, July 30th, 2008

Thought I’d try posting directly from the iPhone for the fun of it. I can see this being useful if I actually did interesting things with my life. As it stands, however, I’m currently sitting in Newtowne park in the square, and here’s what’s going on at the moment:

photo

How to quit your job with an iPhone 3G

Wednesday, July 30th, 2008

In ten easy steps:

  1. Purchase an ’R’ rated movie from the iTunes music store.
  2. Pause movie during particularly noisy sex scene, preferably one involving farm animals.
  3. Turn off phone.
  4. Go to important meeting with your entire staff, including boss.
  5. Turn off ringer using mute switch and put phone to sleep.
  6. Think you’re safe.
  7. Innocently pull out headphones from jack, momentarily shorting out badly designed mechanism in jack used to sense the remote play switch.
  8. Remain blissfully unaware that you’ve just set a chain reaction in motion which will destroy your career.
  9. Sit in stunned horror a few seconds later as sounds of impure love eminate loudly from your shirtpocket in the middle of your boss’ presentation, despite the silent switch being on.
  10. Run back to office in tears to polish up resume.
  11. (Optional.) Write Steve Jobs an angry letter about how good design includes more than just polished metal.

(No, this didn’t happen to me. At least not exactly. It wasn’t a meeting, it was a seminar. And my boss wasn’t there, thankfully. And instead of farm animals, it was far worse: it was emo music.)

RIP American Broadcast Television, 1939–2009

Thursday, May 22nd, 2008

The end of broadcast television was always going to happen eventually, but thanks to the FCC and the vagaries of a little-known modulation format known as 8-VSB, it may happen before the end of this decade. As of February of 2009, analog television signals will be shutdown across in America. The signals which have been on in some form or another for the past 80 years, which brought the whole country together to watch fuzzy images of the moon landings, the Nixon “Checkers” speech, and the first shuttle launch, will suddenly stop. In their place will be digital high definition broadcasts. If you can receive them.

Despite the hype about digital, there are some very nice things about analog, most notably its graceful failure in the presence of noise. If interference degrades your signal, or a bus drives by your house, causing changing power levels, an analog picture will just get a bit fuzzy or maybe you’ll see a ghost image. Either way, you’ll still comprehend what’s going on, and it will be a minor annoyance. In a sense, the beauty of analog transmission is that it leverages the massive ability of the human brain to decipher noisy inputs, making the world’s best signal processor (you!) part of the transmission system. Digital television, however, is all or nothing. Either you get a perfect signal, or you get a black screen. And I predict that it will be the latter for a surprising number of people.

The modulation format chosen for our brave new world of digital television was not decided by engineers as much as by committees of bureaucrats. Their choice, 8-VSB, has two big positives going for it. One, it is power efficient, allowing less energy to be used by the transmitters. And two, and perhaps the biggest reason it was chosen, it relies on patents owned by Zenith, an American company. The downside, and the reason the Europeans don’t use it, is that 8-VSB is very susceptible to something called multi-path interference (MPI). Simply put, MPI happens when there are things—like mountains or buildings, or even buses—off of which the signal can reflect on route to your TV. 8-VSB is especially bad in changing environments, such as when people walk around a room or a plane flies over your house.

The origin of this sensitivity is the tremendous amount of data that must be squeezed into the 6 MHz channel spacing used by existing analog channels. The full data rate of a digital TV signal is almost 20 Mb/s, an astounding amount of data to be sending over the air. It’s even more astounding when you consider that it has to be squeezed into the 6 MHz channels used since the early days of television. To accomplish this feat, the information is spread over the full 6 MHz without any redundancy whatsoever. To be power efficient, it only uses one “carrier.” However, when multiple transmission paths interfere, certain parts of the spectrum (certain frequencies) will destructively interfere, causing loss of signal at those frequencies. This frequency-dependent attenuation has to be removed by equalization before the whole signal can be reliably deciphered. As you can imagine, doing this when the equalization needed is constantly changing is very difficult. In practice, the screen will go black while the receiver tries to figure out what to do. The Europeans, to their credit, use a modulation system called COFDM that is akin to having hundreds of independent radio stations each with a tiny bandwidth transmitting simultaneously, each carrying a simpler part of the more complicated signal. This is much less susceptible to interference, as each low-bandwidth subchannel only has to be equalized relative to itself, and there’s not much that can happen over a very narrow bandwidth signal. (There was actually quite a bit of “drama” over our choice of schemes, as partly detailed in this article.)

My skepticism about the switch to digital comes from forced experience with it, as I’m not allowed to have cable where I live. Most Boston stations have been broadcasting in digital for some time (in addition to their analog signals) and I can attest that it’s very difficult to get good reception where we are in Cambridge, due to all the buildings. We are a scant 5–7 miles from the transmitters, very close by most standards, and yet our digital signals are flaky and will go out completely if a bus drives by or a person walks by our window. We’ve becomed conditioned to expect the picture to go black whenever we hear a bus approach. And this is with a top-of-the-line antenna and a TV with a fifth generation receiver chip.

The reason I’m writing about all of this is not to complain for the sake of complaining. That is something I would never do! Nor do I think it would be the end of the world if we can’t all watch Knitting with the Stars or Survivor XXIV, Staten Island. I decided to write about this because the switch to digital could potentially be such a disaster that it could cause an interesting shift in our nation’s media consumption. It could also be a potentially lucrative shift if you invest in companies who stand to benefit, like Comcast or DirecTV.

In terms of social impact, the (few) people who were on the edge regarding TV, who maybe had an old analog TV around for news or the occasional football game, will probably end up giving up broadcast TV entirely, switching to Internet-based media. However, tens of millions of others will be driven to cable or satellite TV, many simply due to confusion over what the switch means. (A majority of people surveyed thought that they would have to buy a new TV once the switch occurs.) A high proportion of people still using OTA TV are poor—predominantly living in urban apartments, the worst possible situation for digital TV reception—and will no longer be able to receive any television. The result is that they will become even less connected to mainstream American media and news, for good or bad.

In terms of business, I think this will finally put the stake in the local affiliate system, as the need for local broadcast facility was one of the reasons they existed to begin with. Along with them will go the curious phenomenon known as the local news broadcast. (So at least one good thing will come of it.) National television networks will still exist, but unemcumbered by contracts with local affiliates, distribution will become entirely on demand through cable and satellite, and increasingly through the Internet. I would guess Apple will play a major role, offering a box (a la Apple TV) that allows one on-demand access to programs with targeted (and non-optional) advertising. (Microsoft will try to do the same, offering a set top box based on Windows, and will fail miserably.) The move to on-demand programming will bring the final demise of the network news departments. Nobody will be willing to sit through an on demand full news broadcast when there is always a sitcom to be had. We will realize, too late, that the imposed schedule of broadcast television was the last bit of social discipline we had, forcing us to at least sit through the news before we got Seinfeld at 8.

All because somebody in the government decided vestigial sideband modulation was the way to go.

Problems with video resolution resetting after wake in Vista?

Saturday, April 19th, 2008

Ah, the fun with Vista continues. For the longest, most infuriating time, my screen settings would completely reset after my Dell Latitude D620 laptop would come out of sleep. It appears that the problem was with the Intel integrated graphics drivers. Is that Microsoft’s fault for doing something dumb in Vista, or Intel’s fault? I don’t care. The problem has been fixed by a driver upgrade from Intel.

So, I thought I’d put up this quick post in case other people have been having the same problems with their laptops running Vista. Check to see if your laptop uses the Intel 945 graphics chip. If so, your problems might be solved by upgrading to the latest driver. For your convenience, here is a link to the drivers from Dell’s FTP server:

Intel 945 Vista 32 bit drivers

Sorry this wasn’t a very fun post, but sometimes you gotta pay the bills.

In defense of Google’s Street View, and a proposed definition of online privacy

Monday, April 14th, 2008

Quick Summary. Google’s street view is simply a representation of reality on a specific day, and they have not highlighted any aspect of the dataset, and furthermore the dataset is comprehensive. Given the mapping between reality and the dataset that is inherent in something like Street View, one’s privacy on the day your photo was taken and one’s privacy in the dataset are commensurate, because your relative anonymity is the same in each. Arguments pointing out that certain people and websites can highlight compromising pictures are missing the point, and are like blaming camera manufacturers for the actions of paparazzi. If a company decides to single out a certain picture on somebody on Street View on your website, that company is the party violating privacy, not Google. Google is producing an unbiased representation of reality; just as in physical reality, it is the choices and actions of others who decide whether or not privacy is violated.

 

Recently, Google has been driving around various metropolitan areas (including Boston) in a fleet of funky-looking cars adorned with eight cameras mounting on their roofs (see below) profligately photographing everything within view of the street every few feet, and linking the resulting panoramic shots to their respective locations in Google Maps. Their eventual goal is to have virtually every building on every street in every major city photographed, such that you can click on a street and see a picture of the surroundings from that location. You’d have to be Mr. and Mrs. Boring to not think that’s cool.

Car used by Google to obtain panoramic Street View data.

Car used by Google to obtain panoramic Street View data.

Right now, the resolution is sufficient to find that bar from which you stumbled home one night but whose name eludes, or to get a decent idea about whether or not the Lake View Retirement Home really has one. As it grows more complete, it will be a profoundly powerful dataset, and will doubtless result in all manner of unforeseen applications. This will be especially true if Google actually uses higher resolution pictures. Do you want to see when a favorite business is open, but they don’t have a website? You could, in theory, check out the hours posted on the front of their store with sufficiently high resolution imagery. If you’re wondering about the legal parking hours on the streets near a restaurant you’re planning to visit, you could read the parking signs across town from your computer.

Unfortunately, reactionary privacy concerns have plagued the service since its inception, and if the service survives at all, it’s likely that it will be limited to low resolution pictures. Some of the criticism has predictably come from people who have been photographed doing things they shouldn’t, but much of the ire has come from people who simply think that having a picture of them taken while they were in public shouldn’t be allowed online. And I have to admit, I took pause when I found our own car parked in our usual spot:

Our car, as found on Google's Street View.

Our car, as found on Google

However, upon further reflection, I realized that it is unreasonable to object to this as a privacy violation, for reasons that are especially clear in this particular case. Quite literally, there is going to be a nearly one-to-one correlation between the Google Street View dataset and the real world. Thus, while your image might be available to everybody, so are millions of other images. One might expect that at any given moment, the proportion of people interested in the Google picture of the specific place you were the day the google car spotted you is very roughly the same as those interested in that specific spot in real life at any given moment. Thus, for exactly the same reason you only saw a few people on the street with you at the moment the picture was taken, it’s likely only a few people are interested, at any one time, in that picture.

(more…)