« first day (2781 days earlier)      last day (1664 days later) » 

Evil
Evil
1:19 AM
@ThePlasmaRailgun What? Sorting networks like bitonic sort works well in practice. What construction do you have in mind?
 
Bounty!
Bounty!
2:14 AM
0
Q: Why does Min-Max algorithm delays a good move indefinitely?

RajI implemented a min-max algorithm for a game and discovered a problem. Let's say there is a 2x2 grid: .. .. Assume we start at location (0, 0) and the target is (1, 1): S. .T Moves allowed: adjacent or diagonal move. Evaluation: if I land at (1, 1), I get +100. If I implement the mini-m...

algorithms game-theory minmax-algorithm minimax
 
 
22 hours later…
ThePlasmaRailgun
ThePlasmaRailgun
11:48 PM
@Evil Oh, I was saying it would be possible to construct some algorithms in general that hide insanely massive constants
Not specifically for sorting networks
But I feel like specifically choosing a problem to make a linear time algorithm with a massive constant is cheating
I was interested in the existence of naturally occuring, practical problems with misleading big O runtimes
It turns out there's actually a name for them:
Galactic algorithm
A galactic algorithm is one that runs faster than any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by Richard Lipton and Ken Regan, as they will never be used on any of the merely terrestrial data sets we find here on Earth. An example of a galactic algorithm is the fastest known way to multiply two numbers, which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits, which...
This one is pretty great
An O(n log n) multiplication algorithm
 

« first day (2781 days earlier)      last day (1664 days later) »