Multiprecision Floating-point to Continued Fraction Cruncher
Zuuv is a program that can compute the regular continued fraction of a number from it's floating-point representation (a file containing hex or dec digits). Its features include:
- Advanced algorithms for log-linear runtime
- Ability to utilize hard-disk to perform extremely large calculations
- Ability to automatically save and resume partially computations
- Multi-threading
Zuuv has been utilized to break world records for computation of regular continued fraction terms of important mathematical constants such as Pi, Euler-Mascheroni etc, even on regular PCs. Here are the current record computations done using Zuuv:
| Constant | Terms | Date | Time | System Details | Link | Comments |
|---|---|---|---|---|---|---|
| Pi | 30,113,021,586 | Apr 2021 | ~6 days | Intel Core i5 9300H, 8GB DDR4 @ 2666MHz | All of the terms | The computation added a new term to the OEIS sequence A033089 |
| Euler's constant | 16,695,279,010 | Apr 2021 | ~2 days | Intel Core i5 9300H, 8GB DDR4 @ 2666MHz | All of the terms | See comments on A033091 |
Windows builds, along with the required DLLs can be found in the builds directory.
modernsubdirectory contains builds for newer processorslegacysubdirectory contains builds for older processors
IMPORTANT: Starting Release 2.0, LINUX IS NO LONGER SUPPORTED For older versions of Zuuv, Linux build might require mpir-3.0.0 library to be installed.
- Download and install mpir library:
wget https://mpir.org/mpir-3.0.0.zip - Navigate to
mpir-3.0.0folder and run./configure --enable-cxx. Install all the requirements withsudo apt install <program>in the case that./configurefails due to some missing program. - Run
make install
The program requires a minimum of four threads to run efficiently. I haven't personally tested it on a dual-core setup, but I would expect performance issues. After downloading, to check if everything is alright, do a quick continuant benchmark (option 4) to see if everything is running fine.
Zuuv takes in a file containing the stream of digits of a number and calculates its regular continued fraction terms in multiple iterations, each stored in the subdirectory iterations. A file pi_1m_hex.txt, containing one million hexadecimal digits of pi, is provided in the source/constants subdirectory to experiment with Zuuv before launching a serious computation.
It is recommended to estimate the resources and the time a computation would need before starting a computation. The option "Estimate RAM usage and computation times" in Zuuv would provide you with a very rough but practical estimate.
As a rule of thumb, you can compute 1.167 x <number of hex digits> terms or 0.97 x <number of dec digits> terms of simple continued fraction. For example, a file containing five billion hex digits of pi can be used to compute 5 billion x 1.167 = 5.835 billion terms of simple continued fraction of pi.
There are two computation modes.
| Computation Mode | RAM requirements | Disk requirements | Resumable | Speed | Comments |
|---|---|---|---|---|---|
| RAM based | High | Output only | No | Fastest | Use for small computations that can fit in RAM |
| Disk based | Adjustable (low) | High | Yes | Fast | Use for large computations that can't entirely be done in RAM |
Disk based computations are the way to go for large computations. Disk-based computations can be used to control RAM requirements through adjusting bytes per file. Also, disk based computations are resumable and fault tolerant: if the program is terminated for any reason, the computation can begin again from the same iteration given that the values in folders disk_mpz and iterations are preserved.
There are four default benchmarks provided:
Zuuv attempts to calculate the terms of the regular continued fraction of a random fraction. This benchmark isn't very scalable beyond 4-cores (the procedure is essentially sequential in nature, and hence difficult to parallelize beyond 4-cores. However, I am open to ideas.).
Zuuv attempts to calculate the continued of a list of random numbers (generated according to the Gauss-Kuzmin distribution to simulate continued fraction terms). The benchmark timing should benefit with increase in processor cores, as the procedure is well-parallelized.
Zuuv attempts to benchmark a critical multiplication routine required in disk-based computations. This procedure again is well parallelized and should benefit well from scaling.
Zuuv compares the speed of MPIR-based multiplication with YMP-based multiplication.
This repository contains all the dependencies needed for a compilation under Microsoft Visual Studio.
- Clone this repository
- Open the project file "zuuv.vcxproj"
- Run the compilation
Zuuv is written in C++17 and depends on the mpir-3.0.0 library.
You will need to download and extract the mpir-3.0.0 library, and enable C++17 standard.
- Clone this repository.
- Goto File -> New -> Project from Existing Code. Choose the
sourcefolder
- Download and extract the mpir-3.0.0 library.
- In Project -> Properties -> C/C++ -> General -> Additional Include Directories, add the path to
mpirsub-directory insidempir-3.0.0folder - In Project -> Properties -> Linker -> Input -> Additional Dependencies, add path to
mpir.lib
- Goto Project -> Properties -> C/C++ -> Language -> C++ Language Standard, and choose "ISO C++17 Standard"
- Install the mpir-3.0.0 library following the instructions given under "Installation" -> "Linux"
- Navigate to
sourcefolder and use the following command-line
g++ *.cpp -I /usr/lib/local/include -L /usr/lib/local/lib -lmpir -pthread -std=c++17 -Ofast -DNDEBUG -o zuuv
In case of problems, feel free to write to me.
Here is an incomplete list of contribution ideas:
- Break some world records with Zuuv. Calculate regular continued fraction expansions of some important mathematical constant. This is actually easy to do with Zuuv even on a regular PC, given that you're dedicated enough. Given the attention computation of decimal digits of constants gets, it is a shame that continued fraction exapansions haven't catched up, especially considering that continued fraction expansions are more mathematically interesting.
- Redesign the UI of Zuuv. Set defaults everywhere so that the user doesn't have to think too much.
- Better parallelization. Crunching continued fraction expansions is inherently sequential in nature. As such, parallelization might require algorithmic changes. Zuuv still doesn't use often use more than 50% of the available CPU multithreading power on average. However, maybe certain routines can be parallized via a GPU (e.g. basecase calculations of continuants of a list of numbers).
If you're interested in contributing to Zuuv or are considering breaking a world record, do let me know, and I will try to help you.