5
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ What's the acceptable I/O? Input as integer years, and return two float/doubles, or do you want string parsing and formatted returns as well? Also in your table, the bottom right entry is formatted differently from the rest. \$\endgroup\$ May 7 at 19:41
  • \$\begingroup\$ No formatting necessary, float/double input, and float or double output \$\endgroup\$
    – LWS SWL
    May 7 at 20:03
  • \$\begingroup\$ I believe time-to-wait of 1000000 years is off by 2 -> 36.81, not 38.81 \$\endgroup\$ May 7 at 20:21
  • 1
    \$\begingroup\$ We're supposed to return both time-to-wait and time-it-takes, right? \$\endgroup\$ May 7 at 21:14
  • \$\begingroup\$ What's the maximum N we have to be precise to and to what ±x%? \$\endgroup\$ May 7 at 22:10

9 Answers 9

2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Wow. I have an 87 byte solution I've been working on for about 2 hours using Newton's method, but this is clearly better \$\endgroup\$ May 7 at 21:13
  • \$\begingroup\$ Based on the wording of the question, "how long should I wait to buy the machine ... and how much time does it take", you need to return both time-to-wait and time-it-takes \$\endgroup\$ May 7 at 21:54
  • \$\begingroup\$ You don't need any of those newlines btw \$\endgroup\$
    – Steffan
    May 7 at 22:03
  • \$\begingroup\$ You actually don't even need eval, just do with(Math)f=a=>max(0,log2(a/LOG2E)*2-2) \$\endgroup\$
    – Steffan
    May 7 at 22:06
  • 5
    \$\begingroup\$ @Steffan The byte count is for the second line only. The rest just makes it easier to test. \$\endgroup\$
    – Neil
    May 7 at 22:06
1
\$\begingroup\$

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.)
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Do you need the ()s around *r/2? \$\endgroup\$
    – Neil
    May 9 at 12:51
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 35 bytes. When golfing you don't need to worry about localizing variables (usually), Ramp is Max[0,#]&, Log2 exists, use a few logarithm transformation rules, and finally double after everything else so you don't need to parenthesize (a/2). \$\endgroup\$
    – att
    May 9 at 22:32
  • \$\begingroup\$ Wow. I guess if you put it in a list, the Slots still apply and you can get rid of the Block? \$\endgroup\$
    – Romanp
    May 10 at 13:16
  • \$\begingroup\$ Slots work anywhere inside a pure function. Also, #/2^a/2 is \$\left.\frac{\texttt{#}}{2^a}\right/2\$, not \$\frac{\texttt{#}}{2^{a/2}}\$. \$\endgroup\$
    – att
    May 10 at 17:27
0
\$\begingroup\$

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)];
}
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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 1/(log_a(b)) == log_b(a)
\$\endgroup\$
1
  • \$\begingroup\$ You don't need to count the f=, and /log2(e) -> *log(2) for -3. \$\endgroup\$
    – att
    May 9 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.