2014-08-16

On generating integer-sided triangles with an integer area/perimeter ratio

This blog post contains come comments about finding all triangles whose sizes are integers and the area/perimeter ratio is the integer r. This is related to Project Euler problem 283.

The blog post contains a nice analysis and some pseudocode for generating all possible (a, b, c) size triplets for the given ratio r. Unfortunately both the analysis and the pseudocode contains some mistakes.

Here is the corrected version:

def find_triangles_correct(r):
  for u in divisors of 2r:
    for v in 1 to floor(sqrt(3) * u):
      if gcd(u, v) == 1:
        lhs = 4*r*r*(u*u+v*v)
        for d1 in positive divisors of lhs:
          if d1 <= lhs / d1:
            d2 = lhs / d1
            if not (u < v and d1*u < (2r(v*v-u*u))):
              if ((d1+2ru) mod v) = 0 and ((d2+2ru) mod v) = 0:
                a = (d1 + 2ru) / v + 2rv / u
                b = (d2 + 2ru) / v + 2rv / u
                c = (d1 + d2 + 4ru) / v
                yield a, b, c
Some mistakes and other inaccuracies in the original:
  • The variable r were silently renamed to m.
  • The formulas for a, b and c were not included.
  • The analysis incorrectly states that v must be smaller than floor(sqrt(3)*u)). The correct statement is: v must be smaller than sqrt(3)*u. Before the correction some solutions such as (6, 8, 10) for r=1 were not generated.
  • The condition d1 <= lhs / d1 had a >= instead.

Please note that the algorithm yields each triangle once, in an unspecified order of a, b and c within the triangle.

2014-08-12

How the lifetime of temporaries is extended because of references in C++

This blog post summarizes what I learned about C++ today about how the lifetime of temporaries is extended because of references.

Normally a temporary is destroyed at the end of the statement, for example temporary string returned by GetName() lives until the end of the line defining name. (There is also the return value optimization which may eliminate the temporary.)

#include <stdio.h>

#include <string>
using std::string;
string GetName() {
  return string("foo") + "bar";
}
int main() {
  string name = GetName();
  printf("name=(%s)\n", name.c_str());
  return 0;
}

However, it's possible to extend the life of the temporary by assigning it to a reference-typed local variable. In that case, the temporary will live until the corresponding reference variable goes out of scope. For example, this will also work and it's equivalent to above:

#include <stdio.h>
int main() {
  const string &name = GetName();
  printf("name=(%s)\n", name.c_str());
  return 0;
}

Please note that there is no lifetime extension if the function returns a reference, and also in some other cases related to function boundaries. See more details about reference initialization.