Validate the network with the time complexity O(L・φ^N)

[mizar]

Let the number of inputs be $N$ and the number of comparators be $L$.

It is well known that the 0-1 principle allows the verification of networks with a computational complexity of $O(L\cdot 2^N)$,

With an ingenious implementation, this can be achieved with a computational complexity of $O(L\cdot\varphi^N)$, where $\varphi$ is the golden number $\varphi=\dfrac{1+\sqrt{5}}{2}\simeq 1.618$.

This is due to the fact that the number of branches in the search tree is a Fibonacci number $\mathrm{Fib}(N+1)=\left\lfloor\dfrac{\varphi^{N+1}}{\sqrt{5}}+\dfrac{1}{2}\right\rfloor$.

The following is a paper (in Japanese) describing this algorithm:

• Hisayasu Kuroda. (1997). A proposal of Gap Decrease Sorting Network. Trans.IPS.Japan, vol.38, no.3, p.381-389. http://id.nii.ac.jp/1001/00013442/
• Hisayasu Kuroda, (1994). A Study of Sorting networks -Gap Decrease Sort-. IPSJ SIG Technical Reports, vol.1994, no.108(1994-HPC-054), p.53-60. http://id.nii.ac.jp/1001/00029885/

Here is an example implementation in Python:

• Improvement of time complexity by DFS brianpursley/sorting-network#9

See also the probrem of competition programming "Verification of Sorting Network" (in Japanese):

• https://yukicoder.me/problems/no/3047
• https://yukicoder.me/problems/no/3047/editorial (needs login)
• https://gist.github.com/mizar/dbed8f81e1b9f483eaf12dd22a50e3a9 (GPT Translate)

This is a demonstration video of a fast N=40 verification using multi-threading. (Executed on Tauri)

• https://x.com/i/status/1897301788824576407

sortingnetwork-tauri-app.2025-03-05.23-54-31.mp4

Note, however, that this method is useful when $N$ is large, but when $N$ is small, the $O(L\cdot 2^N)$ method with SIMD is faster.

[bertdobbelaere]

Hi, thanks for pointing this out to me. I'm interested to understand how this algorithm is working, there may be ideas in it that are insightful. Unfortunately my Japanese is rather bad I trying to get the papers in readable form using online conversion tools didn't immediately give good results, but I'll give it another try later.
I developed a sorting network verification script on my own using a similar algorithm as SorterHunter uses in its "prefix processor" i.e. merging clusters and weeding out patterns that can't occur, I committed it in the "Util" directory so you can compare it. Although my algorithm gives satisfying results, the worst case complexity is not something I studied, so it would be nice to have an algorithm that has clean and low bounds in complexity and memory

[mizar]

Please refer to the following for some description of the contents of the paper:

• Improvement of time complexity by DFS brianpursley/sorting-network#9 (comment)

[mizar]

Partial translation by GPT of the problem and explanation has been added.

• https://gist.github.com/mizar/dbed8f81e1b9f483eaf12dd22a50e3a9

[bertdobbelaere]

Thanks! I understand now how the algorithm works and I think its main advantage over my current verifier so far is that it doesn't consume a lot of memory and has documented worst case complexity.
As for practical speed, I used the network in Sort_36_227_18.json as benchmark.
With the three-valued logic algorithm I got from https://yukicoder.me/submissions/1034656/source, I measured 15.1s
With the cluster merge algorithm from nw_tool.py however, I measured 0.0377s (both runs with pypy3)
Although at first sight much slower, I still like the idea because it might be possible to combine the principles and come to a still faster verification approach, but this will not be trivial

[mizar]

Although there is not much advantage in terms of execution speed, there are implementation variations that reduce the size of state storage by bitwise operations.
https://yukicoder.me/submissions/1042163

[mizar]

An additional approach is to change the search order, remove duplicates.

input (N36L227D18):

1
36 227
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 1 2 3 4 7 8 11 12 15 16 19 20 23 24 27 28 31 32 3 4 5 6 11 12 13 14 19 20 21 22 27 28 29 30 3 4 5 6 7 8 9 10 19 20 21 22 23 24 25 26 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 5 6 9 10 13 14 15 16 25 26 33 34 2 3 4 12 14 17 24 26 3 4 8 18 23 24 4 6 7 8 13 14 17 18 25 28 2 5 6 9 10 11 12 13 16 18 22 23 29 30 3 4 8 10 13 21 22 28 31 32 2 5 8 9 10 12 14 15 16 18 20 26 30 34 3 4 6 10 12 14 16 18 20 22 24 28 29 32 4 6 7 9 10 15 16 17 18 23 24 25 29 32 5 8 10 13 14 17 19 21 22 25 26 30 6 9 13 15 17 18 21 23 26 29 6 9 11 14 16 18 20 22 25 27 30 8 10 12 24 26 28
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 35 36 5 6 9 10 13 14 17 18 21 22 25 26 29 30 33 34 7 8 9 10 15 16 17 18 23 24 25 26 31 32 33 34 11 12 13 14 15 16 17 18 27 28 29 30 31 32 33 34 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3 4 11 12 27 28 23 24 21 22 31 32 35 36 11 13 23 20 33 25 34 35 19 13 14 34 29 33 9 24 19 12 31 20 23 30 29 33 7 8 15 21 24 19 14 27 28 26 31 25 32 35 5 6 9 16 15 27 24 29 33 34 3 7 11 19 23 21 27 17 25 28 22 29 32 35 5 8 9 15 13 19 17 23 21 27 25 31 33 34 5 12 8 13 14 19 20 21 22 27 28 31 30 33 7 11 12 16 15 18 20 24 23 27 29 32 8 11 14 16 19 20 22 24 28 31 7 10 12 15 17 19 21 23 26 28 31 9 11 13 25 27 29

