# Fast recursion with big rationals

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?

Many thanks for any help!

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 `BigInt`s, 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
``````
1 Like

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