0
\$\begingroup\$

I've written a simple JavaScript function to find numbers that contain both the attributes of a Triangle (\$ n(n+1)/2 = x \$) and a Square (\$ n^2 = x \$) number.
The challenge was given in Matt Parker's Things to Make and Do in the Fourth Dimension.

function main() {
  for (var i = 1; i < 1000000; i++) {
    var triangled = ( i * ( i + 1 ) ) / 2;
        if(Math.sqrt(triangled) % 1 === 0) {
         // print
      }
  }
}

Here's the JSFiddle of the same.

The algorithm n = 1000000 takes about ~35ms but gets considerably slower with higher values

~300ms for n = 10000000

~3000ms for n = 100000000

The only priority is performance. Any tips?

\$\endgroup\$
  • \$\begingroup\$ Have you tried Googling your title? When I Google it, the top hit is a Wikipedia page which contains more than enough information to get outside the range of JS numbers in a matter of milliseconds. \$\endgroup\$ – Peter Taylor Jul 15 '16 at 10:09
  • \$\begingroup\$ Surely! But I want to improve the algorithm....the numbers are not an issue :P \$\endgroup\$ – Paras Jul 15 '16 at 10:10
1
\$\begingroup\$

First, I tried to be mathematically clever (by trying something with the odd and evenness of triangular and square numbers). That resulted in me making a mistake and getting a bogus result.

Then I took a good look at your code. You are calling Math.sqrt for every iteration. That's really slow, so if we could work around that, it'd be a huge performance boost. And we can work around it, by keeping track of the next target to hit.

Additionally, if we're gonna pass every integer anyway, why don't we add them as we go, rather than constantly recalculation triangle? A triangular number consists of all the whole positive integers at or below N, so by simply summing as we go, we can keep a calculated triangular number in memory without the need to recalculate every iteration.

The resulting code...

function main() {
var timer = Date.now();
  var triangleSum = 0;
  var productCounter = 1;
  var product = 1;
  for (var i = 1; i < 100000000; i++) {
    triangleSum += i;
    if(triangleSum === product)
    {
        document.getElementById('log').innerHTML += '<p>' + Math.sqrt(triangleSum)+ ' and ' + i + ': ' + triangleSum + '</p>';
    }
    if(triangleSum >= product)
    {
        productCounter++;
        product = productCounter * productCounter;
    }
  }
  document.getElementById('log').innerHTML += '<p><b>Time taken: ' + (Date.now() - timer) + ' milliseconds</b></p>';
}

Runs in 380 ms compared to the 5346 ms it was giving me before.

\$\endgroup\$
  • \$\begingroup\$ Have you checked to make sure it returns the same results? I don't quite follow how this works, and I don't see any calculations of triangular numbers in this code. \$\endgroup\$ – Simon Forsberg Jul 15 '16 at 12:45
  • \$\begingroup\$ @SimonForsberg a triangular number N is 1 + 2 + 3 + ... + N. So summing from 1 to N gives you the triangular number... which is what I'm doing here. \$\endgroup\$ – Pimgd Jul 15 '16 at 12:55
  • 1
    \$\begingroup\$ Oh, right, in that case I'd recommend to name it triangleSum or something like that. I didn't realize that connection. \$\endgroup\$ – Simon Forsberg Jul 15 '16 at 12:56
  • \$\begingroup\$ @SimonForsberg my variable names are poorly chosen, yeah... fixt \$\endgroup\$ – Pimgd Jul 15 '16 at 12:57
  • \$\begingroup\$ That's a clever workaround, I didn't realize this relation between triangle nunbers .... thanks! \$\endgroup\$ – Paras Jul 18 '16 at 1:57

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.