On Sep 2, 12:51 pm, [EMAIL PROTECTED] wrote: > I'm pretty new to python, but am very happy with it. As well as using > it at work I've been using it to solve various puzzles on the Project > Euler site -http://projecteuler.net. So far it has not let me down, > but it has proved surprisingly slow on one puzzle. > > The puzzle is: p is the perimeter of a right angle triangle with > integral length sides, {a,b,c}. which value of p < 1000, is the > number of solutions {a,b,c} maximised? > > Here's my python code: > > #!/usr/local/bin/python > > solutions = [0] * 1001 > p = 0 > > for a in xrange(1, 1000): > for b in xrange(1, 1000 - a): > for c in xrange(1, 1000 - a - b): > p = a + b + c > if p < 1000: > if a ** 2 + b ** 2 == c ** 2: > solutions[p] += 1 > > max = 0 > maxIndex = 0 > index = 0 > for solution in solutions: > if solution > max: > max = solution > maxIndex = index > index += 1 > > print maxIndex > > It takes 2 minutes and twelve seconds on a 2.4GHz Core2Duo MacBook > Pro. Surprised at how slow it was I implemented the same algorithm in > C: > > #include <stdio.h> > #include <stdlib.h> > > int main() { > int* solutions = calloc(1000, sizeof(int)); > > int p; > for(int a = 1; a < 1000; ++a) { > for(int b = 1; b < 1000 - a; ++b) { > for(int c = 1; c < 1000 - a - b; ++c) { > p = a + b + c; > if(p < 1000) { > if(a * a + b * b == c * c) { > solutions[p] += 1; > } > } > } > } > } > > int max = 0; > int maxIndex = 0; > > for(int i = 0; i < 1000; ++i) { > if(solutions[i] > max) { > max = solutions[i]; > maxIndex = i; > } > } > printf("%d\n", maxIndex); > return 0; > > } > > gcc -o 39 -std=c99 -O3 39.c > > The resulting executable takes 0.24 seconds to run. I'm not expecting > a scripting language to run faster than native code, but I was > surprised at how much slower it was in this case. Any ideas as to what > is causing python so much trouble in the above code?
from math import sqrt solutions = [0] * 1001 p = 0 for a in xrange(1, 1000): a2 = a*a for b in xrange(1, 1000 - a): c = sqrt(a2 + b*b) if c == int(c) and a+b+c < 1000: solutions[a+b+int(c)] += 1 max = 0 maxIndex = 0 index = 0 for solution in solutions: if solution > max: max = solution maxIndex = index index += 1 print maxIndex -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list