3
\$\begingroup\$

This is a code challenge, from Codewars, the details of the specific challenge in depth can be found here: https://www.codewars.com/kata/magnet-particules-in-boxes/javascript.

The summary of it though is a function which gives a sum of particles in a set of boxes given a number of rows and a number of columns to work with. You are given a specific function that calculates the number of particles in the box based off of the specific box that is being calculated. Here is the equation:

$$ v(k,n) = \frac{1}{k(n + 1)^{2k}} $$

$$ doubles (k_{max}, n_{max}) = \sum_{k=1}^{k_{max}} \sum_{n=1}^{n_{max}} v(k,n) $$

Here is the function I came up with:

function doubles(maxk, maxn) {

  let total = 0

  for(let k = 1; k <= maxk; k++){
    const twoK = 2*k
    for(let n = 1; n <= maxn; n++){
      total += 1/(k*Math.pow(n+1, twoK))
    }
  }

  return total
}

My function does the job perfectly, and comparing it to other responses marked as 'best practices' it is very similar. But I would like to know if anyone sees obvious ways to improve my function, or I would really love to see something that can improve the time complexity of the function, if that is possible.

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

Inside the inner loop, \$1/k\$ is a constant term. So you could extract that multiplication from the inner loop, and apply it on the computed subtotal. This won't change the order of complexity though.

I was wondering if there is a closed form for computing the sum of reciprocal powers (to replace the summing and thereby speed things up), but I couldn't find.

I was also wondering if you inverted the direction of computations to sum by columns instead of summing by rows, would there be a closed form to replace the summing, but I couldn't find that either.

Other than some clever math optimizations, the computation by rows or columns could run in parallel, but the input parameters would have to be large enough to be worth the overhead.

\$\endgroup\$

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.