FastRationals.jl gives you rational arithmetic that is much faster than the system Rationals. Please note that this is not a general purpose package. It works well only when working either
- in limited rational domains, say ±1//50_000 … ±50_000//1
or
- with large rationals (BigInt numerators and denominators)
System rationals reduce the result of every rational input and each arithmetic operation to lowest terms. FastRationals reduce values on input and prior to showing them; however the result of an arithmetic operation is reduced only if overflow occur while it is being calculated. With appropriately sized numerators and denominators, this takes less time.
Expect 10x arithmetic performance with limited rational domains.
Expect 100x with sum, prod over hundreds of large rationals.
The README has details, guidance, and links to benchmarking scripts. If you run any of the benchmarks, please consider posting your results with config info here.
Thanks to @klacru (Klaus Crusis) for his contributions.
5 Likes
Hello! This is a nice work.
However, I have thrown it my usual benchmark for Rationals (typical of the kind of computational difficulties you can encounter in representation theory), that is Hilbert matrices.
function test_hm(rtype,rank)
hm(rank)=[rtype(1)//(n+m) for n in 1:rank, m in 1:rank]
m=hm(rank)
one(m)==m*inv(m)
end
julia> @btime test_hm(BigInt,8)
2.218 ms (84722 allocations: 1.57 MiB)
true
julia> @btime test_hm(FastQBig,8)
14.908 s (89829 allocations: 4.07 GiB)
true
I was complaining because the following computation is 5 to 20 times slower than other systems which have BigInts (Python, Ruby, Sage, Gap, Magma)
julia> @btime test_hm(BigInt,45)
1.038 s (14544348 allocations: 276.10 MiB)
true
But the computation is simply impossible with FastQBig …
I hope you will consider this as an example to optimize (or tell me if it will be forever a counter-example).
Thank you for the interest. That is as expected. You are using small rationals with FastQBig. That is not one of the “privileged” domains that work well. Using large rationals with FastQBig with the operations of sum or prod works well. Using small rationals with FastQ64 works well as long as they stay relatively small (less restrictive than “staying similarly small”) as the computation proceeds.
julia> using BenchmarkTools
julia> function test_hm(rtype,rank)
hm(rank)=[rtype(1)//(n+m) for n in 1:rank, m in 1:rank]
m=hm(rank)
one(m)==m*inv(m)
end
julia> @btime test_hm(Rational{Int64},8)
174.999 μs (152 allocations: 12.08 KiB)
true
julia> julia> @btime test_hm(FastQ64,8)
41.300 μs (19 allocations: 7.91 KiB)
true
This type is not intended for use with any sort of rational in any admissible computation). The README goes into some detail and various levels of explanation or demonstration of some good applications and a few inappropriate ones.
There may be good approaches to broadening the domains and sorts of applicability while maintaining appreciable speed-up. Thoughts and contributions are welcome.
Dear Jeffrey,
I am really interested in the case where the rank is 45, not 8. In this case you need big numbers.
Do you suggest anything for that case?