Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What algorithm blows your mind? (Reddit compsci)

reddit.com

Post reply on HN
Print view View original

51–60 of 71 posts

Re: What algorithm blows your mind? (Reddit compsci)

#51

Post by lmkg »

michael_nielsen wrote: post #28
cperciva wrote: post #27

My mind is blown by the algorithm for matching with mismatches which I present in the first chapter of my thesis. It shouldn't be, given that I discovered this algorithm -- but somehow "I take the Fourier Transfer of the FreeBSD kernel" sounds more like the punch line to a joke than the first step in an algorithm.

Speaking of incredibly cool algorithms based on Fourier transforms, the Schoenage-Strassen algorithm for multiplying integers is also amazing: http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen... At least to me, it seems hard to imagine that multiplying two N-bit integers could be done with less than O(N^2) operations. Schoenage-Strassen lets you do it using O(N log N log log N) operations!

This is the one that blew my mind. "If we treat the numbers as polynomials, then the multiplication can be reduced to a Fourier transform!" is also one of those things that sounds like a punchline. Each step of the algorithm just sounds stupider and stupider, and slower and slower... and then you get to the last step, where all the multiplications by exponentials of complex numbers get replaced by bitshifts. Suddenly the entire algorithm collapses in on itself to reveal something efficient.

Re: What algorithm blows your mind? (Reddit compsci)

#52

Post by Zaak »

jules wrote: post #44
RiderOfGiraffes wrote: post #33

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9... High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

Why are high dimensional spheres spikey?

I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.

Re: What algorithm blows your mind? (Reddit compsci)

#53

Post by cperciva »

signa11 wrote: post #32
bobds wrote: post #22

Earlier quoted context omitted.

Also the fact that you can use more bits per element and reduce the error rate for false positives. Using around 3 bytes per element, can bring the error rate down to 0.001%.

also the fact that you can use multiple hash functions to reduce the error rate even further is pretty nice. this is of course without incurring the overhead of extra storage space...

Using multiple hash functions requires that you use additional storage in order to maintain the same occupancy ratio.

Re: What algorithm blows your mind? (Reddit compsci)

#54

Post by cperciva »

Zaak wrote: post #52
jules wrote: post #44

Earlier quoted context omitted.

Why are high dimensional spheres spikey?

I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.

Not at all. The expected distance between the center of an n-ball and a random point in the ball is n/(n+1) times the radius.

Now, if you look at an n-sphere with respect to orthogonal axes, you find that moving along an axis you get out as far as (1, 0, ... 0) and moving "away" from the axes you only get to (1/sqrt(n), 1/sqrt(n), ... 1/sqrt(n)); but this isn't due to the sphere being spiky -- rather, it's because orthogonal axes are spiky.

Re: What algorithm blows your mind? (Reddit compsci)

#55

Post by orangecat »

RiderOfGiraffes wrote: post #48
jules wrote: post #44

Earlier quoted context omitted.

Why are high dimensional spheres spikey?

Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore. I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful. Please. Thanks.

Please do. My guess would be similar to Zaak's: the n-dimensional volume of an n-dimensional hypersphere approaches 0 as n approaches infinity. (http://www.mathreference.com/ca-int,hsp.html). A hypersphere with radius 1 centered at the origin has to get out to 1 along each axis (e.g. x=1, y=z=0 for a 3 dimensional sphere), and in order for that not to contribute much volume, it has to be a narrow spike rather than a gradual curve.

Re: What algorithm blows your mind? (Reddit compsci)

#56

Post by pjscott »

nl wrote: post #16

Bloom Filters: http://en.wikipedia.org/wiki/Bloom_filter Sort of a probabilistic hash, where you trade space for accuracy. But it's also like a memory function - it can remember if it has seen a piece of data before.

I love that they're fast enough to use in hardware. Some of the newer schemes for hardware-accelerated transactional memory use Bloom filters to probabilistically detect when two transactions are using the same memory addresses. This is so much easier and more efficient than previous approaches, which had to use content associative memories and expensive broadcast operations.

Re: What algorithm blows your mind? (Reddit compsci)

#57

Post by dlnovell »

The Genetic Algorithm. It totally blew my mind when I read about it's successful application to evolving satellite antennas for JPL, and the automated design of an analog->digital signal converter that relies on a component that isn't actually connected to anything else.

Re: What algorithm blows your mind? (Reddit compsci)

#58

Post by varjag »

ardit33 wrote: post #4

Kruskal, Prims and reverse-delete algorithms to find the Minimum Spanning Tree in a graph, are fun, not that hard, and very practical. http://en.wikipedia.org/wiki/Minimum_spanning_tree Think about it, every time you get a google map direction/route, one of them is in play.

Also a bit different, but perhaps even more widespread application of spanning trees is STP family of L2 network bridging protocols.

http://en.wikipedia.org/wiki/Rapid_Spanning_Tree_Protocol

Re: What algorithm blows your mind? (Reddit compsci)

#59

Post by chrisaycock »

Poul-Henning Kamp (creator of Varnish) recently published the B-heap algorithm. It's a cache-friendly version of the binary heap storage we all learned as freshmen.

PHK points out that mapping node n to nodes 2n and 2n+1 will cause cache misses (and often page faults) as we vertically descend the tree. So instead, rearrange the mapping so that the child nodes are often very near their parent node. That way, heap comparisons are usually performed in the same virtual page, which cuts-down on the number of disk accesses the operating system must perform.

http://queue.acm.org/detail.cfm?id=1814327

Re: What algorithm blows your mind? (Reddit compsci)

#60

Post by davidj »

493108359702850190027577767239076495728490777215020863208075 018409792627885097658864557802013660073286795447341128317353 678312015575359819785450548115719393458773300380099326195058 764525023820408110189885042615176579941704250889037029119015 870030479432826073821469541570330227987557681895601624030064 111516900872879838194258271674564774816684347928464580929131 531860070010043353189363193439129486044503709919800477094629 215581807111691530318762884778783541575932891093295447350881 882465495060005019006274705305381164278294267474853496525745 368151170655028190555265622135314631042100866286797114446706 366921982586158111251555650481342076867323407655054859108269 562666930662367997021048123965625180068183236539593483956753 575575324619023481064700987753027956186892925380693305204238 149969945456945774138335689906005870832181270486113368202651 590516635187402901819769393767785292872210955041292579257381 866058450150552502749947718831293104576980909153046133594190 302588132059322774443852550466779024518697062627788891979580 423065750615669834695617797879659201644051939960716981112615 195610276283233982579142332172696144374438105648552934887634 921030988702878745323313253212267863328370279250997499694887 759369159176445880327183847402359330203748885067557065879194 611341932307814854436454375113207098606390746417564121635042 388002967808558670370387509410769821183765499205204368255854 642288502429963322685369124648550007559166402472924071645072 531967449995294484347419021077296068205581309236268379879519 661997982855258871610961365617807456615924886608898164568541 721362920846656279131478466791550965154310113538586208196875 836883595577893914545393568199609880854047659073589728989834 250471289184162658789682185380879562790399786294493976054675 348212567501215170827371076462707124675321024836781594000875 05452543537
Post reply on HN