Cluster Searches
In the 80's on an Amdahl mainframe, Landon Noll defined a cluster search that we can now characterize as roughly an O(N^3) algorithm on O(N) heron angles using O(N) memory. He created pythagorean triangles whose sides were at most 2^19, and then looked at triples of pythagorean triangles (including reflections and rotations) along with the the origin to pull out 4-clusters.
There were a couple of limitations here. First, for a given angle, the angle may have existed in the list of pythagorean triangles multiple times. Dilated variants of the 3,4,5 triangle appeared over 100,000 times in the list. Second, for a collection of angles, the angles were only tested to see if they formed a 4-cluster if the smallest 4-cluster would fit in a square of radius 2^19.
This search generated a fair number of 6-clusters. As discussed earlier in this blog, we later extracted the primitive heron triangles from this set of 6-clusters. We then used a different algorithm to search this collection of interesting heron triangles for 7-clusters. The different algorithm did not limit itself to angles that composed the heron triangles. When testing two heron triangles to see if they formed a 4-cluster, the resulting 4-cluster could contain arbitrary angles.
This algorithm was O(N^2) in the number of heron triangles. Since each pair of pythagorean triangles forms a heron triangle, this can be considered O(N^4) in the number of pythag triangles. Slower than the search used on the Amdahl. On the other hand, this search looked at very few heron triangles. It only considered heron triangles that had proven themselves by forming 6-clusters.
More recently, we have been looking at algorithms that are O(N^3) in the number of pythagorean triangles and which use O(N^2) memory. These algorithms form all 4-clusters for a given set of heron angles. The memory consumption is large, but they form a more complete set of 4-clusters with less duplication.
This leads to a couple of approaches. One approach is to select a set of heron angles and then find all N-clusters that can be formed from just those angles.
Another approach is to figure out how to find an interesting set of heron triangles that are likely to occur in large clusters and then explore just that set of heron triangles for large clusters.
There were a couple of limitations here. First, for a given angle, the angle may have existed in the list of pythagorean triangles multiple times. Dilated variants of the 3,4,5 triangle appeared over 100,000 times in the list. Second, for a collection of angles, the angles were only tested to see if they formed a 4-cluster if the smallest 4-cluster would fit in a square of radius 2^19.
This search generated a fair number of 6-clusters. As discussed earlier in this blog, we later extracted the primitive heron triangles from this set of 6-clusters. We then used a different algorithm to search this collection of interesting heron triangles for 7-clusters. The different algorithm did not limit itself to angles that composed the heron triangles. When testing two heron triangles to see if they formed a 4-cluster, the resulting 4-cluster could contain arbitrary angles.
This algorithm was O(N^2) in the number of heron triangles. Since each pair of pythagorean triangles forms a heron triangle, this can be considered O(N^4) in the number of pythag triangles. Slower than the search used on the Amdahl. On the other hand, this search looked at very few heron triangles. It only considered heron triangles that had proven themselves by forming 6-clusters.
More recently, we have been looking at algorithms that are O(N^3) in the number of pythagorean triangles and which use O(N^2) memory. These algorithms form all 4-clusters for a given set of heron angles. The memory consumption is large, but they form a more complete set of 4-clusters with less duplication.
This leads to a couple of approaches. One approach is to select a set of heron angles and then find all N-clusters that can be formed from just those angles.
Another approach is to figure out how to find an interesting set of heron triangles that are likely to occur in large clusters and then explore just that set of heron triangles for large clusters.
posted by Cesium at 20:05
0 Comments:
Post a Comment
<< Home