[HN Gopher] A binary tree of all Pythagorean triples
___________________________________________________________________
A binary tree of all Pythagorean triples
Author : hakmem
Score : 129 points
Date : 2024-11-21 07:24 UTC (15 hours ago)
(HTM) web link (richardt.io)
(TXT) w3m dump (richardt.io)
| sevensor wrote:
| This is wonderful! I'd somehow missed the classical enumeration
| of Pythagorean triples. I learned them as magic numbers. That
| structure alone is worth the price of admission.
| not2b wrote:
| You changed the article's title to an incorrect one. The tree of
| primitive Pythagorean triples is ternary, not binary. Each node
| has three children.
| generationP wrote:
| Both conventions are valid. You call it binary when you view it
| as a rooted tree, or ternary if you view it just as a graph.
| nyrikki wrote:
| But it _all_ triples?
|
| > I sketch how the stereographic projection of the Stern-
| Brocot tree forms an ordered binary tree of Pythagorean
| triples, which can be used to compute best approximations of
| turn angles of points on the circle and finally trigonometric
| functions
|
| The permutation and stack problem in the page seem to
| indicate this is a potential method for approximations, but
| insufficient for _all_
|
| That said I am reading this on mobile and may have missed
| something.
| not2b wrote:
| The ternary tree contains all primitive triples (where the
| GCD of the terms is 1), where a<b<c. So it contains (3,4,5)
| but not (6,8,10) or (4,3,5).
| nyrikki wrote:
| Yes, but the binary projection does not according to the
| link.
|
| 345 and 435 would require two binary trees.
| AnotherGoodName wrote:
| I think skipping transposed values is fine though. You
| could just mirror the output at 45degrees for that if you
| wanted it. It does hit all distinct triples including the
| multiples of triples so it's more inclusive of everything
| than the ternary tree.
| hakmem wrote:
| You can see both triples are contained in one binary tree
| using the big diagram in section 3. The triple [3 4 5]
| has the "path" RR. The triple [4 3 5] the path R.
| feoren wrote:
| Keep reading. The Barning-Hall tree is ternary, but this
| article is mostly devoted to the Stern-Brocot tree, which is
| binary.
| ColinWright wrote:
| From the article:
|
| "I sketch how the stereographic projection of the Stern-Brocot
| tree forms an ordered binary tree of Pythagorean triples ..."
|
| ... and ...
|
| "Before that, I briefly recapitulate the classical enumeration
| of Pythagorean triples and the ternary Barning-Hall tree."
|
| So this article is about the _binary_ tree representation.
| matt3210 wrote:
| Very nice! nit: website isn't mobile friendly
| lollobomb wrote:
| Wow, this is extremely cool! Only problem, the JS slows my
| Firefox almost to freezing, is it normal?
| hakmem wrote:
| Yes, this is normal. I am sorry, I am working on a more
| efficient implementation.
|
| The JavaScript of this page does a lot of number crunching.
|
| It is actually doing arithmetic on the Stern-Brocot tree. It is
| all written in ClojureScript and not really optimized yet. I
| mention in the paper that I do not even use TCO.
|
| Anyway, thank you - and all the people here - for the kind
| words! I am so happy that my article was so well received
| today.
| akomtu wrote:
| A simple trick to solve nearly all freezing problems: move
| the computations to a background thread, aka Worker in JS
| terms.
___________________________________________________________________
(page generated 2024-11-21 23:00 UTC)