4by12

aMule Hacking

May 31, 2007 – 3:19 am

aMule is an open source eMule-like client. It enforces a strict upload/download ratio at the client side: You set the maximum upload rate, and your down rate is limited accordingly. For example, if you allow aMule to use 5 kB/s for upload, your maximum download rate is 20 kB/s. 9 kB/s upload gives you 36 kB/s. 10 kB/s gives you unlimited download bandwidth.

My problem is (or rather, was ) this: 36 kB/s for download is very little compared with my ADSL line’s capacity of 180 kB/s. But to get the full speed I need to allow aMule to use 10 kB/s out of about 12 kB/s of upload capacity, which makes web surfing extremely painful (ping google.com gives > 2 secs). I don’t mind sharing my bandwidth, but this is too much.

I tried being a good citizen by doing some traffic shaping with wondershaper at my router, giving aMule traffic low priority compared with web surfing. This isn’t trivial, because aMule uses varying ports at both ends of a connection. I used netstat --program to find the peers and then lowered their priorities by host. This helped matters a bit (reducing latency to about half a second), but surfing still felt sluggish.

So I pulled out the big(ger) guns. I downloaded the aMule source code and found this nice little function in Preferences.cpp:

// Here we slightly limit the users' ability to be a bad citizen: for very low upload rates
// we force a low download rate, so as to discourage this type of leeching.
// We're Open Source, and whoever wants it can do his own mod to get around this, but the
// packaged product will try to enforce good behavior.
//
// Kry note: of course, any leecher mod will be banned asap.
void CPreferences::CheckUlDlRatio()
{
	// Backwards compatibility
	if ( s_maxupload == 0xFFFF )
		s_maxupload = UNLIMITED;

	// Backwards compatibility
	if ( s_maxdownload == 0xFFFF )
		s_maxdownload = UNLIMITED;

	if ( s_maxupload == UNLIMITED )
		return;

	// Enforce the limits
	if ( s_maxupload < 4  ) {
		if ( ( s_maxupload * 3 < s_maxdownload ) || ( s_maxdownload == 0 ) )
			s_maxdownload = s_maxupload * 3 ;
	} else if ( s_maxupload < 10  ) {
		if ( ( s_maxupload * 4 < s_maxdownload ) || ( s_maxdownload == 0 ) )
			s_maxdownload = s_maxupload * 4;
	}
}

So, commented out the ‘Enforce the limits’ section, compiled, and viola — your basic leech mod. Now I was free to set my upload rate to 1 kB/s without affecting my download rate, but I didn’t want to do that because:

I didn’t want to be a leech. As a citizen, I try to follow a set of rules that I believe is scalable. What I mean by ’scalable’ is this: If everyone followed my set of rules, the community would prosper. My rules aren’t necessarily the official ones. For example, I always vote at elections because I believe that if everyone voted it would be good for society. There’s no rule that says you have to vote, but it’s scalable so I do it. Anyway, being a leech on a P2P network is certainly not scalable.
aMule has a ‘credit’ system: When you are on someone’s queue waiting to download a chunk, uploading him some data gives you credit. You use this credit to jump ahead in his queue. The queue wait is typically very long, so jumping ahead is significant. Hence your effective upload rate still affects your download rate, even with the mod.
Leeching clients are banned when they are discovered. As far as I can tell, this is not done automatically, but rather manually by people who notice skewed upload/download ratios.

Fortunately, there is good middle ground: Setting my upload rate to 7 kB/s. At this rate web surfing is smooth, I still share most of my bandwidth, and chances of getting detected are slim to none. Best of all, this is scalable behavior: If everyone set their upload rate to 3 kB/s under their max rate, and got max down rate in return, things would be terrific.

Posted in Software | 2 Comments »

Fwd: Spread this number

May 1, 2007 – 5:02 pm

09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0

This is the Processing Key that will allow viewing HD-DVD movies on Linux. What’s happening now with this key is similar to what happened a couple of years ago with the DVD key and DeCSS.

For more, see here and here. The second link is an account of how the key was recovered by the guy who did it. Spread the word!

Posted in Software | No Comments »

