VẤN ĐỀ TÍNH TOÁN VỚI CÁC SỐ LỚN
Vấn đề tính toán với các số lớn có ý nghĩa rất lớn trong thực tế. Chẳng
hạn, thuật toán mã hoá công khai RSA (do Rivers, Shamir và Adleman viết
ra vào năm 1978) sử dụng tới 512 số khoá (thuật toán này có liên quan đến
việc phân tích các số nguyên tố). Trong nhiều ngành khoa học kỹ thuật khác,
chúng ta còn phải sử dụng tới các con số lớn hơn thế rất nhiều. Trong bài báo
này, chúng tôi muốn trình bày với đọc giả đôi nét xung quanh vấn đề tính
toán với số lớn qua các phép toán phổ biến như: cộng, trừ, nhân, chia, khai
căn, luỹ thừa và kiểm tra tính nguyên tố.
Trước hết chúng ta cùng bàn về một số môi trường lập trình để thể hiện
chương trình tính toán với số lớn:
- Với ngôn ngữ lập trình Pascal: Nếu sử dụng cấu trúc dữ liệu
(CTDL) kiểu chuỗi thì chỉ có thể thao tác với các số trong phạm vi 255 chữ
số; nếu sử dụng CTDL kiểu mảng thì có thể thao tác với các số lớn vượt xa
giới hạn 255 chữ số gấp nhiều lần, có thể đạt tới hàng ngàn chữ số (lưu ý khi
làm việc với CTDL mảng là kích thước của mảng cho phép khai báo một số
rất lớn nhưng vẫn bị hạn chế vì bộ nhớ dành cho mảng là 64K); cách làm khác
là sử dụng con trỏ để khai thác vùng nhớ Heap của máy tính, bằng cách sử
dụng CTDL kiểu mảng động để thao tác với các số lớn tới hàng tỉ con số (vì
kích thước mảng động phụ thuộc vào dung lượng Ram thực tế của máy tính).
- Với ngôn ngữ lập trình Delphi hay Java ta có thể thao tác với các số
lớn tới hàng tỉ con số thông qua CTDL kiểu chuỗi hay CTDL kiểu mảng.
Ngoài ra, cũng có thể sử dụng các ngôn ngữ thông dụng khác như C/C+
+ để viết chương trình. Chúng ta tạm thời thoả thuận với nhau rằng: tuỳ thuộc
yêu cầu mà lựa chọn môi trường lập trình cũng như CTDL phù hợp. Vấn đề
quan trọng là thuật toán thể hiện, phần tiếp theo sẽ trình bày các thuật toán có
liên quan.
1.Thuật toán cộng hai số:
Để cộng hai số nguyên a và b ta thực hiện như phép cộng bằng tay hai
số thông thường. Tức là thực hiện lần lượt phép tính từ bên trái, sử dụng một
biến trung gian để lưu phần dư tại mỗi bước.

i
:=tg;
end;
for i:= n-m to 1 do{chuyển đoạn đầu còn lại (nếu có) của a vào c}
begin
c
i
:= (a
i
+du ) mod 10;
du:=(a+du) div 10;
end;
if (du>0) then c
0
:= du;
3.Thuật toán nhân hai số:
Thuật toán này có thể dễ dàng suy ra từ thuật toán cộng hai số, xin dành
cho bạn đọc tự tìm hiểu.
4.Thuật toán chia hai số:
- Cắt lần lượt từng “đoạn“ của số bị chia tính từ bên trái (có cộng thêm
phần dư của các bước trung gian).
- Đem chia các đoạn đó cho số chia bằng phép toán trừ.
- Thương tìm được chính là dãy các số là kết quả của phép chia các
“đoạn” cho số chia (được phát triển dần về phía bên phải).
- Phần dư của phép chia chính là “đoạn” còn lại không thể chia được
nữa.
5.Thuật toán khai căn bậc hai của một số nguyên X (kết quả là một số
nguyên):
b:=1;
l:=<số chữ số của X>;

