Changed division semantics
Friday, 26. January 2007, 15:14:01
The new division semantics may appear to be strange at first but is carefully crafted to make it possible to do an efficient transpose of a list.
Let's say we want to transpose the following '3x4 list':
[1; 2; 3 4; 5; 6 7; 8; 9 10;11;12]
To do this we first right-multiply the list with the number of columns (3):
3 [ 1; 2; 3
4; 5; 6
7; 8; 9
10;11;12] *
36 [ 1; 2; 3
4; 5; 6
7; 8; 9
10;11;12
1; 2; 3
4; 5; 6
7; 8; 9
10;11;12
1; 2; 3
4; 5; 6
7; 8; 9
10;11;12]
After that, we left-divide the result with the number of columns:
36 [ 1; 2; 3
4; 5; 6
7; 8; 9
10;11;12
1; 2; 3
4; 5; 6
7; 8; 9
10;11;12
1; 2; 3
4; 5; 6
7; 8; 9
10;11;12] 3 /
giving us the transpose we want:
36 [ 1; 4; 7;10
2; 5; 8;11
3; 6; 9;12] 1
To understand the new division semantics, it is best to picture it as being a digital line-drawing algorithm with x's being the pixels of a line.
The previous version of division would draw the following line:
[ x; 2; 3
x; 5; 6
x; 8; 9
x;11;12
x; 2; 3
x; 5; 6
x; 8; 9
x;11;12
x; 2; 3
x; 5; 6
x; 8; 9
x;11;12]
while the new version draws the line from top-left to bottom-right:
[ x; 2; 3
x; 5; 6
x; 8; 9
x;11;12
1; x; 3
4; x; 6
7; x; 9
10; x;12
1; 2; x
4; 5; x
7; 8; x
10;11; x]
What makes the new division interesting is that the same trick can be achieved on huge lists. For instance the following code transposes a 50000x50000 matrix:
50000 2500000000 ~ * 50000 /
producing the result:
125000000000000 [0;50000;100000;150000;200000;250000;300000;
350000;400000;450000;500000;550000;600000;650000;700000;750000
... {2500000000} ... 2499299999;2499349999;2499399999;2499449999;
2499499999;2499549999;2499599999;2499649999;2499699999;2499749999;
2499799999;2499849999;2499899999;2499949999;2499999999] 1
You can find the newest version (0_5_5) on the Enchilada website.
WIDGETIZE