Prev: STATIC UNIVERSE: EINSTEINIANA'S NEW MONEY-SPINNER
Next: Try to solve a quartic equation
From: Golabi Doon on 31 Jul 2010 02:59
Hello,

Consider the problem:

sum_k arctan(x_k) < a

where k=1,...n and x_k are real variables and "a" is a given constant.
You choose a specific choice of values for x_1,...x_n and give it to
me. I should give you one of these two answers: "your choice satsfies
the inequality" or "I don't know". Of course, I would like to avoid
the answer "I don't know" as much as I can.

However, I am limited to check your solution only with elementary
tools that can handlelow-degree polynomials possibly with "a few"
applications of elementary functions (note that the original function
uses n applications of arctan, and n can be large, so it is not
desired). For example, I would be happy if had a condition of form
sum_k x_k^2 < sqrt(a) or something like sum_k arctan(x_k^3) < a^2.

In a formal sense, I am asking for the largest subset of the solution
space (thus a sufficient condition for the original inequality) that
can be expressed in a nice form.

Your help would be highly appreciated

Golabi
From: Golabi Doon on 31 Jul 2010 03:07
On Jul 31, 1:59 am, Golabi Doon <golabid...(a)gmail.com> wrote:
> desired). For example, I would be happy if had a condition of form
> sum_k x_k^2 < sqrt(a) or something like sum_k arctan(x_k^3) < a^2.

In the second example, I meant to write arctan(sum_k x_k^3) < a^2 , so
that there is one application of arctan.

Golabi
From: Ilmari Karonen on 31 Jul 2010 11:14
On 2010-07-31, Golabi Doon <golabidoon(a)gmail.com> wrote:
>
> Consider the problem:
>
> sum_k arctan(x_k) < a
>
> where k=1,...n and x_k are real variables and "a" is a given constant.
> You choose a specific choice of values for x_1,...x_n and give it to
> me. I should give you one of these two answers: "your choice satsfies
> the inequality" or "I don't know". Of course, I would like to avoid
> the answer "I don't know" as much as I can.
>
> However, I am limited to check your solution only with elementary
> tools that can handlelow-degree polynomials possibly with "a few"
> applications of elementary functions (note that the original function
> uses n applications of arctan, and n can be large, so it is not
> desired).

What you seem to want is an "easily computable" lower bound for
arctan(x). For that, have you considered a simple piecewise linear
approximation?

Also, you could do some shortcut checks to avoid needless computation
in some cases. For example, if n < 2 a / pi, then any x_1, ..., x_n
will satisfy the inequality, while if n < -2 a / pi none of them will.
Whether this is something worth checking for depends on what values a
and n are likely to take.

Also, if you expect most sums to be dominated by a few large terms,
you may be able to save effort by sorting the inputs by absolute value
and summing them in that order, while keeping track of the range in
which the final sum might lie if all the remaining terms were equal
(and either all positive or all negative). Note that if f(x) <=
arctan(x), then -f(-x) >= arctan(x), so you can get the upper bound
using the same function you use for the lower bound.

