Finding three integers such that their sum of cosine values become max
As pointed out by Jean-François Fabre in the comments, there are plenty of tricks you could apply to improve performance, but by first of all
- noting that the values of
a
andb
determine the value ofc
, - noting that at least one of the three variables, WLOG
a
, is less than or equal toN/3
, - using the remaining symmetry in
b
andc
to boundb
betweena
and(N - a)//2 + 1
- precomputing all relevant values of cos, and trying to avoid looking up the same values in rapid succession,
- pruning the outer loop to stop early when a given value of
cos(a)
can never lead to a new maximum, - using Numba to JIT-compile the code and get some performance for free (about a factor of 400 for
N = 500
),
then the otherwise bruteforcy solution terminates relatively quickly for N = 1000000
:
import numpy as npfrom numba import jit@jitdef maximize(N): cos = np.cos(np.arange(N)) m = -3 for a in range(1, N//3 + 1): cosa = cos[a] if m - 2 > cosa: continue for b in range(a, (N - a)//2 + 1): c = N - a - b res = cosa + cos[b] + cos[c] if res > m: m = res bestabc = (a, b, c) return m, bestabcmaximize(1000000) # (2.9787165245899025, (159775, 263768, 576457))
It's worth noting that the symmetry exploited above only holds so far as one is willing to ignore the fact that numerical issues cause addition of floating-point numbers not to be commutative in general; that is cos(a) + cos(b)
need not be the same as cos(b) + cos(a)
. Chances are that you won't worry about that though.
Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos
, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).
First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:
from math import cosimport timeimport numpy as npfrom numba import jitdef calc(n): x = 1 y = 1 z = 1 total = cos(x) + cos(y) + cos(z) for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat. cosx = cos(x) for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z z = n-x-y #Infer the z, taking the rest in account temp = cosx + cos(y) + cos(z) if temp > total: total = temp return totaltic = time.clock()total = calc(10000)print(time.clock()-tic)print (total)
Will take 1.3467099999999999
(on my machine).
And as @fuglede mentioned, it is worth using numba for further optimizing.
Edit:Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos
is actually faster:
import numpy as npfrom math import cosimport timeimport timeitcos_arr = np.cos(np.arange(10000000))tic = time.time()def calc1(): total = 0 for j in range(100): for i in range(10000000): total += cos_arr[i]def calc2(): total = 0 for j in range(100): for i in range(10000000): total += cos(i)time1 = timeit.Timer(calc1).timeit(number=1)time2 = timeit.Timer(calc2).timeit(number=1)print(time1)print(time2)
With output:
127.9849290860002108.21062094399986
If i move the array creation inside the timer, its even slower.
There is absolutely no need to calculate 3 x n^3 cosine values.
We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.
Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.
To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.
And calculating cos(x) is slow, so you store the values into a table.
So:
Set c[i] = cos (i) for 1 ≤ i ≤ n. Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i]. Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].for x = elements of array x where c[x] + 2 ≥ bestTotal for y = x to (n-x)/2 z = n - x - y total = c[x] + c[]y] + c[z] if total > bestTotal (bestx, besty, bestz) = (x, y, z) bestTotal = total
You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).
So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.
If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.
for x in 1 to n/3 let s = n - x let P = s / 2pi, rounded to the nearest integer let d = (s - P * 2pi) / 2 let maxSum [x] = cos(x) + 2*cos(d)Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i]. Set (bestx, besty, bestz) = (1, 1, n-2)Set bestTotal = c[bestx] + c [besty] + c [bestz].for x = elements of array x where maxSum[x] ≥ bestTotal for y = x to (n-x)/2 z = n - x - y total = c[x] + c[]y] + c[z] if total > bestTotal (bestx, besty, bestz) = (x, y, z) bestTotal = total
PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.