Tại sao bình phương một số nhanh hơn nhân hai số ngẫu nhiên?

Question

Nhân hai số nhị phân mất n^2 lần, nhưng bình phương một số có thể được thực hiện hiệu quả hơn bằng cách nào đó. (với n là số bit) Làm thế nào có thể được?

Hoặc là không thể? Đây là điên rồ!

Answer 1

1. Có tồn tại các thuật toán hiệu quả hơn O (N^2) để nhân hai số (xem Karatsuba, Pollard, Schönhage-Strassen, vv)

2. Hai vấn đề "nhân hai tùy N số bit "và" Square một số bit N tùy ý "có cùng độ phức tạp.

Chúng tôi có

4*x*y = (x+y)^2 - (x-y)^2 

Vì vậy, nếu bình phương số nguyên N-bit mất O (f (N)) thời gian, sau đó là sản phẩm của hai số nguyên N-bit tùy ý có thể thu được trong thời gian O (f (N)) quá.(Có nghĩa là 2x tiền N-bit, 2x vuông N-bit, 1x 2N-bit Tóm lại, và 1x 2N-bit shift)

Và rõ ràng là chúng tôi có

x^2 = x * x 

Vì vậy, nếu nhân hai N-bit số nguyên lấy O (f (N)), sau đó bình phương số nguyên N bit có thể được thực hiện trong O (f (N)).

Bất kỳ thuật toán tính toán sản phẩm nào (trả về hình vuông) cung cấp thuật toán tính toán hình vuông (trả lời sản phẩm) với cùng chi phí tiệm cận.

Như đã lưu ý trong các câu trả lời khác, các thuật toán được sử dụng để nhân nhanh có thể được đơn giản hóa trong trường hợp bình phương. Việc đạt được sẽ được trên hằng số ở phía trước của f (N), và không phải trên f (N) chính nó.

Answer 2

Bạn có nghĩa là nhân một số với lũy thừa là 2 không? Điều này thường nhanh hơn nhân hai số ngẫu nhiên vì kết quả có thể được tính bằng cách dịch chuyển bit đơn giản. Tuy nhiên, hãy nhớ rằng bộ vi xử lý hiện đại dành rất nhiều lực lượng silic vũ phu đến các loại tính toán và hầu hết số học được thực hiện với mù tốc độ so với bộ vi xử lý cũ

Answer 3

Các căn bậc hai của 2 ⁿ là 2 ^n/2 hoặc 2 ^{n >> 1}, vì vậy nếu số của bạn là sức mạnh của hai thứ thì hoàn toàn đơn giản khi bạn biết được sức mạnh. Để nhân thậm chí còn đơn giản hơn: 2 * 2 là 2 ^{4 + 8}. Không có ý nghĩa gì trong những phát biểu này bạn đã làm.

Answer 4

Tôi tin rằng bạn có thể đang đề cập đến exponentiation by squaring. Kỹ thuật này không được sử dụng để nhân, nhưng để nâng lên một sức mạnh x^n, trong đó n có thể lớn. Thay vì nhân x lần N lần, một thực hiện một loạt các bình phương và thêm hoạt động có thể được ánh xạ tới biểu diễn nhị phân của N. Số hoạt động nhân (đắt hơn số bổ sung cho số lớn) được giảm từ N để đăng nhập (N) đối với thuật toán lũy thừa ngây thơ.

Answer 5

Tôi có nó!

2 * 2 

đắt hơn

2 << 1 

(Thông báo trước là nó chỉ hoạt động cho một trường hợp.)

Answer 6

Tôi nghĩ rằng bạn là hoàn toàn sai trong báo cáo của bạn

Nhân hai số nhị phân mất n^2 lần

Nhân hai số 32 bit lấy chính xác một chu kỳ đồng hồ. Trên một bộ xử lý 64 bit, tôi giả định rằng nhân hai số 64 bit lấy chính xác 1 chu kỳ đồng hồ. Nó thậm chí sẽ không ngạc nhiên của tôi rằng một bộ xử lý 32 bit có thể nhân hai số 64bit trong 1 chu kỳ đồng hồ.

yet squaring a number can be done more efficiently somehow. 

Vuông một số chỉ nhân số với chính nó, vì vậy đó chỉ là phép nhân đơn giản. Không có hoạt động "vuông" trong CPU.

Có thể bạn đang bối rối "bình phương" với "nhân với sức mạnh của 2". Nhân với 2 có thể được thực hiện bằng cách dịch chuyển tất cả các bit một vị trí sang "trái". Nhân với 4 là chuyển tất cả các bit hai vị trí sang "trái". Bởi 8, 3 vị trí. Nhưng thủ thuật này chỉ áp dụng cho sức mạnh của hai người.

Answer 7

Squaring một chữ số n có thể nhanh hơn nhân hai số n chữ số ngẫu nhiên. Googling tôi tìm thấy this article. Đó là về số học chính xác tùy ý nhưng nó có thể liên quan đến những gì bạn yêu cầu.Trong đó các tác giả nói điều này:

trong bình phương một số nguyên lớn, tức là X^2 = (xn-1, xn-2, ..., x1, x0)^2 nhiều thuật ngữ chéo sản phẩm của dạng xi * xj và xj * xi tương đương nhau. Họ chỉ cần được tính một lần và sau đó chuyển sang trái để tăng gấp đôi. Một hoạt động bình phương chữ số n là được thực hiện chỉ sử dụng (n^2 + n)/2 phép nhân đơn chính xác.

Answer 8

Nếu bạn có số nhị phân A, có thể (luôn bằng chứng cho người đọc mong muốn) (2^n + B), có thể được bình phương là 2^2n + 2^(n +1) B + B^2. Sau đó chúng ta có thể lặp lại việc mở rộng, cho đến khi một điểm B bằng không. Tôi đã không nhìn quá khó khăn vào nó, nhưng bằng trực giác, nó cảm thấy như thể bạn sẽ có thể làm cho một chức năng bình phương mất ít bước thuật toán hơn một phép nhân đa năng.

Answer 9

Nếu bạn giả định chiều dài cố định với kích thước chữ của máy và số được bình phương trong bộ nhớ, thao tác bình phương chỉ yêu cầu một tải từ bộ nhớ, vì vậy có thể nhanh hơn.

Đối với số nguyên chiều dài tùy ý, phép nhân thường là O (N²) nhưng có các thuật toán làm giảm số này cho số nguyên lớn.

Nếu bạn cho rằng cách tiếp cận đơn giản O (n ²) để nhân một bởi b, sau đó cho mỗi bit trong một bạn phải thay đổi b và thêm nó vào một ắc nếu đó bit là một . Đối với mỗi bit trong a, bạn cần thay đổi và bổ sung 3N.

Lưu ý rằng

(x - y)² = x² - 2 xy + y² 

Do đó

x² = (x - y)² + 2 xy - y² 

Nếu mỗi y là sức mạnh lớn nhất của hai không lớn hơn x, điều này mang lại một giảm đến một hình vuông thấp hơn, hai ca và hai bổ sung. Khi N bị giảm trên mỗi lần lặp lại, bạn có thể nhận được hiệu suất tăng (đối xứng nghĩa là nó truy cập từng điểm trong tam giác thay vì hình chữ nhật), nhưng nó vẫn là O (N²).

Có thể có một đối xứng tốt hơn để khai thác.

Answer 10

Trước hết câu hỏi tuyệt vời! Tôi ước có nhiều câu hỏi như thế này.

Vì vậy, nó chỉ ra rằng phương pháp tôi đưa ra là O (n log n) cho phép nhân chung chỉ trong độ phức tạp số học. Bạn có thể đại diện cho bất kỳ số X như

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0 
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0 

nơi

x_i, y_i \in {0,1} 

sau đó

XY = sum _ {k=0}^m+n r_k 2^k 

nơi

r_k = sum _ {i=0}^k x_i y_{k-i} 

mà chỉ là một ứng dụng chuyển tiếp thẳng của FFT để tìm ra giá trị của r_k cho mỗi k trong (n + m) log (n + m) thời gian.

Sau đó, đối với mỗi r_k, bạn phải xác định mức độ tràn lớn và thêm nó cho phù hợp. Đối với bình phương một con số này có nghĩa là O (n log n) số học hoạt động.

Bạn có thể thêm giá trị r_k hiệu quả hơn bằng thuật toán Schönhage – Strassen để thu được hoạt động bit O (n log n log log n) bị ràng buộc.

Câu trả lời chính xác cho câu hỏi của bạn đã được đăng bởi Eric Bainville.

Tuy nhiên, bạn có thể bị ràng buộc tốt hơn nhiều so với O (n^2) để bình phương một số đơn giản vì có tồn tại nhiều giới hạn tốt hơn để nhân số nguyên!

Answer 11

Giống như những người khác đã chỉ ra, bình phương chỉ có thể nhanh hơn khoảng 1,5X hoặc 2X so với phép nhân thường xuyên giữa các số tùy ý. Lợi thế tính toán đến từ đâu? Đó là sự đối xứng. Hãy tính toán hình vuông của 1011 và cố gắng phát hiện ra một mẫu mà chúng ta có thể khai thác. u0:u3 đại diện cho các bit trong số từ quan trọng nhất đến ít quan trọng nhất.

1011 //        u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3 
    1011 //      u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3  
    0000 //   u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3     
1011 // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3       

Nếu bạn xem xét các yếu tố ui * ui cho i=0, 1, ..., 4 để tạo thành đường chéo và bỏ qua chúng, bạn sẽ thấy rằng các yếu tố ui * uj cho i ≠ j được lặp lại hai lần.

Do đó, tất cả những gì bạn cần làm là tính tổng sản phẩm cho các phần tử bên dưới đường chéo và nhân đôi nó, với sự dịch chuyển trái. Cuối cùng bạn đã thêm các phần tử chéo.Bây giờ bạn có thể thấy tốc độ 2X đến từ đâu. Trong thực tế, tốc độ tăng lên khoảng 1.5X vì đường chéo và các hoạt động phụ.

Answer 12

a^2 (a + b) * (a + b) + b^2 ví dụ: 66^2 = (66 + 6) (66-6) + 6^2 = 72 * 60 + 36 = 4356

cho a^n chỉ cần sử dụng quy tắc điện

66^4 = 4356^2

Answer 13

Giả sử bạn muốn mở rộng phép nhân (a+b)×(c+d). Nó chia thành bốn phép nhân riêng lẻ: a×c + a×d + b×c + b×d.

Nhưng nếu bạn muốn mở rộng ra (a+b)², thì chỉ cần ba phép nhân (và nhân đôi): a² + 2ab + b².

(Cũng lưu ý rằng hai trong số các phép nhân là thân hình vuông.)

Hy vọng rằng đây chỉ là bắt đầu để đưa ra một cái nhìn sâu sắc vào một số các speedups rằng có thể xảy ra khi thực hiện một hình vuông trên một phép nhân thông thường.