Fun with PDEs

May 1, 2007 – 4:58 am

I just finished working on a numerical simulation of a set of partial differential equations (PDE). I developed these equations for a physics research project I’m involved in. The equations did not seem to be solvable analytically, so I had to do it numerically. This was my first attempt at solving a PDE, and writing the simulation turned out to be much more involved than with ordinary differential equations. Here are a couple of interesting pitfalls I encountered.

PDE Primer

In case you’re not familiar with the terminology, I’ll first explain what a PDE is. A simple equation contains one or more unknowns which represent numbers. For example: x^2 - x - 1 = 0 . An ordinary differential equation (ODE) is similar, except the unknown is a function rather than a number. Such an equation involves derivatives of the function. Here is an example:

$f\prime(x) = f(x)$

-
The solution of this particular equation is f(x) = c e^x , where can be any number. Finally, a partial differential equation (PDE) involves a function that has two or more parameters, and includes partial derivatives of this function. For example, the following equation describes waves propagating through a medium:

$\frac { \partial^2 f } { \partial t^2 } = v^2 \, \frac { \partial^2 f } { \partial x^2 }$

-
PDEs are very important in physics. In fact, many of the basic laws of nature are described as PDEs. Examples include Maxwell’s equations, Shcrodinger’s equation, and Einstein’s field equations.

On to the simulation!

Pitfall 1: Exploding Waves

So, I built my model for the problem, derived the equations, and was ready to solve them. By ’solving’ I mean that I start out with the known function at time t=0, and I want to find out what that function is at a later time. My function initially looked like this:

Some thousands of time-steps later, it evolved into this:

So far so good, but then it completely exploded:

Going back a bit in time, I was able to trace the beginning of this explosion:

And zooming in on the ‘wavy’ part:

It looked as though waves were forming on my function, and then ‘exploding’.

Inherent Instabilities

I was certain I had a bug, but I couldn’t find it. While debugging, at one point I decreased the spatial resolution — using less points per unit of space to describe the function… and the problem was gone! So, decreasing the accuracy of my solution actually solved the instability… That was very weird.

Mentioning this to a Ph.D student at the lab, he said this problem sounded familiar to him. And as it turns out, this is a universal problem with PDEs: If the time step is too large compared with the spatial resolution, the amplitude of small waves with short wavelengths quickly increases with time until they dominate the solution. This is due to the way numerical derivatives are calculated. The difficulty here is that the time step needs to be incredibly small, making calculation unfeasible. For some equation, the situation is even worse, as they are unstable for any time step, no matter how small.

For simple PDEs, it is very easy to see this effect by taking the function f to be a wave, and watching what happens to the amplitude over time. You can see a derivation of this result here. For a more in-depth discussion, Numerical Recipes is your friend. This method of analyzing equations is called von Neumann stability analysis.

In Comes Lax

Okay, so I found out not alone, but what can be done to solve this problem? The first thing I tried was to calculate the derivative more accurately. There is a method called Savitzky-Golay, where you fit a polynomial to your function at each point, and calculate the polynomial’s derivative at that point. The brilliant thing is that this whole operation (fit + derive) can be done using a single convolution, which costs a meager O(n log n) of processing time.

So I implemented S-G, only to discover it doesn’t solve the problem. More on that in a future post.

As it turns out, there is an incredibly simple solution due to Lax, which says the following. When advancing the function value to the next time step, you do something like this for each position:

$f[j] = f[j] + \frac { \partial f } { \partial t } [j] * dt$

-
The Lax method says that the f[j] at the right-hand side should be replaced by an average of it’s neighboring cells:

$f[j] = \frac{f[j-1] + f[j+1]}{2} + \frac { \partial f } { \partial t } [j] \; dt$

-
And that’s it! This replacement causes a numerical diffusion that ’sedates’ the unruly waves, causing them to decay instead of explode. The time step used in the simulation still needs to be below some value, but now it decreases linearly with the spatial distance dx, which is much better than before. So Lax saved the day — and that was the end of my first pitfall. This is getting to be quite a long post, so I’ll describe the second problem in another post. Cheers!

