Talk:Pythagorean triples: Difference between revisions
→javascript: Nothing to stop you showing a web-page-embedded example
(→Math tags broken?: new section) |
(→javascript: Nothing to stop you showing a web-page-embedded example) |
||
| (13 intermediate revisions by 7 users not shown) | |||
Line 50:
3. Generating triples with the parent-child relationship. Each iteration increases perimiter of current triple by about 2, so recursion will run <math>O({\rm log}n)</math> deep, that's also the space requirement (stack space); each recursion produces 3 triples, so running time is 3 to the power of depth, which is <math>O(n)</math>. Non-primitives come with no extra cost. For this particular task, it may be the most efficient method speed-wise. --[[User:Ledrug|Ledrug]] 23:56, 29 June 2011 (UTC)
:Note that "For this particular task, it may be the most efficient method speed-wise." probably assumes a low-parallelism implementation. If we had an infinite number of cpus, method 2 might be faster, because after treating one potential triple the work of any one cpu is done. In method 3, a cpu must continue its work, building further triples based on an initial triple. Obviously, of course, this way of thinking is not relevant in the context of a single cpu with only one core. So, if method 3 is faster, there would probably be a limit on the number of available cpus to handle computations for a given perimeter. (This kind of thinking might become relevant in GPU implementations.) --[[User:Rdm|Rdm]] 13:43, 16 December 2011 (UTC)
:: No doubt parallelism can be important, but the approximation of an ''infinite'' number of parallel processing unit is a little too blindly exuberant (10^9 perimeter has 70M primitives, which is too high for number of cores, GPU units or CPUs on a cluster). Even if we can count on this optimism, there are two points to consider: a) the recursive generation of method 3 can be parallelized. At each step, there are three branches for next step, and you could dispatch them to separate units. It fully "fans out" after log<sub>3</sub>N steps; as long as number of cores is not comparable to number of primitives, this is negligible. b) method 2 needs to scan a range of numbers to pick out coprime pairs, which is a significant overhead, while method 3 always generates triples that satisfy requirements. Well, the third of the two points is: c) The recursion is very simple, almost certainly simpler than dispatching to multiple cores or GPU units. Even if you have highly parallel hardware, it might be better to limit how far you want the code to be parallelized.
:: The point c above is why I don't quite buy the J "we can run this code in parallel later" mantra (or the Perl6 "it will hopefully be efficient when it's implemented" notion): parallelism is highly complicated, and though automated optimization may work for some common scenarios, you can't rely on it to work out for everything everywhere. Sometimes you have to optimize stuff by hand: you sort of know what ''should'' happen, the compilers don't. If they could figure that out, there would be no halting problem. --[[User:Ledrug|Ledrug]] 02:03, 17 December 2011 (UTC)
::: Well, ultimately, discussions like this are not what counts -- it's implementations where you can measure timing (though also you can sometimes see factor of 2 differences in timings, running the same code on the same machine, and timings themselves need to be taken with a grain of salt).
:::That said... it's quite true that an "infinite number of cpus" is not a practical system -- it's a simplification for algorithm analysis (much like big-O notation is a simplification). But it's also true that GPUs do not rely on having a physical execution unit for every pixel.
:::Anyways, roughly speaking, on modern CPUs, the biggest time eater is the cache miss. After that it's the failed branch prediction. Actual computation is almost (but not quite) free, in comparison. GPUs shift the balance somewhat (with tighter limits on branching, and more heavily favoring pushing decision making to a higher level in the code).
:::So, for example, I'm not sure what Perl has to do with this kind of analysis. (Perl, in my experience, tends to have extremely high quantities of branches, in its implementation.) --[[User:Rdm|Rdm]] 14:44, 19 December 2011 (UTC)
== Ready to graduate? ==
Line 64 ⟶ 73:
I see literal <nowiki><math></math></nowiki> tags everywhere...<br/>Is this a bug introduced by the server switch perhaps?
: Looks like it. Already reported to site owner. –[[User:Dkf|Donal Fellows]] 13:58, 14 December 2011 (UTC)
:: Still not working in Chrome? --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 01 May 2016
== Wrong? ==
Both [[wp:Pythagorean_triple|Wikipedia]] and Sloane's [https://oeis.org/A020882 A020882] agree that there are 16 primitive Pythagorean triples with c up to 100:
: (3 , 4 , 5), (5, 12, 13), (7, 24, 25), (8, 15, 17), (9, 40, 41), (11, 60, 61), (12, 35, 37), (13, 84, 85), (16, 63, 65), (20, 21, 29), (28, 45, 53), (33, 56, 65), (36, 77, 85), (39, 80, 89), (48, 55, 73), (65, 72, 97)
Why do all of our solutions give 7 instead of 16? Which nine aren't counted?
[[User:CRGreathouse|CRGreathouse]] 06:36, 13 September 2012 (UTC)
:''The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.'' So, for example, the triangle with side lengths 48, 55, 73 has a perimeter of 176. --[[User:Rdm|Rdm]] 14:18, 13 September 2012 (UTC)
:: Got it. For some reason I kept reading it as c not P. [[User:CRGreathouse|CRGreathouse]] 00:12, 14 September 2012 (UTC)
==Several formulae rendered invisible to many browsers by cosmetic edits==
Cosmetic edits made to the task page on May 1 2016, including the injection of spaces around expressions in <math> tags, have left several of the formulae completely invisible to all browsers which display the graphic file version of formulae rather than processing the MathML (this is, in fact, the majority of browsers). The MediaWiki processor does not currently expect such spaces, and generates syntactically ill-formed HTML if they are introduced. Other aspects of these edits may further compound the problem. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:48, 20 September 2016 (UTC)
: Removed redundantly injected space around <math> tag contents, restoring visibility of server-side formula graphics [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:43, 30 October 2016 (UTC)
== javascript ==
can we have a webpage version of the code?--[[User:Xdv|xarilaos]] ([[User talk:Xdv|talk]]) 17:07, 31 December 2021 (UTC)
: It's not quite clear to me whether you are requesting permission to do that (no need for permission, go ahead)
: or asking someone else to do it ?
: JavaScript is, of course, defined by the ECMAScript standards which neither include nor depend on the web browser Document Object Model. Not all JS interpreters are embedded in browsers, and web page elements are not part of the JavaScript language, but there is nothing to stop you showing a web-page-embedded example. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:15, 31 December 2021 (UTC)
| |||