Tôi có thể tìm các thuật toán nhân và chia nhỏ ở đâu?

Question

Tôi đang làm việc trên bộ điều khiển vi mô mà không cần nhân và chia phần cứng. Tôi cần phải nấu các thuật toán phần mềm cho các hoạt động cơ bản này, đó là một sự cân bằng tốt đẹp về kích thước và hiệu quả nhỏ gọn. Cổng trình biên dịch C của tôi sẽ sử dụng các thuật toán này, chứ không phải chính các nhà phát triển C.

Google-fu của tôi cho đến nay hầu hết đều có tiếng ồn về chủ đề này.

Có ai có thể chỉ cho tôi thông tin gì đó không? Tôi có thể sử dụng hướng dẫn thêm/phụ và thay đổi. Bảng tìm kiếm dựa trên thuật toán cũng có thể làm việc cho tôi, nhưng tôi là một chút lo lắng về nhồi nhét rất nhiều vào back-end của trình biên dịch ... um, vì vậy để nói chuyện.

Answer 1

Dưới đây là một thuật toán phép nhân đơn giản:

1. Bắt đầu với chút ngoài cùng bên phải của số nhân.

2. Nếu bit trong số nhân là 1, thêm nhơn

3. phím Shift nhơn bởi 1

4. Di chuyển đến bit tiếp theo trong số nhân và quay lại bước 2.

Và đây là thuật toán phân chia:

1. I f ước số lớn hơn cổ tức, dừng lại.

2. Khi thanh ghi số chia nhỏ hơn số đăng ký cổ tức, hãy dịch sang trái.

3. phím Shift ước đăng ký ngay bằng cách 1.

4. Subtract ước đăng ký từ sổ đăng ký cổ tức và thay đổi chút để 1 vào sổ đăng ký kết quả tại các bit tương ứng với tổng số ca thực hiện để đăng ký ước.

5. Bắt đầu lại ở bước 1 với thanh ghi số chia ở trạng thái ban đầu.

Tất nhiên, bạn sẽ cần đặt trong séc để chia cho 0, nhưng nó sẽ hoạt động.

Các thuật toán này, tất nhiên, chỉ dành cho số nguyên.

Answer 2

Dưới đây là một thuật toán phân chia: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html

Tôi giả sử chúng ta đang nói về ints?

Nếu không có hỗ trợ phần cứng, bạn sẽ phải triển khai ngoại lệ chia cho từng số không.

(Tôi không có nhiều may mắn khi tìm một thuật toán nhân, nhưng tôi sẽ tiếp tục tìm kiếm nếu người khác không tìm thấy một thuật toán).

Answer 3

Một thuật toán nhân đơn giản và khá hiệu quả cho các số nguyên là Russian Peasant Multiplication.

Đối với hợp lý, bạn có thể thử một số nhị phân quote notation, để phân chia dễ dàng hơn bình thường.

Answer 4

Để nhân, hãy thêm một phần sản phẩm từ phép nhân được dịch chuyển sang bộ tích lũy iff bit tương ứng trong hệ số được thiết lập. Shift nhân và nhân ở cuối vòng lặp, kiểm tra hệ số & 1 để xem có nên thực hiện thêm hay không.

Answer 5

tham khảo ưa thích của tôi cho những thứ như thế này, có sẵn ở dạng cuốn sách:

http://www.hackersdelight.org/

Ngoài ra bạn không thể đi sai với TAoCP: http://www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 6

Nó chỉ ra rằng tôi vẫn còn có một số cũ Mã lắp ráp 68000 cho phép nhân dài và chia dài. 68000 mã là khá sạch sẽ và đơn giản, vì vậy phải dễ dàng dịch cho chip của bạn.

68000 đã nhân và chia hướng dẫn IIRC - Tôi nghĩ rằng chúng được viết dưới dạng bài tập học tập.

Quyết định chỉ cần đặt mã ở đây. Đã thêm nhận xét và, trong quá trình này, đã khắc phục được sự cố.