Posted in Mathematics, Physics, Uncategorized | 1 Comment »

Test your Math skills

March 17, 2007 – 7:04 pm

Here’s a question that was asked in a recent oral exam for a Master’s degree in Mathematics.

Let $f : [0,1] \rightarrow \mathbb R$ be a real function such that has a limit at each point. Does have at least one continuity point?

Everything you need to solve this question is covered in the first year or so of undergraduate math. Don’t continue reading if you want to try solving it yourself…

Solution. We will show that has a continuity point. has a limit at each point, so let $F : [0,1] \rightarrow \mathbb R$ be a function such that

$\forall x \in [0,1]$ $F(x) = lim_{y \rightarrow x} f(y)$

Lemma.

is continuous.

Proof. Choose some $x_0 \in [0,1]$ . Intuitively, F(x_0)

’s limit, so in a small enough surrounding of x_0

will be close to F(x_0)

. Hence, the limits F(x)

will also be close to F(x_0)

, and thus

is continuous at x_0

.

Formally, let $\epsilon > 0$ . Then there exists $\delta > 0$ such that

$\forall x \in (x_0-\delta,x_0+\delta) \setminus \{x_0\} \; |f(x) - F(x_0)|<\epsilon$

Which means that for all such x

$|lim_{y \rightarrow x} f(y) - F(x_0)|<\epsilon$

$|F(x) - F(x_0)|<\epsilon$
And the Lemma is proved.

Our purpose now is to show that there is a point

such that

. Let’s count the points of

that are ‘far away’ from the limit

. Choose some $\epsilon>0$ and define the set:

$A_\epsilon = \{ \, x \, | \, f(x) \, > \, F(x) + \epsilon \, \}$

Lemma. $A_{\epsilon}$ is finite.

Proof. Suppose $A_{\epsilon}$ is infinite, then because [0,1]

is compact we can find a series $\{x_n\} \subset A_\epsilon$ such that $x_n \longrightarrow x_0$ and $x_n \neq x_0$ for some $x_0 \in [0,1]$ .

Therefore, $f(x_n) \longrightarrow F(x_0)$ . But for large enough , we must have

$f(x_n) \, > \, F(x_n) + \epsilon \, > \, F(x_0) + {\epsilon \over 2}$
where we have used

’s continuity at x_0

. Thus we reach a contradiction, and $A_\epsilon$ must be finite.

Now let’s take $A = \bigcup_{n=1}^{\infty} A_{1/n}$ . Then from the lemma we have that A is an enumerable set. A also contains all the points for whom $f(x) \, > \, F(x)$ .

Likewise we can define

$B_\epsilon = \{ \, x \, | \, f(x) \, < \, F(x) - \epsilon \, \}$
$B = \bigcup_{n=1}^{\infty} B_{1/n}$

And together with A we find that

$A \cup B = \{\, x \, | \, f(x) \, \neq \, F(x) \, \}$
But $A \cup B$ is enumerable, so $[0,1] \setminus (A \cup B) \neq \emptyset$ , so there exists a point $x_0 \in [0,1]$ such that f(x_0) = F(x_0)

is a continuity point for

.

QED

Posted in Mathematics | No Comments »

Recommended Todo web app: Vitalist

February 21, 2007 – 5:44 am

I’ve been looking for a good application to manage todo lists — or Getting Things Done (GTD) as it’s called these days. I have been using Remember The Milk but found it annoying. Yesterday I discovered Vitalist and, well, I was blown away. It’s as though they had found a way to read my mind, searched through all the junk, collected any thought I ever had about The Perfect Todo Application, and then went ahead and materialized the whole thing in the form of a sleek web app, adding some brilliant ideas in the process. Brilliant.

So what’s the big deal about a todo app? For starters, It has a simple and effective workflow concept behind it: New todos usually go into the Inbox. Adding a todo is quick and painless. It can be done using the app, or you can send in the item by email. So for example if you’re somewhere listening to the radio, and you hear a song you’d like to download later, you can use your phone to send in an item that says ‘download that song’ — and it’ll show up in you Inbox. Neat, huh?

The next step is to catalog the items in the Inbox. Here you have several options:

