Finding three integers such that their sum of cosine values become max
up vote
13
down vote
favorite
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)
python optimization numbers combinations
add a comment |
up vote
13
down vote
favorite
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)
python optimization numbers combinations
1
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
What's the correct result forx
,y
andz
?
– iGian
Dec 1 at 19:13
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03
add a comment |
up vote
13
down vote
favorite
up vote
13
down vote
favorite
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)
python optimization numbers combinations
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)
python optimization numbers combinations
python optimization numbers combinations
edited Dec 1 at 11:28
asked Dec 1 at 9:36
barbossa
1128
1128
1
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
What's the correct result forx
,y
andz
?
– iGian
Dec 1 at 19:13
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03
add a comment |
1
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
What's the correct result forx
,y
andz
?
– iGian
Dec 1 at 19:13
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03
1
1
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
What's the correct result for
x
, y
and z
?– iGian
Dec 1 at 19:13
What's the correct result for
x
, y
and z
?– iGian
Dec 1 at 19:13
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03
add a comment |
5 Answers
5
active
oldest
votes
up vote
5
down vote
accepted
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.
Any answer that callscos(x)
more than once for eachx
deserves a downvote.
– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just setcosx =
cos(x)` after the firstfor
-statement, and use that instead ofcos(x)
. Try it and see.
– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython%timeit
magic, looking upcos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
– fuglede
Dec 2 at 5:53
|
show 6 more comments
up vote
12
down vote
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
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))
add a comment |
up vote
3
down vote
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.
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
add a comment |
up vote
1
down vote
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.
New contributor
add a comment |
up vote
-1
down vote
This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
Also, don't forget to check whether n in the set is an integer to reduce the sample space.
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finiten
which give you cosines of 1.
– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
add a comment |
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
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.
Any answer that callscos(x)
more than once for eachx
deserves a downvote.
– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just setcosx =
cos(x)` after the firstfor
-statement, and use that instead ofcos(x)
. Try it and see.
– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython%timeit
magic, looking upcos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
– fuglede
Dec 2 at 5:53
|
show 6 more comments
up vote
5
down vote
accepted
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.
Any answer that callscos(x)
more than once for eachx
deserves a downvote.
– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just setcosx =
cos(x)` after the firstfor
-statement, and use that instead ofcos(x)
. Try it and see.
– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython%timeit
magic, looking upcos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
– fuglede
Dec 2 at 5:53
|
show 6 more comments
up vote
5
down vote
accepted
up vote
5
down vote
accepted
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.
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.
edited Dec 2 at 6:07
answered Dec 1 at 10:19
Dinari
1,275422
1,275422
Any answer that callscos(x)
more than once for eachx
deserves a downvote.
– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just setcosx =
cos(x)` after the firstfor
-statement, and use that instead ofcos(x)
. Try it and see.
– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython%timeit
magic, looking upcos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
– fuglede
Dec 2 at 5:53
|
show 6 more comments
Any answer that callscos(x)
more than once for eachx
deserves a downvote.
– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just setcosx =
cos(x)` after the firstfor
-statement, and use that instead ofcos(x)
. Try it and see.
– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython%timeit
magic, looking upcos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
– fuglede
Dec 2 at 5:53
Any answer that calls
cos(x)
more than once for each x
deserves a downvote.– TonyK
Dec 1 at 20:43
Any answer that calls
cos(x)
more than once for each x
deserves a downvote.– TonyK
Dec 1 at 20:43
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
– Dinari
Dec 1 at 22:25
You don't need an array access. You just set
cosx =
cos(x)` after the first for
-statement, and use that instead of cos(x)
. Try it and see.– TonyK
Dec 1 at 22:59
You don't need an array access. You just set
cosx =
cos(x)` after the first for
-statement, and use that instead of cos(x)
. Try it and see.– TonyK
Dec 1 at 22:59
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
– Dinari
Dec 2 at 5:26
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython
%timeit
magic, looking up cos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.– fuglede
Dec 2 at 5:53
I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython
%timeit
magic, looking up cos[a]
in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.– fuglede
Dec 2 at 5:53
|
show 6 more comments
up vote
12
down vote
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
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))
add a comment |
up vote
12
down vote
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
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))
add a comment |
up vote
12
down vote
up vote
12
down vote
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
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))
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
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))
edited Dec 2 at 5:46
answered Dec 1 at 10:13
fuglede
6,47911239
6,47911239
add a comment |
add a comment |
up vote
3
down vote
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.
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
add a comment |
up vote
3
down vote
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.
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
add a comment |
up vote
3
down vote
up vote
3
down vote
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.
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.
edited Dec 1 at 18:46
answered Dec 1 at 15:21
gnasher729
41.2k44676
41.2k44676
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
add a comment |
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
" z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
– MSalters
Dec 1 at 23:00
add a comment |
up vote
1
down vote
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.
New contributor
add a comment |
up vote
1
down vote
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.
New contributor
add a comment |
up vote
1
down vote
up vote
1
down vote
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.
New contributor
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.
New contributor
edited Dec 6 at 12:50
Cosmic Ossifrage
2,0151115
2,0151115
New contributor
answered Dec 6 at 11:54
William Vaughn
111
111
New contributor
New contributor
add a comment |
add a comment |
up vote
-1
down vote
This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
Also, don't forget to check whether n in the set is an integer to reduce the sample space.
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finiten
which give you cosines of 1.
– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
add a comment |
up vote
-1
down vote
This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
Also, don't forget to check whether n in the set is an integer to reduce the sample space.
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finiten
which give you cosines of 1.
– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
add a comment |
up vote
-1
down vote
up vote
-1
down vote
This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
Also, don't forget to check whether n in the set is an integer to reduce the sample space.
This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
Also, don't forget to check whether n in the set is an integer to reduce the sample space.
edited Dec 1 at 10:00
answered Dec 1 at 9:46
S. Patel
1579
1579
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finiten
which give you cosines of 1.
– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
add a comment |
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finiten
which give you cosines of 1.
– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
2
2
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
Such numbers would be irrational while all @barbossa's inputs are rational.
– fuglede
Dec 1 at 9:49
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
– S. Patel
Dec 1 at 10:07
1
1
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
The inputs are assumed to be positive.
– fuglede
Dec 1 at 10:08
@S.Patel since x, y, and z are positive integers, there are no solutions for finite
n
which give you cosines of 1.– Sneftel
Dec 1 at 14:43
@S.Patel since x, y, and z are positive integers, there are no solutions for finite
n
which give you cosines of 1.– Sneftel
Dec 1 at 14:43
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
– gnasher729
Dec 1 at 18:54
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53569487%2ffinding-three-integers-such-that-their-sum-of-cosine-values-become-max%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40
dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50
I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24
What's the correct result for
x
,y
andz
?– iGian
Dec 1 at 19:13
Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03