On Sat, 4 Jan 2020 at 09:37, Dean Rasheed <dean.a.rasheed@gmail.com> wrote:
>
> Well Vik has now provided a numeric implementation and it doesn't
> appear to be too much code.
>
BTW, I did a bit of research into the efficiency of Euclid's
algorithm. It's actually quite interesting:
It turns out that the worst case is when the inputs are successive
values from the Fibonacci sequence. In that case, since
Fib(n)/Fib(n-1) = 1 remainder Fib(n-2), the algorithm will walk
backwards through the whole sequence before terminating, and the
result will always be 1.
For bigint inputs, the worst case is gcd(7540113804746346429,
4660046610375530309) which requires something like 90 divisions.
Testing that, it's still sub-millisecond though, so I don't think
there's any problem there.
OTOH, for numeric inputs, this could easily end up needing many
thousands of divisions and it's not hard to construct inputs that take
minutes to compute, although this is admittedly with ridiculously
large inputs (~10^130000), and AFAICS, the performance is OK with
"normal" sized inputs. Should we put a limit on the size of the
inputs? I'm not sure exactly how that would work, but I think it would
have to take into account the relative weights of the inputs rather
than just the maximum weight. At the very least, I think we need a
check for interrupts here (c.f. the numeric factorial function).
Perhaps such a check is sufficient. It's not like there aren't lots of
other ways to tie up the server.
There are apparently more efficient algorithms, but I think that
should definitely be kept out of scope for this patch.
Regards,
Dean