Contexts: Catalog items by the context they should be performed in. For example, create a @Phone context that includes all items that require making a phone call. Then, when you’re at a phone, you can quickly look these up.
Projects: Just a simple grouping of items into projects. Contexts and Projects are orthogonal: Any item can belong to both a project and a context.
Waiting: Items that you delegate to someone else go into the ‘Waiting’ state until that person gets back to you.
Someday: Stuff you want to do someday but not right now. Vitalist will remind you every once in a while about these.
Reference: Little bits of information you want to store somewhere. For example, when I order heating gas for my apartment they give me a confirmation number for the order. I never know where to put it. Now I can just tap the number into my phone and email it to my Inbox. The next time I’m at a computer, I’ll move the item into the Reference list for keeps.

After GMail, this is definitely my ‘best web app around’.

Posted in Software, Personal | 1 Comment »

Poof and Foop

January 9, 2007 – 11:55 pm

This BoingBoing article raises the following question: (see the link for a nice illustration)

If a can of compressed air is punctured and the escaping air blows to the right, the can will move to the left in a rocket-like fashion.
Now consider a vacuum can that is punctured. The air blows to the left as it enters the can. After the vacuum is filled the can will

a. be moving to the left
b. be moving to the right
c. not be moving

What a great question! To clarify the problem, let’s say we don’t just puncture the right wall, but remove it altogether. So at t=0 we have a vessel with a left wall but without a right wall, and with vacuum inside. What happens next is pretty straightforward: gas molecules are hitting the left wall from the outside of the vessel, thus exerting a force to the right. No molecules are hitting the vessel from the right however, so we have a net force to the right. Hence at t=0 the vessel accelerates to the right.

The acceleration continues as the gas fills the vessel, until the first molecules that entered the vessel begin hitting the left wall — this time from the inside. The process of filling the vessel takes a finite amount of time, and therefore at the end of it the vessel is moving to the right with velocity V.

But that’s not the end of the story. Suppose the vessel is now completely filled with gas from the outside, so we have the same particle density with the same velocity distribution hitting the left wall from the inside as from the outside, and the vessel as a whole is moving to the right. To understand what happens next, let’s look at matters from the vessel’s point of view.

So we’re sitting on the vessel, completely still, and watching particles hitting our wall from the left and from the right. Whenever a particle hits the wall, we see it completely reverse its velocity and momentum. The vessel absorbs the difference in momentum and accelerates. But from our point of view, the particles to our left are slower than the ones to our right! That’s because, in the original frame of reference, the vessel is moving to the right — i.e. toward the particles on the right, and away from the particles on the left. As a result, the particles on the left are depositing less momentum with each hit on the wall — in other words, they are exerting a weaker force than those particles on the right.

We’ve shown that F<F’, so we have a net force to the left — slowing the vessel down. The slowing down will continue until V=0, at which time F=F’ and the process is complete. So the answer is that at the end of the process, the vessel isn’t moving, but is positioned to the right of its original position.

Oh, and One Last Thing :). If you haven’t already, go feast your eyes on the iPhone. The revolution has come!

Posted in Physics | No Comments »

Why Quantum Gravity?

December 6, 2006 – 5:22 am

One of the hot research topics in theoretical physics today is quantum gravity. While physicists already figured out how to treat the rest of the basic forces in nature quantum mechanically, gravity is proving to be more difficult in this respect. One may ask, why bother? Why can’t we just live happily with our existing classical description of gravitation, namely general relativity? After all, there is no experimental evidence that gravity acts differently on small scales.

I’ll give my view on this in a minute, but please take it with a grain of salt, me being a mere undergrad and all

Most problems nature presents us with are too complicated for us to solve. If we are ever to solve anything, we must make our models as simple as possible: Take into account only those aspects of the system that are absolutely essential to describe the phenomena we are interested in. Otherwise, the models will lie beyond that tiny region of mathematics that we know how to handle. Deciding which parts to keep and which to throw out is a guessing game, and sometimes we get it wrong. One of the clues that we got it wrong is the appearance of a singularity: A region of the problem where the model breaks down, and fails to provide a solution.

