nicknash

8 ms·

31.
Mining Adobe's Password Disaster in Microseconds with an FM-index(ocfnash.wordpress.com)
3 points by nicknash 13y ago|0 comments
32.
Nanex was wrong: There was no great fed robbery(virtu.com)
4 points by nicknash 13y ago|0 comments
33.
Gustafson's Law(en.wikipedia.org)
3 points by nicknash 13y ago|0 comments
34.
by nicknash 13y ago
Interesting that it involved a significant computational effort in verifying the GRH up to a large finite constant.
35.
Stop Discriminating Against Both Sides: The Reverse Regression Effect(concretenonsense.wordpress.com)
1 points by nicknash 13y ago|0 comments
36.
The Matrix Puzzle From Hell, Revisited(nicknash.me)
2 points by nicknash 14y ago|0 comments
37.
by nicknash 14y ago
I think it's right. One way to convince yourself is just to add counters to the implementation of bubble sort, run it for a larger input, and then verify the probabilities (including the conditional probabilities) match what I claim. You're
38.
by nicknash 14y ago
Agreed. The post wasn't meant to suggest anybody should go and optimize! Just that simple looking code can be tricky/interesting. Also, even artificially skewing the pivot in quicksort as suggested in the paper you reference doesn't work ex
39.
by nicknash 14y ago
Well, all the efficient comparison-based sorting algorithms (i.e. O(n log n) time) will cause Omega(n log n) mispredictions. So in a sense they're all the same* At the same time, quicksort has the very nice property that if it accidentally
40.
by nicknash 14y ago
Ah no bother -- always a pleasure Paul!
41.
by nicknash 14y ago
I'm not sure I buy this as a lesson. Choosing between two asymptotically (very) different algorithms (probably linear vs quadratic in your case) isn't really a performance tweak in my book, even though as you point out it wasn't dominant in
42.
by nicknash 14y ago
I'm not sure you're quite right about 1. Depending on what you mean exactly. For example, insertion sort is O(n^2) but mispredicts O(n) times. That doesn't seem often to me. There are (artificial) mergesorts that execute O(nlogn) branches b
43.
by nicknash 14y ago
I think you're right about the name! Some people have really thought about its apparent enduring popularity, e.g. Astrachan's old paper: http://cs.stmarys.ca/~muir/csci4452_11/ClassNotes/Astrachan_...
44.
What’s really so bad about bubble sort?(nicknash.me)
133 points by nicknash 14y ago|58 comments