STDIO
Tìm kiếm gần đây
    • 0

    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; }
    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.

    Sản phẩm

    Đề xuất

    Sự Thật Về Web Design Và Graphic Design

    Sự Thật Về Web Design Và Graphic Design

    Web Design thường được hiểu nghĩa tiếng Việt đó là thiết kế web, Graphic ...

    STDIO SolutionsThiết kế

    07/06/2017

    SHA-1 - Secure Hash Algorithm 1

    SHA-1 - Secure Hash Algorithm 1

    SHA-1 là một trong những thuật toán băm mã hóa, được dùng trong việc ...

    Cyber SecurityCơ bản

    04/05/2019

    Khám phá thêm

    Thông Số Kỹ Thuật Arduino Uno R3 - Các Biến Thể và Lưu Ý

    Thông Số Kỹ Thuật Arduino Uno R3 - Các Biến Thể và Lưu Ý

    Arduino board có rất nhiều phiên bản với hiệu năng và mục đích sử dụng ...

    Điện Tử Ứng DụngArduino

    13/10/2014

    Đồ Hoạ trên Cửa Sổ Dòng Lệnh - Console Graphics

    Đồ Hoạ trên Cửa Sổ Dòng Lệnh - Console Graphics

    Các thư viện đồ họa đã phát triển rất mạnh mẽ, tận dụng gần như tối đa ...

    Vũ Quang Huy

    02/10/2014

    Heap Sort - Thuật Toán Sắp Xếp Vun Đống

    Heap Sort - Thuật Toán Sắp Xếp Vun Đống

    Với độ phức tạp trong trường hợp xấu nhất bằng O (n log n), giải thuật ...

    Giải Thuật Lập TrìnhGiải thuật sắp xếp

    04/09/2017

    Kỹ Thuật Grayscale và Nhị Phân Hoá Ảnh (Adaptive Threshold)

    Kỹ Thuật Grayscale và Nhị Phân Hoá Ảnh (Adaptive Threshold)

    Giới thiệu và chi tiết các thuật toán Grayscale, ảnh nhị phân và một số ...

    Computer VisionOpenCV

    23/01/2015

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    Giới thiệu những thuật toán cơ sở trong xử lý hình thái học, những thuật ...

    Computer VisionOpenCV

    23/01/2015

    Cơ Bản về Mã Hóa

    Cơ Bản về Mã Hóa

    Mạng máy tính là một môi trường mở, những thông tin gửi lên hoặc nhận về ...

    Cyber SecurityBảo mật

    03/12/2014

    Xử Lý Ảnh Với OpenCV: Lọc Số Trong Ảnh

    Xử Lý Ảnh Với OpenCV: Lọc Số Trong Ảnh

    Giới thiệu lọc số ảnh, khái niệm và công thức nhân chập ma trận, một số ...

    Computer VisionOpenCV

    23/01/2015

    CBP-8: Component Điều Khiển và AI – Component Ra Lệnh

    CBP-8: Component Điều Khiển và AI – Component Ra Lệnh

    Component ra lệnh - các Component có khả năng gửi Entity Command cho ...

    Lập Trình GameKiến Thức Nâng Cao

    21/08/2015

    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 - 2020