1

I'm trying to invent or find a distance function in a two-dimensional space that only makes use of the basic arithmetic operations (+,-,*,/) as I want to use that function in a "programming language" that only supports these operations (and no if/else statements etc.). Do you have any idea what could help me here?

Pold
  • 133
  • If you are unable to use the square root operation, then you must settle for approximate distances. – Austin Mohr Jan 31 '14 at 04:57
  • Yes, that would be fine. In fact, the taxicab geometry/Manhattan length would really fulfill my needs but it makes use of the absolute value. – Pold Jan 31 '14 at 05:03
  • I don't think it's possible to make a practical language without any if/then – qwr Jan 31 '14 at 05:18
  • What about relational operators like $>$ and $<$? I ask because you can often avoid if/then clauses with statements like z = x * ( y < 1 ) + -1 * x ( y >= 1 ) rather than if(y < 1 ) then z = x, else z = -x. – AnonSubmitter85 Jan 31 '14 at 05:28
  • I intepret @Pold 's question as without any kind of conditional statement – qwr Jan 31 '14 at 05:35
  • @qwr I'd consider a relational test as fundamentally different from a conditional statement. Conditionals would imply branching, while a relational test is just another value output from the ALU and written to memory. – AnonSubmitter85 Jan 31 '14 at 05:40

2 Answers2

0

You can approximate square roots with the Babylonian method. It can calculate to any precision without branching (if / then / else)

qwr
  • 10,716
  • But what about determining the starting value and when you can stop iterating? – AnonSubmitter85 Jan 31 '14 at 05:27
  • If you really want to avoid conditional statements, you can start at any positive value. You can determine a set amount of iterations, that is not conditional. – qwr Jan 31 '14 at 05:32
0

So, as I understand it, you need some way to measure "distance" between two points in $\mathbb R^2$.

Let's denote two typical points by $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$.

The simplest distance function is $d(P_1,P_2) = 0$ if $P_1=P_2$ and $d(P_1,P_2) = 1$ otherwise. This is in fact a "distance" function (in the sense of metric spaces) but it might be too crude for your purposes.

Another option is $$ d(P_1,P_2)=(x_1-x_2)^2 + (y_1-y_2)^2 $$

This is obviously the square of the normal Euclidean distance, but it might work for you. Depends what properties you want, of course.

bubba
  • 43,483
  • 3
  • 61
  • 122
  • I accept this answer. Of course, I was thinking about using the squared Euclidean distance before posting my question. Now, as there seem to be no other working solutions, I'll use it in my code. – Pold Feb 07 '14 at 03:57