Thumbnail cache in Windows 7 / Vista – a rumination

Today I was thinking about the security implications of thumbnail caching systems on most PCs out there today. What I mean by that is this: whenever you use Windows Explorer to browse a directory that contains photos or other images, and you enable the “thumbnail view” feature, you would see a thumbnail of each of the images. By default, Windows caches these thumbnails, so that it doesn’t have to regenerate the thumbnails the next time you browse the same folder.

This has several implications in terms of privacy and security, since it means that a copy of each image is made elsewhere on the computer (albeit lower resolution), basically without the user’s knowledge. This is good news from a forensic examiner’s point of view, since the thumbnail cache can contain thumbnails of images that have long been deleted. However, from the user’s point of view, it can present a privacy/security issue, especially if the images in question are confidential or sensitive.

Windows XP caches thumbnails in the same folder as the original images. It creates a hidden file called “Thumbs.db” and stores all the thumbnails for the current folder in that file. So, even if the original images were deleted from the folder, the Thumbs.db file will still contain thumbnails that can be viewed at a later time.

However, in Windows 7 and Windows Vista, this is no longer the case. The thumbnails are now stored in a single centralized cache under the user’s profile directory: C:\Users\[username]\AppData\Local\Microsoft\Windows\Explorer\thumbcache*.db

The above directory contains multiple thumbnail cache files, each of which corresponds to a certain resolution of thumbnails: thumbcache_32.db, thumbcache_96.db, thumbcache_256.db, and thumbcache_1024.db.

So then, wouldn’t you like to find out what thumbnails your computer has cached in these files? Well, now you can! I’ve whipped up a small utility for the sole purpose of viewing the contents of these thumbnail caches:

This is probably not the first utility that does this, but it’s definitely the simplest. It automatically detects the thumbnail caches present on your computer, and lets you view all the thumbnail images in each cache.

If you want to disable the thumbnail cache in Windows 7 or Vista, you can find instructions here.

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

A few nitpicks of Star Trek (2009)

Let me state for the record that I loved the new Star Trek movie. Given the last several Star Trek TNG films of the last decade, the franchise was clearly in desperate need of a reboot, and J. J. Abrams did an outstanding job of that. I thought the idea of branching off into an entirely new timeline was genius, and gives a new meaning to the very word “reboot.”

However, the new film certainly had no shortage of plot holes and scientific inaccuracies. It’s taken a while for me to crystallize my thoughts on it, but after watching it last week again on Blu-ray, I couldn’t help but jot down a few nitpicks that really stuck out in my mind. Forgive my inner nerd for really showing in this post, and please feel free to contribute your own nitpicks in the comments, or criticize mine as you see fit! And, off we go.

A supernova that threatens the galaxy?

During his mind-meld with James Kirk, the elder Spock recounts the story that led to their current predicament.

According to Spock, a supernova explosion occurs in his time that threatens the survival of the galaxy. That’s curious… what kind of supernova is this? Granted, supernova explosions are very luminous, but a single supernova would certainly not threaten an entire galaxy, and it certainly wouldn’t carry the kind of planet-destroying force as shown in the film, at least not outside of a single star system.

Using our primitive Hubble Telescope, we have observed plenty of supernova remnants within our own galaxy that pose no threat to us whatsoever. The supernova remnants can grow to several light years in size, but that kind of distance is still minuscule on a galactic scale.

As it is depicted in the movie, Romulus is literally torn apart by the force of the supernova explosion. This means that it must have been the actual Romulan Sun that exploded. No stellar explosion can maintain that kind of force if it originated from a different star system.

It seems unlikely that Romulan scientists didn’t anticipate their own sun going supernova many years in advance of the explosion. Stellar evolution, although not yet completely understood, is nevertheless fairly predictable. It should be relatively easy, especially for a warp-capable species, to tell if a planet’s parent star is on the verge of exploding. Romulus could have been safely evacuated well before its star reached the end of its life.

Appalling Vulcan irresponsibility

I’m not sure I understand why the Vulcans felt it was their duty to contain the supernova. The Romulan star system is nowhere near Vulcan, so why was it up to the Vulcans to stop the explosion? OK, let’s assume for a moment that Vulcans are the only species that has “red matter” technology, so they’re the only ones who can stop the supernova by creating a black hole.

But wait… it’s well-known that the Romulans use singularities (black holes) on a routine basis as a power source for their Warbirds, so the Romulans must be perfectly capable of creating black holes themselves! Couldn’t they simply fling an abandoned Warbird into the supernova, and let the supernova be consumed by the black hole that powers the ship’s warp core?

OK, let’s assume that it was absolutely necessary for the Vulcans to handle this threat. In that case, it seems like the Vulcans handled it extremely irresponsibly, and completely contrary to logic.

Why was it the job of a geriatric diplomat (Spock) to deliver the red matter to the site of the supernova explosion? Was he going to negotiate a peace treaty with it? Couldn’t they have sent someone more appropriate, such as a team of special-forces commandos, or at least someone in better health, or even an unmanned missile that simply plunges into the supernova along with the payload of red matter, much like Dr. Soran did with trilithium in Star Trek Generations?

Why is there so much red matter aboard Spock’s ship? Seriously, if it only takes one droplet of red matter to create a black hole, why was there a comically gigantic ball of it aboard Spock’s ship? That’s enough to create a million black holes! Where else were they planning to use this much red matter?

The Vulcans should have anticipated that red matter could be used as a weapon of genocide. They should have recognized the staggering security risk of allowing red matter to come anywhere close to hostile territory. So why did they place their entire supply of red matter, capable of destroying a million planets, onto a virtually unarmed scout ship, and proceed to send the scout ship into Romulan space?! What did they think would happen?

All of this seems very irresponsible on the part of the Vulcans. Because of their short-sightedness, they’ve indirectly caused the destruction of their own homeworld, and altered the timeline for everybody else.

Black holes and time travel

In the movie, both Nero and Spock travel backwards in time by entering a black hole (facepalm!). This is basically on the same theoretical footing as traveling back in time by performing a slingshot around a star, which made complete sense in Star Trek IV: The Voyage Home.

