Nhân các số nguyên rất dài

Question

Có một thuật toán để nhân chính xác hai số nguyên dài tùy ý với nhau không? Ngôn ngữ tôi đang làm việc được giới hạn ở độ dài nguyên không dấu 64 bit (kích thước số nguyên tối đa là 18446744073709551615). Thực tế, tôi muốn có thể làm điều này bằng cách chia nhỏ từng số, xử lý bằng cách nào đó bằng cách sử dụng số nguyên 64 bit không dấu, và sau đó có thể đặt chúng lại với nhau thành một chuỗi (sẽ giải quyết được vấn đề về kết quả nhân lưu trữ).

Bất kỳ ý tưởng nào?

Answer 1

Hầu hết các ngôn ngữ có chức năng hoặc thư viện mà làm điều này, thường được gọi là một thư viện bignum (GMP là một tốt nhất.)

Nếu bạn muốn tự mình làm, tôi sẽ làm điều đó theo cùng một cách mà mọi người làm ăn lâu phép nhân trên giấy. Để làm điều này, bạn có thể làm việc với các chuỗi chứa số, hoặc thực hiện nó trong nhị phân bằng cách sử dụng các phép toán bitwise.

Ví dụ:

45 
x67 
--- 
315 
+270 
---- 
585 

Hoặc trong hệ nhị phân:

101 
    x101 
    ---- 
    101 
    000 
+101 
------ 
11001 

Edit: Sau khi thực hiện nó trong hệ nhị phân tôi nhận ra rằng nó sẽ đơn giản hơn nhiều (và nhanh hơn tất nhiên) để mã hóa sử dụng các hoạt động bitwise thay vì các chuỗi chứa các số cơ sở-10. Tôi đã chỉnh sửa ví dụ nhân nhị phân của mình để hiển thị mẫu: cho mỗi bit 1 ở số dưới cùng, thêm số trên cùng, bit dịch chuyển sang trái vị trí của 1 bit lần đến một biến. Cuối cùng, biến đó sẽ chứa sản phẩm.

Để lưu trữ sản phẩm, bạn sẽ phải có hai số 64 bit và tưởng tượng một trong số đó là 64 bit đầu tiên và bit còn lại là 64 bit thứ hai của sản phẩm. Bạn sẽ phải viết mã mang phần bổ sung từ bit 63 của số thứ hai đến bit 0 của số đầu tiên.

Answer 2

Có, bạn làm điều đó bằng cách sử dụng một kiểu dữ liệu có hiệu quả là một chuỗi các chữ số (giống như một chuỗi 'bình thường' là một chuỗi ký tự). Làm thế nào bạn làm điều này là rất phụ thuộc vào ngôn ngữ. Ví dụ, Java sử dụng BigDecimal. Ngôn ngữ của bạn đang sử dụng là gì?

Answer 3

Điều này thường được dùng làm bài tập về nhà. Thuật toán bạn học được ở cấp lớp sẽ hoạt động. Sử dụng một thư viện (một số được đề cập trong các bài viết khác) nếu bạn cần điều này cho một ứng dụng thực tế.

Answer 4

Cách đơn giản nhất là sử dụng cơ chế sách học, chia các số có kích thước tùy ý của bạn thành các khối 32 bit mỗi.

Cho A B C D * E F G H (mỗi đoạn 32 bit, với tổng số 128 bit)
Bạn cần một mảng đầu ra rộng 9 dwords. Đặt ra [0..8] tới 0

Bạn sẽ bắt đầu bằng cách thực hiện: H * D + out [8] => Kết quả 64 bit.
Lưu trữ các bit 32 bit thấp ra ngoài [8] và lấy 32 bit cao khi mang theo
Tiếp theo: (H * C) + ra [7] + mang
Một lần nữa, lưu trữ ít 32 bit ra ngoài [ 7], sử dụng 32 bit cao khi mang theo
sau khi thực hiện H * A + out [4] + carry, bạn cần tiếp tục lặp cho đến khi bạn không mang theo.

Sau đó lặp lại với G, F, E.
Đối với G, bạn bắt đầu ra ngoài [7] thay vì ra [8], v.v.

Cuối cùng, bước qua và chuyển đổi các số nguyên lớn thành chữ số (mà sẽ đòi hỏi phải có "chia số lượng lớn bởi một từ duy nhất" thói quen)

Answer 5

Nếu bạn không thể sử dụng một thư viện bignum hiện như GMP, kiểm tra Wikipedia's article on binary multiplication with computers. Có một số thuật toán tốt, hiệu quả cho việc này.

Answer 6

đây là mảnh mã của tôi trong C. Tốt phương pháp nhân cũ

char *multiply(char s1[], char s2[]) { 
    int l1 = strlen(s1); 
    int l2 = strlen(s2); 
    int i, j, k = 0, c = 0; 
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string 
    int temp; 

    strrev(s1); 
    strrev(s2); 
    for (i = 0;i <l1+l2; i++) { 
     r[i] = 0 + '0'; 
    } 

    for (i = 0; i <l1; i ++) { 
     c = 0; k = i; 
     for (j = 0; j < l2; j++) { 
      temp = get_int(s1[i]) * get_int(s2[j]); 
      temp = temp + c + get_int(r[k]); 
      c = temp /10; 
      r[k] = temp%10 + '0'; 

      k++; 
     } 
     if (c!=0) { 
      r[k] = c + '0'; 
      k++; 
     } 
    } 

    r[k] = '\0'; 
    strrev(r); 
    return r; 
}