4 ms·

I'm always impressed how much faster you can go compared to a naive algorithm - if you know what you are doing. This clocks in at 730x and that might not be th

I'm always impressed how much faster you can go compared to a naive algorithm - if you know what you are doing. This clocks in at 730x and that might not be the peak. Compare: The original steam enginge trains went I believe 10km/h, so if it received the same level of speedup, it reaches somehere between mach 5 and 10. You can classify this algorithm as hypersonic ;-)

hinkley 8y ago
Tangent: There’s a square power law for velocity due to wind resistance. People aren’t impressed that a pro bicyclist is going “only” twice as fast as them but that’s four times as strong, for three times as long. If modern train engine produced 700 times as much power that’s only 26 times faster for the same cargo (don’t they pull more now?) And we do have trains that can go 260 km/hr... just not with cargo. progress, man.
- gh02t 8y ago
  I actually find the practicalities of algorithm choice even more fascinating. For example, Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication in certain situations (medium sized matrices), but it is rarely used because it is complicated to implement and less numerically stable.
  - electricslpnsld 8y ago
    > Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication Coppersmith–Winograd approaches take the crown for asymptotic scaling in matrix-matrix multiplication [1]. It kind of blows my mind that a tight bound on the complexity of matrix-matrix multiplication still isn't known! Edit: Some quick googling shows that François Le Gall took the crown in 2014. [1] https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
    - Paul_Diraq 8y ago
      The problem with the algorithms faster than conventional mm is, that they are defined on mathematical numbers. E.g. strassens-algorithms assumes something like: (A+B)C - BC = AC With the convential floating point representation this becomes a problem if B >> A because of rounding errors. Most algorithms faster than Strassen assume: (( fA + B)C - BC)/f = AC and (fA + B)C = BC +fAC f is then choosen in such a way, that fAC is neglegible. But if that is the case fA is much smaller than B and we automatically get numerical problems. There is a procedure to remove the fAC terms (which would imply that f could be choosen close to 1) which armortizes over enough recursions. But for Coppersmith-Winograd (and derivatives like Le-Galls algorithm). We need to divide the matrix in each recursion step into enough submatrices that the indices can be treated heuristically(lets say a division of each index in each iteration in 100 subindices). This would imply the sides of each matrix must be at least of size 100^n_recusion. We won't need to multiply matrices of that size.
      - geezerjay 8y ago
        Thank you for posting your comment. Very insightful and packed with goodies!
    - gh02t 8y ago
      Oh, right indeed. I had forgotten about those since they aren't really practical. I honestly find it pretty amazing that any sub-cubic algorithms can even exist for dense matrix multiplication. It's just far enough away from my expertise to seem magical.
- PyroLagus 8y ago
  And when you see the world record bicycle speed of 144km/h on a recumbent with full body fairing, you realize just how significant wind resistance is and how important aerodynamics is.
- iopq 8y ago
  I was in Japan and the shinkansen definitely had cargo on it

hinkley 8y ago

Tangent: There’s a square power law for velocity due to wind resistance. People aren’t impressed that a pro bicyclist is going “only” twice as fast as them but that’s four times as strong, for three times as long. If modern train engine produced 700 times as much power that’s only 26 times faster for the same cargo (don’t they pull more now?) And we do have trains that can go 260 km/hr... just not with cargo. progress, man.

gh02t 8y ago
I actually find the practicalities of algorithm choice even more fascinating. For example, Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication in certain situations (medium sized matrices), but it is rarely used because it is complicated to implement and less numerically stable.
- electricslpnsld 8y ago
  > Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication Coppersmith–Winograd approaches take the crown for asymptotic scaling in matrix-matrix multiplication [1]. It kind of blows my mind that a tight bound on the complexity of matrix-matrix multiplication still isn't known! Edit: Some quick googling shows that François Le Gall took the crown in 2014. [1] https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
  - Paul_Diraq 8y ago
    The problem with the algorithms faster than conventional mm is, that they are defined on mathematical numbers. E.g. strassens-algorithms assumes something like: (A+B)C - BC = AC With the convential floating point representation this becomes a problem if B >> A because of rounding errors. Most algorithms faster than Strassen assume: (( fA + B)C - BC)/f = AC and (fA + B)C = BC +fAC f is then choosen in such a way, that fAC is neglegible. But if that is the case fA is much smaller than B and we automatically get numerical problems. There is a procedure to remove the fAC terms (which would imply that f could be choosen close to 1) which armortizes over enough recursions. But for Coppersmith-Winograd (and derivatives like Le-Galls algorithm). We need to divide the matrix in each recursion step into enough submatrices that the indices can be treated heuristically(lets say a division of each index in each iteration in 100 subindices). This would imply the sides of each matrix must be at least of size 100^n_recusion. We won't need to multiply matrices of that size.
    - geezerjay 8y ago
      Thank you for posting your comment. Very insightful and packed with goodies!
  - gh02t 8y ago
    Oh, right indeed. I had forgotten about those since they aren't really practical. I honestly find it pretty amazing that any sub-cubic algorithms can even exist for dense matrix multiplication. It's just far enough away from my expertise to seem magical.
PyroLagus 8y ago
And when you see the world record bicycle speed of 144km/h on a recumbent with full body fairing, you realize just how significant wind resistance is and how important aerodynamics is.
iopq 8y ago
I was in Japan and the shinkansen definitely had cargo on it