Tính tổng, tích modulo và bán tổng-- computing modulo sum, modulo product and semi-sum

Đây là bài trả lời cho bài toán bug bug bug trên facebook mà mình post mấy hôm trước. Xin vui lòng để lại comment nếu bạn có lời giải tốt hơn; mình sẽ cập nhật vào bài viết chính (tất nhiên cả thông tin của tác giả). Bài toán như sau:

  1. Cho 3 số nguyên dương kiểu int a,b,p, tính tổng (a+b) \mod p.
  2. Cho 3 số nguyên dương kiểu int a,b,p, tính tích a*b \mod p.
  3. Cho 2 số nguyên kiểu int x,y, tìm \lfloor \frac{a+b}{2} \rfloor.

 

Tại sao những câu hỏi này thú vị?

Thông thường, khi bạn được yêu cầu viết code cho các câu hỏi trên, bạn có thể sẽ làm như sau:

 
int sum_mod(int a, int b, int p){
	return (a+b)%p;
}

int prod_mod(int a, int b, int p){
	return (a*b)%p;
}

int semi_sum(int a, int b){
	return (a+b)/2;
}

 

Các đoạn code này thoạt nhìn có vẻ đúng nhưng bên trong nó tiềm ẩn những lỗi nghiêm trọng. Trong hai đoạn code trả lời câu hỏi (1) và (2), lỗi cơ bản mà ta có thể gặp đó là tràn số. Ví dụ a = 2147483629, b = 2029484451, p = 2147483633 thì tổng a+b và tích a*b không còn có thể biểu diễn được bằng kiểu int nữa. Trong đoạn code cho câu hỏi (3), ngoài lỗi tràn số, kết quả trả về sẽ bị sai khi a+b < 0. Ví dụ a = -3, b = -4, đoạn mã sẽ trả về -3 thay vì -4.

Một nhận xét đơn giản mà ta dễ thấy đó là kết quả đầu ra của các câu hỏi trên có thể biểu điên được bằng kiểu int. Tuy nhiên, khi bạn nghĩ sâu hơn về làm thể nào để tránh tràn số, bạn sẽ thấy trả lời câu hỏi này một cách trọn vẹn không hề đơn giản.

Tổng modulo

Ngược lại với bài toán tổng modulo, bài toán hiệu modulo có thể tính được dễ dàng mà không sợ tràn số.

Cho 3 số nguyên không âm kiểu int a,b,p, trong đó 0\leq a,b < p, tính hiệu (a-b) \mod p.

 

Ta có thể giả sử a , b đều nhỏ hơn p bằng cách lấy mod trước khi tính hiệu. Hiệu số (a-b) luôn có thể biểu diễn được bằng kiểu int. Do đó, nếu (a \geq b) ta tính tính (a-b) \mod p = a-b. Nếu a < b, ta sẽ tính (a - b)\mod p = (p + (a - b) ). Chú ý ở đây ta giả sử a, b đều nhỏ hơn p, do đó 0 \leq p + (a-b) < p. Code:

 
int diff_mod(int a, int b, int p){
	return (a >= b)? (a-b) : (p + a - b);
}

 

Bài toán tổng modulo có thể quy về hiệu modulo bằng mẹo sau:

(a + b) \mod p  = (a - (p-b)) \mod p \qquad (1)

 

Trước khi ta chuyển về tính hiệu, ta đảm bảo a,b đều nhỏ hơn p bằng cách lấy modulo p. Code:

 
int sum_mod_fixed(int a, int b, int p){
	int x = a%p;
	int y = b%p;
	return diff_mod(x, p-y,p);
}

 
Tích modulo

Tính tích a*b \mod p, ta sử dụng ý tưởng chia để trị trong bài tính lũy thừa x^n.

  1. Nếu b chẵn, a*b = a*\lfloor b/2\rfloor + a*\lfloor b/2\rfloor.
  2. Nếu b lẻ, a*b = a*\lfloor b/2\rfloor + a*\lfloor b/2\rfloor + a.

Ta sẽ gọi đệ quy để tính a*\lfloor b/2\rfloor \mod p và sử dụng thủ tục tính tổng modulo để tính tổng. Code

 
int prod_mod_fixed(int a, int b, int p){
	if (b==1) return a%p;
	else{
		int x = prod_mod_fixed(a,b/2,p);
		int y = sum_mod_fixed(x,x,p);
		if(b%2 == 0){	// b is even
			return y;
		} else return sum_mod_fixed(y,a,p); 
	}
}

 

Phân tích độ phức tạp: Thủ tục đệ quy có độ sâu \log b. Mỗi lần gọi đệ quy, ta mất (\log a + \log b) thao tác bít để tính a*b từ kết quả của lời gọi đệ quy. Do đó, tổng số thao tác bít là:

O(\log a\log b + \log^2 b) \qquad (2)

 

Tính bán tổng

Nếu tràn số không xảy ra, thủ tục semi_sum ở phần giới thiệu sẽ trả lại kết quả \lfloor\frac{a+b}{2} \rfloor đúng nếu a+b \geq 0 và trả lại \lceil \frac{a+b}{2} \rceil nếu ngược lại.

Ta sẽ sử dụng công thức cơ bản sau để biến đổi nửa tổng về dạng mà ta có thể tính đơn giản được:

\lfloor m +x \rfloor = m +  \lfloor x \rfloor \quad \forall m \in \mathbb{Z} \qquad (3)

\lfloor  \frac{x}{2}\rfloor = x -  \lceil \frac{x}{2} \rceil \quad \forall x \in \mathbb{Z} \qquad (4)

Trường hợp a,b khác dấu, tràn số sẽ không bao giờ xảy ra. Do đó, ta chỉ cần kiểm tra xem nếu a+b \geq 0, ta sẽ áp dụng thủ tục semi_sum, và áp dụng (4) nếu ngược lại.

Trường hợp a,b cùng dấu, ta giả sử a \geq b. Ta có:

\lfloor \frac{a+b}{2} \rfloor = \lfloor b +  \frac{a-b}{2} \rfloor  =  b +  \lfloor \frac{a-b}{2} \rfloor \qquad (5)

Do a-b \geq 0, phần nguyên theo (4) có thể tính như trong semi_sum (mà không lo tràn số vì a,b cùng dấu).

Code:

 
int semi_sum_fixed(int a, int b){
	if((a^b) < 0){	// a and b have different signs
			return (a + b < 0? a+b - (a+b)/2 : (a+b)/2);
	} else {
		return (a < b ? a + (b-a)/2 : b + (a-b)/2);
	}
}

 

Code ở trên ta sử dụng phép XOR (\oplus) để kiểm tra xem hai số có cùn dấu hay không. Hai số nguyên a,b cùng dấu khi và chỉ khi a\oplus b \geq 0, ở đây \oplus là phép XOR bit.

Remark Code ở trên chỉ mang tính minh họa. Để code hiệu quả hơn, ta có thể thay thế một số thao tác đại số (kể cả lệnh rẽ nhánh if, then) bằng các thao tác bít. Ví dụ x \mod 2 = x\&1, x/2 = x \gg 1, .... Xem thêm tại bài các thao tác xử lí bít.

Code đầy đủ: click-here.
Tham khảo

[1] Ruggieri, Salvatore. On computing the semi-sum of two integers. Information Processing Letters 87.2 (2003): 67-71.

Facebook Comments

Tags: ,

Reply

Your email address will not be published. Required fields are marked *