4 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
source | link

In my other answerother answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five² can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five² can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five² can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].
3 adds a note about ordering the two selected elements
source | link

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of fivefive² can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five² can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].
2 added 100 characters in body
source | link

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar.  Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar.  

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, selection networks have also been studied. Knuth tells us that finding the two smallest numbers out of five can be done with $\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
1
source | link