Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Generate cuboids with integer sides and diagonals: how to improve the time complexity?

I quickly wrote this code to test when all sides and diagonals of a cuboid a,b,c,d,e and f are all integers. It seems to work just fine but it takes way too much time for higher and higher values to loop through (for ex 10000+).

Is there any way to make this code run faster ? or maybe someway to get rid of that nasty three nested for loops ?

I thought of a few ways to reduce the complexity of this code but it doesn’t go through all combinations which is something I want to happen.

const generate_good_cuboid = () => {
  let good_couples = [];
  let couples = [];
  for (let a = 1; a < 10000; a++) {
    for (let b = 1; b < 10000; b++) {
      for (let c = 1; c < 10000; c++) {
        let e_squared = Math.pow(a, 2) + Math.pow(c, 2);
        let e = Math.sqrt(e_squared);
        if (Number.isInteger(e)) {
          let d_squared = Math.pow(a, 2) + Math.pow(b, 2);
          let d = Math.sqrt(d_squared);
          if (Number.isInteger(d)) {
            let f_squared = Math.pow(b, 2) + Math.pow(c, 2);
            let f = Math.sqrt(f_squared);
            if (Number.isInteger(f)) {
              good_couples.push({ a, b, c, d, e, f });
            }
          }
        }
      }
    }
  }
  return couples;
};


console.log(generate_good_cuboid());
Tags:

3

Answers


  1. 0

    You can avoid the inner loop if the a & b sides doesn’t give an integer. Also you could use (d|0) === d which is faster.

    const generate_good_cuboid = sz => {
  let good_couples = [];
  for (let a = 1; a < sz; a++) {
      for (let b = 1; b < sz; b++) {
          const d = Math.sqrt(a ** 2 + b ** 2);
          if ((d|0)===d) {
              for (let c = 1; c < sz; c++) {
                  const e = Math.sqrt(a ** 2 + c ** 2);
                  if ((e|0)===e) {
                      const f = Math.sqrt(b ** 2 + c ** 2);
                      if ((f|0)===f) {
                          good_couples.push({ a, b, c, d, e, f });
                      }
                  }
              }
          }
      }
  }

  return good_couples;
};

console.log(generate_good_cuboid(10000));
    Login or Signup to reply.
  2. 0

    A trivial optimisation would be to compute d (from a and b) and check for its integer-ness before looping over all c.

    Further, you could avoid generating duplicates such as a=3, b=4 and a=4, b=3 by limiting your results to a < b < c, and permute your solutions if you need all of them. Then you can optimise for (let b = a; b < 10000; b++) and for (let c = b; c < 10000; c++) (although this doesn’t really change complexity).

    Last but not least, you could generate all known-good sets of Pythagorean triples up-front (only once), and then just search through those to find two triples (triangles) that share one side, and check whether the other two legs (catheti) form a Pythogorean triple as well. Use any of the known algorithms (generating Pythagorean triples, tree of primitive Pythagorean triples, Efficiently find all the Pythagorean triplets, best way to generate Pythagorean triples etc.) for the first part.

    Login or Signup to reply.
  3. 0

    Here is a solution that uses the Tree of primitive Pythagorian triples to generate all Pythagorian triples whose greatest element is less than your limit.

    Then it creates a graph (adjacency list) where one integer has a link with another if they are the lesser two members of a Pythagorian triple.

    Finally it checks if these can be combined to the desired combinations of a, b, and c:

    function* pythagorianTriples(limit) {
    const ABC = [
        [[1, -2, 2], [2, -1, 2], [2, -2, 3]],
        [[1,  2, 2], [2,  1, 2], [2,  2, 3]],
        [[-1, 2, 2], [-2, 1, 2], [-2, 2, 3]]
    ]
    let triples = [[3, 4, 5]];
    while (triples.length) {
        const children = [];
        for (const triple of triples) {
            const sorted = triple.toSorted((a, b) => a - b);
            if (sorted[2] >= limit) continue;
            const maxCoeff = Math.floor(limit / sorted[2]);
            // Yield multiples of this primitive pythagorian triple
            for (let i = 1; i <= maxCoeff; i++) {
                yield [sorted[0] * i, sorted[1] * i, sorted[2] * i];
            }
            // Get the triple's three children in the tree of Pythagorian triples:
            children.push(...ABC.map(mat =>
                mat.map(row => 
                    row[0] * triple[0] + row[1] * triple[1] + row[2] * triple[2]
                )
            ));
        }
        triples = children;
    }
}

function generateGoodCuboids(limit) {
    const pairSide = Array.from({length: limit}, (_, i) => new Set);
    const triples = [...pythagorianTriples(limit)];
    // Link pairs that belong to same Pythagorian triple; for fast lookup
    for (const [a, b] of triples) {
        pairSide[a].add(b);
        pairSide[b].add(a);
    }
    // Find valid combinations
    const solutions = [];
    for (const [a, b] of triples) {
        for (const c of pairSide[a]) {
            if (c >= b && pairSide[b].has(c)) solutions.push([a, b, c]);
        }
    }
    // For convenience, sort them:
    return solutions.sort(([a], [b]) => a - b);
}

const cuboids = generateGoodCuboids(1000);
console.log(`There are ${cuboids.length} solutions for sides < 1000:`);
for (const cuboid of cuboids) console.log(...cuboid);

// For 10 times more:
const cuboids2 = generateGoodCuboids(10000);
console.log(`There are ${cuboids2.length} solutions for sides < 10000`);

// For 10 times more:
const cuboids3 = generateGoodCuboids(100000);
console.log(`There are ${cuboids3.length} solutions for sides < 100000`);

    The script finds 8 solutions (ignoring permutations) when the limit is 1000; it repeats the job for 10000 (128 solutions) and 100000 (1457 solutions).

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search