Y[1]=1;Y[2]=30;
a=1;s1=0;
{đoạn thủ tục lặp}
s2=3;
b=3 div(2*a)=1;i=3;
s2=30; s1=21;
a=a*10+b=11;
s1=9;
Ta được kết quả a=11.
3
130
A
Để chương trình thực hiện hiệu quả hơn, ta có thể cải thiện thuật toán đi
đôi chút (chi tiết về phần cài đặt bạn đọc có thể tham khảo trong chương trình.
Nếu muốn tìm hiểu về chương trình chi tiết, bạn có thể liên hệ với toà soạn).
6.Thuật toán nâng lên luỹ thừa:
Giả sử cần tính b = a
k
. Thông thường ta sử dụng thuật toán sau:
b:= 1;
for i:=1 to k do b:= b*a;
Như vậy cần phải lặp k bước để tìm kết quả, đây là chi phí quá lớn
(đặc biệt khi k lớn tới con số hàng ngàn đơn vị). Ta cải tiến với ý tưởng sau:
b:=1;
while (k > 0) do
if (k mod 2 = 1) then
begin
b:= b*a;
k:=k- 1;
end

k
(k > 2)được tính dựa vào d
k-1
:
+Nếu k lẻ: d
k
=d
k-1
+2
+Nếu k chẵn: d
k
=d
k-1
+4
(Ví dụ:d
0
=2, d
1
=3, d
2
=5, d
3
=7, d
4
=11, d
5
=13, d
6
=19… ).
4

ok:=false
End
else
Begin i:=i+1;j:=j+1;end;
end;
ss:=ok
end;
Procedure tru(d,k:integer);
5
var tg,phu:byte;j,i:integer;
begin
phu:=0;j:=lb;
for i:=k downto d do
begin
if a[i]-b[j]- phu<0 then
begin
a[i]:=a[i]+10-b[j]-phu;
phu:=1;
end
else
begin
a[i]:=a[i]-b[j]-phu;
phu:=0;
end;
j:=j-1;
end;
end;
Procedure xu_ly;
var t:byte;k,i:integer;
begin

begin
val(s[i],x,code);
la:=la+1;a[la]:=x;
end;
until s='';
repeat
readln(f,s);
for i:=1 to length(s) do
begin
val(s[i],x,code);
lb:=lb+1;b[lb]:=x;
end;
until s='';
close(f);b[0]:=0;
end;
Procedure test;
var f:text;i:integer;
begin
init; xu_ly;
assign(f,'chia.out');
rewrite(f);
if lc=0 then writeln(f,0)
else
begin
for i:=1 to lc do
begin
write(f,c[i]);
if i mod 60=0 then writeln(f);
end;
if i mod 60<>0 then writeln(f);

có thể liên hệ trực tiếp với toà soạn, chương trình được viết bằng ngôn ngữ
Java theo cách tiếp cận hướng đối tượng có thể thao tác với các số nguyên
và số thực.

import java.io.*;
//lop so thuc lon voi cac phep toan
//thong thuong:cong , tru, nhan, chia, khai can va kiem
//tra tinh nguyen to
class BigNum {
private int dau;//duong la 0,am la 1
8
private String val;
private int num;//so chu so sa dau phay
//con structors
public BigNum( BigNum b){ this(b.dau,b.val,b.num);}
public BigNum() { val=new String("0");dau=1;num=-1;}
public BigNum(int d,String s,int p) {dau=d;val=s;num=p;}
public BigNum(String s) {
char c=s.charAt(0);
if (c=='+'){s=s.substring(1);dau=1;}
else if(c=='-'){ s=s.substring(1);dau=0;}
else dau=1;
int i=s.indexOf('.');
if(i==-1)i=0;
else i=s.length()-i-1;
if(i!=0)
s=s.substring(0,s.length()-i-1)+s.substring(s.length()-i);
val=s;num=i;
}
//phep toan cong hai so lon

while( (i<x.length() ) & ok & kt )
if (x.charAt(i)> y.charAt(i) ) ok= false;
9
else if (x.charAt(i)< y.charAt(i) ) kt=false;
else i++;
if(i==x.length())ok=false;
return ok;
}
//thuc hien phep tru hai SO NGUYEN x,y
private String sub1(String x,String y){
int i,odd=0,temp;
int lx=x.length();
int ly=y.length();
String s=new String();
if(lx>ly)
for (i=0;i<lx-ly;i++)y=0+y;
else for (i=0;i<ly-lx;i++)x=0+x;
for (i=x.length()-1;i>=0;i ){
temp= x.charAt(i)- y.charAt(i)-odd ;
if (temp<0){odd=1; s=(temp+10) +s;}
else { odd=0;s=temp+s;}
}
// cat bo phan bang 0 o dau
i=0;
while ( (i<s.length()-1) && (s.charAt(i)=='0') ) i++;
return s.substring(i);
}
//thuc hien phep tru hai SO LON x,y
public BigNum sub(BigNum x,BigNum y){
//x-y=x+(-y)

return s;
}
//thuc hien phep nhan hai SO NGUYEN x,y
private String mul_1(String x,String y){
String temp,z=new String();
int i,k=0;
//cat bo phan chu so bang 0 o cuoi
i=x.length()-1;
while ( (i>=0) && (x.charAt(i)=='0') ) i ;
k=x.length()-i-1;
x=x.substring(0,i+1);
i=y.length()-1;
while ( (i>=0) && (y.charAt(i)=='0') ) i ;
k=k+y.length()-i-1;
y=y.substring(0,i+1);
for ( i=0;i<x.length();i++){
temp=mul_2(x.charAt(i),y);
z=z+0;
z= add1(z,temp);
}
for (i=0 ;i<k;i++) z=z+0;
if(z.length()==0)return "0";
if(z.charAt(0)=='0')z=z.substring(1);
return z;
}
//thuc hien phep nhan hai SO LON x,y
public BigNum mul(BigNum x,BigNum y){
return new
BigNum( (x.dau==y.dau)? 1:0 ,mul_1(x.val,y.val),(x.num+y.num) );
}

