Tản mạn một bài toán trong ProjectEuler
code
39
algorithm
33
math
10
White

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:

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

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

khoinv

6 bài viết.
28 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
1 2
có thể bạn biết thừa] Ctags là gì + Cách cài đặt Ctags thì các bạn có thể xem ở bài (Link) của bạn @hienvd. Minh xin được tóm tắt lại: vim và 1 s...
khoinv viết hơn 1 năm trước
1 2
White
1 0
Link tổng hợp các Awesome Repository https://github.com/sindresorhus/awesome content khoinv 21112016
khoinv viết hơn 1 năm trước
1 0
White
1 1
Cách gán kiểu cho dữ liệu Json Kiến thức: JSON.stringify(obj) sẽ tự động gọi obj.toJSON JSON.parse(obj) có thêm thêm vào hàm obj.parse Dưới là i...
khoinv viết hơn 1 năm trước
1 1
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 7 tháng trước
44 7
White
53 23
Luận về comment code (Phong cách kiếm hiệp) Comment code luôn là vấn đề gây tranh cãi sứt đầu mẻ trán trong giới võ lâm. Xưa kia, thuở còn mài đít...
Huy Hoàng Phạm viết gần 3 năm trước
53 23
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
6 bài viết.
28 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!