Fix IndexManager with many small segments
IxManager_Choose_Sparse would throw when handling more than about 40
segments because of the integer overflow test in S_fibonacci.
Also, the naive recursive implementation of S_fibonacci had abysmal
performance. After all, the result was created by adding only 0s and
1s. The number of calls to S_fibonacci when computing fib(n) was
fib(n+1), resulting in more than a billion of iterations with n ~ 45.
On my (heavily loaded and low-end) test machine, Choose_Sparse could
take up to 40 seconds to complete.
On the positive side, if anyone was hit by this performance problem,
it's likely they also saw the "index n too large" exception and we
only had two reports so far.
Use a precomputed lookup table and fix the test for large values of n.
Fixes LUCY-318.
2 files changed
