Tính ƯCLN của hai số lớn

Mình tính toán ra trên giấy: Nếu cho một số có 9*10^8 chữ số.

– Nếu dùng hệ cơ số 10 (sử dụng xâu để lưu số) thì sẽ mất 900MB để lưu một số.

– Nếu dùng hệ cơ số 10^9 (sử dụng mảng kiểu Integer) thì sẽ mất 900 / 9 * 4 = 400MB. (RẤT ĐÁNG LƯU TÂM)

– Nếu dùng bits để tính toán thì mình thấy chỉ hạn chế được khoảng 25MB, tức là lưu một số vẫn phải mất 375MB (Mình tính con số này trong Matlab bằng cách giải phương trình: 2^n = 10^(9*10^8) với n là số bits cần biểu diễn). Nên mình nghĩ nếu cài đặt thì nên sử dụng hệ 10^9 là tốt nhất. Vì nếu dùng bits thì mình chỉ được lợi thời gian trong phép toán div 2… nhưng sau đó một số phép khác lại cần phải cài đặt thêm, thậm chí là hơi phức tạp. Ví dụ như: chuyển số từ hệ 2 về hệ 10 (dùng giản đồ Hoorne), rồi chuyển số từ hệ 10 về hệ 2.

Chương trình cài đặt theo 3 phương pháp: Chia liên tiếp, Trừ liên tiếp, và phối hợp Trừ liên tiếp kết hợp với thuật toán gần giống như bình phương và nhân.

Các bạn hãy giải thích làm sao phương pháp Chia liên tiếp lại tốt nhất? Tại sao phương pháp Trừ liên tiếp lại không tốt? Sửa đổi thế nào để phương pháp Trừ liên tiếp kết hợp với thuật toán gần giống như bình phương và nhân tốt như phương pháp Chia liên tiếp?

Sau đây là chương trình trên hệ cơ số 10, số biểu diễn có tối đa 255 chữ số. Sử dụng dữ liệu kiểu xâu để biểu diễn số lớn. Chương trình viết trên ngôn ngữ Free Pascal.

{$MODE OBJFPC}
// Chuong trinh nay phai chay tren Free Pascal
uses crt;
const fi = 'UCLN.INP';
      fo = 'UCLN.OUT';

Type bigNum = string; // bigNum co toi da 255 ki tu

var a, b, k: bigNum;
    dem: integer;
    f: text;

// Cac ham danh cho tinh UCLN va UCLN2
// ********************************************************

function cmp(a,b : bigNum): integer;
// So sanh hai so nguyen
begin
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        if a = b then exit(0);
        if a > b then exit(1);
        exit(-1);
end;

function add(a,b : bigNum): bigNum; // Phep cong
var sum, carry, i, x, y : integer;
    c : bigNum;
begin
        carry:=0;c:='';
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                x:= ord(a[i])-ord('0'); {ord('0')=48}
                y:= ord(b[i])-ord('0');
                sum:=x + y + carry;
                carry:=sum div 10;
                c:=chr(sum mod 10 +48)+c;
        end;
        if carry>0 then c:='1'+c;
        add:=c;
end;

function sub(a,b:bigNum):bigNum; // Phep tru
var c :bigNum;
    s,borrow,i :integer;
begin
        borrow:=0;c:='';
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])-ord(b[i])-borrow;
                if s<0 then
                begin
                        s:=s+10;
                        borrow:=1;
                end
                   else borrow:=0;
                c:=chr(s +48)+c;
        end;
        while (length(c)>1)and(c[1]='0') do delete(c,1,1);
        sub:=c;
end;

function bigMod2(a,b:bigNum):bigNum; // Phep mod
var hold :bigNum;
    kb :array[0..10]of bigNum;
    i,k :longint;
begin
        kb[0]:='0';
        for i:=1 to 10 do
        kb[i]:=add(kb[i-1],b);
        hold:='';
        for i:=1 to length(a) do
        begin
                hold:=hold+a[i];
                k:=1;
                while cmp(hold,kb[k])<>-1 do
                inc(k);
                hold:=sub(hold,kb[k-1]);
        end;
        bigMod2:=hold;
