1

After listening to an advice regarding my code, I found the algorithm behind a generating code function, which allows me to procedurally generate code that would evaluate itself.

[(a_0, a_1, a_2) for a_0, a_1, a_2 in product(range(1,100),repeat=3) if a_0 ** 2 + a_1 ** 2  == a_2 ** 2]

This is the result of the coding. As you can see, I am using itertools product function, which as I know needs to be optimised. If this post gets viewed enough, I will publish the code that generated this.

I researched about what could I do. First, I realised that in any pythagorean triple the last number of the tuple (i.e. (3,4,5)) is bigger than the other numbers in the triple, so I put ||max(-the variables I used) < the biggest variable| in the function:

[(a_0, a_1, a_2) for a_0, a_1, a_2 in product(range(1,100),repeat=3) if a_0 ** 2 + a_1 ** 2  == a_2 ** 2 and max(a_0,a_1) < a_2]

But I don't really now if this accelerates the function. Is there a better way to optimise this function? If you have any answers or questions, I would greatly appreciate them!

Edit: Thanks to the petition of @Stef of using itertools' combination function instead of product, but sadly that function doesn't fasten the process.

Also I'm talking about optimising this function, not about making it work (it does work).

Edit2: I tested out many times the function with product and with combinations, and it turns out combinations is faster by a factor of over 6 in triples. It does greatly optimise the function, so thanks to @Stef for helping me out.

Also, if there is a function that can optimise this to the maximum, I would really appreciate it. The function can be from any module, including built-in functions if possible.

TechYharon
  • 11
  • 7
  • At the very least you can use `combinations(range(1,100), 3)` instead of `product(range(1,100), repeat=3)`. This will only consider triplets with `a_0 < a_1 < a_2`, so only 161700 triplets instead of 1000000 triplets. Note that a_2 has to be bigger than the other two for obvious reasons, but also a_0 and a_1 cannot be equal, otherwise `a_0**2 + a_1**2 == a_2**2` would be equivalent to `2 * (a_0**2) = a_2**2` which would be equivalent to `2 = (a_2 / a_0)**2` which would mean that 2 has a rational square root. – Stef Feb 12 '23 at 13:53
  • Although, rather than iterating on triplets, it would be much more efficient to iterate on pairs, and calculate the third number directly: `[(a, b, c) for a, b in combinations(range(1, 100), 2) if (c := isqrt(a2b2 := a**2+b**2))**2 == a2b2]`. Where `combinations` is from `itertools` and `isqrt` is from `math`. This way you only consider 4950 pairs. – Stef Feb 12 '23 at 13:59
  • I don't see *"this function that generates pythagorean group of n elements (like triples but with any number of elements)"* anywhere. – Kelly Bundy Feb 12 '23 at 14:07
  • @Stef that wouldn't let me extend the pythagorean triples to more variables, rather than 3 only. The one using pairs is what I'm referring to. – TechYharon Feb 12 '23 at 18:48
  • ~xombinations` instead of `product` *"doesn't fasten the process"*? That's odd. Should make it about six times faster for triples, more for longer tuples. – Kelly Bundy Feb 12 '23 at 18:58
  • @TechYharon What is a "Pythagorean triple with more variables"? Is it something like `10**2 + 11**2 + 12**2 == 13**2 + 14**2`? If so, I still recommend using `combinations` over `product`. And I still recommend trying to remove the last variable from the loop, and calculate it directly. For instance, `(a,b,c,d,e)` can only satisfy the relation `a**2 + b**2 + c**2 == d**2 + e**2` if `e == isqrt(a**2 + b**2 + c**2 - d**2)`, so you don't need to loop over a multitude of values for `e`; just loop over possible values for `(a,b,c,d)` and calculate `e` directly. – Stef Feb 12 '23 at 19:16
  • However, as the number of variables increases, the number of possible tuples that you have to iterate over will increase very very fast. So you should either restrict your range (but even that will quickly not be enough), or find a much more efficient method, not based on programming tricks, but on math tricks. For instance, [this answer](https://stackoverflow.com/a/8263898/3080723) relies on the math results described on this page: [Wikipedia: Tree of primitive Pythagorean triples](https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples) – Stef Feb 12 '23 at 19:21
  • @Stef You'd miss 4² + 4² + 7² = 9². – Kelly Bundy Feb 12 '23 at 19:27
  • 1
    @Stef Argh, simpler case: 1² + 2² + 2² = 3². Anyway, itertools still got it covered... – Kelly Bundy Feb 12 '23 at 19:36
  • @Stef I am a Pythagorean group with more variables is, for example, a^3 + b^3 + c^3 = d^3. In a pythagorean group there is ALWAYS a variable on the right, only one. It could be possible that 2 or more variables were on the right, but it wouldn't be a pythagorean group. – TechYharon Feb 12 '23 at 20:10
  • Also if I show the example of Pythagorean triples is because it is the most famous, but my goal is to extend the definition to ANY number of variables of ANY exponents (excluding rationals because I tested it and it always revealed me nothing). – TechYharon Feb 12 '23 at 20:13
  • Interesting. Did you manage to write a function to find solutions of `a**3 + b**3 == c**3`? – Stef Feb 12 '23 at 20:24
  • 1
    @Stef Pfft, easy, I wrote down all solutions of that when I was just four years old. – Kelly Bundy Feb 12 '23 at 21:07
  • Yes @Stef, I recently just did thanks to your contributions. Also, KellyBundy, did you write all of them between what range? Because if the range of a, b and c are between 1 and 100, that's trivial: There are none – TechYharon Feb 13 '23 at 06:32
  • I am trying to extend the triples to a group of n elements, so I doubt that tree of primitive Pythagorean triples would help me @Stef – TechYharon Feb 13 '23 at 06:38
  • I don't know whether there are methods similar to that tree for more than 3. But you have to understand that the number of combinations blows up **really** fast, so iterating over all possible combinations to test, with nested loops, be it with `for`-loops or with itertools, is not going to get you very far at all. – Stef Feb 13 '23 at 09:02
  • Yea, I understand that, but if I want to extend the function to an infinite number of variables of any exponent, a particular tree isn't gonna work as optimally as presented in the question. – TechYharon Feb 13 '23 at 09:03
  • @TechYharon I can't tell whether you're in on the joke or not :-) – Kelly Bundy Feb 13 '23 at 09:15
  • I'm not joking, and, fortunately, I have solved that question, although not as optimized as I thought. – TechYharon Feb 13 '23 at 09:27

0 Answers0