The Holy Grail Of Mathematics.

modest · 11-07-2008

Quote:

Originally Posted by Don Blazys

Hopefully, CraigD will be able to verify your calculation.

Yes, CraigD is much better at this kind of thing than I.

I started over at 250 digit accuracy and got this:

6.22071562877864521059396967031
3416058685026190653406984465260
6975787315898018449813080427575
5047236089986553666526211212228
2582152764102504185301445876882
1758023982143107611879667495337
3863345212891628638680669171900
823407981

Greater accuracy than that (I tried 500 digits) was getting into very significant calculation times.

~modest

Don Blazys · 11-07-2008

To: Modest,

Very promising indeed!

Don.

Don Blazys · 11-07-2008

To: Qfwfq,

Thanks for your most exellent idea/suggestion to use Newtons method on the derivative!

Don.

Don Blazys · 11-08-2008

To: Modest, CraigD, Qfwfq, and anyone else who might be working on determining the root:

sin(x^(1/2))-ln(ln(x))= 0.

Determining the root in the above subtraction is the same as determining the "intersection" of:

sin(x^(1/2))

and

ln(ln(x)).

Would that make a difference in how the computer performs the calculation, and if it does, then can the "intersection" result be used to verify the "Newtons method" result?

Don.

Qfwfq · 11-08-2008

Quote:

Originally Posted by modest

I'm also concerned and very confused that this converged after only 7 iterations. I wasn't expecting that at all.

I used:

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\,\!$

I was also thinking it might be a tad more than 7 iterations but of course it all depends on how much it differs from linear in the interval; once the second derivative has a consistently low value each iteratation improves precision muchly.

Anyway that's the right expression for the increment, the best way to be sure is to have each residue printed as well, this way you could hardly go too wrong, but as far as precision goes when reaching the numeric type's resolution one need to watch out for computational caveats.

Quote:

Originally Posted by modest

Greater accuracy than that (I tried 500 digits) was getting into very significant calculation times.

If the natural log is computationally lightweight a trick migh improve times, although not in quasilinear cases. This place is closing...

Quote:

Originally Posted by Don Blazys

Would that make a difference in how the computer performs the calculation, and if it does, then can the "intersection" result be used to verify the "Newtons method" result?

Er, no. The graphic interpretation is irrelevant to the method.

modest · 11-08-2008

@500 digits (took hours), x =

6.22071562877864521059396967031
3416058685026190653406984465260
6975787315898018449813080427575
5047236089986553666526211212228
2582152764102504185301445876882
1758023982143107611879667495337
3863345212891628638680669171900
8234079808915612501562283150922
3008738517287542763446572627235
8463586832147018101705513403268
8276829275105127873450791589259
6625179577008443871192357568135
7106032592021060326157333916052
5743623563530918921431489655185
9866630347739868615224858990142
0556594477955367710536794228194
67301

f(x) =

0.00000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
000005

Quote:

Originally Posted by Qfwfq

once the second derivative has a consistently low value each iteratation improves precision muchly.

Indeed. I was incorrectly remembering the Newton method from college thinking the rate of convergence was linear. According to wiki, it's at least quadratic.

By the way, my hat's off to PERL.

~modest

Don Blazys · 11-08-2008

To: Modest,

Hi5!, Yoodaman!

Very impressive. I too have been busy, simplifying my formula, and preparing several different versions. That way, you will be able to choose the one that you feel is the most "computer friendly". I should be posting it around Tuesday or Wednesday. (Thursday at the latest).

Don.

modest · 11-09-2008

Quote:

Originally Posted by Don Blazys

been busy, simplifying my formula... I should be posting it around Tuesday or Wednesday. (Thursday at the latest).

Excellent. I'm rooting for your formula

~modest

CraigD · 11-09-2008

Quote:

Originally Posted by CraigD

All of my favorite hand-made calculators are exact precision integer and rational number based, but I could cobble together trig and logarithm approximating functions to some defined precision pretty quickly, and solve

$\sin x^{\frac12}-\ln\ln x = 0$

Using a simple binary search. An answer to a couple of thousand decimal digits precision shouldn’t be too hard.

I was overoptimistic about the precision I could get in a reasonable amount of computing time using exact arithmetic.

Though I’ve had some interesting, educational, and time-devouring experiences trying to optimize the approximating formulas

$\ln x = \sum_{n=0}^{\infty} \frac2{2n-1} \left( \frac{x-1}{x+1} \right)^{2n-1}$

(a key to using this iteratively is to exploit that $\ln x_n = \ln \frac{x_n}{x_{n-1}} +\ln x_{n-1}$ , allowing the input value to be increasingly close to 1, where the approximation converges most quickly).

and

$\sin x = \sum_{n=1}^{\infty} \frac{(-1)^{n-1} x^{2n-1}}{(2n-1)!}$

(which presents more of a challenge, as I don’t yet know an optimization such as the above for it)

To avoid the $x^{\frac12}$ term, which doesn’t in general have an exact rational value, I’ve been using the substitution $Y= x^{\frac12}$ to solve

$\sin Y -\ln\ln Y -\ln 2 = 0$

The main speed trouble I’m seeing is due to the size of the rational number returned by an iteration of the approximation is larger than that of the rational number of its accuracy (the difference between the returned value and the previous iteration’s, AKA the delta). For example, 128 iterations of approximating $\sin \frac{74}{100}$ results in a value with a 927 decimal digit denominator, while the delta is about $10^{539}$ .) Also, with exact rational arithmetic, the computational effort of a calculation depends not only on the number or iterations (in a worse-than-linear way), but on the size of the input rational number (it’s numerator and denominator).

In summary, many thousands of digits of precision for an approximation of an expression involving sines and logarithms using exact rational arithmetic looks a lot harder than I’d guessed a few days ago. My hat is also off to the built-in high-precision calculators for these functions in packages like Perl’s and Ruby’s. And, or course, my hat is always off to that old genius Newton – for those who can be bothered to take a derivative, Newton's method is a much better (about 47 times better, from Modest’s results) approximating method than my usual choice of a binary search.

I’ll keep experimenting with exact arithmetic approaches to transcendental functions especially the trig ones), but must for the time being concede defeat at calculating them to arbitrary precision.

The “holy grail” of any transcendental number approximating method is, IMHO, a spigot algorithm for it, which allows calculating digits or precision – or in fact digits anywhere in the fractional expansion of a number – with a close-to-linear amount of effort. Recent astonishingly high precision estimates of numbers such as $\pi$ come mostly from spigot algorithms.

All of this approximation method discussion is, however, just preliminary to the prime generating algorithm we’re all eagerly awaiting.

In the meanwhile, here’s a plug for a prime-generating algorithm of my own, PRMP - an algorithm for generating the primes using only “+1” and “=”, and my own personal mathematical holy grail, The Starburst Challenge.