On Sat, 4 Jan 2020 at 09:37, Dean Rasheed <dean.a.rash...@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
