Will Any Current 100M Digit LL Tests Finish? - Page 5

retina · 2008-12-22, 01:55

Quote:

Originally Posted by CRGreathouse

I think that only dedicated prime searchers transfer their old GIMPS directories and work-in-progress files to their new computers.

I think only dedicated prime searchers would be testing 100M digit numbers.

CRGreathouse · 2008-12-22, 02:00

Quote:

Originally Posted by starrynte

I'm sure there is a reason, but I can't quite find out how the number 26 is found...

I used nested numerical root-finding (Brent's method), but you could do this a number of different ways. Here's Pari code for it:

Code:

k=-log(2)/1.5;
solve(x=2,3,solve(y=-9,9,1+x*k*exp(k*y)))*12

I restrict x to [2, 3] because I happen to know that's where the answer falls. Likewise, I restrict y to [-9, 9] because I know that at the extreme ends, the optimal starting time will be somewhere between 9 years in the past and 9 years in the future. (That, and 9 is the largest 1-digit number...)

CRGreathouse · 2008-12-22, 02:03

Quote:

Originally Posted by retina

I think only dedicated prime searchers would be testing 100M digit numbers.

I think only foolhardy ones would be. But if we assume that everyone testing a 100M digit number will move the work from computer to computer we are rather begging the question, aren't we? The thread *is* titled "Will Any Current 100M Digit LL Tests Finish?", after all.

jinydu · 2008-12-22, 02:11

Quote:

Originally Posted by starrynte

I'm sure there is a reason, but I can't quite find out how the number 26 is found...

Well, let's try to set up an equation.

Say that at time 0, one can buy a computer with speed r (measured in iterations per second, at 20M FFT, the FFT size used for the smallest 100M digit LL tests). The number of seconds needed to complete 100M iterations is then 100,000,000/r.

Now suppose that one instead waits for t seconds and then buys a computer. The computer's speed will be faster by a factor of 2^(t/d), where d is the time needed for computing speed to double, measured in seconds. Thus the number of seconds needed to run the test is 100,000,000/r2^(t/d). Adding in the waiting time, the time at which the test finishes is t + 100,000,000/r2^(t/d) seconds in the future.

Therefore, the problem is to minimize $t+\frac{10^8}{r2^{t/d}}$ as a function of $t$ .

The derivative of the function is $1-\frac{10^8\log(2)}{rd}2^{-t/d}$ , which is positive when $2^{-t/d}<\frac{rd}{10^8\log(2)}$ and negative when $2^{-t/d}>\frac{rd}{10^8\log(2)}$ . So the function is increasing when $t>d\log(\frac{10^8\log(2)}{rd})/\log(2)$ and decreasing when $t<d\log(\frac{10^8\log(2)}{rd})/\log(2)$ .

Therefore, the best time to buy a computer is:

$t=\frac{d}{\log(2)}\log(\frac{10^8\log(2)}{rd})$

If, instead of iterations per second, one wants to express the answer in terms of time needed to finish the test on a current computer (call it T), the answer is:

$t=\frac{d}{\log(2)}\log(\frac{T\log(2)}{d})$

Note that this quantity is positive when $\frac{T\log(2)}{d}>1$ and negative when $\frac{T\log(2)}{d}<1$ . So when $T>\frac{d}{\log(2)}$ , one should wait before starting the test and when $T<\frac{d}{\log(2)}$ , one should have already started the test. Taking $d$ to be 18 months gives $\frac{d}{\log(2)}$ as approximately 25.9685 months, which confirms CRGreathouse's calculation.

The moral of the story is: Start your calculation when the time needed to complete it is $\frac{d}{\log(2)}$ , i.e. when the calculation time is equal to the time needed for computing speed to increase by a factor of $e$ . Interestingly enough, this rule is independent of whether one is running a 1M, 10M, 100M, or 1B digit test, and the actual doubling time of computing speed.

CRGreathouse · 2008-12-22, 02:41

Quote:

Originally Posted by jinydu

Therefore, the best time to buy a computer is:

$t=\frac{d}{\log(2)}\log(\frac{10^8\log(2)}{rd})$

If, instead of iterations per second, one wants to express the answer in terms of time needed to finish the test on a current computer (call it T), the answer is:

$t=\frac{d}{\log(2)}\log(\frac{T\log(2)}{d})$

Right. Then if you solve for the value of T that makes t = 0 (with d = 18 months), you get T = 25.96851... months.

jinydu · 2008-12-22, 03:43

Now consider the more complicated problem in which one is able to upgrade the computer N times. This is evidently more realistic than assuming that one can upgrade continuously.

First of all, note that one should always use up all N upgrades before the test is finished. Obviously, one should always buy a first upgrade at some time (or else the test will never finish) and if not all of the upgrades have been used up, one can always improve the completion date by adding a upgrade sometime between the last scheduled upgrade and the scheduled completion time. So let us assume that the completion time is after $t_N$ .

Taking a hint from the N = 1 case, let us use the time needed for computing speed to increase by a factor of e as our unit of time, and set our clock so that t = 0 a computer bought at t = 0 will finish the test when t = 1.

Then a computer purchased at time t is $e^t$ times faster than a computer purchased at time 0. So for $1\leq{}i<N$ , the amount of computation done, as a proportion of the entire test, is $e^{t_i}(t_{i+1}-t_i)$ . Thus the amount of computation done by the first N-1 computers is $\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i)$ , which had better be less than 1. This leaves $1-\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i)$ for the final computer to do, giving a completion time of $t_N+e^{-t_N}(1-\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i))$ , which we must minimize as a function of $t_1,...,t_N$ .

[Dinner time. Maybe someone else can finish the rest of the derivation.]

jinydu · 2008-12-22, 08:19

[Detour]

Here is the continuous version of the problem.

Suppose that you have a limited budget (1 unit of money) and want to finish an LL test (1 unit of computing work) at the earliest time possible. At each instant of time, one can buy a computer; the computer's speed is proportional to the amount of money one spends. However, because of continual improvements in technology, the constant of proportionality decays exponentially with time. Treating money as a continuous variable, what is the optimum way to distribute the budget?

Note: The answer should be a function that assigns to instant of time the amount of money one is spending at that instant per unit time.

Let us choose our time unit so that the price per unit computing speed decays by a factor of e every time unit. Computing speed (in the natural units) will then be 1 divided by the number of time units needed to complete the test. Let time 0 be the time at which the cost per unit of computing speed is 1. Then the cost per unit computing speed at time t is $e^t$ .

Let f(t) be any "sensible" distribution. Since you should spend all the money eventually, and assuming that you can't sell computing parts at any time, we have the conditions:

$\int_{-\infty}^{\infty}f(t)dt=1$

$f\geq{}0$

The rate at which you are accumulating computing speed at time t is then $f(t)e^t$ . Thus the total computing speed you have accumulated at time t is $\int_{-\infty}^{t}f(v)e^vdv$ and the total amount of work completed at time t is $\int_{-\infty}^{t}\int_{-\infty}^{u}f(v)e^vdvdu$ . We want to minimize the value of t that makes the previous expression equal to 1.

An inverse function and a double antiderivative... This looks even more difficult than the previous problem...

[/Detour]

jinydu · 2008-12-22, 08:54

Anyway, going back to the discrete problem...

In the case N = 2 (which is the case when one can buy a computer and then upgrade once), the completion time is:

$t_2+e^{-t_2}(1-e^{t_1}(t_2-t_1))$

Using the substitution $u=t_2-t_1$ , this becomes:

$t_2+e^{-t_2}(1-e^{t_2-u}u)$
$=t_2+e^{-t_2}-e^{-u}u$

It is now clear that we should minimize $t_2+e^{-t_2}$ (with $t_2$ free to range over all real numbers) and maximize $e^{-u}u$ (with u non-negative) independently.

By the result for N = 1, it is clear that we should take $t_2=0$ .

Meanwhile, the derivative of $e^{-u}u$ is $-e^{-u}u+e^{-u}=e^{-u}(1-u)$ , which is positive when $u<1$ and negative when $u>1$ . So the maximum occurs at $u=1$ .

Therefore, the optimum strategy is $(t_1,t_2)=(-1,0)$ .

CRGreathouse · 2008-12-22, 16:02

Here's my work on the two-computer case. I will borrow notation from jinydu when possible (so the results are easier to compare), but will use a and b rather than t_1, t_2 for the purchase times for the computers to avoid subscripts. I will use d = 18 months, but this should cause no confusion as I will not simplify the constant further -- substitution should be straightforward.

Let F be the time at which computations are finished. The goal is to minimize F. T represents the time needed to finish the test on a current computer.

In the one-computer case, T = (F - a) * 2^(a/18), and so F = a + T / 2^(a/18).

In the two-computer case, T = (F - a) * 2^(a/18) + (F - b) * 2^(b/18) and so
$F=\frac{T+a\cdot2^{a/18}+b\cdot2^{b/18}}{2^{a/18}+2^{b/18}}.$
As a quick double-check, taking the limit of the above as b approaches $-\infty$ gives the one-computer case.

