On this topic we could see an interesting discussion about how make the fastest euclidean distance.
But I have see that on Octave, it is not true at all...
a= rand(1000, 800);
b= rand(1000, 800);
tic; d = sqrt( sum((a-b) .* (a-b),2)); toc;
tic; d = sqrt( sum(a.*a + b.*b - 2 *( a .*b),2)); toc;
d = abs(aa( ones(size(bb,2),1), :)' + bb( ones(size(aa,2),1), :) - 2*a'*b); toc
A => Elapsed time is 0.02084 seconds.
B => Elapsed time is 0.0335 seconds.
C => Elapsed time is 1.49 seconds.
So on my machine the naive method is the fastest, certainly due the fact that octave do not use SSE library for my part.