Little math problem(s) January 2019
01-26-2019, 10:19 PM
Post: #1
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
Little math problem(s) January 2019
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?

Wikis are great, Contribute :)
01-27-2019, 02:26 AM
Post: #2
 Allen Member Posts: 137 Joined: Aug 2014
RE: Little math problem(s) January 2019
Would it be allowed to calculate the answer 1 million times and take the median?

17bii | 32s | 32sii | 41c | 41cv | 41cx | 42s | 48g | 48g+ | 48gx | 50g | 30b

01-27-2019, 10:16 AM
Post: #3
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) January 2019
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.

Wikis are great, Contribute :)
01-27-2019, 03:28 PM
Post: #4
 Allen Member Posts: 137 Joined: Aug 2014
RE: Little math problem(s) January 2019
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?

17bii | 32s | 32sii | 41c | 41cv | 41cx | 42s | 48g | 48g+ | 48gx | 50g | 30b

01-27-2019, 04:26 PM (This post was last modified: 01-27-2019 04:28 PM by pier4r.)
Post: #5
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) January 2019
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.

Wikis are great, Contribute :)
01-28-2019, 01:53 AM (This post was last modified: 01-28-2019 12:46 PM by Paul Dale.)
Post: #6
 Paul Dale Senior Member Posts: 1,714 Joined: Dec 2013
RE: Little math problem(s) January 2019
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
01-28-2019, 12:12 PM
Post: #7
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) January 2019
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".

Wikis are great, Contribute :)
01-28-2019, 09:59 PM
Post: #8
 Valentin Albillo Senior Member Posts: 776 Joined: Feb 2015
RE: Little math problem(s) January 2019

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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

01-28-2019, 11:03 PM
Post: #9
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: Little math problem(s) January 2019
(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
02-04-2019, 03:15 PM
Post: #10
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) January 2019
(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.

Wikis are great, Contribute :)
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)