; 
; Purpose : division of longword by longword to give longword 
;   : all values signed. 
; Requires : d0.L == Value to divide 
;   : d1.L == Value to divide by 
; Changes : d0.L == Remainder 
;   : d2.L == Result 
;   : corrupts d1, d3, d4 
; 

     section text 

ldiv: move #0,d3  ; Convert d0 -ve to +ve - d3 records original sign 
     tst.l d0 
     bpl.s lib5a 
     neg.l d0 
     not  d3 
lib5a: tst.l d1  ; Convert d1 -ve to +ve - d3 records result sign 
     bpl.s lib5b 
     neg.l d1 
     not  d3 
lib5b: tst.l d1  ; Detect division by zero (not really handled well) 
     bne.s lib3a 
     rts 
lib3a: moveq.l #0,d2  ; Init working result d2 
     moveq.l #1,d4  ; Init d4 
lib3b: cmp.l d0,d1  ; while d0 < d1 { 
     bhi.s lib3c 
     asl.l #1,d1  ; double d1 and d4 
     asl.l #1,d4 
     bra.s lib3b  ; } 
lib3c: asr.l #1,d1  ; halve d1 and d4 
     asr.l #1,d4 
     bcs.s lib3d  ; stop when d4 reaches zero 
     cmp.l d0,d1  ; do subtraction if appropriate 
     bhi.s lib3c 
     or.l d4,d2  ; update result 
     sub.l d1,d0 
     bne.s lib3c 
lib3d:     ; fix the result and remainder signs 
;  and.l #$7fffffff,d2 ; don't know why this is here 
     tst  d3 
     beq.s lib3e 
     neg.l d2 
     neg.l d0 
lib3e: rts 

; 
; Purpose : Multiply long by long to give long 
; Requires : D0.L == Input 1 
;   : D1.L == Input 2 
; Changes : D2.L == Result 
;   : D3.L is corrupted 
; 

lmul: move #0,d3  ; d0 -ve to +ve, original sign in d3 
     tst.l d0 
     bpl.s lib4c 
     neg.l d0 
     not  d3 
lib4c: tst.l d1   ; d1 -ve to +ve, result sign in d3 
     bpl.s lib4d 
     neg.l d1 
     not  d3 
lib4d: moveq.l #0,d2  ; init d2 as working result 
lib4a: asr.l #1,d0  ; shift d0 right 
     bcs.s lib4b  ; if a bit fell off, update result 
     asl.l #1,d1  ; either way, shift left d1 
     tst.l d0 
     bne.s lib4a  ; if d0 non-zero, continue 
     tst.l d3   ; basically done - apply sign? 
     beq.s lib4e  ; was broken! now fixed 
     neg.l d2 
lib4e: rts 
lib4b: add.l d1,d2  ; main loop body - update result 
     asl.l #1,d1 
     bra.s lib4a 

Nhân tiện - tôi chưa bao giờ tìm ra liệu cần phải chuyển đổi mọi thứ thành tích cực ngay từ đầu. Nếu bạn cẩn thận với thao tác dịch chuyển, đó có thể là chi phí có thể tránh được.

Answer 7

Chip vi dòng PICmicro 16Fxxx không có chỉ thị nhân hoặc chia. Có lẽ một số thói quen phân chia mềm và nhân mềm cho nó có thể được chuyển đến MCU của bạn.

PIC Microcontroller Basic Math Multiplication Methods

PIC Microcontroller Basic Math Division Methods

Ngoài ra kiểm tra "Newton's method" for division. Tôi nghĩ rằng phương pháp này mang lại kích thước nhỏ nhất có thể thực thi của bất kỳ thuật toán phân chia nào mà tôi từng thấy, mặc dù giải thích làm cho nó phức tạp hơn thực tế. Tôi nghe nói rằng một số siêu máy tính Cray sớm sử dụng phương pháp của Newton để phân chia.