STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Thuật Toán Big Modulo (Sơ Đồ Nhân Ai Cập)

    Giới thiệu cách tính modulo với n rất lớn.
    03/03/2016 22/09/2020 2 phút đọc
    Thuật Toán Big Modulo (Sơ Đồ Nhân Ai Cập)

    Trong các bài toán giải thuật thường gặp một vấn đề đáng quan tâm nhất đó là thời gian, vấn đề thứ 2 là tính đúng đắn của giá trị.

    Việc giải quyết bài toán tính modulo an mod d có vẻ là đơn giản nhưng để làm một bài toán an mod d với n rất lớn lại là một vấn đề cần quan tâm và được nhiều người nghiên cứu và tìm hướng giải quyết trả lời câu hỏi: "Làm sao xử lý nhanh nhất và ít tốn bộ nhớ nhất, tránh bị tràn bộ nhớ khi tính toán".

    Nội dung chính

    Ví dụ: a = 3, n = 14, d = 100 có 314 = 4782969 → 314 % 100 = 69

    Nếu xét cách giải thông thường thì:

    Bước 1

    Tính 314.

    Việc tính 314 thông thường sẽ tốn với chi phí là O(14).

    Bước 2

    Lấy kết quả bước 1 mod 100 ra kết quả.

    Trong 2 bước trên chi phí bỏ ra chỉ là O(14) không đáng kể.

    Nhưng nếu với một số n rất lớn thì vấn đề sẽ trở lên khó khăn về thời gian và giá trị đúng đắn của modulo. Câu hỏi đặt ra có cách nào để giải quyết một bài toán tính modulo một cách nhanh nhất và ít tốn kém bộ nhớ nhất tránh bị tràn dữ liệu với số n rất lớn.

    Công thức toán học sau đây:

    (A*B*C) mod N == ((A mod N) * (B mod N))* (C mod N)) mod N

    Xét lại ví dụ ban đầu:

    314 = (32)7 = 32 * (32)6 = 32 * 96 = 32 * (92)3 = 32 * 92 * (92)2 = 32 * 92 * 812  [*]

    Từ [*] 314 mod 100 = (32 mod 100) * (92 mod 100) * (812 mod 100 )) mod 100 = 69

    Ý Tưởng thuật toán

    Bước 1

    • t0 = 3
    • res0 = 1
    • r0 = t0 mod d

    Bước 2

    Lặp cho đến khi n = 0 thì chuyển sang bước 3.

    • ti+1 = ri
    • ri+1 = ti+1 mod d
    • resi+1 = (resi*ri+1) mod d

    Bước 3

    Xuất res là module cần tìm.

    Source Code 

    #include <iostream>
    #include <cmath>
     
    using namespace std;
     
    int main()
    {
    	long long a, r, res, d, n;
    res = 1; r = a % d; // Sơ đồ nhân Ai Cập while (n > 0) { if(n & 1) res = (res * r) % d; r = (r * r) %d; n >>= 1; } cout << "res: " << res; return 0; }
    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021