Finding a better approximation for $f(L) = \left\lfloor{\frac{1}{4}\sum_{n=1}^{L-1}\left\lfloor n+300\times2^{n/7}\right\rfloor}\right\rfloor$

146 Views Asked by At

I have the following equation: $$f(L) = \left\lfloor{\frac{1}{4}\sum_{n=1}^{L-1}\left\lfloor n+300\times2^{n/7}\right\rfloor}\right\rfloor$$

And im looking for either a closed-form solution or an approximation such that the error margin is $< 1$ for $1\leq L \leq 99$

It'd be ideal if it would also be the case for bigger values of L but most values of L are going to be between 1 and 99 so a solution that would work for these values would be great either way.

Some of the approximations i know of:

$$f_1(L) = \left\lfloor \frac{L^2}{8}-\frac{14498 L}{63125}-\frac{75 \left(\sqrt[7]{2}-2^{L/7}\right)}{\sqrt[7]{2}-1}\right\rfloor$$

For values of L between 1 and 99 the largest error margin of this function(compared to the original function) is 1 (well that is the case if we treat the output as an integer which is a requirement)

$$f_2(L) = \frac{1}{8} L(L - 1) + 75 \frac{2 ^ {(L - 1) / 7} - 1}{1 - 2 ^ {-1 / 7}} + truncationerror(L)$$ $$trunactionerror(L) \approx -aL$$ Where $0< a < 1$

using $a = 0.109$ the largest error margin is also 1 (it behaves slightly better than the above method)

However my goal is to find an equation that would have an error margin of < 1 (if one exists)

I have also tried fitting the function to a polynomial(a 15-degree polynomial worked quite well for values of L in the range of 1 to 99 but still not perfectly and it wasn't easy to evaluate/compute compared to the 2 approximations above)

I have also asked a similar question in mathematica's stackexchange (linking it here as some of what im asking for has already been discussed, so it might be of help)

Edit: as i mentioned above, the output must be an integer, currently i just floor the result of the approximations and the error is either 0 or 1, perhaps there is a way to determine whether the result has to be floored/rounded/ceiled but i have no clue currently.

1

There are 1 best solutions below

0
On BEST ANSWER

By simple algebraic transformation, one finds that the approximation given in the question is the sum of an exponential term and a quadratic term, which makes sense based on the original definition. That is, $f_1(L) \approx \left\lfloor\exp(La +b) + L^{2}c + Ld + e\right\rfloor$. Initial approximate values for the coefficients fall directly out of the transformation process, for example using Wolfram Alpha.

Solving numerically for $a, b, c, d, e$ is possible, with the complication that this is a step function. With a heuristic approach similar to simulated annealing, I have been able to determine the five coefficients such that there is a perfect match between the approximation and $f(L)$. Since for $1 \le L \le99$, the value of $f(L)$ requires 24 bits, a reasonable guesstimate is that coefficients will comprise a similar but slightly larger number of bits. My best solution so far that minimizes the number of bits needed to represent the coefficients is:

$$a=\frac{106323029}{2^{30}}, \ b=\frac{220787855}{2^{25}}, \ c=\frac{263605}{2^{21}}, \ d=-\frac{142771}{2^{19}}, \ e=-\frac{814191}{2^{10}}$$