Hi!
Now I’m doing one task for OEIS.
In particular, I need to implement a fast algorithm for finding egyptian fractions of shortest length.
There is the next algorithm for to find just the shortest length:
If there is an expansion with k terms, one of the denominators is at most kq/p. So to check whether there is an expansion with at most k terms: for each m from ⌈q/p⌉ to ⌊kq/p⌋, check recursively whether p/q−1/m has an expansion with at most k−1 terms.
I chose Julia for calculations because it is a really fast and powerful language.
Here is the code, it works quite successfully:
using FastRationals
function check(f, k)
if numerator(f) == 1
return true
end
if k == 1
return false
end
for i = ceil(1/f):floor(k/f)
if check(f - Rational{BigInt}(1, Integer(i)), k - 1)
return true
end
end
return false
end
f is a tested fraction (with Rational{BigInt} type), and k is tested length.
There are two things that can improve performance:
The code uses recursion. Its depth is small, but the breadth is very large.
Is it possible to optimize it somehow, maybe with iterators?
I use FastRationals package and it really increased performance
But do I use Julia type conversion correctly?
I played around with your code a bit and it seems quite fast could not find any trivial optimization. Some remarks about your question:
(1) most definitely you can optimise the first part by not having recurstion. This would cur some of the time as you are allocating Rational{} at every iteration. You need to make sure to allocate it once and then just update it. I am unsure on how to archieve that and it does not seem necessary.
(2) what do you mean by that? One thing that I noticed is that if f is a rational of type Int and not BigInt then you would converty a lot, which mifht be sub-optimal.
Just a note: you’re working with BigInts, which are implemented (in all languages?) using the GMP library written in C. My point is that the main factor for performance here is GMP, not Julia, although Julia can certainly make writing such programs much more enjoyable than C.
Without taking a look at the algorithm, I guess your code could be made to allocate much less using the MutableArithmetics package.
I played a bit with your code, here’s a simple way to do less allocation:
function check(val::Val{:slow}, f::Rational{BigInt}, k::Int)
isone(numerator(f)) && return true
isone(k) && return false
for i ∈ ceil(inv(f)):floor(k / f)
check(val, f - Rational{BigInt}(true, Integer(i)), k - 1) && return true
end
false
end
function check(val::Val{:fast}, f::Rational{BigInt}, k::Int)
isone(numerator(f)) && return true
isone(k) && return false
for i ∈ ceil(BigInt, inv(f)):floor(BigInt, k / f)
check(val, f - (true // i), k - 1) && return true
end
false
end
check(v::Val, q::Rational, k::Int) = check(v, big(q), k)
I think the :slow version should be equivalent to your code above, while the :fast version is slightly improved.
There’s half as much allocation and it seems to be faster:
julia> @timev check(Val(:slow), 45677//87653456, 2)
0.004351 seconds (85.32 k allocations: 2.232 MiB)
elapsed time (ns): 4350695
gc time (ns): 0
bytes allocated: 2340792
pool allocs: 46065
non-pool GC allocs: 0
malloc() calls: 28794
realloc() calls: 10461
free() calls: 0
minor collections: 0
full collections: 0
false
julia> @timev check(Val(:fast), 45677//87653456, 2)
0.002902 seconds (45.01 k allocations: 1.178 MiB)
elapsed time (ns): 2902093
gc time (ns): 0
bytes allocated: 1235272
pool allocs: 24952
non-pool GC allocs: 0
malloc() calls: 17276
realloc() calls: 2785
free() calls: 0
minor collections: 0
full collections: 0
false
Firstly thanks for bright example of perfomance tracking with Julia!
And yes, it’s hardly possible to radically increase speed.
So your fast version is very appreciated.
What about MutableArithmetics, its an interesting package.
But seems it will not help to increase perfomance in this case