I’m currently developing a divide and conquer algorithm in Julia that requires multiple precision arithmetic at different levels of the computation:
Leaf Nodes: Operations are performed with approximately 256-bit precision.
Root Node: Requires significantly higher precision, around 10⁴ to 10⁵ bits.
However, I’ve encountered significant performance bottlenecks with the following approaches:
Using BigFloat: While BigFloat provides the necessary precision for both leaf and root nodes, it’s proving to be too slow for the computations at the leaf nodes.
Casting BigFloat to Float64x4: This method also doesn’t yield the performance improvements needed, as it’s still too slow for my application’s requirements.Since there are only few operations per number at every node.
The Flint library could be an alternative option for multiprecision computations. There are multiple wrappers available in Julia, then one I’m most familiar with (since I’m one of the developers) is Arblib.jl.
What will be the best option would likely depend on what types of operations you need to do, and how many. Is it only arithmetics (addition/multiplication) or also elementary functions (sin/cos/etc)?
By “256-bit precision”, do you mean octuple precision Float256 or a larger format with 256 bits of significand precision?
What precision are the nodes between the root and the leaves? If it’s not fixed, can you use a fixed precision?
How are you doing arithmetic after casting BigFloat to 4xFloat64, quad-double?
Is it possible to provide a MWE?
How did you determine said arithmetic is the performance bottleneck?
That said, there are many things getting you far from Float32/Float64 performance. FPUs support single or double precision, so other precisions must be emulated in software at a cost. Larger fixed precision is rarely used or supported because copying and operations require more time. If the data gets large enough to only reasonably allocate on the heap, then you’re doing something similar to and might as well use arbitrary precision, which is better supported.
It seems much better now. Is there a version without the error bound for improved performance? According to Flint’s benchmark, it appears that the Julia wrapper is 20x slower than MPZ in the ‘Exact Linear Algebra’ benchmark at 100 bits, which seems unreasonable (I was also surprised that the C++ wrapper is 2x slower). Does your wrapper experience this slowdown as well?
You can use the Arf type in Arblib.jl if you don’t need the error bounds. That type does however only support basic arithmetic. Note that for higher precision the performance cost of the error bounds is quite small, and the bounds can sometimes be helpful when determining if higher precision is needed.
The benchmarks on the Flint webpage are quite dated, so they might not reflect the current situation. But in general one reason that BigInt and BigFloat computations are relatively slow in Julia is that they typically don’t make use of mutability, leading to a large number of allocations and that tend to slow things down. So if high performance is important for you, try to make use of mutable arithmetic as much as possible (see this part of the Arblib.jl documentation.