Approximation of square root of sum of two squared terms
I have the following equation
$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}$. I want to get rid of square-root and find an approximation which contains only $x_a,x_n,y_a,y_n$ (there should not be any other non-linear operator in the approximation). Can anyone help me in this matter and guide me to the right direction?
$x_n <x_a, y_n<y_a, y_a<x_a$ and $x_a,x_n,y_a,y_n in[-1,1]$. However, $y_n$ is not always less than $x_n$.
real-analysis approximation radicals
|
show 4 more comments
I have the following equation
$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}$. I want to get rid of square-root and find an approximation which contains only $x_a,x_n,y_a,y_n$ (there should not be any other non-linear operator in the approximation). Can anyone help me in this matter and guide me to the right direction?
$x_n <x_a, y_n<y_a, y_a<x_a$ and $x_a,x_n,y_a,y_n in[-1,1]$. However, $y_n$ is not always less than $x_n$.
real-analysis approximation radicals
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53
|
show 4 more comments
I have the following equation
$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}$. I want to get rid of square-root and find an approximation which contains only $x_a,x_n,y_a,y_n$ (there should not be any other non-linear operator in the approximation). Can anyone help me in this matter and guide me to the right direction?
$x_n <x_a, y_n<y_a, y_a<x_a$ and $x_a,x_n,y_a,y_n in[-1,1]$. However, $y_n$ is not always less than $x_n$.
real-analysis approximation radicals
I have the following equation
$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}$. I want to get rid of square-root and find an approximation which contains only $x_a,x_n,y_a,y_n$ (there should not be any other non-linear operator in the approximation). Can anyone help me in this matter and guide me to the right direction?
$x_n <x_a, y_n<y_a, y_a<x_a$ and $x_a,x_n,y_a,y_n in[-1,1]$. However, $y_n$ is not always less than $x_n$.
real-analysis approximation radicals
real-analysis approximation radicals
edited Nov 24 at 22:11
asked Nov 24 at 21:26
Muhammad Usman
136
136
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53
|
show 4 more comments
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53
|
show 4 more comments
3 Answers
3
active
oldest
votes
Let $vec{r}=<x_n,y_n>$, $vec{r_0}=<x_a,y_a>$
$d^2=(vec{r}-vec{r_0})^2$
$d=sqrt{r_n^2+ r_0^2-2 vec{r_n} cdot vec{r_0}}$
From here, I Think there are several options.
With some tweaking, I think you can expand with legendre polynomials.
There's also a vector version of Taylor Series applicable.:
$f(x,y)=f(x_0,y_0)+nabla f cdotvec{ds}+...$
add a comment |
You are not very explicit about the kind of function you allow, nor the desired accuracy.
Your expression (Euclidean distance between two points) is essentially the square root of
$$(x_a-x_n)^2+(y_a-y_n)^2$$
which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.
If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $sqrt2$.
The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.
Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write
$$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|sqrt{1+left(frac{y_a-y_n}{x_a-x_n}right)^2}.$$
Now you only have to approximate $sqrt{1+t^2}$ in the range $[0,1]$.
(Or $sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)
Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf
add a comment |
Starting from Yves Daoust's answer.
A good approximation of $sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be
$$sqrt{1+t^2}sim frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize
$$Phi=int_0^1 left(sqrt{t^2+1}-frac{1+a t^2}{1+b t^2}right)^2 , dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $Phi=8.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3012104%2fapproximation-of-square-root-of-sum-of-two-squared-terms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Let $vec{r}=<x_n,y_n>$, $vec{r_0}=<x_a,y_a>$
$d^2=(vec{r}-vec{r_0})^2$
$d=sqrt{r_n^2+ r_0^2-2 vec{r_n} cdot vec{r_0}}$
From here, I Think there are several options.
With some tweaking, I think you can expand with legendre polynomials.
There's also a vector version of Taylor Series applicable.:
$f(x,y)=f(x_0,y_0)+nabla f cdotvec{ds}+...$
add a comment |
Let $vec{r}=<x_n,y_n>$, $vec{r_0}=<x_a,y_a>$
$d^2=(vec{r}-vec{r_0})^2$
$d=sqrt{r_n^2+ r_0^2-2 vec{r_n} cdot vec{r_0}}$
From here, I Think there are several options.
With some tweaking, I think you can expand with legendre polynomials.
There's also a vector version of Taylor Series applicable.:
$f(x,y)=f(x_0,y_0)+nabla f cdotvec{ds}+...$
add a comment |
Let $vec{r}=<x_n,y_n>$, $vec{r_0}=<x_a,y_a>$
$d^2=(vec{r}-vec{r_0})^2$
$d=sqrt{r_n^2+ r_0^2-2 vec{r_n} cdot vec{r_0}}$
From here, I Think there are several options.
With some tweaking, I think you can expand with legendre polynomials.
There's also a vector version of Taylor Series applicable.:
$f(x,y)=f(x_0,y_0)+nabla f cdotvec{ds}+...$
Let $vec{r}=<x_n,y_n>$, $vec{r_0}=<x_a,y_a>$
$d^2=(vec{r}-vec{r_0})^2$
$d=sqrt{r_n^2+ r_0^2-2 vec{r_n} cdot vec{r_0}}$
From here, I Think there are several options.
With some tweaking, I think you can expand with legendre polynomials.
There's also a vector version of Taylor Series applicable.:
$f(x,y)=f(x_0,y_0)+nabla f cdotvec{ds}+...$
edited Nov 24 at 22:31
answered Nov 24 at 22:21
TurlocTheRed
828311
828311
add a comment |
add a comment |
You are not very explicit about the kind of function you allow, nor the desired accuracy.
Your expression (Euclidean distance between two points) is essentially the square root of
$$(x_a-x_n)^2+(y_a-y_n)^2$$
which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.
If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $sqrt2$.
The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.
Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write
$$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|sqrt{1+left(frac{y_a-y_n}{x_a-x_n}right)^2}.$$
Now you only have to approximate $sqrt{1+t^2}$ in the range $[0,1]$.
(Or $sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)
Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf
add a comment |
You are not very explicit about the kind of function you allow, nor the desired accuracy.
Your expression (Euclidean distance between two points) is essentially the square root of
$$(x_a-x_n)^2+(y_a-y_n)^2$$
which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.
If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $sqrt2$.
The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.
Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write
$$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|sqrt{1+left(frac{y_a-y_n}{x_a-x_n}right)^2}.$$
Now you only have to approximate $sqrt{1+t^2}$ in the range $[0,1]$.
(Or $sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)
Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf
add a comment |
You are not very explicit about the kind of function you allow, nor the desired accuracy.
Your expression (Euclidean distance between two points) is essentially the square root of
$$(x_a-x_n)^2+(y_a-y_n)^2$$
which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.
If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $sqrt2$.
The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.
Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write
$$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|sqrt{1+left(frac{y_a-y_n}{x_a-x_n}right)^2}.$$
Now you only have to approximate $sqrt{1+t^2}$ in the range $[0,1]$.
(Or $sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)
Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf
You are not very explicit about the kind of function you allow, nor the desired accuracy.
Your expression (Euclidean distance between two points) is essentially the square root of
$$(x_a-x_n)^2+(y_a-y_n)^2$$
which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.
If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $sqrt2$.
The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.
Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write
$$sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|sqrt{1+left(frac{y_a-y_n}{x_a-x_n}right)^2}.$$
Now you only have to approximate $sqrt{1+t^2}$ in the range $[0,1]$.
(Or $sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)
Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf
edited Nov 24 at 23:34
answered Nov 24 at 23:17
Yves Daoust
124k671220
124k671220
add a comment |
add a comment |
Starting from Yves Daoust's answer.
A good approximation of $sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be
$$sqrt{1+t^2}sim frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize
$$Phi=int_0^1 left(sqrt{t^2+1}-frac{1+a t^2}{1+b t^2}right)^2 , dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $Phi=8.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.
add a comment |
Starting from Yves Daoust's answer.
A good approximation of $sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be
$$sqrt{1+t^2}sim frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize
$$Phi=int_0^1 left(sqrt{t^2+1}-frac{1+a t^2}{1+b t^2}right)^2 , dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $Phi=8.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.
add a comment |
Starting from Yves Daoust's answer.
A good approximation of $sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be
$$sqrt{1+t^2}sim frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize
$$Phi=int_0^1 left(sqrt{t^2+1}-frac{1+a t^2}{1+b t^2}right)^2 , dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $Phi=8.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.
Starting from Yves Daoust's answer.
A good approximation of $sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be
$$sqrt{1+t^2}sim frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize
$$Phi=int_0^1 left(sqrt{t^2+1}-frac{1+a t^2}{1+b t^2}right)^2 , dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $Phi=8.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.
answered Nov 25 at 6:05
Claude Leibovici
118k1156132
118k1156132
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3012104%2fapproximation-of-square-root-of-sum-of-two-squared-terms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$x_a+y_a-x_n-y_n$ is an approximation, albeit not a good one (though it is good when $x_a-x_ngg y_a-y_n$ or $x_a-x_nll y_a-y_n$)
– Hagen von Eitzen
Nov 24 at 21:29
Would you accept the approximation $1/2?$ If not what are your requirements for the goodness of approximation?
– gammatester
Nov 24 at 21:32
@HagenvonEitzen I have modified my question a bit and add a new condition. I think under that condition, your suggested approximation might work. What do you think?
– Muhammad Usman
Nov 24 at 21:48
@gammatester My requirement is that approximated value should lie in between $in [0.9-1]$
– Muhammad Usman
Nov 24 at 21:51
Then why not use $0.95?$ Again: how accurate should the approximation be?
– gammatester
Nov 24 at 21:53