This isn’t the first time that black holes were portrayed as portals through time in popular media. Black holes are certainly very interesting objects to theorize about, but they’re not quite as exotic as they’re made out to be.

Objects that fall past the event horizon of a black hole do not travel backwards in time. They simply fall closer and closer to the center of the black hole, until finally they’re compressed to a single point of infinite density at the very center, adding to the mass that was already at the central point.

Of course, we don’t yet have the physics to describe the nature of the infinite-density point at the center of the black hole, which is why it’s called a singularity. But we do know that any mass that enters the black hole will remain in the black hole. It doesn’t go backwards in time, nor does it go to another dimension, or another universe. All of the mass will remain in the central singularity for the remaining lifetime of the black hole.

Necessity of drilling

Why was it necessary for Nero to drill to the planet’s core in order to drop the red matter? If the red matter really creates a black hole, it would suffice to drop the red matter anywhere on the planet’s surface, and let the black hole consume the planet from the surface inward. Speaking of red matter…

Red matter?

Theoretically, any amount of matter can be turned into a black hole if it’s compressed into a small enough volume (its Schwarzschild radius). For example, the Earth’s Schwarzschild radius is about 9 millimeters. That is, for the Earth to become a black hole, it would need to be compressed into a volume with a radius of 9 millimeters (about the size of a grape).

Presumably, “red matter” is an exotic form of matter that automatically collapses beyond its own Schwarzschild radius when it’s taken out of its containment field. Fair enough, but there are several major problems with this.

The most serious problem has to do with the size of the black hole that can be created with that amount of red matter. We can see from the movie that red matter is not particularly massive — we see Spock and a Romulan handling containers with samples of red matter without exerting themselves at all. Since it took only a droplet of red matter to create a black hole, let’s assume that the droplet’s mass is 1 gram. The Schwarzschild radius for any massive object is given by the following formula: $$r_\mathrm{s} = \frac{2Gm}{c^2}$$
So, for a mass of 1 gram, the Schwarzschild radius would be about \(1.5 \times 10^{-19}\) meters, which is several orders of magnitude smaller than an atomic nucleus. A black hole of this size would pose no threat whatsoever, and this is for two reasons.

According to modern physics, black holes emit radiation with an intensity that is inversely proportional to their size. This is known as Hawking radiation, named after Stephen Hawking, who postulated its existence. If the black hole emits radiation, that must mean that it’s losing energy, which means that it’s losing mass, which means that it’s getting smaller! And the smaller the black hole gets, the more intense (the higher temperature) its Hawking radiation becomes. This continues until the black hole completely evaporates in a blaze of glory consisting of ultra-energetic gamma rays.

The point is, if Nero used a tiny amount of red matter to create a black hole of the same mass, the black hole would evaporate with a flash of radiation almost instantaneously. The black hole would not go on to swell up and consume the planet.

Incidentally, the theory of Hawking radiation is one response to people’s concerns regarding the possibility of creating a black hole at the Large Hadron Collider. Even if we create a tiny black hole at the LHC, it would instantly evaporate in a flash of radiation, and pose no further threat.

Also, even if black holes do not evaporate due to Hawking radiation, a black hole that’s smaller than an atomic nucleus would have a hard time finding other matter to swallow up. It would take a long time indeed for such a black hole to have a noticeable effect on an entire planet.

Where’s the Time Police?

This next nitpick doesn’t really have to do with the movie itself, but with a different Star Trek story that inadvertently shot the entire franchise in the foot.

In the Star Trek: Voyager episode “Future’s End,” it’s revealed that, in the 29th century, the Federation develops timeships that routinely patrol the timeline and attempt to eliminate any anomalies.

With this story, the writers basically negated any further possibility of having time-travel stories in Star Trek. If a starship travels back in time without “authorization,” we should expect a visit from a temporal patrol ship from the 29th century. The patrol ship would then do whatever is necessary to correct the timeline, and all would be back in order.

In the Voyager episode, the timeship Aeon travels back in time to prevent the destruction of the Solar system. One would think that the destruction of Vulcan is an equally worthy cause for a timeship to investigate, and attempt to prevent. But, of course, we see no hint of this in the movie.

Sound in space

Having sound in space seems to be a sci-fi cliché that the writers and producers just can’t unlearn, so it’s not even a nitpick anymore. And, in all honesty, a little sound adds to the excitement of the space battle scenes, so it’s not that big a deal.

However, in this movie, they actually made an attempt to get it right! I’m referring to the space-jump scene with Kirk, Sulu, and the unimportant guy who dies. When they jump off the shuttle and fall towards the planet, no sound can be heard. As they begin to enter Vulcan’s atmosphere, more and more noise is heard around them. This is absolutely correct!

So why couldn’t the movie take this excellent example and run with it, meaning get rid of all sound in the scenes where the shot takes place in outer space? All of the battle scenes and space explosions still have the usual sounds associated with them, without any regard for the fact that there’s no medium for the sounds to travel through. But I digress.

Epilogue

Well, that’s it for now, and thanks for indulging me. As I mentioned, this movie is a worthy successor to all the previous Star Trek films, as well as simply an excellent movie in its own right. I’m looking forward to the sequel(s).

In the meantime, all of the current sci-fi franchises, including Star Trek, would do well to hire some better scientific consultants. Maybe they can hire me?

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Discovering the 3D Mandelbulb

There is some exciting news this week in the world of fractals. Daniel White, on his website, describes what is apparently a completely new type of fractal, and the closest analog so far to a true 3-dimensional Mandelbrot set!

Although White mentions that this is probably not the “true” 3D Mandelbrot, the new fractal is undoubtedly a sight to behold, especially considering the renderings he showcases on his webpage.

Unable to contain my enthusiasm, I quickly wrote up a small program that uses OpenGL to actually display this shape in 3D, in real time, to get a feel for what this beast looks like from all angles. Don’t get too excited; the program does not render the shape in real time, it just displays the points rendered so far in real time. The actual rendering process can take a minute or so.

Download the program using the link below, and read further for instructions and screen shots.

download

The program basically renders the 3D shape by constructing a “point cloud” that approximates the edge of the fractal.

