AppleTV DNS大法挂了是不是彻底挂了 (转载)# PDA - 掌中宝
x*w
1 楼
矩阵乘法，维度不一定是2的power, divided and conquer
C1 C2 A1 A2 B1 B2
= *
C3 C4 A3 A4 B3 B4
C1 = A1*B1 + A2*B3
C2 = A1*B2 + A2*B4
.........
inplace的程序感觉蛮tricky的：
===========================================
public class StrassenMatrixAlgo {
static void _inner_mul(int[][] a, int ra, int ca, int[][] b, int rb, int cb
,
int[][] c, int rc, int cc, int dim, int orgDim)
{
if (rc >= orgDim || cc >= orgDim ||
ra >= orgDim || ca >= orgDim ||
rb >= orgDim || cb >= orgDim)
return;
if (dim <= 1)
{
c[rc][cc] += a[ra][ca] * b[rb][cb];
return;
}
//c1
_inner_mul(a, ra, ca, b, rb, cb, c, rc, cc, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb, c, rc, cc, dim/2, orgDim);
//c2
_inner_mul(a, ra, ca, b, rb, cb + dim/2, c, rc, cc + dim/2, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc, cc + dim/2
, dim/2, orgDim);
//c3
_inner_mul(a, ra + dim/2, ca, b, rb, cb, c, rc + dim/2, cc, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb, c, rc + dim/2, cc
, dim/2, orgDim);
//c4
_inner_mul(a, ra + dim/2, ca, b, rb, cb + dim/2, c, rc + dim/2, cc + dim/2
, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc +
dim/2, cc + dim/2, dim/2, orgDim);
}
static int[][] MatrixMultiple(int[][] a, int[][] b)
{
int dim = a.length;
int[][] c = new int[dim][dim];
int d = 1;
while (d < a.length)
d *= 2;
_inner_mul(a, 0, 0, b, 0, 0, c, 0, 0, d, dim);
return c;
}
public static void main(String[] strs)
{
int[][] a = {{1,0,2}, {2,1,1}, {1,3,2}};
int[][] b = {{0,1,0}, {1,1,2}, {2,0,1}};
int[][] c = MatrixMultiple(a, b);
}
}
C1 C2 A1 A2 B1 B2
= *
C3 C4 A3 A4 B3 B4
C1 = A1*B1 + A2*B3
C2 = A1*B2 + A2*B4
.........
inplace的程序感觉蛮tricky的：
===========================================
public class StrassenMatrixAlgo {
static void _inner_mul(int[][] a, int ra, int ca, int[][] b, int rb, int cb
,
int[][] c, int rc, int cc, int dim, int orgDim)
{
if (rc >= orgDim || cc >= orgDim ||
ra >= orgDim || ca >= orgDim ||
rb >= orgDim || cb >= orgDim)
return;
if (dim <= 1)
{
c[rc][cc] += a[ra][ca] * b[rb][cb];
return;
}
//c1
_inner_mul(a, ra, ca, b, rb, cb, c, rc, cc, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb, c, rc, cc, dim/2, orgDim);
//c2
_inner_mul(a, ra, ca, b, rb, cb + dim/2, c, rc, cc + dim/2, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc, cc + dim/2
, dim/2, orgDim);
//c3
_inner_mul(a, ra + dim/2, ca, b, rb, cb, c, rc + dim/2, cc, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb, c, rc + dim/2, cc
, dim/2, orgDim);
//c4
_inner_mul(a, ra + dim/2, ca, b, rb, cb + dim/2, c, rc + dim/2, cc + dim/2
, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc +
dim/2, cc + dim/2, dim/2, orgDim);
}
static int[][] MatrixMultiple(int[][] a, int[][] b)
{
int dim = a.length;
int[][] c = new int[dim][dim];
int d = 1;
while (d < a.length)
d *= 2;
_inner_mul(a, 0, 0, b, 0, 0, c, 0, 0, d, dim);
return c;
}
public static void main(String[] strs)
{
int[][] a = {{1,0,2}, {2,1,1}, {1,3,2}};
int[][] b = {{0,1,0}, {1,1,2}, {2,0,1}};
int[][] c = MatrixMultiple(a, b);
}
}