end;
// ********************************************************

// Cac ham danh cho tinh UCLN3
// ********************************************************
function bigDiv1(a:bigNum;b:longint):bigNum;
var s,i,hold:longint;
    c:bigNum;
begin
        hold:=0;s:=0; c:='';
        for i:=1 to length(a) do
        begin
                hold:=hold*10 + ord(a[i])-48;
                s:=hold div b;
                hold:=hold mod b;
                c:=c+chr(s+48);
        end;
        while (length(c)>1) and(c[1]='0') do delete(c,1,1);
        bigDiv1:=c;
end;

function bigMod1(a:bigNum;b:longint):longint;
var i,hold:longint;
begin
        hold:=0;
        for i:=1 to length(a) do
        hold:=(ord(a[i])-48+hold*10) mod b;
        bigMod1:=hold;
end;

function multiply1(a:bigNum;b:longint):bigNum;
var i :integer;
    carry,s :longint;
    c,tmp :bigNum;
begin
        c:='';
        carry:=0;
        for i:=length(a) downto 1 do
        begin
                s:=(ord(a[i])-48) * b + carry;
                carry:= s div 10;
                c:=chr(s mod 10 + 48)+c;
        end;
        if carry>0 then str(carry,tmp) else tmp:='';
        multiply1:=tmp+c;
end;
// ********************************************************

function UCLN(a, b: bigNum): bigNum;
begin
        inc(dem);
        if (cmp(b, '0') = 0) then exit(a) // Truong hop neo (Truong hop co so)
            else exit(UCLN(b, bigMod2(a, b)));
end;

function UCLN2(a, b: bigNum): bigNum;
begin
        inc(dem);
        if (cmp(a, '0') = 0) then exit(b) // Truong hop neo (Truong hop co so)
            else if (cmp(a, b) < 0) then exit(UCLN2(sub(b, a), a))
                 else exit(UCLN2(b, sub(a, b)));
end;

function UCLN3(a, b: bigNum): bigNum;
var k: integer;
begin
        inc(dem);
        // Truong hop neo (Truong hop co so)
        if (a = '1') then exit('1');
        if (b = '1') then exit('1');
        if (a = '0') then exit(b);
        if (b = '0') then exit(a);
        if (bigMod1(a, 2) = 0) then
        begin
                if (bigMod1(b, 2) = 0) then exit(multiply1(UCLN3(bigDiv1(a, 2), bigDiv1(b, 2)), 2))
                   else exit(UCLN3(bigDiv1(a, 2), b))

        end
           else begin
                        if (bigMod1(b, 2) = 0) then exit(UCLN3(a, bigDiv1(b, 2)))
                           else
                           begin
                                k:= cmp(a, b);
                                if (k = 0) then exit(a) // Truong hop neo
                                   else if (k > 0) then exit(UCLN3(b, sub(a, b)))
                                           else exit(UCLN3(sub(b, a), a));
                           end;
                end;

end;

BEGIN
        clrscr;
        assign(f, fi); reset(f);
        readln(f, a);
        readln(f, b);
        close(f);

        assign(f, fo); rewrite(f);
        writeln(f, 'UCLN(');
        writeln(f, a);
        writeln(f, ',');
        writeln(f, b);
        writeln(f, ')');
        writeln(f, '= ');
        try
                dem:= 0;
                k:= UCLN2(a, b);
                writeln('UCLN(', a, ', ', b, ') = ', k);
        except // Neu co loi
                writeln('LOI! So lan goi de quy vuot qua dung luong cua vung nho Stack');
                k:= '-1';
        end;

        writeln(f, k);
        close(f);

        writeln('So lan goi de quy: ', dem);
        writeln('Size of bigNum type: ', sizeof(bigNum)); // chi co 255 ki tu
        writeln('Size of Integer type in {$MODE OBJFPC}: ', sizeof(integer));
        writeln('View the result in the file UCLN.OUT');
        readln;

END.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: