Created
August 29, 2020 13:32
-
-
Save victor-iyi/d8148fc570c9ab764fcbabde6c1351bd to your computer and use it in GitHub Desktop.
Implement the Python's `pow(...)` function as efficient as possible
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import time | |
| def power(base, exp): | |
| """Implement the `pow(...)` function recursively.""" | |
| # Base case. | |
| if exp == 0: | |
| return 1 | |
| elif exp == 1: | |
| return base | |
| # Compute: a^b = a^(c+d) = (a^c) * (a^d) | |
| if exp % 2 == 0: # when even, c==d | |
| half = exp / 2 | |
| return power(base, half) * power(base, half) | |
| else: | |
| c = int(exp / 2) | |
| d = c + 1 | |
| return power(base, c) * power(base, d) | |
| def pow_eff(base, exp): | |
| """Compute the `pow(...)` function more efficiently.""" | |
| number = 1 | |
| while exp: | |
| if exp & 1: | |
| number *= base | |
| exp >>= 1 | |
| base *= base | |
| return number | |
| def test(base, exp): | |
| """Test to compare Python's `pow(...)` with the above implementations.""" | |
| # Test the recursive `power(...)` function. | |
| start = time.time() | |
| re_result = power(base, exp) | |
| re_time = time.time() - start | |
| # Test the efficient `pow_eff(...)` function. | |
| start = time.time() | |
| ef_result = pow_eff(base, exp) | |
| ef_time = time.time() - start | |
| # Test the Python's `pow(...)` function. | |
| start = time.time() | |
| py_result = pow(base, exp) | |
| py_time = time.time() - start | |
| # Print the 3 results & benchmarks. | |
| print(f'Rec: pow({base}, {exp}) = {re_result:,}\tTime: {re_time:.6f}') | |
| print(f'Eff: pow({base}, {exp}) = {re_result:,}\tTime: {ef_time:.6f}') | |
| print(f'Py : pow({base}, {exp}) = {re_result:,}\tTime: {py_time:.6f}') | |
| print('==============================================\n') | |
| if __name__ == '__main__': | |
| # Test 1 | |
| test(base=-2, exp=3) | |
| # Test 2 | |
| test(base=-3, exp=2) | |
| # Test 3 | |
| test(base=3, exp=12) | |
| # Test 4 | |
| test(base=2, exp=16) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment