Little math problem(s) January 2019

[pier4r]

You got a superpower (well, you or you have a computer with a good math library).

If you know the formula or model to be computed, you can compute it approximating the numerical answer with a maximum of 20% relative error.

It seems at the end that you are not very precise (for some value of "precise"), but can you somehow use this superpower and get even more accurate answers?

[Allen]

Would it be allowed to calculate the answer 1 million times and take the median?

[pier4r]

Interesting idea yours!

Two cases.
- In the case of the answer is not always the same, it takes just a long time (spelling out the answer takes time, times one million times)
- Second, case, more challenging. You return the same answer given the same input.

[Allen]

In the case where the model was both slow and not precise, I would discard the model and do something else.

In the second case, where the errors are completely deterministic (but not precise), would it be safe to assume the underlying function is differentiable, and rather than look for variations in the output, one could change the input over successive trials, and use the information learned from that to refine the numeric estimate?

I can't imagine a real world modeling case where either of these two cases would come up. I could be misunderstanding the question?

[pier4r]

Quote:I can't imagine a real world modeling case where either of these two cases would come up. I could be misunderstanding the question?

It is an hypothetical. Especially in math it shouldn't be something new.
It is not a real world application.

About "the model could be slow", it is because if you are the guy with the superpower, spelling out (or writing down) the answer literally takes time, although you have it in your mind immediately. Therefore doing it one million times is exhausting a bit.

(01-27-2019 03:28 PM)Allen Wrote:  In the second case, where the errors are completely deterministic (but not precise), would it be safe to assume the underlying function is differentiable, and rather than look for variations in the output, one could change the input over successive trials, and use the information learned from that to refine the numeric estimate?

We couldn't always ensure it is differentiable, but the idea is on the right track. You can get more precision varying the input over iterations.

[Paul Dale]

As the function approaches zero, the relative error will become controllable.

Given the function F(x), make an estimate ϕ. Due to the relative error, ϕ lies between 0.8 F(x) and 1.2 F(x). i.e. |F(x) - ϕ| ⩽ 0.2 F(x). Now, take the function G(x) = F(x) - ϕ. Make an estimate of this function ζ. Again, |G(x) - ζ| ⩽ 0.2 G(x). This means |F(x) - (ϕ - ζ)| ⩽ 0.04 F(x). Repeat.

Pauli

[pier4r]

Yes indeed.

When I saw it the first time (as someone commented on the problem "If I can approximate with an error of 20%, I will know the answer as precise as I want") I was like "wha?" and then "oh, well done".

[Valentin Albillo]

      
Hi:

(01-27-2019 02:26 AM)Allen Wrote:  Would it be allowed to calculate the answer 1 million times and take the median?

This ^

It works perfectly and requires no clever thought or sophistication whatsoever, simply perform N independent calculations (each with a maximum relative error of 20%), then simply output the mean: probabilistically, the error will be reduced by a factor of Sqr(N) and so will tend to zero as N tends to infinity

As proof-of-concept, simply run this short HP-71B BASIC code snippet: (Sin(1) can be replaced by any other value or formula)

      1    DESTROY ALL @ RANDOMIZE 1 @ T=SIN(1) @ FOR K=1 TO 6 @ N=10^K
      2    S=0 @ FOR I=1 TO N @ S=S+T*(.8+.4*RND) @ NEXT I
      3    DISP USING "8D,3(2X,Z.6D)";N;S/N;T;ABS(S/N-T) @ NEXT K

      > RUN

           N      Mean       Exact     Abs(error)
      ----------------------------------------------
          10    0.867936    0.841471    0.026465
         100    0.832384    0.841471    0.009087
        1000    0.838462    0.841471    0.003009
       10000    0.840485    0.841471    0.000986
      100000    0.841524    0.841471    0.000053
     1000000    0.841477    0.841471    0.000006

As can be seen, the error diminishes steadily as N goes from 10 to one million evaluations by a factor of approximately Sqr(10) = 3.16+ as N increases tenfold, and you eventually get about 5 correct digits, a relative error reduction from the initial 0.2 (20%) for a single evaluation to 0.0000006 (0.0006%) for the average of one million evaluations.

Regards.
V.
 

[Thomas Klemm]

(01-28-2019 01:53 AM)Paul Dale Wrote:  As the function approaches zero, the relative error will become controllable.

Here's an HP-42S program that uses this idea to calculate \(sin(1)\approx8.41470984808e-1\):

Code:

00 { 20-Byte Prgm }
01 1
02 SIN
03 RCL- ST Y
04 RAN
05 0.4
06 ×
07 0.8
08 +
09 ×
10 +
11 END

Make sure to use RAD mode.

Example:

0
R/S
8.13930075171e-1
R/S
8.37292640515e-1
R/S
8.41890339484e-1
R/S
8.41404810797e-1
R/S
8.41460042846e-1
R/S
8.41472832565e-1
R/S
8.41470715347e-1
R/S
8.41470956453e-1
R/S
8.41470980231e-1
R/S
8.41470985454e-1
R/S
8.41470984835e-1
R/S
8.41470984811e-1
R/S
8.41470984808e-1
R/S
8.41470984808e-1
…

Cheers
Thomas

[pier4r]

(01-27-2019 02:26 AM)Allen Wrote:  Would it be allowed to calculate the answer 1 million times and take the median?

Actually I didn't see that one could expand the initial numerical problem to consider the median of it. Therefore obtaining the answer relatively quickly according to the superpower.

Still I am not sure whether the second approach that Paul is getting a precise enough answer with less effort. I didn't dive in it.