Htykuut

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) 

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.

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 1 and (N - a)//2 + 1
  


• precomputing all relevant values of cos, and trying to avoid looking up the same values in rapid succession,


• 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 (thus also for any given 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):

        for b in range(1, (N - a)//2 + 1):

            c = N - a - b

            res = cos[a] + cos[b] + cos[c]

            if res > m:

                m = res

                bestabc = (a, b, c)

    return m, bestabc



maximize(1000000)  # (2.9787165245899025, (159775, 263768, 576457))

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] + cy] + 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] + cy] + 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.