Find numbers that are both Triangle numbers and Square numbers

Question

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?

• Peter Taylor: 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.
• Paras: Surely! But I want to improve the algorithm....the numbers are not an issue :P

Answer 1

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.

• Simon Forsberg: 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.
• Pimgd: @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.
• Simon Forsberg: Oh, right, in that case I'd recommend to name it triangleSum or something like that. I didn't realize that connection.
• Pimgd: @SimonForsberg my variable names are poorly chosen, yeah... fixt
• Paras: That's a clever workaround, I didn't realize this relation between triangle nunbers .... thanks!