Everything in the program should be relatively self-explanatory, but here’s a brief overview of the features so far:

  • The program lets you click-and drag the rendered shape to rotate it in trackball fashion (left mouse button), as well as zooming in and out (right mouse button).
  • The program lets you select the “power” of the Mandelbulb formula, as well as the number of iterations to perform.
  • The program lets you select the resolution of the point cloud.
  • It gives you a “selection cube” with which you can select a subset of the shape to zoom in on (with the “zoom to cube” button).
  • It has a number of other minor features like fog and anti-aliasing.
  • It uses multiple threads to render the shape, so it will take advantage of multiple cores/processors.

Here are some additional screen shots:

Manipulating the selection cube:

After zooming in on the cube:

Zooming in further:

Looking inside:

Colorized points:

The program was written in C# .NET, using the Open Toolkit Library (OpenTK) which provides an excellent OpenGL wrapper.

Of course, this program is very much in its early stages, so don’t expect it to be perfect. As always, comments and suggestions are welcome!

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Make your USB flash drive indestructible!

I don’t know about you, but I’m absolutely in love with USB flash drives (thumb drives, jump drives, whatever you want to call them). I’ve been using them since they first became available. The oldest one I still own is a 16MB drive that I bought for $50 in 2001. The one I currently use is 16GB. That’s three orders of magnitude in eight years — remarkable!

The only problem I have with USB flash drives is when I mistakenly leave them in my pants pockets, and subsequently put the pants into the laundry basket. The flash drive will then suffer the grizzly fate of being spun around the washing machine soaked in soapy water, and will most likely never work again. This made me think about possible methods of somehow sealing the flash drive to make it more resistant to the elements, or to physical impact.

Background

At the office where I work, I had found a supply of epoxy that the hardware engineers use for various purposes. This epoxy comes in little packets, with each packet composed of two pouches containing different substances that, when mixed together, produce the hardening epoxy. I knew about the supply of epoxy for a while, but I hadn’t made the connection between the epoxy and the flash drives until one day, in a moment of total enlightenment, I held up my flash drive in one hand, and an epoxy packet in the other, and began to laugh uncontrollably.

I wasn’t sure yet how well the epoxy would work, but everything about the epoxy seemed perfect, including the quantity, and what was written on the packet, which is:

  • Work time: 3 to 5 minutes.
  • Will not shrink.

That same day, I took an ordinary USB flash drive, removed the plastic case so that the PC board was completely exposed, mixed up some epoxy, and poured it onto both sides of the board, making sure that all the electronic components were fully covered, and only the USB connector exposed. After about 5 minutes the epoxy hardened, and the result was even better than I hoped. The flash drive became indestructible!

Wanting to buy some of these packets for myself, I searched for a distributor of this stuff online. The brand of the epoxy is Hardman (aptly named!), and the first result is Ellsworth Adhesives, which sells a box of 100 packets for about $120. After looking a little harder, it seems that you can get the same box for a lot cheaper, such as from HMC Electronics which sells it for $80, which is 80 cents per packet — a great deal. Plus, the box includes popsicle sticks for easy mixing and spreading.

After I received the box, I encased two more flash drives in epoxy, with the same great results. The epoxy becomes rock-solid and impenetrable! Since then, I’ve been epoxying pretty much everything that makes logical sense: more flash drives, card readers, MP3 players, etc.

Advantages

The benefits of epoxying a USB flash drive (or any other small USB device) include:

  • It looks freakin’ sweet
  • It becomes virtually indestructible (the only remaining destructible component is the USB connector)
  • It becomes waterproof. My current flash drive has survived five wash cycles! Of course you have to allow the USB connector to dry completely, but after that, it’s as if nothing happened.
  • The epoxy helps dissipate heat from the flash memory and controller chips.
  • If the device has an LED, it will make the surrounding epoxy glow, which also looks cool.

Instructions

Here are some brief instructions for encasing your own USB flash drive in epoxy:

Safety first: Make sure you do this in a well-ventilated room, and don’t get any epoxy on your skin or in your eyes. And of course, make sure any data that’s currently on your flash drive is backed up, in case anything “unexpected” happens.

  • Take apart your USB flash drive. This is usually as simple as pulling apart the plastic cover that encases the PCB (printed circuit board). Be careful not to damage any of the delicate electronic components that are soldered onto the board. Throw the plastic away. All you should have left is the PCB with a USB connector soldered to it. If you like, you can write your initials on the PCB with a felt-tip pen, so that they’ll be visible through the clear epoxy when you’re finished.
  • Mix up some epoxy. I would recommend using two packets of the Hardman epoxy for an average-size USB drive (one for each side of the PCB). I usually mix the epoxy with a popsicle stick, on top of a sheet of aluminum foil. The epoxy must be mixed very thoroughly, or it won’t harden uniformly. However, don’t take too long to mix it, since it will begin to harden very quickly.
  • Hold the flash drive by the USB connector, allowing one side of the PCB to face up (you’ll repeat this for the other side), and spread some epoxy right onto the exposed PCB with a popsicle stick (or your tool of choice)! Keep adding epoxy until all the electronic components are completely covered by it, right up to the connector (don’t put any epoxy on or inside the connector itself). Do your best to keep the epoxy well-contained. It can get messy fast.
  • Keep holding the flash drive with the epoxied side facing up, so that the epoxy settles evenly throughout the surface of the PCB. If some of the epoxy starts to drip off the edge, let it drip, or scrape off the excess with the popsicle stick. The epoxy creates an exothermic reaction while setting, so it might get a little warm, but don’t be alarmed — it won’t get too hot to touch. Don’t let anything come into contact with the epoxy while it’s setting, so that you’ll get a smooth, glossy surface.
  • After holding for a few minutes, the epoxy should harden, at which point you can flip over your flash drive and repeat the procedure on the other side of the PCB.
  • When the epoxy on both sides of the PCB has hardened, you’re done! You might want to wait an additional 24 hours for the epoxy to really harden, though.
  • Enjoy your flash drive, which is now stronger than ever, looks slick, and is completely impervious to the elements!

So, then, aside from USB flash drives, what kind of things are you planning to (or have already) encase in epoxy?

(Thanks to Lifehacker for picking up this story)

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

