Practical application of SNs
Opened this issue · 3 comments
Sorry I'm using this issue tracker as a place to dump cool links; maybe we should make some kind of wiki page?
Anyway see appendix S in the following paper: https://ntruprime.cr.yp.to/ntruprime-20170816.pdf
It describes a vectorised implementation of an n=32 merge-exchange net used for constant-time sorting. I have some more info on constant time applications in slides 31-33 of my (now pretty dated) presentation:
It's good. At the moment I view these as requests for implementations, which I definitely need to start on (two projects in the way right now). But a wiki page that listed the different types of sorting networks would be a good idea.
As long as we're on the subject, I acquired a book I never knew existed: Designing Sorting Networks, by Al-Haj Badder & Batcher. You may recognize their names.
Hehe yes I recognise them. I never got a copy of the book but I found a PDF of Baddar's PhD thesis online which I think had a lot of the same material.
DJB just released a sort-of general purpose implementation: