5 ms·
During the solving of a problem on Project Euler, I learned that compilers are smarter than me. I don't remember the problem number or its title, but it involv
by Sohcahtoa82 2y ago
During the solving of a problem on Project Euler, I learned that compilers are smarter than me.
I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right.
My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?
My assembly solution took 5 minutes.
I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.
Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.
- johnsonjo 2y agoSounds like problem 15 [1]? [1]: https://projecteuler.net/problem=15 https://projecteuler.net/problem=15
- Sohcahtoa82 2y agoYup! That was it!
- wging 2y agoIf you want a few similar problems, in ascending order of difficulty, try #81 through #83: https://projecteuler.net/problem=81 https://projecteuler.net/problem=81 https://projecteuler.net/problem=82 https://projecteuler.net/problem=82 https://projecteuler.net/problem=83 https://projecteuler.net/problem=83
- Sohcahtoa82 2y agoCouldn't all three of those be solved using the A* path-finding algorithm?
- wging 2y agoSshhh...
- guessmyname 2y agoLattice Paths — https://projecteuler.net/problem=15 https://projecteuler.net/problem=15 > Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. ─────────┐ ────┐ ────┐ ┌───┬───┐│ ┌───│───┐ ┌───│───┐ │ │ ││ │ │ │ │ │ │ ├───┼───┤│ ├───└────┐ ├───│───┤ │ │ ││ │ │ ││ │ │ │ └───┴───┘│ └───┴───┘│ └───│───┘ ▼ ▼ └────▶ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ ││ │ │ ││ │ │ ││ │ │ └─────────┐ └────┐───┤ │├───┼───┤ │ │ ││ │ │ │ ││ │ │ └───┴───┘│ └───│───┘ │└───┴───┘ ▼ └────▶ └─────────▶ > How many such routes are there through a 20x20 grid?
- Sohcahtoa82 2y agoYup! That was it! Good job on the ASCII art, btw.
- dotancohen 2y ago> How many such routes are there through a 20x20 grid? Is it 21! ?
- Jtsummers 2y agoNope, and only off by a few orders of magnitude.
- dotancohen 2y agoIf it is any comfort, my answer produced a non-negative integer - just like the true answer ))
- mdp2021 2y agoNo. It's 20!/(10!x10!) You have 20 slots to be filled with 10 items vs other 10 items.
- noapologies 2y ago
- deleted 2y ago[deleted]
- archgoon 2y agoSo fun fact, if you compile int sum(int n) { int sum = 0; for(int i = 0; i < n; i++) { sum +=i; } return sum; } clang, with -O2, will turn this into the polynomial (n+1)*n//2. It can also do similar transformations for multiple loops. https://godbolt.org/z/so6neac33 https://godbolt.org/z/so6neac33 So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.
- j2kun 2y agoI believe the term for this is scalar evolution.
- archgoon 2y agoYep! That is it alright. Here's a talk from an llvm conference with the details. https://www.youtube.com/watch?v=AmjliNp0_00 https://www.youtube.com/watch?v=AmjliNp0_00
- sbrother 2y agoThat is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?
- gerdesj 2y agoWe all have our skills and super powers and yours do not involve optimizing for time by switching from C to ASM. Fuck that! I bet you have super powers of some sort. Compilers are not smarter than you - that's daft. The nutters that program the compilers and tweak and twiddle them, are better informed about how to deliver faster machine code for a given task. One of your super powers is to know when to say: "fuck it, I'm trotting off and getting by with a five minutes runtime".