Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def reverse(a):
- '''Complexity - O(a).'''
- if a == 0:
- return 0
- result = 0
- change = -1 if a > 0 else +1
- while a != 0:
- result += change
- a += change
- return result
- assert(reverse(-10) == 10)
- assert(reverse(-1) == 1)
- assert(reverse(-0) == 0)
- assert(reverse(0) == 0)
- assert(reverse(1) == -1)
- assert(reverse(10) == -10)
- def abs(a):
- '''Complexity - O(a) in case a is negative.'''
- if a >= 0:
- return a
- return reverse(a)
- assert(abs(-10) == 10)
- assert(abs(-1) == 1)
- assert(abs(-0) == 0)
- assert(abs(0) == 0)
- assert(abs(1) == 1)
- assert(abs(10) == 10)
- def add(a, b):
- '''The only realized operation.'''
- return a + b
- assert(add(-10, 10) == 0)
- assert(add(-10, -10) == -20)
- assert(add(-10, 0) == -10)
- assert(add(0, -10) == -10)
- assert(add(0, 0) == 0)
- assert(add(0, 10) == 10)
- assert(add(10, 0) == 10)
- assert(add(10, 10) == 20)
- assert(add(10, -10) == 0)
- def subtract(a, b):
- '''Complexity - O(b).'''
- return a + reverse(b)
- assert(subtract(-10, 10) == -20)
- assert(subtract(-10, -10) == 0)
- assert(subtract(-10, 0) == -10)
- assert(subtract(0, -10) == 10)
- assert(subtract(0, 0) == 0)
- assert(subtract(0, 10) == -10)
- assert(subtract(10, 0) == 10)
- assert(subtract(10, 10) == 0)
- assert(subtract(10, -10) == 20)
- def multiply(a, b):
- '''Complexity - 2*(a + b):
- abs(a) -> a
- abs(b) -> b
- reverse(mx) -> max(|a|,|b|)
- range(mnabs) -> min(|a|,|b|)
- '''
- if not a or not b:
- return 0
- # Searhing absolute minimum to take less loop steps below
- mn, mx, result = a, b, 0
- mnabs, mxabs = abs(a), abs(b)
- if mnabs > mxabs:
- mn, mx = mx, mn
- mnabs, mxabs = mxabs, mnabs
- if mn < 0:
- mx = reverse(mx)
- # Main calculation loop
- for i in range(mnabs):
- result += mx
- return result
- assert(multiply(-10, 10) == -100)
- assert(multiply(-10, -10) == 100)
- assert(multiply(-10, 0) == 0)
- assert(multiply(0, -10) == 0)
- assert(multiply(0, 0) == 0)
- assert(multiply(0, 10) == 0)
- assert(multiply(10, 0) == 0)
- assert(multiply(10, 10) == 100)
- assert(multiply(10, -10) == -100)
- def divide(a, b):
- '''Division is checked by multiplication.
- We calculate the sign of result and operate with absolute values of a and b.
- Then we count how many times b is in a.
- Complexity - O(a + b + a//b):
- abs(a) -> a
- abs(b) -> b
- main loop -> a//b
- '''
- if b == 0:
- return 0
- raise Exception
- absa, absb = abs(a), abs(b)
- if absa < absb:
- return 0
- if a == b:
- return 1
- if absa == absb:
- return -1
- # Sign of result
- change = +1 if a > 0 and b > 0 or a < 0 and b < 0 else -1
- # Main calculation loop
- accumulator, result = 0, 0
- while accumulator < absa:
- accumulator += absb
- result += change
- # If a mod b == 0, so we return result.
- if accumulator == absa:
- return result
- # Otherwise we have made one unnecessary step and need to decrease result by 1.
- return subtract(result, change)
- assert(divide(-1, 0) == 0)
- assert(divide(0, 0) == 0)
- assert(divide(1, 0) == 0)
- assert(divide(0, 1) == 0)
- assert(divide(0, -1) == 0)
- assert(divide(-2, -2) == 1)
- assert(divide(-1, -1) == 1)
- assert(divide(1, 1) == 1)
- assert(divide(2, 2) == 1)
- assert(divide(-2, 2) == -1)
- assert(divide(-1, 1) == -1)
- assert(divide(1, -1) == -1)
- assert(divide(2, -2) == -1)
- assert(divide(-1, -2) == 0)
- assert(divide(-1, 2) == 0)
- assert(divide(1, -2) == 0)
- assert(divide(1, 2) == 0)
- assert(divide(-2, -1) == 2)
- assert(divide(-2, 1) == -2)
- assert(divide(2, -1) == -2)
- assert(divide(2, 1) == 2)
- assert(divide(-5, -2) == 2)
- assert(divide(-5, 2) == -2)
- assert(divide(5, -2) == -2)
- assert(divide(5, 2) == 2)
- assert(divide(-5, -3) == 1)
- assert(divide(-5, 3) == -1)
- assert(divide(5, -3) == -1)
- assert(divide(5, 3) == 1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement