Sorry, I can't follow you. What exactly is SUMi?fxm wrote:X1 = 1, X2 = 6
SUMi(Xi^2) = 37
SUMi(SQR(Xi^2)) = 7
X1 = 3, X2 = 5
SUMi(Xi^2) = 34
SUMi(SQR(Xi^2)) = 8
Between these two examples, SUMi(Xi^2) decreases while SUMi(SQR(Xi^2)) increases.
How would you find the shortest distance in a set of points?
Re: How would you find the shortest distance in a set of points?
Re: How would you find the shortest distance in a set of points?
fxm wrote:@dodicat,
Let SUMi(Yi) = Y1 + Y2 + Y3 + .....
We can not compare:
SUMi(Xi^2) = X1^2 + X2^2 + .....
with:
SUMi(SQR(Xi^2)) = SQR(X1^2) + SQR(X2^2) + .....
because the SQR function induces a nonlinearity in the sum.
Examples (with a sum of 2 terms) where that fails:
X1 = 1, X2 = 6
SUMi(Xi^2) = 1^2 + 6^2 = 37
SUMi(SQR(Xi^2)) = 1 + 6 = 7
X1 = 3, X2 = 5
SUMi(Xi^2) = 3^2 + 5^2 = 34
SUMi(SQR(Xi^2)) = 3 + 5 = 8
Between these two examples, SUMi(Xi^2) decreases while SUMi(SQR(Xi^2)) increases.
This is what the dodicat's code does (viewtopic.php?p=273613#p273613).
Re: How would you find the shortest distance in a set of points?
Thanks, that is much clearer now. Are you sure that dodicat's code sums up the elements (wrongly) as SQR(X1^2) + SQR(X2^2)?To me, it looks like the correct Pythagoras: A²+B²=C² or rather dx²+dy²=dist²
Code: Select all
#define rawlength(a,b) ((a.xb.x)*(a.xb.x)+(a.yb.y)*(a.yb.y))
Re: How would you find the shortest distance in a set of points?
I'm talking about this line of code:
if f=0 then total+=sqr(L) else total+=L
in the function 'distance(points() As pt,f as long=0) As double'.
He then compares (in viewtopic.php?p=273613#p273613) the results ('total') obtained with f=0 or f=1:
if f=0 then total+=sqr(L) else total+=L
in the function 'distance(points() As pt,f as long=0) As double'.
He then compares (in viewtopic.php?p=273613#p273613) the results ('total') obtained with f=0 or f=1:
Code: Select all
original distance 353607.8960705228
pseudo dist array dist
1e+020
157149997 358751.941673827 1
156502903 355714.6772599964 3
150981928 348062.2103850992 6
149868626 345199.2785204384 34
148818352 347659.1081542731 184
148261510 343807.2098599597 400
146532917 340238.0074669157 572
146378242 342773.662772364 2215
146264168 342588.527484985 6106
146006296 343279.4116236997 13841
optimized distance 343279.4116236997
1.352633499987817 seconds

 Posts: 2583
 Joined: Jan 02, 2017 0:34
 Location: UK
Re: How would you find the shortest distance in a set of points?
I am a bit pushed for time at the moment but this may be useful. It simply calculates the square root of four singles in parallel and is faster than the FPU with one single. The asm is by Paul Dixon at the PowerBASIC forum in a thread discussing a very different topic.
On my machine 100,000 Sqrt4() comes in at just less than half a millisecond.
On my machine 100,000 Sqrt4() comes in at just less than half a millisecond.
Code: Select all
'#Console On
Type Single4
first AS Single
second AS Single
third AS Single
fourth AS Single
End Type
#macro Sqrt4(a)
Asm
movups xmm0, a
sqrtps xmm0,xmm0
movups a, xmm0
End ASm
#endmacro
Dim As Single4 a
a.first = 123.456
a.second = 234.567
a.third = 345.678
a.fourth = 456.789
Sqrt4(a)
Print a.first, a.second, a.third, a.fourth
Sleep
Last edited by deltarho[1859] on Jun 29, 2020 21:51, edited 1 time in total.
Re: How would you find the shortest distance in a set of points?
Thanks fxm.
Just because a sum of squared distances through points might be greater than another sum of squared distances doesn't mean that the actual distance is also greater.
So the squared distances can be used for comparisons with each other, and have no direct associations with actual distances.
So they shouldn't be mixed.
Yea, that's it fxm, your simple example shows this.
Thanks again.
Just because a sum of squared distances through points might be greater than another sum of squared distances doesn't mean that the actual distance is also greater.
So the squared distances can be used for comparisons with each other, and have no direct associations with actual distances.
So they shouldn't be mixed.
Yea, that's it fxm, your simple example shows this.
Thanks again.
Re: How would you find the shortest distance in a set of points?
@dodicat: I've tried to understand your code, and especially why you sum up the "total distance". You are not doing two loops as shown below, how will you identify the two closest points?
Below pts() is the array of points. It's Assembly but I hope it's understandable. The instructions mov and mrm assign values to the first operand; mul eax is like x=eax*eax
Below pts() is the array of points. It's Assembly but I hope it's understandable. The instructions mov and mrm assign values to the first operand; mul eax is like x=eax*eax
Code: Select all
For_ ecx=0 To points1 ; setup
mov pts(ecx, x), Rand(GuiWidth) ; assign random
mov pts(ecx, y), Rand(GuiHeight) ; x+y values
Next
mov minDist, 9999 ; start with a high value to trigger the comparisons
For_ ct=0 To points1 ; outer loop
mrm px, pts(ct, x) ; get x and y of
mrm py, pts(ct, y) ; the current point
mov ecx, ct ; take the index of the current point...
.Repeat
inc ecx ; ... and compare to all following points
mov eax, pts(ecx, x) ; get x of inner loop point
sub eax, px ; subtract x of outer loop point
mul eax ; square it: dx^2
push eax ; save dx^2
mov eax, pts(ecx, y) ; get y of inner loop point
sub eax, py ; subtract y of outer loop point
mul eax ; square it: dy^2
pop edx ; get dx^2 back
add eax, edx ; dx^2+dy^2 to eax
.if eax<minDist
mov pointB, ecx ; remember the index of the inner loop point
m2m pointA, ct ; remember the index of the outer loop point
mov minDist, eax ; and the distance, of course
.endif
.Until ecx>=points ; end of inner loop
Next

 Posts: 326
 Joined: Dec 02, 2011 22:51
 Location: France
Re: How would you find the shortest distance in a set of points?
I just try to thought a little around this problematic, not seeking for solutions around the web. I tried to think about ideas but,... Not around mathematics, just logic. Am I wrong or this problem may be far more complex than what it could looks like at first sight ?
Re: How would you find the shortest distance in a set of points?
jj2007
My distance function simply returns the total distance through the array.
I must use total the sqr(L) of course and not the L, for reasons discussed (fxm).
My own (mov minDist, 9999) is actually 1e20 to start,and the minimum is found in the 1 to 20000 loop.
I don't need two loops for this.
As soon as a new minimum (distance, not squared distance) is found the array configuration is saved in the opt() array.
To get the (distance, not squared distance), the distance function is called with
distance(p(),0). (I have it distance(p(),1) in the code which is in error because it yields the squared distance with the flag 1.
A rule of thumb I will remember is that If I find the smallest squared or Manhattan distance then I will have found the smallest squared or Manhattan distance, and not the smallest distance, it is elementary really, but I got a bit caught out.
The whole thing comes under the travelling salesman problem which has a non analytic brute force solution.
The second piece of code (to get the two closest points) is a bit easier, just use bubble sort loops (two) to bring every array point to every other array point just once and measure the squared distance each time and get a minimum yielding the two array indices of the closest two when the loops are completed
I think your asm code does this.
My distance function simply returns the total distance through the array.
I must use total the sqr(L) of course and not the L, for reasons discussed (fxm).
My own (mov minDist, 9999) is actually 1e20 to start,and the minimum is found in the 1 to 20000 loop.
I don't need two loops for this.
As soon as a new minimum (distance, not squared distance) is found the array configuration is saved in the opt() array.
To get the (distance, not squared distance), the distance function is called with
distance(p(),0). (I have it distance(p(),1) in the code which is in error because it yields the squared distance with the flag 1.
A rule of thumb I will remember is that If I find the smallest squared or Manhattan distance then I will have found the smallest squared or Manhattan distance, and not the smallest distance, it is elementary really, but I got a bit caught out.
The whole thing comes under the travelling salesman problem which has a non analytic brute force solution.
The second piece of code (to get the two closest points) is a bit easier, just use bubble sort loops (two) to bring every array point to every other array point just once and measure the squared distance each time and get a minimum yielding the two array indices of the closest two when the loops are completed
I think your asm code does this.
Who is online
Users browsing this forum: Google [Bot] and 3 guests