Can I please ask - it is an internal limit of Julia or of MPFR lib?
I don’t know what algorithm they use, but computing the hexadecimal digits of pi is a problem amenable to be parallelised and, most importantly, it doesn’t require using arbitrary precision anywhere: Computing the hexadecimal value of pi
Computing pi ^ pi ^ pi however is a completely different problem, and unless there are other similar smart algorithms, I think you’re out of luck
13 Likes
You mentioned the link because of what - I did download the Julia language and registered on this forum)
I was impressed by the shortness and beauty of Julia’s code and decided to try.
yCruncher can do many types of Pi-formulas, but last records were set by using Chudnovsky formula.
The problem in pi^pi - it is a “non-integer power”.
Honestly, I, with my normal human brain, cannot understand or even imagine - how it is possible to be able to multiply a number to itself not-integer number of times?! Somebody can understand how it is possible?
But somehow they created algorithms for this.
With my brain I can understand how to calculate, for example, 2^20 - just multiply 2 to itself 20 times. Very easy to understand.
But how it is possible to be able to calculate 2^2.3? How it is possible to multiply 2 by itself non-integer number of times? I cannot understand it.
Moreover, in the case of pi^pi - we need to multiply pi, which is an infinitely-precise number, to itself a non-integer number of times! How it is possible guys?! But somehow - when I enter to calculator pi^pi - it gives me an answer. I cannot understand how it works! And I want to figure out and do a super high precision calculation)
From the internal comments of the MPFR C library:
mpfr_prec_t is currently limited to “long”. This means that
under MS Windows, the precisions are limited to about 2^31.
It is internal to the MPFR lib. It is possible, on some other systems, probably with some C source or other configurational customization before compilation, that the library would compile with a larger max precision – but you would find the computational time becomes a good deal longer. I have no more information on this. For more detail consult the documentation and the source code at https://www.mpfr.org/mpfr-current/.
1 Like
Sound strange. 2^31bits it is less than 1 billion hex digits!
For example here:
http://www.holoborodko.com/pavel/mpfr/
he said: “MPFR library allows user to conduct floating-point calculations with virtually any (restricted by available memory only) precision with correct rounding.”
interesting is it really ANY precision or as you told - limited to 2^31 )
I mentioned the link because the problem here isn’t simply the language to use, but more importantly the algorithm. Computing with high precision pi ^ pi ^ pi in the brute-force way you’re thinking of, with two naive exponentiations of number with a very large precision, is extremely inefficient at best, but more realistically not feasible.
Julia doesn’t magically make your code fast, you need first to implement fast algorithms, appropriate for the problem at hand
9 Likes
OK. You want the MPFR question/answer list (subscribe to ask).
https://sympa.inria.fr/sympa/arc/mpfr
3 Likes
Algorithm is of course number one to start with.
But in today’s world, we usually do not write libraries from scratch - we are using existing libs/langs.
As we can see above - Julia can offer only up to 2^31 bits precision, but, if I’m not mistaken, MPFR library can allow precision without any limits. If it is a case - the problem with Julia lies in the realization of connectivity between Julia and MPFR library.
I will continue my investigation about the existence or non-existence of internal bit precision limit in MPFR, but so far, all that I read - point to the idea of the possibility to use any precision in MPFR without a 2^31 bits limit.
If it will be true - Julia as a language cannot be used for my task because of the internal realization of precision in Julia.
At the moment I think I need to find a C-language specialist and ask him to investigate MPFR lib for my needs.
You might want to look up Nemo.jl, it uses MPFR but not only, and there might not be the same limitation for the precision: http://nemocas.github.io/Nemo.jl/latest/arb.html#Nemo.const_pi-Tuple{ArbField}
2 Likes
I believe you have your priorities in the wrong order. You first want to well understand the problem and find the best algorithm to address it. Then you can look for libraries that already implement what you think is the best algorithm for your problem.
As I already said above, I don’t think using arbitrary precision for such a problem makes sense here. You should look for something like a recursive formula, if it exists at all for your problem.
13 Likes
Oh man! I just realized IT IS YOU who wrote the article because of which I downloaded Julia)
Dear Mosè, thank you so much! Your code motivated me to try Julia )
I love how you did it. Thank you for your article!
I found a book about modern math algoritms and its computer realizations:
https://members.loria.fr/PZimmermann/mca/pub226.html
“Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, Cambridge University Press, 2010.”
Oh, it looks so hard/so complex from the outside.
Maybe it is possible to imagine the existence of a faster solution to calculate pi^pi^pi besides currently available standard methods but I even cannot fully understand the amazing complexity of today’s already existing math algorithms. Look at the book and how complex it was even in 2010.
I also found another math lib by amazing guy Fabrice Bellard
bellard.org/libbf/
btw, he is an author of even faster formula to calculate N-th binary number of Pi:
/wiki/Bellard’s_formula
I think I can try to use both libs MPFR and LibBF using their standard methods of calculation.
I cannot imagine how can I try to invent a new algorithm to calc pi^pi^pi besides standard step by step classic calculations.
I can imagine doing 3 steps:
- calculate pi with high precision → save result 1
- calculate pi[1] with high precision → save result 2
- calculate pi[2] with high precision → final result after 3 steps
to do this I only need to use One function, only One - “non-integer power”
Because I do not need a function to calculate pi - I can use yCruncher or download already calculated Pi up to Trillions of digits.
Because of that, I think that I need only one function: pow(float, float)
I’m not sure is it even possible to calculate pi^pi^pi directly without doing it step by step with limited precision in each step.
That’s a question for a math specialist.
Maybe you right that I need to join math forums first and to ask mathematicians about possible algorithms able to solve my task.
P.S. I think Julia developers should consider removing the 2^31 precision limit in Julia. This is sad that this beautiful language has this ugly limit built-in.
I’m sure MPFR lib has no such limit internally.
2 Likes
I’d start with power series expansions of the log/exp reformulations mentioned earlier.
2 Likes
The restriction is in MPFR: the library uses a C long to represent the precision of a value and a long can only represent values up to 2^31-1 on 32-bit systems and 2^63-1 on 64-bit systems. To be clear computing billions of floating-point digits is not the intended use case for MPFR; indeed, there is almost no practical application for that kind of precision.
12 Likes
Theoretically, that isn’t guaranteed by the compiler, right? You could always build your own C compiler to get more bits out of it.
1 Like
It would be much easier to patch the source of MPFR to use a larger integer type instead of long. That may not be the only limitation, however, but it is a hard limitation imposed by MPFR (and not by Julia).
7 Likes
I have 64-bit CPU.
For me, 2^63-1 - is good enough bit precision for my goal.
I want to calculate up to 100,000,000,000 digits. this is “only” 100 billion.
2^63-1 = 9223372036854775807 bits - more than enough for me.
But when I tried Julia - it showed me an error.
Why Julia is internally limited to 32-bit style (2^31-1) precision I do not know.
I have x64, why Julia cannot use x64 long for precision I do not know. This is a problem of Julia lang. I cannot use Julia for my task.
IIRC long Is 32 bits on 64 bit Windows.
5 Likes
This is a fun thread since it brings up a couple interesting points that I particularly like. One, if you push any problem, no matter how straightforward-seeming, to a sufficient scale, it becomes a research problem. Probably nobody has ever before computed that many digits of pi^pi^pi. Second, there is no general way to efficiently compute any numerical result you might want. (By “efficient” I mean something like taking less than 100 years. If something “only” takes a couple minutes or days, see point one above.) Wolfram Research has probably done more than anyone to push the generality of numerical results you can get (“all functions to all precisions”), but as soon as the scale gets big enough (either problem size, or the required level of performance), cleverness will always be needed. That’s why Mosè said the algorithm comes first.
When I try Jeffrey’s code above:
(etc.)
I get these times:
100000 bits: 0.072 seconds
1000000 bits: 0.98 seconds
10000000 bits: 19.3 seconds
So even if MPFR can ultimately do it, it will take a heck of a lot of time and RAM. Requesting much larger precision on 64-bit linux works fine for me, but I run out of RAM very quickly. I would recommend doing a back-of-the-envelope estimate of the needed resources.
23 Likes
Another thing to note is that in these kinds of problems the actual result is generally the least interesting aspect; it will just be a long sequence of digits that nobody can do anything useful with. It’s very much a case of the journey is everything, proving that you can compute something that nobody did before. And the core to making the journey worthwhile is finding new algorithms, not only computing something nobody did before but something nobody was even able to compute before.
To make this more concrete I was involved in the efforts to compute the exact number of legal positions on a 19×19 go board. This is a mere 171 digit number but quite intricate to compute. Brute force enumeration falls flat at about a 5×5 board. A relatively straightforward application of dynamic programming goes up to maybe 12×12 or so. Beyond that required various clever algorithmic improvements and eventually supercomputing power to crack 19×19. Even more interesting, at least from my point of view, were the spin-off analytical results about the number of legal positions on an N×N board.
You can read all about this exciting journey in https://tromp.github.io/go/gostate.pdf if you want details. But the final result 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
is just that, a sequence of digits.
28 Likes
Amazing work cited in Wikipedia page for the Go game. Quoting from the referenced publication: “The L(19,19) computation took over 250_000 CPU hours and 30 PB of disk IO, generously provided by the Intelx86 Linux clusters at the IAS School of Natural Sciences in Princeton, the IDA Center for Communications Research, also in Princeton, and on a HP Helion Cloud server”…
OMG.
3 Likes