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 np
from numba import jit
@jit
def 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, bestabc
maximize(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 cos
import time
import numpy as np
from numba import jit
def 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 total
tic = 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 np
from math import cos
import time
import timeit
cos_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.9849290860002
108.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.
No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
f(n) = abs(2pi*n-round(2pi*n))
as n
goes from 1 to N, where N is your upper limit of search.
Cosine is 1 at multiples of 2*pi
so we search for the two or three multiples closest to an integer within the search limit.
Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.