I need to write a python script that counts the number of times these operations: +, -, *, //, %, >, <, ==, <=, >= are performed in a piece of python code relative to the input of N.
Python Code:
def bar(k):
score = 0
for i in range(2, k + 1):
j = i - 1
while j > 0:
if i % j == 0:
score = score // 2
else:
score = score + 10
j = j - 1
return score
mod = 10**9 + 7
def foo(n):
m = n % 3
if n == 0:
return 1
elif m == 0:
v = foo(n // 3)
t = 0
for i in range(1, n+1):
t = t + bar(4 * i)
return v + t
elif m == 1:
v = foo(n - 1)
return v + bar(n * n * n)
else:
v = foo(n - 2)
r = 1
for a in range(2, n):
r = r * a % mod
r = r + bar(n)
return v + r
My Script:
def count_operations(n):
if n == 0:
return 1 # Base case: 1 operation for returning 1
elif n % 3 == 0:
return count_operations(n // 3) + 4
elif n % 3 == 1:
return 6 + count_operations(n - 1) + 4
else:
return 9 + 2 * count_operations(n - 2)
I wrote the script with the understanding of when N=1,calculating m=1 % 3 takes 1 operation, and the value of m is 1. Then the code executes 3 tests of the == operation before finding one to be true, when it encounters elif m == 1:. Up to that point, 4 operations have been performed.
Then it performs a recursive call with foo(n-1) which means that 5 operations have now been performed before the recursive call (the last for the -). The recursive call now has n=0, so 2 more operations occur (n%3 and n==0), before it returns with its result of 1. That makes a total of 7 basic operations that have now been performed to the point of returning from the recursive call to foo.
The code next encounters return v + bar(nnn), which means that 2 more operations (both *) occur before the call to bar followed by 1 more (+) afterwards, to bring the total 10, not counting the number done in bar. Simulating the call to bar(1), 1 more operation (k+1) is performed when the top end of the range of the for loop is calculated, bringing the total to 11. The for loop terminates immediately since the range of its iteration is empty, and the score of 0 is returned to complete the (already counted) + operation and return statement in foo. So, that means a total of 11 basic operations were performed, and we return 11 as the answer for when N=1.
So, my script only works correctly when n=1 anyone can help me fixed my script to get an understanding of how to do the proper counting when N>1?
My inefficient code what produces the correct answer:
class Integer(int):
n_ops = 0
def new_patch(name):
def patch(self, *args):
Integer.n_ops += 1
value = getattr(int, name)(self, *args)
if isinstance(value, int) and not (value is True or value is False):
value = Integer(value)
return value
patch.__name__ = name
return patch
methods = {
'__le__': '\u2264',
'__lt__': '<',
'__ge__': '\u2265',
'__gt__': '>',
'__eq__': '==',
'__add__': '+',
'__sub__': '-',
'__mul__': '*',
'__floordiv__': '//',
'__mod__': '%',
}
for name in methods:
setattr(Integer, name, new_patch(name))
def bar(k):
score = 0
for i in range(2, k + 1):
j = i - 1
while j > 0:
if i % j == 0:
score = score // 2
else:
score = score + 10
j = j - 1
return score
mod = 10**9 + 7
Integer.n_ops+=1
def foo(n):
m = n % 3
if n == 0:
return 1
elif m == 0:
v = foo(n // 3)
t = 0
for i in range(1, n+1):
t = t + bar(4 * i)
return v + t
elif m == 1:
v = foo(n - 1)
return v + bar(n * n * n)
else:
v = foo(n - 2)
r = 1
for a in range(2, n):
r = r * a % mod
r = r + bar(n)
return v + r
def countOps(n):
print(f'Number of operations when n={n}: {Integer.n_ops}')
First of all, as you want to count both % and == as operations, the first base case should be return 2 instead of return 1. Also the constant terms you add in the other return statements seem all wrong. For instance, the second return statement should count 6 instead of 4 as its constant term: there are n % 3, n == 0, m == 0, n // 3, n+1, v+t. It seems you have not counted the comparisons.
Here is an analysis to get the correct counts:
First look at bar.
The number of operations in the body of the while loop is 4: a %, ==,
either // or +, and -.
The number of executions of the while loop body is 𝑗, and the operation in the while condition is executed one more time, so that gives 5𝑗+1 operations for the while, not considering the outer loop yet.
The body of the for loop has one more operation (a -) so that body executes 5𝑗+2 operations.
The for loop makes 𝑖 vary from 2 to 𝑘 (inclusive), and thus 𝑗 varies from 1 to 𝑘−1 (inclusive), so we have this count of operations:
∑𝑗=1..𝑘−1(5𝑗+2)
= 5∑𝑗=1..k−1(𝑗) + 2(𝑘−1)
The sum term is a triangular number. We can substitute it:
5(𝑘²−𝑘)/2 + 2(𝑘−1)
= (5𝑘² − 𝑘 − 4) / 2
Add to that the operation in the range argument, and we get as final number of operations for bar(k):
(5𝑘² − 𝑘 − 2) / 2
Now look at foo.
For the case where 𝑚 is 0:
One iteration of the for loop body executes 2 operations and those from the bar call, i.e.
2 + (5(4𝑖)² − 4𝑖 − 2) / 2
= 40𝑖² − 2𝑖 + 1.
As 𝑖 iterates from 1 to 𝑛 (inclusive), we have this sum:
∑𝑖=1..𝑛(40𝑖² − 2𝑖 + 1)
= 40∑𝑖=1..𝑛(𝑖²) − 2∑𝑖=1..𝑛(𝑖) + 𝑛
The second sum is again a triangular number, while the first is a square pyramidal number, for which there also is a closed formula, and so we can write the above as:
40(2𝑛³+3𝑛²+𝑛)/6 − 2(𝑛²+𝑛)/2 + 𝑛
= 20(2𝑛³+3𝑛²+𝑛)/3 − 𝑛² − 𝑛 + 𝑛
= (40𝑛³ + 57𝑛² + 20𝑛)/3
There are 6 more operations to add to this (n % 3, n == 0, m == 0, n // 3, n+1, v+t), excluding the recursive call (which apparently you want to maintain), so we arrive at this count for when 𝑚 is 0:
(40𝑛³ + 57𝑛² + 20𝑛 + 18) / 3
For the case where 𝑚 is 1:
We have one call of bar with argument 𝑛³, so that represents (5(𝑛³)² − 𝑛³ − 2) / 2 operations.
There are 8 more operations to add to this (n % 3, n == 0, m == 0, m == 1, n - 1, n * n * n (2), v + bar()), so we arrive at
(5𝑛6 − 𝑛³ + 14) / 2
For the case where 𝑚 is 2:
One iteration of the for loop body executes 3 operations and those from the bar call, i.e.
3 + (5𝑛² − 𝑛 − 2) / 2
= (5𝑛² − 𝑛 + 4) / 2.
As 𝑎 iterates from 2 to 𝑛−1 (inclusive), we have 𝑛−2 of those iterations, where the number of operations don't depend on 𝑎, and so we get:
(𝑛 − 2)(5𝑛² − 𝑛 + 4) / 2
= (5𝑛³ − 11𝑛² + 6𝑛 − 8) / 2
There are 6 more operations to add to this (n % 3, n == 0, m == 0, m == 1, n - 2, v + r), so we arrive at
(5𝑛³ − 11𝑛² + 6𝑛 + 4) / 2
The above analysis leads to the following code for count_operations:
def count_operations(n):
if n == 0:
return 2
elif n % 3 == 0:
return count_operations(n // 3) + (40*n**3 + 57*n*n + 20*n + 18) // 3
elif n % 3 == 1:
return count_operations(n - 1) + (5*n**6 - n**3 + 14) // 2
else:
return count_operations(n - 2) + (5*n**3 - 11*n*n + 6*n + 4) // 2