Taking the derivative wrt b (for fixed a) gives
$F'=\frac{(2^{b/18}+\frac{b^2\ln2}{18}2^{b/18})(2^{a/18}+2^{b/18})-(T+a\cdot2^{a/18}+b\cdot2^{b/18})(\frac{b\ln2}{18}2^{b/18})}{\left(2^{a/18}+2^{b/18}\right)^2}$
and setting this to zero gives
$(2^{b/18}+\frac{b^2\ln2}{18}2^{b/18})(2^{a/18}+2^{b/18})=(T+a\cdot2^{a/18}+b\cdot2^{b/18})(\frac{b\ln2}{18}2^{b/18}).$
. . .
Cheating with Mathematica, this makes
$b=a+(2^{-a/18} T \log (2)-18 W\left(\frac{2^{\frac{1}{9} 2^{-\frac{a}{18}-1} T}}{e}\right)-18)/\ln 2$
I don't know how jinydu's solution avoids the use of the W function; it seems that a solution must have this. But regardless, substituting this into the original gives a one-variable minimization problem. Unfortunately, with the W, this doesn't seem to be solvable except numerically.

fivemack · 2008-12-22, 16:54

Quote:

Originally Posted by retina

I think it would be interesting to calculate the required data bus bandwidth needed to do a 6 month 100Mdigit LL test. Assuming perfect synchronisation within the cores and never an idle memory bus cycle I wonder what sort of data rate is required. Very high bandwidths would probably need multiple channels of RAM or ultra wide data bus widths or both.

100Mdigits in six months means you need an iteration time of 0.047 seconds for a size-20M FFT.

I don't know how many memory accesses exactly are required for such an FFT; I'd guess eight runs through the whole data, to split from 160MB of raw input to a 1MB cache size and recombine afterwards. So 1.28GB in 0.047 seconds, 27GB/second - a quarter the speed of the memory on a present-day GTX280, a bit faster than the fastest reports from overclocked Nehalems.

jinydu · 2008-12-22, 17:19

Quote:

Originally Posted by CRGreathouse

I don't know how jinydu's solution avoids the use of the W function; it seems that a solution must have this.

Well I've come up with a more elegant "coordinate system". See posts 50 and 52.

View Poll Results: Will Any Current 100M Digit LL Tests Finish?
Yes	34	73.91%
No	12	26.09%
Voters: 46. You may not vote on this poll

2008-12-22, 03:43	#50
jinydu Dec 2003 Hopefully Near M48 2×3×293 Posts	Now consider the more complicated problem in which one is able to upgrade the computer N times. This is evidently more realistic than assuming that one can upgrade continuously. First of all, note that one should always use up all N upgrades before the test is finished. Obviously, one should always buy a first upgrade at some time (or else the test will never finish) and if not all of the upgrades have been used up, one can always improve the completion date by adding a upgrade sometime between the last scheduled upgrade and the scheduled completion time. So let us assume that the completion time is after $t_N$ . Taking a hint from the N = 1 case, let us use the time needed for computing speed to increase by a factor of e as our unit of time, and set our clock so that t = 0 a computer bought at t = 0 will finish the test when t = 1. Then a computer purchased at time t is $e^t$ times faster than a computer purchased at time 0. So for $1\leq{}i<N$ , the amount of computation done, as a proportion of the entire test, is $e^{t_i}(t_{i+1}-t_i)$ . Thus the amount of computation done by the first N-1 computers is $\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i)$ , which had better be less than 1. This leaves $1-\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i)$ for the final computer to do, giving a completion time of $t_N+e^{-t_N}(1-\sum_{i=1}^{N-1}e^{t_i}(t_{i+1}-t_i))$ , which we must minimize as a function of $t_1,...,t_N$ . [Dinner time. Maybe someone else can finish the rest of the derivation.] Last fiddled with by jinydu on 2008-12-22 at 03:48

2008-12-22, 08:19	#51
jinydu Dec 2003 Hopefully Near M48 11011011110₂ Posts	[Detour] Here is the continuous version of the problem. Suppose that you have a limited budget (1 unit of money) and want to finish an LL test (1 unit of computing work) at the earliest time possible. At each instant of time, one can buy a computer; the computer's speed is proportional to the amount of money one spends. However, because of continual improvements in technology, the constant of proportionality decays exponentially with time. Treating money as a continuous variable, what is the optimum way to distribute the budget? Note: The answer should be a function that assigns to instant of time the amount of money one is spending at that instant per unit time. Let us choose our time unit so that the price per unit computing speed decays by a factor of e every time unit. Computing speed (in the natural units) will then be 1 divided by the number of time units needed to complete the test. Let time 0 be the time at which the cost per unit of computing speed is 1. Then the cost per unit computing speed at time t is $e^t$ . Let f(t) be any "sensible" distribution. Since you should spend all the money eventually, and assuming that you can't sell computing parts at any time, we have the conditions: $\int_{-\infty}^{\infty}f(t)dt=1$ $f\geq{}0$ The rate at which you are accumulating computing speed at time t is then $f(t)e^t$ . Thus the total computing speed you have accumulated at time t is $\int_{-\infty}^{t}f(v)e^vdv$ and the total amount of work completed at time t is $\int_{-\infty}^{t}\int_{-\infty}^{u}f(v)e^vdvdu$ . We want to minimize the value of t that makes the previous expression equal to 1. An inverse function and a double antiderivative... This looks even more difficult than the previous problem... [/Detour] Last fiddled with by jinydu on 2008-12-22 at 08:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
332.2M - 333.9M (aka 100M digit range)	Uncwilly	LMH > 100M	684	2018-07-01 10:52
overclocking an i7-2600 to finish an 100M exponent in less than a year :)	emily	Hardware	4	2013-02-28 20:11
I want a 100M digit Mersenne that....	JuanTutors	PrimeNet	8	2012-12-06 13:47
100M-digit n/k pairs	__HRB__	Riesel Prime Search	0	2010-05-22 01:17
100M digit prime	Unregistered	Information & Answers	10	2010-03-24 20:16

2008-12-22, 08:54	#52
jinydu Dec 2003 Hopefully Near M48 6DE₁₆ Posts	Anyway, going back to the discrete problem... In the case N = 2 (which is the case when one can buy a computer and then upgrade once), the completion time is: $t_2+e^{-t_2}(1-e^{t_1}(t_2-t_1))$ Using the substitution $u=t_2-t_1$ , this becomes: $t_2+e^{-t_2}(1-e^{t_2-u}u)$ $=t_2+e^{-t_2}-e^{-u}u$ It is now clear that we should minimize $t_2+e^{-t_2}$ (with $t_2$ free to range over all real numbers) and maximize $e^{-u}u$ (with u non-negative) independently. By the result for N = 1, it is clear that we should take $t_2=0$ . Meanwhile, the derivative of $e^{-u}u$ is $-e^{-u}u+e^{-u}=e^{-u}(1-u)$ , which is positive when $u<1$ and negative when $u>1$ . So the maximum occurs at $u=1$ . Therefore, the optimum strategy is $(t_1,t_2)=(-1,0)$ .

2008-12-22, 16:02	#53
CRGreathouse Aug 2006 13533₈ Posts	Here's my work on the two-computer case. I will borrow notation from jinydu when possible (so the results are easier to compare), but will use a and b rather than t_1, t_2 for the purchase times for the computers to avoid subscripts. I will use d = 18 months, but this should cause no confusion as I will not simplify the constant further -- substitution should be straightforward. Let F be the time at which computations are finished. The goal is to minimize F. T represents the time needed to finish the test on a current computer. In the one-computer case, T = (F - a) * 2^(a/18), and so F = a + T / 2^(a/18). In the two-computer case, T = (F - a) * 2^(a/18) + (F - b) * 2^(b/18) and so $F=\frac{T+a\cdot2^{a/18}+b\cdot2^{b/18}}{2^{a/18}+2^{b/18}}.$ As a quick double-check, taking the limit of the above as b approaches $-\infty$ gives the one-computer case. Taking the derivative wrt b (for fixed a) gives $F'=\frac{(2^{b/18}+\frac{b^2\ln2}{18}2^{b/18})(2^{a/18}+2^{b/18})-(T+a\cdot2^{a/18}+b\cdot2^{b/18})(\frac{b\ln2}{18}2^{b/18})}{\left(2^{a/18}+2^{b/18}\right)^2}$ and setting this to zero gives $(2^{b/18}+\frac{b^2\ln2}{18}2^{b/18})(2^{a/18}+2^{b/18})=(T+a\cdot2^{a/18}+b\cdot2^{b/18})(\frac{b\ln2}{18}2^{b/18}).$ . . . Cheating with Mathematica, this makes $b=a+(2^{-a/18} T \log (2)-18 W\left(\frac{2^{\frac{1}{9} 2^{-\frac{a}{18}-1} T}}{e}\right)-18)/\ln 2$ I don't know how jinydu's solution avoids the use of the W function; it seems that a solution must have this. But regardless, substituting this into the original gives a one-variable minimization problem. Unfortunately, with the W, this doesn't seem to be solvable except numerically.