# [Numpy-discussion] fast way of doing "cross-multiplications" ?

Tim Hochberg tim.hochberg at cox.net
Tue Jul 18 11:13:23 CDT 2006

```Eric Emsellem wrote:
> thanks for the tips. (indeed your "add.reduce" is correct: I just wrote
> this down too quickly, in the script I have a "sum" included).
>
> And yes you are right for the memory issue, so I may just keep the loop
> in and try to make it work on a fast PC...(or use parallel processes)
>
> (is "sum" different than "add.reduce"?)
>
> thanks again to both Bill Baxter and Perry Greenfield for their fast
>
I just wanted to add that there are faster, but considerably complicated
ways to attack this class of problems. The one I've looked at in the
past was the fast multipole method and I believe there are others. I'm
not sure whether these can be implemented efficiently in numpy, but you
may want to take a look into this kind of more sophisticated/complicated
approach if brute forcing the calculation doesn't work.

-tim

> cheers
>
> Eric
>
> Perry Greenfield wrote:
>
>> On Jul 18, 2006, at 10:23 AM, Eric Emsellem wrote:
>>
>>
>>> Hi,
>>>
>>> I have a specific quantity to derive from an array, and I am at the
>>> moment unable to do it for a too large array because it just takes too
>>> long! So I am looking for an advice on how to efficiently compute such a
>>> quantity:
>>>
>>> I have 3 arrays of N floats (x[...], y[..], z[..]) and I wish to do:
>>>
>>> result = 0.
>>> for i in range(N) :
>>>    for j in range(i+1,N,1) :
>>>       result += 1. / sqrt((x[j] - x[i])**2 + (y[j] - y[i])**2 + (z[j] -
>>> z[i])**2)
>>>
>>>
>>> Of course the procedure written above is very inefficient and I thought
>>> of doing:
>>>
>>> result = 0.
>>> for i in range(N) :
>>>    result += 1. / sqrt((x[i+1:] - x[i])**2 + (y[i+1:] - y[i])**2 +
>>> (z[i+1:] - z[i])**2)
>>>
>>> Still, this is quite slow and not workable for very large arrays (> 10^6
>>> floats per array).
>>>
>>> Any hint on how to speed things up here?
>>>
>>>
>>> Eric
>>>
>> Perhaps I'm misunderstanding the last variant but don't you want
>> something like:
>>
>> result = 0.
>> for i in range(N) :
>>    result += add.reduce(1. / sqrt((x[i+1:] - x[i])**2 + (y[i+1:] -
>> y[i])**2 +
>> (z[i+1:] - z[i])**2))
>>
>> instead since the expression yields an array with a decreasing size
>> each iteration?
>>
>> But besides that, it seems you are asking to do roughly 10^12 of these
>> computations  for 10^6 points. I don't see any way to avoid that given
>> what you are computing. The solution Bill Baxter gives is fine (I
>> think, I haven't looked at it closely), but the usual problem of doing
>> it without any looping is that it requires an enormous amount of
>> memory (~10^12 element arrays) if I'm not mistaken. Since your second
>> example is iterating over large arrays (most of the time, not near the
>> end), I'd be surprised if you can do much better than that (the
>> looping overhead should be negligible for such large arrays). Do you
>> have examples written in other languages that run much faster? I guess
>> I would be surprised to see it possible to do more than a few times
>> faster in any language without some very clever optimizations.
>>
>> Perry
>>
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>
>
>

```