Knowing what kind of distribution of inputs you expect might help in
coming up with more optimizations. In particular, you didn't
explicitly mention whether any of x_1, ..., x_n can ever be negative.
I assumed above that they could, but if they can't, that simplifies
things a lot.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
From: achille on 31 Jul 2010 13:43
On Jul 31, 11:14 pm, Ilmari Karonen <usen...(a)vyznev.invalid> wrote:
> On 2010-07-31, Golabi Doon <golabid...(a)gmail.com> wrote:
>
>
>
>
>
> > Consider the problem:
>
> > sum_k arctan(x_k) < a
>
> > where k=1,...n and x_k are real variables and "a" is a given constant..
> > You choose a specific choice of values for x_1,...x_n and give it to
> > me. I should give you one of these two answers: "your choice satsfies
> > the inequality" or "I don't know". Of course, I would like to avoid
> > the answer "I don't know" as much as I can.
>
> > However, I am limited to check your solution only with elementary
> > tools that can handlelow-degree polynomials possibly with "a few"
> > applications of elementary functions (note that the original function
> > uses n applications of arctan, and n can be large, so it is not
> > desired).
>
> What you seem to want is an "easily computable" lower bound for
> arctan(x).  For that, have you considered a simple piecewise linear
> approximation?
>
> Also, you could do some shortcut checks to avoid needless computation
> in some cases.  For example, if n < 2 a / pi, then any x_1, ..., x_n
> will satisfy the inequality, while if n < -2 a / pi none of them will.
> Whether this is something worth checking for depends on what values a
> and n are likely to take.
>
> Also, if you expect most sums to be dominated by a few large terms,
> you may be able to save effort by sorting the inputs by absolute value
> and summing them in that order, while keeping track of the range in
> which the final sum might lie if all the remaining terms were equal
> (and either all positive or all negative).  Note that if f(x) <=
> arctan(x), then -f(-x) >= arctan(x), so you can get the upper bound
> using the same function you use for the lower bound.
>
> Knowing what kind of distribution of inputs you expect might help in
> coming up with more optimizations.  In particular, you didn't
> explicitly mention whether any of x_1, ..., x_n can ever be negative.
> I assumed above that they could, but if they can't, that simplifies
> things a lot.
>
> --
> Ilmari Karonen
> To reply by e-mail, please replace ".invalid" with ".net" in address.

How about approximate atan(x) by a piecewise rational function:

f(x) = pi/2 - x/(k+x^2) when x > 1
x/(1+k*x^2) when -1 <= x <= 1
-pi/2 -x/(k+x^2) when x < -1

where k = 4/pi - 1. It is easy to check for all x,

| atan(x) - f(x) | < 0.007
and | atan(x)/f(x) - 1 | < 0.011

This implies:
1) for any x_1,..x_n,
\sum f(x_i) < a - 0.007 n => \sum atan(x_i) < a
2) for any x_1,..,x_n, all > 0,
\sum f(x_i) < a/1.011 => \sum atan(x_i) < a.
From: Ilmari Karonen on 1 Aug 2010 14:52
On 2010-07-31, achille <achille_hui(a)yahoo.com.hk> wrote:
> On Jul 31, 11:14 pm, Ilmari Karonen <usen...(a)vyznev.invalid> wrote:
>> On 2010-07-31, Golabi Doon <golabid...(a)gmail.com> wrote:
>>
>> > Consider the problem:
>> >
>> > sum_k arctan(x_k) < a
>> >
>> > where k=1,...n and x_k are real variables and "a" is a given constant.
>> > You choose a specific choice of values for x_1,...x_n and give it to
>> > me. I should give you one of these two answers: "your choice satsfies
>> > the inequality" or "I don't know". Of course, I would like to avoid
>> > the answer "I don't know" as much as I can.
>>
>> > However, I am limited to check your solution only with elementary
>> > tools that can handlelow-degree polynomials possibly with "a few"
>> > applications of elementary functions (note that the original function
>> > uses n applications of arctan, and n can be large, so it is not
>> > desired).
>>
>> What you seem to want is an "easily computable" lower bound for
>> arctan(x). For that, have you considered a simple piecewise linear
>> approximation?
>
> How about approximate atan(x) by a piecewise rational function:
>
> f(x) = pi/2 - x/(k+x^2) when x > 1
> x/(1+k*x^2) when -1 <= x <= 1
> -pi/2 -x/(k+x^2) when x < -1
>
> where k = 4/pi - 1. It is easy to check for all x,
>
> | atan(x) - f(x) | < 0.007
> and | atan(x)/f(x) - 1 | < 0.011

That's a very nice approximation. However, the OP seems to be
specifically looking for an upper bound (and not a lower bound as I
wrote above by mistake), whereas your f(x) is less then arctan(x)
whenever -1 < x < 0 or x > 1.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
 |  Next  |  Last
Pages: 1 2
Prev: STATIC UNIVERSE: EINSTEINIANA'S NEW MONEY-SPINNER
Next: Try to solve a quartic equation