Tràn số và BigInteger

Tràn số và BigInteger

In Uncategorized

Nếu đã từng dấn thân vào code thì mấy cái như lỗi tràn số chắc đã không còn quá xa lạ với dân coder như chúng ta.

Tâm sự người coder - Will code for food - VN-Zoom | Cộng đồng Chia ...

Thực ra nói là quen thuộc nhưng lỗi tràn số ứng dụng trong thực tế tôi lại chưa gặp bao giờ vì tôi cũng chưa động chạm đến dự án thực tế gây ra lỗi trần số. 😀
Nhưng tôi đã gặp khá nhiều các bài toán giải thuật liên quan đến tràn số. Cuộc đời đầy sóng gió với tôi khi đó khi code bằng ngôn ngữ JavaScript, C/C++. Ví dụ với bài toán sau

Cộng trừ nhân chia 2 số nguyên lớn - Code xử lý số nguyên lớn C/C++

Nếu chỉ tính N! với N<=20 thì đó là việc ai cũng làm được với kiểu dữ liệu Long bình thường vì long có giá trị khoảng 9*10^18.
Nhưng như bài toán trên, trước đây mỗi lần gặp nó thì chỉ có một ý nghĩ duy nhất hiện lên trong đâu tôi: “Thôi bốc Sh*t rồi ” Với N! N=1000 không chỉ cần 100 thôi cũng đã là quá lớn rồi . Tất nhiên bế tắc thì đành hỏi sư phụ Google và tôi có được kết quả
https://nguyenvanhieu.vn/cong-tru-nhan-chia-2-so-nguyen-lon/
Ok vẫn là toang rồi :D. Phải code lại hẳn một thư viện để xử lí số nguyên lớn chưa nói đến trình độ chưa có lại có tốn quá nhiều thời gian và công sức. Có vẻ như thử thách này đưa tôi vào đường cùng đầy bế tắc.

What to do When you have NO Idea What You're Doing — Kristen Simonelli

Sau đó, một thời gian, khi bâng quơ giải trí với vài câu code lại gặp một bài toán kiểu tương tự. Ôi shit, cái gì cần phải đến cuối cùng cũng phải đến thôi. Ngồi nghĩ mãi không ra tôi tham khảo code ở phần thảo luận thấy dùng ngôn ngữ Python chỉ mất một dòng và không xảy ra lỗi tràn số nào, đều có thẻ xử lí được. What the hell???? Sau đó tôi liền hỏi ý kiến sư phụ lần nữa thì đời quả thật đầy rẫy bất công đến ngôn ngữ cũng vậy. Các ngôn ngữ như Java, Python, Ruby,etc có hỗ trợ hẵn kiểu BigInteger hay nôm na có thể xử lí được các số rất lớn.
Cụ thể trong Java có BigInteger Class
Khai báo như sau:
BigInteger num = new BigInteger();
Với bài toán tính giai thừa số lớn như trên thì giải quyết như sau:

mport java.math.BigInteger; 
import java.util.Scanner; 
  
public class Example 
{ 
    // Returns Factorial of N 
    static BigInteger factorial(int N) 
    { 
        // Initialize result 
        BigInteger f = new BigInteger("1");
  
        // Multiply f with 2, 3, ...N 
        for (int i = 2; i <= N; i++) 
            f = f.multiply(BigInteger.valueOf(i)); 
  
        return f; 
    } 
  
    // Driver method 
    public static void main(String args[]) throws Exception 
    { 
        int N = 20; 
        System.out.println(factorial(N)); 
    } 
} 

Kết luận : mỗi ngôn ngữ đều có điểm mạnh điểm yếu riêng. Vì thế tùy trường hợp mà sử dụng phù hợp là tốt nhất.
Bây giờ tôi không còn sợ mấy bài toán tràn số nữa rồi :D. Nói thế thôi chứ với những bài số quá lớn không thể thao tác BigInteger được ta vẫn phải thao tác với string.

Conal Dev
tham khảo : https://www.geeksforgeeks.org/biginteger-class-in-java/
https://nguyendangkhiemit.wordpress.com/2014/10/08/biginteger-trong-java/