There are several examples. One is the ultraviolet catastrophe in blackbody radiation, which provided evidence that classical physics was insufficient, and which also showed that quantization might be a good way of looking at things. Another example, I believe, is from hydrodynamics, where viscosity (internal fluid friction) is sometimes introduced to get rid of singularities.

So what does this have to do with quantum gravity? Well, our classical description of gravity, general relativity, contains singularities. One such singularity occurs at the beginning of time — the big bang. Einstein’s equations allow us to calculate what happened right after the big bang, but they don’t tell us what went on prior to it. They sort of break down.

Judging from history, this suggests that general relativity is not a complete description of gravity–that something is missing. And betting on quantum gravity as that something seems to me a pretty good bet, seeing how we were able to solve similar problems we had with the other forces using this method.

I’d like to thank prof. Oded Agam from the HU, whose discussion of singularities in physics during a recent colloquium led me to this post

Posted in Physics | No Comments »

Fermi Questions

November 16, 2006 – 11:29 pm

Just found this nice list of Fermi questions. According to this Science Olympics site, A “Fermi question” is a question in physics which seeks a fast, rough estimate of quantity which is either difficult or impossible to measure directly.

Here’s a nice question from the list:

If the mass of one teaspoon of water could be converted entirely into energy in the form of heat, what volume of water, initially at room temperature, could it bring to a boil? (litres).

Let’s see now. First, how much energy would we get by converting a teaspoon of water into heat? By far the largest contributor would be the rest mass of the water. The mass/energy conversion ratio is given by E=mc^2 . A teaspoon contains a few grams of water, say 4 grams. So the amount of heat we get from it is:

$E_{teaspoon} = 4_{gr} (3 * 10^8_{m/s})^2 = 36 * 10^{-3}_{kg} * 10^{16}_{m^2/s^2} = 3.6 * 10^{14} _J$

Where J stands for Joule. 1 Joule is about 0.25 kilo-calories. Next, how much energy do we need to invest to boil 1 litre of water starting at room temperature? First, we need to heat the water from about 20 degress celsius to 100 degrees. Raising the temperature of 1 gram of water by 1 degree celsius takes about 4 Joules. So to heat 1 litre:

$E_1 = 4_{J/gr K} * 80_{K} * 1_{kg} = 3.2 * 10^5_J$

(K means Kelvin, which is for our purposes the same as degrees celsius)

But that’s just half the story. Once we’re at 100 degrees, transforming the water from liquid to gas requires an additional investment of energy, known as latent heat. This has nothing to do with temperature — the temperature doesn’t change at all during the process of vaporization itself. For water at 100 deg celsius, the latent heat for vaporization is about 2 kJ/gr. So to vaporize 1 litre of water we need:

$E_2 = 2 * 10^3_{J/gr} * 1_{kg} = 2 * 10^6_J$

Clearly the latent heat is the important factor here. So, the energy required to boil a litre of water is $E_{boil} = E_1 + E_2 = 2.3 * 10^6_J$ . Hence, the energy in our teaspoon can be used to boil this many litres:

$E_{teaspoon}/E_{boil} = 1.5 * 10^8$

Or about 150 million litres. To put that number in perspective, let’s measure the water volume in olympic swimming pools. i.e. how many olympic pools can a single teaspoon of water evaporate? According to this site, an olympic pool holds

$50_m * 25_m * 2_m = 2.5 * 10^3 * 10^6_{cm^3} = 2.5 * 10^6_{litre}$

of water. Therefore, a teaspoon-worth of water can vaporize about 60 olympic swimming pools!

Posted in Physics | No Comments »

Continuous Compound Interest

November 11, 2006 – 9:01 pm

Long time no blogging! A lot has happened since my last post. I got married, was out on a honeymoon, left my job and returned to school to finish my degree. But now I’m back, so read on and enjoy!

We were in the office a while back, and we started talking about compound interest. You can calculate compound interest over different time intervals: Yearly, monthly, weekly, and so on. What will happen if we take the limit as the interval approaches zero, i.e. use continuous time? How much interest will we get?

Read the rest of this entry »