if (isGreat(x,d,k,y)==false)
if (k>lx-2 ){z=0+z;}
else k++;
k ;
do{ k++;t=0;
while( (x[d]==0)&&(d<k ) ) d++;
while(isGreat(x,d,k,y)){
p=0;j=ly-1;
for(i=k;i>=d;i ){
if(x[i]-y[j]-p<0) {x[i]=x[i]-y[j]-
p+10;p=1;}
else {x[i]=x[i]-y[j]-p;p=0;}
j ;
}
if((x[d]==0)&&(d<lx) ) d++;
t++;//System.out.println("dk:"+d+k);
}//of while
z=z+t;//System.out.println("t:"+t);
}//of do
while(isGreat(x,d,lx-1,y)&&(k<lx) ) ;
while(k<lx-1){z=z+0;k++;}
while( (d<lx)&&(x[d]==0) ) d++;
//chia tiep phan du con lai
String st=new String();
for (;d<lx;d++){st=st+x[d];}
for (i=0;i<=n+ly;i++)st=st+0;
if(n!=0)
if (st.charAt(0)=='0'){ for (i=0;i<n;i++)z=z+0;}
else{
po=z.length();

//chu so thap phan la n
public BigNum divReal(BigNum x,BigNum y,int n){
String xx=new String(x.val);
String yy=new String(y.val);
if (x.num>y.num)
for (int i=0;i<x.num-y.num;i++)xx=xx+0;
else for (int i=0;i<y.num-x.num;i++)yy=yy+0;
return new BigNum( (x.dau==y.dau)? 1:0 ,divInt(xx,yy,n),n);
}
//tinh luy thua a co so k
public BigNum exp(BigNum a,int k){
String x=new String("1");
String y=new String(a.val);
int i=k,j=k;
while (k>0){
// k chan
if(k%2==1){
x=mul_1(x,y);
k ;}
else {
//k le
y=mul_1(y,y);
k=k/2;}
}
if((i%2==1)&&(a.dau==0)) i=0;
else i=1;
return new BigNum(i,x,a.num*j);
}
//kiem tra xx co chia het cho yy hay khong
public boolean chiaHet(String xx,String yy){

//phep chia xx cho yy lay phan nguyen
//de phuc vu cho phep toan khai can
public String div1(String xx,String yy){
int x[]=new int[xx.length()+1];
int y[]=new int[yy.length()+1];
int lx=x.length;
int ly=y.length;
if (isLess(xx,yy)) return "0";
String z=new String();
int i,j,d,k,t,p;
x[0]=0;
for (i=0;i<lx-1;i++) x[i+1]=xx.charAt(i)-48;
y[0]=0;
for (i=0;i<ly-1;i++) y[i+1]=yy.charAt(i)-48;
d=1;k=ly-1;
if (isGreat(x,d,k,y)==false) k++;
k ;
do{ k++;
t=0;
while( (x[d]==0)&&(d<k ) ) d++;
while(isGreat(x,d,k,y)){
//tru
p=0;j=ly-1;
for(i=k;i>=d;i ){
14
if(x[i]-y[j]-p<0) {x[i]=x[i]-y[j]-
p+10;p=1;}
else {x[i]=x[i]-y[j]-p;p=0;}
j ;
}

if(chiaHet(s,d)) kt=false;
}
}
while((kt)&&(isLess(d,can) ));
return kt;
}//of else
}
//phep toan khai CAN NGUYEN so nguyen s
public String sqrt(String s) {
String a2,a,d,b,s1,s2;
int temp,k,l;
k=s.length();
l=0;
if(k<3)
return
Integer.toString( (int)Math.sqrt(Integer.parseInt(s)) );
15
if (k%2==0){
temp=(s.charAt(0)-48)*10+s.charAt(1)-48;
l+=2;
a=Integer.toString( (int)Math.sqrt(temp) );
d=sub1(Integer.toString(temp),mul_1(a,a));
}
else{
temp=s.charAt(0)-48;
l++;
a=Integer.toString( (int)Math.sqrt(temp) );
d=sub1(Integer.toString(temp),mul_1(a,a));
}
if(d.charAt(0)=='0')d=d.substring(1);

public String getVal() {return val;}
public void setVal(String s){val=s;}
public int getDau(){return dau;}
public void setDau(int d){ dau=d;}
public String toString(){
String s=new String(val);
if(num<val.length() )
s=val.substring(0,val.length()-num)+"."+
16
val.substring(val.length()-num);
else {for(int i=1;i<num-val.length()+1;i++) s=0+s;
s="0"+"."+s;}
return ((dau==1)||(val.charAt(0)=='0') )? s: "-"+ s; }
}
// test big real number
public class TestBigNum1 {
public static BigNum a,b;
private static BufferedReader reader=new BufferedReader (
new InputStreamReader(System.in) );
//read data by using input stream reader
public static String readData(String s){
System.out.println(s);
return readLn();
}
public static String readLn(){
while (true) try {
return reader.readLine();
} catch (IOException e){
System.err.println("Error in input :"+e.toString());
System.err.println("Please re-enter data.");

b=new BigNum(readData("So chia:"));
int n=Integer.parseInt(readData("So chu so thap
phan "));
c=a.divReal(a,b,n);
System.out.println("division is :"
+ c.toString() );break;}
case 5:{
a=new BigNum(readData("Co so :"));
int e=Integer.parseInt( readData("So mu :")
);
c=a.exp(a,e);
System.out.println("exponentiation is :"
+ c.toString() );
break;}
case 6:{a=new BigNum(readData("Enter the number to
check primitive: "));
String s=a.getVal();
if(a.check(s))
System.out.println("It's "+"prime nuber");
else System.out.println("It isn't prime
number");
break; }
}
}//of while
while ((control>0)&&(control<7));
}//of main
}
18