Extremely silly math musing

[cnoocy]

Question:
If the popular version of Moore's law (computing speed increases by a factor of 2 every 18 months) were to apply continuously,(which it doesn't) at what point does a process become not worth hitting start on.

That is, if I have a program that takes 80 years to run, I shouldn't start it now. I can get it done in 23 years by waiting 3 years, at which point the program will only take 20 years. So at what point (expressed as current time to completion) should I hit start?

I have an answer, but I'd like someone to check my math. So if you're interested in trying it yourself, do so before clicking on the cut-tag.


My thinking:

So, the time to complete the project can be expressed in years as:
y = x + T / 2 ^(x/1.5)
where
T = the time it takes at time 0
and
x = the time at which it is started.

We (okay, I, since you're not insane) want the value of T that puts the minimum of y at x=0. The minimum of this function occurs when the slope of y=x and y=T/2^(x/1.5) balance each other out.
d(T/2^(x/1.5))/dx - dx/dx = 0
d(T/2^(x/1.5))/dx = -1
which gets me (via calculus I had to look up again) to
(-2T*ln(2)/3)*(2^(-2x/3) = -1
but since we're interested in x=0, we get
1* -2T*ln(2)/3 = -1
T = 3/2*ln(2)

T = 2 years and just under 59 days.

So don't hit go until the ETA is two years and two months away.
(does quick check)
At which point the speed will have increased by e. That seems right.
I wonder if there's a shorter way to get to that result.

Comments

[dougo.livejournal.com]

Guy Steele gave a talk at the MIT AI Lab a few years ago about solving a board game called Teeko. The problem was posed in 1972 but it didn't become feasible to solve (via brute force) until 1998. Unfortunately the talk doesn't seem to be online anywhere, but I remember it having a joke about using Moore's Law to solve an exponential problem in polynomial time.

Also, hi! I only just now figured out who you (and other JBPers with non-obvious LiveJournal userids) are. You were right about the stomach flu warning, by the way. :(

[cnoocy]

Thanks, and welcome. I hope you got through the mental weirdness phase okay. Are you off Gatorade yet?

[dougo.livejournal.com]

Mental weirdness is right... Fever dreams about being stumped on a puzzle are not much fun. But then fever dreams aren't much fun in general. Still, it may be a while before I can look at a puzzle and not feel a little queasy.

By the time I had enough energy to drive down to Brooks to pick up some Gatorade, I was probably past the point of needing it, although it was refreshing. Maybe I should just always keep a few bottles around for emergencies.

[libskrat]

Does this assume that there is no way to reap any benefits from Moore's Law once you've started your project?

Because if you can swap out part of your system (say, in a grid) while you're running, you want to start now no matter what the speed will be henceforth.

Or have I missed something?

[cnoocy]

Yes, this does assume that you have to complete the project on the exact same hardware on which you began it. In a constantly updated grid, your completion time will be some limit or series of the T/2^(x2/3) stat. It's not a particularly realistic problem, just a mathematical diversion.

[rikchik.livejournal.com]

How do you get that the speed will have increased by e?

[cnoocy]

You're starting it when T = 3/2ln(2). The formula for the time taken by the process is:
T_x = T₀/2^(x2/3)
So:
T_x = T₀/2^((3/2ln(2))2/3)
T_x = T₀/2^(1/ln(2))
So the speed has increased by 2^(1/ln(2)), which is e.

[rikchik.livejournal.com]

Your post said that T_x, not x, was 3/2 * ln(2). I don't think you calculated x (which I'm curious about).

[cnoocy]

If you start at time 0, you'll be done T₀ years later, at which point x = T₀.

[rikchik.livejournal.com]

That T₀ is unrelated to your original T₀. How long do you wait to start if you have a problem to solve that will take T₀ time to complete right now?

[cnoocy]

You wait until T_x = 3/2ln(2). If T₀ <= 3/2ln(2), start now.

[cnoocy]

As for a formula, I'm not sure it gets any simpler than 3(log₂(3T/2ln(2)))/2.