I Need Moore(less) Chips

Question

If you wanted to compute a very large long problem, that on a machine that you could buy today for an inflation adjusted price, will take some amount of years/decades. The issue is, if you only have that budget, and so can only purchase one machine. So if you purchase the machine now, it may actually take longer to compute than if you purchase one later, for the same inflation adjusted price, because of Moore's Law.

Moore's law states that machines will double in everything every two years, so, theoretically, a problem that takes m years to compute now, will only take m/2 years 2 years from now. The question is, how long should I wait to buy the machine, if I need to compute a problem that takes m years to compute, to get the optimal time of computation, which is inclusive of the time waited to buy the machine, and how much time does it take?

It is assumed both that I gain no money, and make just enough interest on my money to beat inflation, but no more, and also that Moore's Law continues ad infinitum.

some examples:

years	time-to-wait	time-it-takes
0 years	0 seconds, buy now!	0 years
1 year	0 seconds, buy now!	1 year
2 years	0 seconds, buy now!	2 years
3 years	0.1124 years	2.998 years
4 years	0.9425 years	3.828 years
5 years	1.5863 years	4.472 years
7 years	2.557 years	5.443 years
8 years	2.942 years	5.828 years
10 years	3.586 years	6.472 years
20 years	5.586 years	8.472 years
100 years	10.23 years	13.12 years
1000000 years	38.81 years	takes 39.70 years

Code-golf, so shortest answer wins.

Desmos example text:

f\left(t\right)=N\cdot\left(\frac{1}{2}^{\frac{t}{2}}\right)+t

Answer 1

Wolfram Language (Mathematica), 29 bytes