The Math Book: Get it Now!

Cliff Pickover, the prolific author of more than forty popular science and mathematics books, has outdone himself with his latest compilation: The Math Book. This is a collection of 250 “milestones” of mathematics throughout history, complete with breathtaking glossy color illustrations for each entry (a first for his books), as well as insightful descriptions that explain the history and the significance of each of these marvels of mathematics.

This book is especially significant in one other way: it contains my artwork! The book’s entry on Knight’s Tours (p. 186) familiarizes the reader with the history of this problem, dating all the way back to Euler in 1759. And, alongside the article, Pickover displays a 30×30 knight’s tour that was solved by my neural network knight’s tour implementation. For the picture in the book, I used a modified version of the program that generated a sufficiently hi-res image. That particular knight’s tour took about 3 days for my computer to generate.

I’m deeply grateful to have one of my creations published in a book by someone as influential as Cliff Pickover. Of course, it’s all of the 250 entries in the book that make it an incredibly fascinating stroll through the history of mathematics. As mentioned elsewhere, this book definitely has bestseller potential, and could easily be one of Pickover’s best works. Buy the book now!

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Beginning Java ME: A Simple Mandelbrot Viewer

Version 3.0 of the Java ME SDK from Sun makes it very easy to start developing Java applications for mobile devices. The SDK comes with a full-fledged (and surprisingly usable) IDE, as well as a suite of emulators and example applications, all of which allows you to pick up and start writing your own apps in no time. I’ve always wanted to develop a few small applications that I could run from my phone, so I thought this might be a good time to start.

My first idea was to develop a very basic Mandelbrot set renderer and zoomer. Sure, it’s not very "useful," but it’s definitely pretty, and you’ll know that you’ll always have one of the defining symbols of modern mathematics right at your fingertips.

And, of course, it’s an awesome way to pick up chicks at the bar or dance club. I mean, come on, flash ‘em the old Mandelbrot set, and they’ll be all over you, am I right? Anyone?

Just as a refresher, the Mandelbrot set is plotted by iterating through the complex quadratic polynomial zn+1 = zn2 + c, where c is each “pixel” within the range of the complex plane we want to plot. If the sequence is bounded for a given c (within a certain number of iterations), the point is considered part of the Mandelbrot set, and the pixel is colored black. If the sequence is unbounded for a given c, the color of the pixel is determined by how “fast” the sequence diverges. The more iterations we take for our calculation, the more “precise” the set’s boundary will be.

Here are some fundamental requirements for the application:

  • Render the Mandelbrot set using a predefined color palette
  • Allow the user to "move" the drawing by pressing the L, R, U, and D keys
  • Allow the user to "zoom" in and out of the Set by pressing, say, the 1 and 3 keys
  • Allow the user to decrease/increase iterations by pressing, oh I don’t know, the 7 and 9 keys, respectively

Creating a New Project

Now that we have some requirements, let’s get down to business. We’ll create a brand new project in the Java ME SDK, and we’ll call it something original, like Mandelbrot:

screenshot1.png

Using all of the defaults for the purposes of this project is just fine. The SDK should generate a project that targets CLDC 1.1 (Connected Limited Device Configuration) and MIDP 2.0 (Mobile Information Device Profile). It will also automatically create a MIDlet class that represents our new application.

The automatically-generated class descends from the base MIDlet class, and implements the CommandListener interface, which enables our app to "listen" to commands that we can assign to buttons on your phone. The class will be called something like HelloMIDlet, but we can easily rename it to something more pertinent like MandelbrotApp, and erase the "hello world" code so we have a totally clean class.

Theoretically, however, in addition to a class that extends MIDlet, we’ll also need a class that extends the base class Canvas (we’ll call it MandelbrotCanvas), so that we can perform any kind of graphics operations we need. This class will also be responsible for capturing keystrokes from the phone’s keypad (this is different from capturing "commands" which the MIDlet class does).

The Code