https://yukicoder.me/submissions/1042163 : 6.280s (DFS)
https://yukicoder.me/submissions/1051158 : 0.707s (BFS, remove duplicate status each comparator)
https://yukicoder.me/submissions/1051337 : 0.450s (DFS, remove duplicate status each layer)

[mizar]

This is an implementation that partially incorporates clusters in the BFS approach. N36L227D18 was also used as input.

https://yukicoder.me/submissions/1051837 : 0.045s (PyPy3)
https://yukicoder.me/submissions/1051835 : 0.014s (Rust)

[mizar]

input (N36L227D18)

nw_tool.py : 0.021s (PyPy3)
https://yukicoder.me/submissions/1054117 : 0.028s (PyPy3)
https://yukicoder.me/submissions/1054116 : 0.007s (C++)

input (N51L389D20)

1
51 389
2 4 5 6 9 10 13 14 17 18 21 22 25 26 29 30 33 34 37 38 41 42 45 46 49 1 4 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 50 1 2 5 6 8 9 10 12 13 14 16 18 20 21 22 24 25 26 30 34 38 42 46 49 2 3 5 6 7 8 9 10 11 12 14 15 16 17 19 22 23 26 28 29 33 40 1 4 5 6 7 8 10 11 12 13 15 18 20 27 28 29 30 34 37 39 44 2 3 4 6 8 11 14 16 17 19 20 21 27 28 30 35 38 41 43 46 1 3 4 7 12 15 17 18 20 22 24 25 27 32 34 37 40 42 1 2 7 9 11 12 13 14 16 18 19 23 24 25 26 31 33 36 38 48 2 4 7 9 10 15 16 19 21 26 28 30 31 33 36 42 44 47 4 5 6 10 11 13 22 24 25 27 32 35 38 39 44 5 6 11 13 14 16 19 20 21 22 23 26 28 29 35 36 43 3 9 10 12 15 16 17 18 20 23 24 26 31 32 34 39 40 2 6 8 10 11 14 15 19 22 24 27 32 33 35 40 44 2 3 7 8 14 16 18 20 23 24 27 28 31 34 40 50 3 7 8 9 11 12 15 19 24 28 31 32 35 36 39 48 3 7 8 12 16 20 22 24 27 28 30 32 36 40 44 49 8 11 12 15 16 19 20 23 24 26 28 31 32 35 36 39 40 43 5 9 10 13 14 17 18 21 23 25 26 29 31 33 34 37 38 41 42 45 5 7 9 11 13 15 17 19 21 22 25 27 29 30 33 35 37 39 41 43 45 47 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48
3 50 7 8 11 12 15 16 19 20 23 24 27 28 31 32 35 36 39 40 43 44 47 48 51 2 49 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 51 4 3 41 7 32 37 11 48 29 15 44 19 28 45 23 40 33 27 31 35 39 43 47 50 49 50 25 42 31 36 13 38 47 20 30 43 24 45 27 46 39 34 48 37 41 44 17 45 9 26 35 51 14 19 16 25 23 46 24 47 40 33 38 42 41 43 48 18 7 33 10 12 15 26 32 25 23 51 37 39 36 34 50 42 45 47 49 21 11 13 19 16 31 29 26 28 38 36 33 35 44 46 41 51 49 5 22 27 21 15 20 29 34 28 30 39 35 40 37 46 50 41 44 42 51 6 5 11 17 22 27 20 23 25 38 32 34 43 37 48 46 51 50 9 17 14 18 15 21 26 28 29 31 40 43 42 47 48 9 10 37 17 18 42 27 24 25 30 31 34 32 33 39 40 47 29 13 14 33 19 37 21 22 41 27 49 30 35 36 38 43 44 13 9 34 21 29 18 20 45 26 42 31 43 38 39 50 47 4 13 22 19 25 26 29 30 33 35 37 39 46 45 49 51 5 17 21 14 18 22 25 29 34 38 41 45 42 46 44 49 4 9 13 17 21 25 23 26 29 33 31 37 41 45 46 50 10 13 14 17 18 21 22 25 27 29 30 33 34 37 38 41 42 45 8 11 12 15 16 19 20 22 24 27 28 30 32 35 36 39 40 43 44 48 6 8 10 12 14 16 18 20 23 24 26 28 31 32 34 36 38 40 42 44 46 48 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49

nw_tool.py : 5.547s (PyPy3)
https://yukicoder.me/submissions/1054117 : 5.028s (PyPy3)
https://yukicoder.me/submissions/1054116 : 1.241s (C++)

[mizar]

Network Verification demo (Rust, Tauri):

sortingnetwork-tauri-app.2025-03-19.15-27-51-1.mp4

[mizar]

demo app:
https://github.com/mizar/sortingnetwork-tauri-app