{y+#/2^(y/2),y>0}~Minimize~y&

Try it online!

Returns {time-it-takes, {y->time-to-wait}}.

There's a built-in. All is well.

Answer 2

JavaScript (ES7), 52 bytes

f=eval(`
with(Math)a=>[b=max(0,log2(a*LN2)*2-2),b+a/2**(b/2)]
`)

<input oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 2 bytes thanks to @Samathingamajig.

Answer 3

x86 64-bit machine code, 30 bytes

D9 EA D8 C0 D9 E8 DB 2F DB F2 72 0D D8 F2 D9 F1 D8 C0 D9 C9 D8 C1 DB 3F C3 DE D9 D8 E0 C3

This takes in RDI a pointer to a double-extended-precision floating-point number, used both for the input \$m\$ and for the output of total time taken, and returns the waiting time on the FPU register stack.

Try it online!

Letting \$x\$ be the running time in years, the total time is \$ 2\log_2(m/x) + x \$. The derivative of that is \$ \frac{2}{\ln(2)} \frac xm \frac{-m}{x^2} + 1 = \frac{-2}{\ln(2)x} + 1 \$, which is zero when \$ x = \frac{2}{\ln(2)} = 2\log_2(e)\$. Therefore, that is the optimal value if it is valid – if \$m\$ is at least that value.

In assembly:

f:  fldl2e                  # Push log_2(e) onto the FPU register stack.
    fadd st(0), st(0)       # Double it by adding it to itself.
    fld1                    # Push 1 onto the FPU register stack.
    fld TBYTE PTR [rdi]     # Push m onto the FPU register stack.
    fcomi st(0), st(2)      # Compare m and 2*log_2(e).
    jb low                  # Jump if m < 2*log_2(e).
    fdiv st(0), st(2)       # Divide m by 2*log_2(e).
    fyl2x                   # Taking the top two values (m/(2*log_2(e)), 1) as (x, y),
                            # replace them with y*log_2(x).
    fadd st(0), st(0)       # Double the result, getting the waiting time.
    fxch st(1)              # Exchange values, moving 2*log_2(e) to the top.
    fadd st(0), st(1)       # Add the waiting time to 2*log_2(e) for the total time.
    fstp TBYTE PTR [rdi]    # Store that at the address and pop it off the stack.
    ret                     # Return.
low:
    fcompp                  # Compare the two values on top of the stack and pop both.
    fsub st(0), st(0)       # Subtract the remaining value from itself, producing 0.
    ret                     # Return. (The value at the address is unchanged.)

Answer 4

Jelly, 16 bytes

2Æl2÷«ɓ÷l2Ḥ»0,+¥

A monadic Link that accepts a positive number, m years, and yields a list of two numbers, [wait, total] in years.

Note: Input is strictly positive - inputting 0 will yield [nan, nan] which is technically true as one cannot do anything in zero time.

Try it online!

How?

2Æl2÷«ɓ÷l2Ḥ»0,+¥ - Link: number, M
2                - two
 Æl              - natural logarithm
   2÷            - two divided by that
     «           - minimum with M
      ɓ          - start a new dyadic chain - f(M, CalculationTime=that)
       ÷         - M divided by CalculationTime
        l2       - log-base-two
          Ḥ      - halved
           »0    - maximum with zero
               ¥ - last two links as a dyad - f(WaitTime=that, CalculationTime)
              +  -   WaitTime add CalculationTime = TotalTime
             ,   -   WaitTime paired with that -> [WaitTime, TotalTime]

Answer 5

C (GCC), 79 77 bytes

-2 bytes thanks to @Neil

f(x,r)double*r,x;{r[1]=(*r=fmaxl(0,2*log(x*log(2)/2)/log(2)))+x/pow(2,*r/2);}

Attempt This Online!

Answer 6

Wolfram Language (Mathematica), 35 bytes

- a lot from ATT

2{a=Ramp@Log2[Log@2#/2],a+#/2^a/2}&

Try it online!

---

Explanation:

2 Take twice

{a=Ramp@ zero or

Log2, the base-2 logarithm

Log@2 of the natural logarithm of 2

# times the input

/2] divided by two.

, a Then, output this

+#/ plus the input divided by

2^a two to the power of the variable,

/2}& all divided by two.

Answer 7

JavaScript (V8), 87 bytes

s=(n,x=3,i=999,l=Math.LN2)=>i?s(n,x+2/l-2**(x/2+2)/n/l/l,i-1):[x=x>0?x:0,n*.5**(x/2)+x]

Try it online!

Returns both time-to-wait and time-it-takes. You could remove 1 byte to make it less precise at higher values, as 86 fits all test cases, but the problem does not tell a range you have to be precise to.

This uses Newton's Method on the first derivative of the function given to find the minimum.

Pre-golfed code: (derivatives found with WolframAlpha)

const f=(x,n)=>n*.5**(x/2)+x; // f(t)
const g=(x,n)=>1-n*2**(-x/2-1)*Math.LN2; // f'(t)
const h=(x,n)=>2**(-2-x/2)*n*Math.LN2**2; // f''(t)

const solution = n => {
  let x = 3; // arbitrary number that seems to work
  for (let i = 0; i < 999; i++) {
    // console.log(x);
    x = x - g(x,n)/h(x,n);
  }
  x = Math.max(0,x);
  return [x, f(x,n)];
}

Answer 8

05AB1E (legacy), 20 bytes

žr.²/.²·Í¾‚àÐ;oIs/+‚

Port of @Neil's JavaScript answer.

Uses the legacy version of 05AB1E, because apparently o (\$2^a\$ builtin) doesn't work for zero as float (0.0)..

Try it online or verify all test cases.

Explanation:

žr                   # Push builtin e
  .²                 # Take the base-2 logarithm of it
    /                # Divide the (implicit) input-integer by this
     .²              # Get the base-2 logarithm of that again
       ·             # Double it
        Í            # Decrease it by 2
         ¾‚          # Pair it with 0
           à         # Get the maximum of this pair
            Ð        # Triplicate this maximum
             ;       # Halve the top copy
              o      # Push 2 to the power this
               Is/   # Push the input, and divide it by this value
                  +  # Add it to the other maximum-copy
                   ‚ # Pair it with the remaining maximum
                     # (after which this pair is output implicitly as result)

Answer 9

Python 3.8 (pre-release), 73 70 bytes

from math import*
lambda a:[b:=log2(max(a*log(2),2))*2-2,b+a/2**(b/2)]

Try it online!

• -3 Thanks to att, since