Làm thế nào để thực hiện phân chia bằng cách thêm?

Question

Câu hỏi phỏng vấn.

Làm cách nào để thực hiện phân chia bằng cách thêm? giả sử họ là tất cả int.

Ý tưởng của tôi

1. Thêm ước với chính nó cho đến khi nó lớn hơn cổ tức. Mỗi lần lặp lại, giữ nguyên kết quả trước khi thêm.
2. Thương là tổng kết quả trước lần bổ sung cuối cùng. phần còn lại có thể được tính bằng cách thêm 1 cho đến quotient * divisor + reminder == dividend.

Đó là O(e^n), có ý tưởng nào tốt hơn không? hoạt động bit?

Answer 1

Trong số học số, chúng tôi có thể đặt tên cho các phương thức khôi phục và không khôi phục thành các thuật toán phân chia đơn giản dựa trên cộng/trừ. Số lần lặp trong các phương thức này là O(n) (trong đó n là số bit). Có các phương pháp như Newton-Raphson hoặc tính toán đối ứng dựa trên phép nhân và số lần lặp trong chúng là O(log n). Hãy nhìn vào http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

chia m bởi n:

int r = m; 
int q = 0; 

while(r >= n) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while((t = x+x) < r) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    r -= x; 
} 

Kết quả là q - thương, r - còn lại.

Ý tưởng là x+x giống với x*2.

UPD:

Một số có thể phàn nàn rằng r -= x không phải là bổ sung. Vâng, chúng tôi có thể cập nhật các thuật toán để không sử dụng phép trừ:

int p = 0; 
int q = 0; 

while(p+n <= m) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    p += x; 
} 

Kết quả là q - thương.

Nếu chúng ta cần thời gian còn lại thì chúng ta tiến hành như sau (p - đầu ra từ trên):

int r = 0; 

while(p < m) 
{ 
    int x = 1; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
    } 

    r += x; 
    p += x; 
} 

Kết quả là r - còn lại.

Thuật toán rõ ràng là đa thức (không theo cấp số nhân) thời gian chạy.

Answer 3

Bạn sẽ chia bộ phận thành các thành phần logarit của nó và sau đó tính toán chúng.