<jupyter_start><jupyter_text>--- Item XVILet $f(x) = \sum_{i=1}^n \alpha_i \text{sinc}(x-x_i)$ where $\text{sinc}(x) = \frac{\sin(x)}{x}$. Compute the total number of operations needed for evaluation of $f(x)$ at $x_j$, for $j=1 \dots n$. Also implement this algorithm and validate your estimation.---The first observation is that $\text{sinc}(x-x_i)$ should be defined as $\text{sinc}(0)=1$ when $x=x_i$. In this case, it's not necessary to compute one of the $\sin$'s nor the division.So, for evaluating the function on a particular point $x$, the amount of $\sin$ that have to be calculated is $n$, but if $x=x_j$ for some $j$, then $n{-}1$ $\sin$ have to be calculated. The same goes for the amount of divisions by $x-x_j$, substractions to get $x-x_j$, multiplications by $a_j$ and $n-1$ sums to get the final amount.| Operation | Times performed | Total ops. ||:------| -----:| ---: || compute $x-x_j$  | $n$ | $n$ || compute $\sin(x-x_j)$ | $n-1$ | $(n-1)C$ || divide $\sin(x-x_j)$ by $x-x_j$ | $n-1$ | $n-1$ || multiply by $a_i$ | $n-1$ | $n-1$ || sum over $i$ | $n-1$ | $n-1$ |This results in $4n-3+C(n-1)$ operations for each $f(x_j)$, if we compute add the operations required to compute all of them, we will end with $n(4n-3+C(n-1)) = O(n^2)$ where $C$ is the cost of computing a $\sin$.Of course, additional optimizations could be done if some relations between the $x_j$ hold.<jupyter_code>def sinc_sum(xs,alphas):
    n = len(xs)
    def loc_func(x):
        delta_xs = x-xs
        sinc = np.ones(n)
        sinc[delta_xs!=0] = np.sin(delta_xs[delta_xs!=0])/delta_xs[delta_xs!=0]
        return np.sum(alphas*sinc)
    return loc_func
N = np.logspace(1,4.4,num=30,dtype='int') # from 10 to ~25000
ts = []
for n in N:
    xsi = np.random.random(n)
    asi = np.random.random(n)
    f = sinc_sum(xsi,asi)
    start = time.time()
    f_evals = [f(x) for x in xsi]
    end = time.time()
    ts.append(end-start)
ts = np.array(ts)
plt.plot(N,ts,'o-')
plt.grid(True)
plt.show()<jupyter_output><empty_output><jupyter_text>We perform a linear regression with the last points, in logarithmic scale<jupyter_code>regr = linear_model.LinearRegression()
start = len(N)//2
logN = np.log(N.reshape((-1,1)))
logt = np.log(ts.reshape((-1,1)))
regr.fit(logN[start:],logt[start:])
# Check predictions:
res = np.exp(regr.predict(logN))
plt.loglog(N,res,label="fit")
plt.loglog(N,ts,label="real times")
plt.legend()
print("regr. coef     : %f"%regr.coef_)
print("regr. intercept: %f"%regr.intercept_)<jupyter_output>regr. coef     : 1.794841
regr. intercept: -15.550982
{'fraction_non_alphanumeric': 0.18252730109204368, 'fraction_numerical': 0.0218408736349454, 'mean_word_length': 3.923224568138196, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '202086', 'license': 'MIT', 'n_tokens_mistral': 1035, 'n_tokens_neox': 1008, 'n_words': 283, 'path': 't1_questions/item_16.ipynb', 'repo_name': 'autopawn/cc5-works', 'size': '2564'}