Timeline for Project Euler Problem 45
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 6, 2019 at 17:06 | comment | added | Acccumulation | tt, pp, hh is rather opaque. | |
| Sep 5, 2019 at 18:53 | comment | added | ShadowRanger | With all three optimizations, on my local CPython 3.7.2 x64 machine, the runtime reduces from ~25 ms to ~8.5 ms (#1 drops it to ~19.5 ms, #1+#2 gets it to ~13 ms, with #1+#2+#3 dropping it down to 8.5 ms), a nearly 2/3rds reduction in runtime, for code that is (to me at least) equally readable; no really tricky code used solely to squeeze out a few nanoseconds. | |
| Sep 5, 2019 at 18:44 | comment | added | ShadowRanger | 2) Change while p < h: p = next(pentagonal_numbers) to for p in pentagonal_numbers: if p >= h: break. Since pentagonal_numbers advances slower than polygonal_numbers(6) you can safely advance the iterator at least once, and letting the for loop do the work instead of manually calling next makes a surprisingly big difference on CPython. 3) Put the code into a main function, and invoke it with if __name__ == '__main__': main() at the bottom; run in global scope, every variable access requires a dict lookup; in function scope, it's just an array lookup with a constant index. | |
| Sep 5, 2019 at 18:31 | comment | added | ShadowRanger | Some optimizations are available here to reduce work further: 1) Change polygonal_numbers to loop over for n in count(1, sides - 2):, which lets the accumulate step be just result += n, and removes a constant subtraction and an unnecessary multiplication from each loop, reducing runtime by ~40% (on CPython 3.7 x64). Or for ~55% runtime reduction, replace the body of the function entirely with yield 0 followed by yield from accumulate(count(1, sides - 2)) (accumulate also comes from itertools, but unfortunately doesn't take a start value, thus the explicit yield 0). | |
| Sep 5, 2019 at 16:13 | comment | added | ShadowRanger | Qualification: int / int will be ever so slightly slower than int // int when the ints are small, simply because of the cost to convert from int to C double. But for apples to apples comparisons, float / float always beats int // int. Point is, speed shouldn't really be the consideration here, just use whichever makes logical sense (obviously, if you need floor division, use floor division instead of int(float / float), because the conversion back will more than wipe out any "savings"). | |
| Sep 5, 2019 at 16:05 | comment | added | ShadowRanger | Minor correction to your assertion "Floating-point division, using the / instead of the // operator, is even slower". The raw processor instructions usually do FP division faster (e.g. on Skylake-X, 32 bit int DIV/IDIV family have a latency of ~24 cycles, and take 6 cycles to complete and 64 bit int is substantially slower, while FDIV is 14-16 cycle latency, 4-5 cycles to complete), and on CPython, the int related work is more expensive, since it needs to account for infinite precision ints, where float just does the raw C double division. | |
| Sep 5, 2019 at 13:36 | comment | added | JollyJoker | From @200_success' Oeis link, a(n) = 37635*a(n-1) - 37635*a(n-2) + a(n-3) is probably unbeatable for speed. Just hardcode the first three numbers. Then again, the question is about the third number... | |
| Sep 5, 2019 at 12:10 | comment | added | David Hammen | While this is fairly fast for finding the third hexagonal pentagonal number it is slow for finding the fourth such number. That would require even more sophistication. | |
| Sep 4, 2019 at 22:03 | vote | accept | ifsoMarcus | ||
| Sep 4, 2019 at 21:09 | comment | added | 200_success | By the way, Project Euler 45 is just A046180. Other intersections of polygonal numbers are also documented. | |
| Sep 4, 2019 at 21:00 | history | edited | 200_success | CC BY-SA 4.0 | added 133 characters in body |
| Sep 4, 2019 at 20:54 | history | answered | 200_success | CC BY-SA 4.0 |