Tản mạn một bài toán trong ProjectEuler

code

39

algorithm

33

math

11

khoinv viết ngày 09/11/2016

Hôm nay vô tình đọc được bài của anh @huytd về Bàn về phương pháp tối ưu tính tổng các số Fibonacci
Theo chuỗi cảm hứng mình cũng xin chia sẻ về bài toán projectEuler48

Cách giải đơn giản

sum((pow(i,i) for i in range(1,1000))) % 10**10

Problem: Điều gì sẽ sảy ra là thay 1000 bằng 10^6 hoặc một số lớn hơn nữa? máy tính có tính được luôn (10^6)^(10^6)?

kết quả tìm kiếm trên google theo cách làm bên dưới, và họ cũng hướng dẫn cách giảm số phép module lại( dựa vào thời gian thực hiện phép so sánh nhanh hơn phép module trong một số case) sẽ làm tăng tốc độ

Lợi dụng 2 tính chất của phép toán module dưới đây

(a*b) % c = ((a % c) * (b % c) )% c (1)
(a+b) % c = ((a % c) + (b % c) )% c (2)

Solution

    modulo = 10**10
    result = 0
    for i in range(1,10**6):
        temp = i
        for j in range(1,i):
            temp *= i
            temp %= modulo

        result += temp
        result %= modulo
    print result

Discussion Cách này sẽ cho kết quả nhưng chắc là phải đợi lâu. Có cách nào để giải quyết bài toán này?

• Tìm ra 1 công thức toán học, tính 1 phát ra luôn( Mình không biết, có bạn nào biết bảo mình với nhé)
• Tìm cách cải thiện việc tính (a^a % modulo)

Thay đổi cách tính (a^a % modulo)

Thêm một tính chất của phép lũy thừa

a^(x+y) = a^x * a^y (3)

Áp dụng (1) và (3) ta có thể cải tiến code theo cách dưới đây

modulo = 10**10

def module_of_sum(a, b, modulo):
    return (a + b) % modulo

def module_of_pow(a, n):
    """
    caculate module pow
    """
    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 in 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 Cách trên đã nhanh hơn, với máy tính của mình tầm 14s.

Cải tiến việc tính (a^a % modulo) một chút

Nếu để ý một chút bạn sẽ thấy:

• module_of_pow(2,2) và module_of_pow(4,4) có liên quan gì không nhỉ? bạn có thể làm gì được ở đây? Nếu bạn tìm ra chúng thì chúc mừng bạn, bạn có thể áp dụng memorize pattern. Tham khảo về cách này trong bài viết Memoization and Decoratorcủa anh @VuNhatMinh
• Nếu bạn cho rằng nó không liên quan tới nhau, thì cũng xin chúc mừng bạn, vì nó giúp bạn nghĩ đến việc tính toán song song. Tham khảo Sử dụng coroutine trong python để cài đặt thuật toán điều phối các request của anh @kiennt

Cách áp dụng memorize pattern:

Với k là số nguyên tố, và việc áp dụng k =2, k= 3, k= 5... hoặc áp dụng tất cả là do bạn.
Mình đã thử với range(1, 10^6), trên spec máy của mình thì kết quả là khi áp dụng k = {2,3,5,7} thì việc tính toán nhanh hơn được 40%
Solution

def module_of_pow_using_memorize(k_prime_list):
    """
    apply memorize pattern to cache previos result
    As you see
    If a == k*b:
        a^a = (k*b)^(k*b)
            = ((k*b)^b)^k
            = (k^b * b^b)^k
    In this case, we only consider k is prime number
    because b always less than or equal to a(b <= a),
    so if we cache caculted of b^b and k^b result,
    and using it to caculate a^a
    """
    # array to store b^b
    memory_b = [1]
    # array to store k^b
    memory_k = []

    for i in range(0, max(k_prime_list) + 1):

        # init data for k^0
        memory_k.append(1)

    def wrapper(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

Cách áp dụng tính toán song song( mình chưa implement bằng python)

Một người bạn đã chỉ mình cách này và implement bằng C++ và nhận được kết quả nhanh hơn 75% so với cách tính tuần tự không áp dụng memorize trên spec máy 4 core của anh ấy) chắc cách này không lạ gì với các anh trong nhóm #hardcode