Finding three integers such that their sum of cosine values become max

Question

There are three integers x, y and z (each of them >= 1) and a given upper bound integer n < 10^6. Also, n = x + y + z and output = cos(x) + cos(y) + cos(z).

The exercise is to maximize output.

I wrote a simple script for this, but the time complexity is O(n^3). Is there any way to simplify this?

from math import cos

n = 50
x = 1
y = 1
z = 1

total = cos(x) + cos(y) + cos(z)

for x in xrange(n):
    for y in xrange(n):
        for z in xrange(n):
            if x + y + z == n:
                temp = cos(x) + cos(y) + cos(z)
                if temp > total: total = temp

print round(total, 9) 

Answer 1

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 and b determine the value of c,
• noting that at least one of the three variables, WLOG a, is less than or equal to N/3,
• using the remaining symmetry in b and c to bound b between a 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.