Guest
|
 Posted:
Wed Jul 20, 2005 8:15 am Post subject:
SIMD interleave |
|
|
It was recently asked:
| Quote: | I have a pricky problem of interleaving large
uni-dimensional arrays. How can it be done in-place?
|
| Quote: | How to map the following
|
| Quote: | ----------------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | etc etc | N - 1 |
----------------------------------------------------------
|
| Quote: | --------------------------------------------
| 0 | N/2 | 1 | N/2+1 | 2 | N/2+3 | etc etc |
--------------------------------------------
|
In place. That does seem to make things complicated.
For a concrete example:
0 1 2 3 4 5 6 7
0 4 1 5 2 6 3 7
if we try to do it 'in place', we begin by leaving 0 and 7 alone.
Copy 1, write it in 2; copy 2, write it in 4; copy 4, write it in 1.
Copy 3, write it in 6; copy 6, write it in 5; copy 5, write it in 3.
Note that we need to remember two numbers at once, since we need to
copy numbers just before we over-write them. If we reverse the order,
the second number to be remembered just gets used at the end.
But how do we change this into a general algorithm?
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F
Here, we have a chain involving the powers of 2: 1, 2, 4, 8; another
chain starting with 3: 3, 6, C, 9; another chain starting with 5: 5, A;
another chain starting with 7: 7, E, D, B.
John Savard |
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in