Posted in Mathematics | No Comments »

Hypercubes and Hamilton Circuits

September 24, 2006 – 12:56 am

The Ising model is a simple model used to describe a magnet: It consists of a grid of spins. Each spin can be thought of as a tiny magnet, and can have the value +1 or -1 (called ‘up’ and ‘down’). Two neighboring spins interact, having positive energy if they are in opposite directions (e.g. up and down), and negative energy if they are in the same direction. So, neighboring spins ‘want’ to be in the same direction, to minimize energy.

This model is used to calculate various properties of magnets. For example, suppose we want to measure the average magnetization of the grid in a given temperature. The magnetization of a specific state is just the sum of all the spin values in that state. So if all the spins are up and the grid size is 5×5, the magnetization is 25. To calculate the average magnetization, we’d have to know the probability of each state. We’d then multiply each state’s magnetization by the probability of reaching that state, and sum over all the states. The probability distribution is given by the Maxwell-Boltzmann distribution, an important result of statistical physics.

If the grid size is sufficiently small (up to about 5×5), we can actually go over all the possible states and calculate an accurate average value for the magnetization. What is the most efficient way of going over all the states? It is very convenient to implement this algorithm by flipping just one spin at a time. In this case, the most efficient algorithm would iterate over the possible states by flipping just one spin in each step.

Let’s think of a state as a series of bits, 0 meaning a spin value of ‘down’ and 1 meaning a spin value of ‘up’. We can think of this series as a binary number, and iterate the states by incrementing this number. For example, if the grid size is 2×2, then we can iterate as follows: 0000, 0001, 0010, 0011, 0100, … This method works, but it takes more than one spin to switch states (on average). For example, going from 0111 to 1000 requires 4 flips. It is easy to see that the average number of flips per step for a series of length n is approximately:

$<flips/step> \approx \frac{1}{2^n} \sum_{k=0}^{n-1} \frac{2^n}{2^k} = 2(1-2^{-n}) \to 2$

With the limit taken as $n \to \infty$ .

Let’s try to improve on this. In a previous post, I noted that we can think of a hypercube’s vertex as a series of bits. So iterating over all the spin states is like walking on a hypercube, visiting all of its vertices. We want to flip just one spin at each step — that would be the most efficient algorithm. In the hypercube analogy, this is the same as saying we are allowed to walk only on the graph’s edges, because edges only connect vertices that differ by exactly one bit. So now we’re trying to find an algorithm that walks the edges of a hypercube, vists all the vertices, and vists each vertex exactly once. This is almost the definition of a Hamilton circuit, except we don’t have to go back to the first vertex at the end.

Trying it out for a 3D cube, it’s obviously very easy to do this: We can start at the top face and walk through the 4 vertices there. Then we can ‘climb down’ to the bottom face, and finish walking through the bottom 4 vertices. We can generalize this concept inductively: Given such an algorithm for an (n-1)-hypercube, we can use it to build an algorithm for an n-hypercube: Start with the vertex 0000…0, and use the (n-1) algorithm to go over all the 0xxx..x vertices. Let’s say the algorithm finishes at vertex 0111…1. Next, ‘climb up’ to vertex 1111…1, and run the (n-1) algo. backwards to go through all the ‘upper’ states, reaching 1000…0. We can even complete a full Hamilton cycle by climbing back down to 0000…0.

Of course, we have an algorithm for n=0, so inductively we get an algorithm for every n. This algorithm goes over all the states, using just one flip (or edge) for each step.

When I told my girlfriend about my discovery, she told me this was a well-known method called Gray code. Party pooper.

Posted in Mathematics | No Comments »

4by12

aMule Hacking

Fwd: Spread this number

Fun with PDEs

PDE Primer

Pitfall 1: Exploding Waves

Inherent Instabilities

In Comes Lax

Test your Math skills

Recommended Todo web app: Vitalist

Poof and Foop

Why Quantum Gravity?

Fermi Questions

Continuous Compound Interest

Hypercubes and Hamilton Circuits

Subscribe

Recent Comments

Recent Posts

Archives

Categories

Math blogs

Physics blogs

Tech blogs

Meta