Let’s first go over the MandelbrotApp class. Here are the first few lines of the class, followed by some explanation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class MandelbrotApp extends MIDlet implements CommandListener {
    private Display myDisplay;
    private MandelbrotCanvas myCanvas;
    private Command exit = new Command ("Exit", Command.EXIT, 1);
    private Command about = new Command ("About", Command.ITEM, 2);
 
    private int[] colorPalette;
    private int[] scanlineBuffer;
    private int screenWidth = 0, screenHeight = 0;
 
    public float rangex1 = -2F, rangex2 = 0.5F, rangey1 = -1.4F, rangey2 = 1.4F;
    public int numIterations = 24;
 
 
    public MandelbrotApp () {
        super ();
 
        myDisplay = Display.getDisplay (this);
        myCanvas = new MandelbrotCanvas (this);
        myCanvas.setCommandListener (this);
        myCanvas.addCommand (exit);
        myCanvas.addCommand(about);
 
        scanlineBuffer = null;
        colorPalette = new int[256];
 
        for(int i=0; i<64; i++)
            colorPalette[i] = (((i * 4) << 8) | ((63 - i) * 4));
        for(int i=64; i<128; i++)
            colorPalette[i] = ((((i - 64) * 4) << 16) | (((127 - i) * 4) << 8));
        for(int i=128; i<192; i++)
            colorPalette[i] = (((255) << 16) | ((i - 128) * 4));
        for(int i=192; i<256; i++)
            colorPalette[i] = ((((255 - i) * 4) << 16) | (255));
 
    }

In the above code, we perform some initialization of things we’ll use later on. First we create an instance of our canvas object (MandelbrotCanvas), and assign two commands ("exit" and "about") to the canvas. This means that when the canvas becomes visible, these two commands will become available from the two top buttons of your handset’s keypad. Also, by setting the canvas’ CommandListener to this, we’re saying that this class will handle the commands issued while the canvas is displayed. The variables rangex1, rangex2, rangey1, and rangey2 represent the initial boundaries for our Mandelbrot calculation. By manipulating these variables we can pan and zoom in and out of the image.

We also define a color palette that we’ll use when rendering the Mandelbrot set. The color palette contains 256 entries, and is simply a gradient of colors from red, to green, to blue, and back to red. Additionally, we define a variable called scanlineBuffer which will actually contain the screen contents before they’re painted onto the screen. We leave this initialized to null, because we’ll dynamically allocate this buffer the first time our paint event is called.

Next, we’ll create a function that actually renders the Mandelbrot set onto our screen buffer. This function uses the standard Mandelbrot algorithm without any fancy attempts at optimization, so it may be slower for some phones than others (on some phones it will be god-awful slow; sorry!).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
    public void RenderMandelbrot(){
        if((myCanvas.getWidth() != screenWidth) || (myCanvas.getHeight() != screenHeight)){
            screenWidth = myCanvas.getWidth();
            screenHeight = myCanvas.getHeight();
            scanlineBuffer = new int[screenWidth * screenHeight];
        }
 
        float bmpWidth = (float)screenWidth;
        float bmpHeight = (float)screenHeight;
 
        float x, y, xsquare, ysquare, dx, dy, bail = 4, j, p;
        int i, mul, col;
        int xpos, ypos;
        float[] q = null;
 
        if(screenWidth > screenHeight) q = new float[screenWidth + 1];
        else q = new float[screenHeight + 1];
 
        mul = 255 / numIterations;
        dx = (rangex2 - rangex1) / bmpWidth;
        dy = (rangey2 - rangey1) / bmpHeight;
 
        q[0] = rangey2;
        for(i=1; i < q.length; i++) q[i] = q[i - 1] - dy;
        xpos = 0; ypos = 0;
 
        for(p = rangex1; p <= rangex2; p += dx){
            i = 0;
            for(j = rangey1; j <= rangey2; j += dy){
                x = 0; y = 0; xsquare = 0; ysquare = 0; col = 1;
                while(true){
                    if(col > numIterations){
                        scanlineBuffer[ypos*screenWidth + xpos] = 0;
                        break;
                    }
                    if((xsquare + ysquare) > bail){
                        scanlineBuffer[ypos*screenWidth + xpos] = colorPalette[(col*mul)%255];
                        break;
                    }
                    xsquare = x * x;
                    ysquare = y * y;
                    y *= x;
                    y += (y + q[i]);
                    x = xsquare - ysquare + p;
                    col++;
                }
                i++;
                ypos++;
                if(ypos >= screenHeight) break;
            }
            myCanvas.repaint();
            myCanvas.serviceRepaints();
            xpos++;
            if(xpos >= screenWidth) break;
            ypos = 0;
        }
    }

Notice in the above function that, inside the outer loop, we force a repaint of the canvas, so that the user gets a sense of the graphic actually being drawn in real time. If we didn’t do this, the app would be totally unresponsive until all of the image is rendered.

When the app is started, the following function is called, where we set the canvas to be the currently-displayed object, and call the Mandelbrot rendering function:

1
2
3
4
    public void startApp () throws MIDletStateChangeException {
        myDisplay.setCurrent (myCanvas);
        RenderMandelbrot();
    }

Another point of interest in this class is the paint handler. This function actually gets called from the Canvas class (see lower), but I put the paint code in this class for convenience.

1
2
3
4
5
6
7
8
9
10
    public void paint (Graphics g) {
 
        g.drawRGB(scanlineBuffer, 0, screenWidth, 0, 0, screenWidth, screenHeight, false);
 
        g.setColor(0xFFFFFF);
        int fontHeight = g.getFont().getHeight();
        int strY = 4;
        g.drawString("(C) Dmitry Brant", 4, strY, 0); strY += fontHeight;
        g.drawString("Iterations: " + Integer.toString(numIterations), 4, strY, 0); strY += fontHeight;
    }

In the above function, all we do is draw our screen buffer to the screen, then write some text over the image, which includes a little copyright message and the current number of iterations used in the Mandelbrot calculation. Note that we dynamically get the height of the phone’s font (and adjust accordingly), since the font varies greatly between different phone models.

The other interesting function in this class is the command handler. This function will be called when either the "Exit" or "About" commands are pressed while our app is running. If "Exit" is pressed, we’ll destroy the application. If "About" is pressed, we’ll display a simple Alert message:

1
2
3
4
5
6
7
8
9
10
11
12
    public void commandAction (Command cmd, Displayable disp) {
        if (cmd == exit) {
            destroyApp (true);
        }
        else if(cmd == about){
            Alert alert = new Alert ("About...");
            alert.setType (AlertType.INFO);
            alert.setTimeout (Alert.FOREVER);
            alert.setString ("Copyright 2009 Dmitry Brant.\nhttp://dmitrybrant.com");
            myDisplay.setCurrent (alert);
        }
    }

Finally, let’s have a quick look at the MandelbrotCanvas class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class MandelbrotCanvas extends Canvas {
    MandelbrotApp myApp;
 
    MandelbrotCanvas (MandelbrotApp mandelTestlet) {
        myApp = mandelTestlet;
    }
 
    void init () {
    }
 
    void destroy () {
    }
 
    protected void paint (Graphics g) {
        myApp.paint (g);
    }
 
    protected void keyPressed (int key) {
        int action = getGameAction (key);
 
        float xScale = (myApp.rangex2 - myApp.rangex1);
        float yScale = (myApp.rangey2 - myApp.rangey1);
 
        boolean gotAction = true, gotKey = true;
        switch (action) {
        case LEFT:
            myApp.rangex1 += (xScale / 16.0F);
            myApp.rangex2 += (xScale / 16.0F);
            break;
        case RIGHT:
            myApp.rangex1 -= (xScale / 16.0F);
            myApp.rangex2 -= (xScale / 16.0F);
            break;
        case UP:
            myApp.rangey1 -= (yScale / 16.0F);
            myApp.rangey2 -= (yScale / 16.0F);
            break;
        case DOWN:
            myApp.rangey1 += (yScale / 16.0F);
            myApp.rangey2 += (yScale / 16.0F);
            break;
        case FIRE:
        default:
            gotAction = false;
        }
 
        if(!gotAction){
            switch (key){
            case KEY_NUM1:
                myApp.rangex1 -= (xScale / 4.0F);
                myApp.rangex2 += (xScale / 4.0F);
                myApp.rangey1 -= (yScale / 4.0F);
                myApp.rangey2 += (yScale / 4.0F);
                break;
            case KEY_NUM3:
                myApp.rangex1 += (xScale / 4.0F);
                myApp.rangex2 -= (xScale / 4.0F);
                myApp.rangey1 += (yScale / 4.0F);
                myApp.rangey2 -= (yScale / 4.0F);
                break;
            case KEY_NUM7:
                myApp.numIterations-=4; if(myApp.numIterations < 2) myApp.numIterations = 2;
                break;
            case KEY_NUM9:
                myApp.numIterations+=4;
                break;
            default:
                gotKey = false;
            }
        }
 
        if(gotAction || gotKey)
            myApp.RenderMandelbrot();
    }

The only relevant functions in the above class are the paint function, which is called automatically whenever the screen needs repainting, and the keyPressed function, which gets called when the user presses any of the keys on the keypad.

Notice how pressing the Up/Down/Left/Right buttons causes the x- and y-ranges to be panned to simulate the effect of scrolling, and the "1" and "3" keys have the effect of zooming. Keys "7" and "9" are also programmed to decrease and increase the number of iterations by 4. After any key is pressed, the graphic is redrawn due to RenderMandelbrot() being called again.

Testing the App

That’s about all there is to it. The next step is to test how the app works. If we run the app from the IDE of the Java ME SDK, it automatically launches a default emulator and loads the app onto it:

screenshot2.png

Seems to work fine on the emulator! Now how about getting it onto an actual phone? Building the app produces two files: a .JAR file, which is the actual app, and a .JAD file, which is a text file that contains certain descriptions about the app (such as the author, copyright, and URL). But what do we do with these files?

Loading a Java app onto a phone can be done in a few different ways:

  • Download from the Web
  • Download over Bluetooth
  • Download with Java App Loader (Motorola phones only)
  • Load from a memory card
  • Hack right into the phone

I’m fortunate enough to have a Motorola RAZR V3xx, which has a microSD slot. I was amazed how easy it was to get it up and running on this phone. Here’s all that’s required to install a Java app onto this phone (and probably similar Motorola models that accept a microSD card):

  • With the microSD card in the phone, connect a USB cable from your computer to the phone (it will map as a disk drive)
  • Copy your app’s .JAR and .JAD files to the /mobile/kjava directory
  • Disconnect the USB cable from the phone
  • On the phone, go to Menu -> My Stuff -> Games & Apps -> [Install New], and select your app from the list
  • That’s it! The app will now be installed on the phone!

Installing over the Web

screenshot3.jpg

If you don’t have a phone that lets you install apps from a microSD card, you can download the app from the Web using your phone. This is, of course, only if your phone has an active account and supports Web access. You’ll also probably be paying a few cents for the data transfer, depending on the wireless plan you purchased from your carrier. Oh, and of course, your phone must support CLDC 1.1 (1.0 doesn’t have floating-point support), and MIDP 2.0, which most modern phones do.

Now then, if you want to load an app that you wrote onto your phone over the Web, you need to have access to a web server where you can place your app to be downloaded. For my example, I’ll use my web server, dmitrybrant.com, and I’ll put the app in a subdirectory, like so:

I put both the .JAR and .JAD files in the "jme" subdirectory. To download the app, you only need to link to the .JAD file. But wait! There’s one more crucial step to take before our app can be downloaded from a phone. We need to edit the .htaccess file in this directory, and add the proper MIME types for our files:

AddType text/vnd.sun.j2me.app-descriptor jad
AddType application/java-archive jar

Once this is done, we can try downloading the app to our phone. After a minute of fat-fingering the URL, agreeing to install an unsigned app, and waiting for it to finish installing… lo and behold:

For the record, the above screen took about 20 seconds to draw on my V3xx. Your phone may be significantly slower (or faster, but probably not). So be prepared to wait a bit for the drawing to complete. Or go ahead and optimize the code to use integer-only math! (Let me know if you do!)

Browse the source code for this project on GitHub.
Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Seven-Segment Display for .NET

Seven-segment displayI’m usually not a big fan of custom controls except in the most extreme circumstances. From the point of view of usability, it should always make the most sense to use the controls that are shipped with the Operating System. Your user base is already familiar with the OS’s native controls, so creating custom controls would only add to the learning curve for your application. But I digress. Sometimes, there are certain controls that just beg to be written, whether they’re useful or not.

That’s why I decided to write this seven-segment LED control: not because it’s any more "useful" than a standard Label control, but because it looks freakin’ sweet. I also wrote the control to become more familiar with the internals of C# and .NET in general. And, if you like the control and are able to use it, or learn from it, so much the better.

Even if you haven’t heard the name "seven-segment display" before, you’ve probably seen quite a few in your lifetime. They appear on pretty much every piece of electronic equipment that needs to display numbers for any reason, like the timer on a microwave oven, the display on a CD player, or the time on your digital wristwatch.

They’re called seven-segment displays because they’re actually made up of seven "segments" — seven individual lights (LEDs or otherwise) that light up in different patterns that represent any of the ten digits (0 – 9).

So, what are you waiting for? Download the test application which the screen shot is from. (Or browse the source code on GitHub)

Using the code

This custom control can be built into your application by simply including the "SevenSegment.cs" file in your project. Rebuild your project, and you’ll be able to select the SevenSegment control from your tool palette and drop it right onto your forms.

To replicate the look of a seven-segment display, I draw seven polygons that precisely match the physical layout of a real display. To model the polygons, I drew them out on graph paper, and recorded the coordinates of each point in each polygon. To draw the polygons on the control, I use the FillPolygon function, passing it the array of points that represent the polygon. Let’s examine the control’s Paint event to see exactly what’s going on:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private void SevenSegment_Paint(object sender, PaintEventArgs e)
{
	//this will be the bit pattern that gets shown on the segments,
	//bits 0 through 6 corresponding to each segment.
	int useValue = customPattern;
 
	//create brushes that represent the lit and unlit states of the segments
	Brush brushLight = new SolidBrush(colorLight);
	Brush brushDark = new SolidBrush(colorDark);
 
	//Define transformation for our container...
	RectangleF srcRect = new RectangleF(0.0F, 0.0F, gridWidth, gridHeight);
	RectangleF destRect = new RectangleF(Padding.Left, Padding.Top, this.Width - Padding.Left - Padding.Right, this.Height - Padding.Top - Padding.Bottom);
 
	//Begin graphics container that remaps coordinates for our convenience
	GraphicsContainer containerState = e.Graphics.BeginContainer(destRect, srcRect, GraphicsUnit.Pixel);
 
	//apply a shear transformation based on our "italics" coefficient
	Matrix trans = new Matrix();
	trans.Shear(italicFactor, 0.0F);
	e.Graphics.Transform = trans;
 
	//apply antialiasing
	e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
	e.Graphics.PixelOffsetMode = PixelOffsetMode.Default;
 
	// Draw elements based on whether the corresponding bit is high!
	// "segPoints" is a 2D array of points that contains the segment coordinates to draw
	e.Graphics.FillPolygon((useValue & 0x1) == 0x1 ? brushLight : brushDark, segPoints[0]);
	e.Graphics.FillPolygon((useValue & 0x2) == 0x2 ? brushLight : brushDark, segPoints[1]);
	e.Graphics.FillPolygon((useValue & 0x4) == 0x4 ? brushLight : brushDark, segPoints[2]);
	e.Graphics.FillPolygon((useValue & 0x8) == 0x8 ? brushLight : brushDark, segPoints[3]);
	e.Graphics.FillPolygon((useValue & 0x10) == 0x10 ? brushLight : brushDark, segPoints[4]);
	e.Graphics.FillPolygon((useValue & 0x20) == 0x20 ? brushLight : brushDark, segPoints[5]);
	e.Graphics.FillPolygon((useValue & 0x40) == 0x40 ? brushLight : brushDark, segPoints[6]);
 
	//draw the decimal point, if it's enabled
	if (showDot)
		e.Graphics.FillEllipse(dotOn ? brushLight : brushDark, gridWidth - 1, gridHeight - elementWidth + 1, elementWidth, elementWidth);
 
	//finished with coordinate container
	e.Graphics.EndContainer(containerState);
}

You can set the value displayed in the control through two properties: Value and CustomPattern. The Value property is a string value that can be set to a single character such as "5" or "A". The character will be automatically translated into the seven-segment bit pattern that looks like the specified character.

If you want to display a custom pattern that may or may not look like any letter or number, you can use the CustomPattern property, and set it to any value from 0 to 127, which gives you full control over each segment, since bits 0 to 6 control the state of each of the corresponding segments.

The way it’s done in the code is as follows. I have an enumeration that encodes all the predefined values that represent digits and letters displayable on seven segments:

1
2
3
4
5
6
7
8
9
10
11
public enum ValuePattern
{
    None = 0x0, Zero = 0x77, One = 0x24, Two = 0x5D, Three = 0x6D,
    Four = 0x2E, Five = 0x6B, Six = 0x7B, Seven = 0x25,
    Eight = 0x7F, Nine = 0x6F, A = 0x3F, B = 0x7A, C = 0x53,
    D = 0x7C, E = 0x5B, F = 0x1B, G = 0x73, H = 0x3E,
    J = 0x74, L = 0x52, N = 0x38, O = 0x78, 
    P = 0x1F, Q = 0x2F, R = 0x18,
    T = 0x5A, U = 0x76, Y = 0x6E,
    Dash = 0x8, Equals = 0x48
}

Notice that each value is a bit map, with each bit corresponding to one of the seven segments. Now, in the setter of the Value property, I compare the given character against our known values, and use the corresponding enumeration as the currently displayed bit pattern:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//is it a digit?
int tempValue = Convert.ToInt32(value);
switch (tempValue)
{
	case 0: customPattern = (int)ValuePattern.Zero; break;
	case 1: customPattern = (int)ValuePattern.One; break;
	...
}
...
//is it a letter?
string tempString = Convert.ToString(value);
switch (tempString.ToLower()[0])
{
	case 'a': customPattern = (int)ValuePattern.A; break;
	case 'b': customPattern = (int)ValuePattern.B; break;
	...
}

Either way, the bit pattern to be displayed in the control ends up in the customPattern variable, which is then used in the Paint event as shown above.

You can also "italicize" the display by manipulating the ItalicFactor property. This value is simply a shear factor that gets applied when drawing the control, as seen in the Paint event. An italic factor of -0.1 makes the display look just slightly slanted, and a whole lot more professional.

If you begin noticing that the segments are being drawn outside the boundary of the control (perhaps from too much italicizing), you can use the Padding property and increase the left/right/top/bottom padding until all of the shapes are within the control’s client rectangle.

The control has several other convenient properties for you to play with, such as the background color, the enabled and disabled color for the segments, and the thickness of the segments.

Seven-segment array

In addition to the seven-segment control itself, I’m throwing in another control which is an array of seven-segment displays. This allows you to display entire strings on an array of 7-seg displays. Check out the demo application, and dig around the source code to see how it’s used; it’s really simple.

To use the array control, include the "SevenSegmentArray.cs" file in your project and rebuild. You’ll then be able to select the SevenSegmentArray control from the tool palette.

This control has an ArrayCount property that specifies the number of 7-seg displays in the array, as well as a Value property that takes any string to be displayed on the array. Easy, right?

Other thoughts

I must say I had a lot of fun writing this control, and .NET helped put a lot of the fun into it by making it incredibly easy to draw your own shapes, transform coordinates, and introduce truly powerful properties.

Also, coming from somewhat of an electronics background, for me, seeing this control brings a certain nostalgia for simpler times. I hope you enjoy it.

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

DiskDigger – Version 0.8.0

Today I released the latest version of the DiskDigger data recovery utility. Highlights from this version include:

  • Ability to actually undelete files (complete with file names) from the following file systems: FAT12, FAT16, FAT32, NTFS, and exFAT.
  • Split the program into two modes of operation: undelete and deep scan (lovingly dubbed “dig deep” and “dig deeper”).
  • Built in a better manifest file that automatically asks for admin privileges in Vista.

As far as I can tell, DiskDigger is the first utility (at least the first free one) that can undelete files from exFAT partitions.

So what are you waiting for? Download it and try it out!

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Binomial Coefficients and Stirling Numbers in C#

As long as I’m on a roll with my posts on number theory in C#, I thought I’d briefly discuss how to generate binomial coefficients, and then move on to Stirling numbers of the second kind, both of which are extremely useful in combinatorics and finite calculus.

Some prerequisites for calculating binomial coefficients include a standard factorial function, nothing special:

1
2
3
4
5
6
7
long factorial(long n)
{
    if (n == 0) return 1;
    long t = n;
    while(n-- > 2) t *= n;
    return t;
}

Note that I use longs whenever possible because, despite the performance hit from 64-bit operations, it’s worth it to be able to work with numbers that are double the magnitude of ints.

We will also need a function for calculating a falling power of a number, which is defined as: $$x^{\underline{n}} = x(x-1)(x-2)\ldots(x-(n-1))$$You’ll see why in a moment.

1
2
3
4
5
6
long fallingPower(long n, long p)
{
    long t = 1;
    for (long i = 0; i < p; i++) t *= n--;
    return t;
}

Notice that the above function handles the case $$n^{\underline{0}}$$ returning 1. However, it does not handle the case of p > n, which would give an incorrect result, but this is not necessary for our purposes.

Binomial Coefficients

Recall that the definition for the binomial coefficient is $${n \choose k} = \frac{n!}{k!(n-k)!}$$ However, using this exact formula to compute binomial coefficients is a bit naive. If we use falling powers (sometimes called falling factorials), the above formula easily reduces to: $$\frac{n^{\underline{k}}}{k!}$$

We can improve the algorithm a bit more by adding the condition:

$${n \choose k} =
\begin{cases}
\frac{n^{\underline{k}}}{k!} \quad \mbox{if } k \leq \lfloor n/2 \rfloor,\\
\frac{n^{\underline{n-k}}}{(n-k)!} \quad \mbox{if } k > \lfloor n/2 \rfloor.
\end{cases}
$$

Not only is this algorithm faster, but it can also handle larger coefficients than the original formula, since neither the falling power nor the factorial ever gets larger than n/2.
The code for this is straightforward:

1
2
3
4
5
6
long binomialCoeff(long n, long k)
{
    if ((k < 0) || (k > n)) return 0;
    k = (k > n / 2) ? n - k : k;
    return fallingPower(n, k) / factorial(k);
}

However, this is still not as optimal as it can be. The most optimal approach would be to accumulate the falling power while dividing by each factor of the factorial in place. This would minimize the chance of overflow errors, and allow for even larger coefficients to be calculated. The disadvantage of this algorithm is the necessary use of floating-point math:

1
2
3
4
5
6
7
long binomialCoeff(long n, long k) {
    if ((k < 0) || (k > n)) return 0;
    k = (k > n / 2) ? n - k : k;
    double a = 1;
    for (long i = 1; i <= k; i++) a = (a * (n-k+i)) / i;
    return a + 0.5;
}

Stirling Numbers

Stirling numbers (of the second kind) are useful for, among other things, enumerating the coefficients of the falling-power expansion of a regular power. For example, how would we express x3 in terms of falling powers of x? That is, how do we arrive at an equation of the form $$x^3 = ax^{\underline 3} + bx^{\underline 2} + cx^{\underline 1}$$ Well, we could just solve the equation directly, but this would get unwieldy for higher powers. A neat way of doing this involves the use of Stirling numbers of the second kind, $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$$ A useful theorem for computing these numbers is

$$\left\{\begin{matrix} n \\ k \end{matrix}\right\}=\frac{1}{k!} \sum_{i=0}^{k}(-1)^i{k \choose i}(k-i)^n$$

1
2
3
4
5
6
7
8
9
10
11
long stirling(long n, long k)
{
    long sum = 0, neg = 1;
    for (long i = 0; i <= k; i++)
    {
        sum += neg * binomialCoeff(k, i) * pow(k - i, n);
        neg = -neg;
    }
    sum /= factorial(k);
    return sum;
}

With the Stirling numbers in hand, we can now obtain the coefficients for falling power expansions:

$$x^m = \sum_{k=0}^{m}\left\{\begin{matrix} m \\ k \end{matrix}\right\}x^{\underline k}$$

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter

Project Euler — Problem 197

I never thought that solving random math problems can be addictive, but Project Euler does exactly that. Not only does it make you flex your math muscles, it also challenges you to take your programming language of choice to its limits. So it’s a total win-win: you brush up on your math skills, and broaden your programming repertoire at the same time.

Once I discovered Project Euler, I couldn’t pull myself away from the computer until I solved as many problems as I could. As of this writing I’ve solved 187 of their 211 problems.

This will be the first of a series of posts about particular Euler problems, and how easily they can be solved with C# and a bit of common-sense math. The problems I discuss will not be in any particular order, mind you.

Problem 197 has to do with finding the nth term of a particular recursively defined sequence: $$u_{n+1} = f(u_n)$$ with $$u_0 = -1, f(x) = \lfloor 2^{30.403243784-x^2}\rfloor \cdot 10^{-9}$$

Of course, as with most Project Euler problems, the value for n is set ridiculously high, presumably to eliminate the possibility of brute-forcing the problem (within the lifetime of the universe).

Fortunately, it takes little more than a superficial examination to see that this problem is actually quite simple in disguise. If we look at the first few terms of the sequence, we can already guess that this sequence appears to be “converging” to a function that oscillates between two values, approximately 0.681 and 1.029 (I won’t give precise numbers, since that would give away the solution).

This means that all we need to do is go far enough into the sequence that the deviation of the oscillations is less than the desired precision asked by the problem (10-9). And it so happens that we don’t need to go out far at all. The sequence actually settles on its two oscillatory values as early as the 1000th term (probably even earlier)! Therefore, the sum of the 1000th and 1001st term will be equivalent to the sum of the 1012th and (1012+1)st term, which is what the problem asks for!

The code to do this is elementary. I accomplished it with a mere 5 lines of C# code. Can you do better?

Share this article:
  • Facebook
  • LinkedIn
  • Reddit
  • Twitter