Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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) 
like image 354
ahrooran Avatar asked Dec 01 '18 09:12

ahrooran


4 Answers

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.

like image 161
fuglede Avatar answered Oct 23 '22 03:10

fuglede


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.

like image 41
Dinari Avatar answered Oct 23 '22 04:10

Dinari


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.

like image 3
gnasher729 Avatar answered Oct 23 '22 03:10

gnasher729


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.

like image 1
William Vaughn Avatar answered Oct 23 '22 04:10

William Vaughn