双和优化

Question

最近我在我的一次采访中得到了这个问题,我很遗憾地跳过了,但我很想知道答案.你能帮助我吗？

int sum = 0;
int num = 100000000;
for (int i = 0; i < num; i++){
    for (int j = 0; j < num; j++ ){
        sum += m_DataX[i] * m_DataX[j];
    }
}

编辑:此外,我想看看是否有可能优化,如果我们有以下表达式sum:

sum += m_DataX[i] * m_DataY[j];

Answer 1

简单地说,数字之和的平方.为什么？

让一个数组是, |1|2|3|

然后,代码生成

1*1 + 1*2 + 1*3
2*1 + 2*2 + 2*3
3*1 + 3*2 + 3*3

那是,

(1*1 + 1*2 + 1*3)+ (2*1 + 2*2 + 2*3)+(3*1 + 3*2 + 3*3)

=>1(1+2+3) + 2(1+2+3) + 3(1+2+3)

=> (1+2+3)*(1+2+3)

因此,代码将是

int tempSum = 0;
for (int i = 0; i < num ; i ++){
   tempSum+=m_DataX [i];
}

sum=tempSum*tempSum;

更新:

如果, sum += m_DataX[i]*m_DataY[j]

让两个数组是,|1|2|3|和|4|5|6|

因此,

1*4 + 1*5 + 1*5
2*4 + 2*5 + 2*6
3*4 + 3*5 + 3*6

=> 1*4 + 2*4 + 3*4+ 1*5 + 2*5 + 3*5+ 1*6 + 2*6 + 3*6 => (1+2+3)*(4+5+6)