Profile

cnoocy: green a-e ligature (Default)
(boing!) Cnoocy Mosque O'Witz

Expand Cut Tags

No cut tags
cnoocy: green a-e ligature (Default)
[personal profile] 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.

Date: 2004-01-22 09:02 am (UTC)
From: [identity profile] 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. :(

Date: 2004-01-23 04:13 am (UTC)
From: [identity profile] 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.

Date: 2004-01-22 10:19 am (UTC)
libskrat: (Default)
From: [personal profile] 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?

Date: 2004-01-22 11:34 am (UTC)
From: [identity profile] rikchik.livejournal.com
How do you get that the speed will have increased by e?

Date: 2004-01-22 12:12 pm (UTC)
From: [identity profile] rikchik.livejournal.com
Your post said that Tx, not x, was 3/2 * ln(2). I don't think you calculated x (which I'm curious about).

Date: 2004-01-22 12:27 pm (UTC)
From: [identity profile] rikchik.livejournal.com
That T0 is unrelated to your original T0. How long do you wait to start if you have a problem to solve that will take T0 time to complete right now?

Most Popular Tags

Style Credit

Page generated Jun. 14th, 2025 11:53 am
Powered by Dreamwidth Studios