Spread a problem in Project
Simple solution
1 | sum ((pow (i, i) for i in range (1,1000)))% 10 ** 10 |
Problem : What will happen to replace 1000 with 10 ^ 6 or a larger number? Is the computer countable (10 ^ 6) ^ (10 ^ 6)?
Search results on google follow the way below, and they also instruct how to reduce the number of re-module permission (based on the time taken by the faster comparison of the module in some cases) will speed up
Take advantage of the 2 properties of the module operation below
1 2 | (a * b)% c = ((a% c) * (b% c))% c (1) (a + b)% c = ((a% c) + (b% c))% c (2) |
Solution
1 2 3 4 5 6 7 8 9 10 11 | modulo = 10 ** 10 result = 0 for i in range (1,10 ** 6): temp = i cho j trong phạm vi (1, i): temp * = i temp% = modulo result + = temp result% = modulo print result |
Discussion This will give results but it must be a long wait. Is there any way to solve this problem?
- Find out a math formula, give me a calculation. (I don't know, do you know, tell me)
- Find ways to improve calculation (a ^ a% modulo)
Change calculation method (a ^ a% modulo)
Add a property of exponentiation
1 | a ^ (x + y) = a ^ x * a ^ y (3) |
Applying (1) and (3) we can improve the code in the following way
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | modulo = 10 ** 10 def module_of_sum (a, b, modulo): return (a + b)% modulo def module_of_pow (a, n): "" " caculate the pow module "" " if n == 0: return 1 if n == 1: return a% modulo tmp = module_of_pow (a, n / 2) return (tmp * tmp * module_of_pow (a, n - n / 2 * 2))% modulo for i trong range (1, 10 ** 6): total_of_module = module_of_sum (total_of_module, module_of_pow (i, i), modulo) print "result is {0}". format (total_of_module% modulo) return total_of_module |
Discussion The above method was faster, with my computer about 14s.
Improved calculation (a ^ a% modulo) a bit
If you look a little bit, you'll see:
- is the module_of_pow (2.2) and module_of_pow (4,4) related? What can you do here? If you find them, congratulate you, you can apply memorize pattern. Refer to this in the article Memoization and Decorator by Vu Nhat Minh
- If you think it's unrelated, congratulations, because it helps you think about parallel computing. Refer Use coroutine in python to install the algorithm that coordinates your kiennt requests
How to apply memorize pattern:
With k being prime, and applying k = 2, k = 3, k = 5 … or applying it all is yours.
I tried range (1, 10 ^ 6), on my machine spec, the result is when applying k = {2,3,5,7}, the calculation is 40% faster
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | def module_of_pow_using_memorize (k_prime_list): "" " hãy chọn memorize mẫu để gỡ bỏ previos As you see If a == k * b: a ^ a = (k * b) ^ (k * b) = ((k * b) ^ b) ^ k = (k ^ b * b ^ b) ^ k In case this, we only consider k is prime number vì b luôn ít hơn hoặc bằng một (b <= a), so với chúng không thể xóa được b ^ b và k ^ b kết quả, và sử dụng nó để tạoulate a ^ a "" " # array để lưu b ^ b memory_b = [1] # array để lưu k ^ b memory_k = [] for i in range (0, max (k_prime_list) + 1): # init data for k ^ 0 memory_k.append (1) wrapper def (a, n): if n == 0: result = 1 if n == a: memory_b.append (result) return result if n == 1: result = (a% modulo) if n == a: memory_b.append (result) return result k = 0 # cache k ^ b for i in k_prime_list: if a% i == 0: memory_k [i] = (memory_k [i] * i)% modulo k = i if k! = 0: memory_k [k] = (memory_k [k])% modulo # caculate a ^ a b = a / k result = ((memory_b [b] * memory_k [k]) ** k)% modulo # cache a ^ a memory_b.append (result) return result tmp = wrapper (a, n / 2) result = tmp * tmp * wrapper (a, n - n / 2 * 2)% modulo if n == a: memory_b.append (result) return result return wrapper |
How to apply parallel calculations (I have not implemented in python)
A friend pointed this way and implemented in C ++ and received results 75% faster than sequential calculation without applying memorize on his 4 core machine spec) this way is no stranger to you guys. #hardcode group