Logic đằng sau thuật toán phân chia Fourier là gì?

Question

từ Wikipedia: fourier division.

Đây là một ảnh chụp màn hình của cùng: (view in full-resolution)

logic đằng sau thuật toán này là gì?

Tôi biết nó có thể được sử dụng để chia số lượng rất lớn, nhưng chính xác nó hoạt động như thế nào?

Answer 1

điều này dường như là một sự chuyển đổi thông minh của thuật toán Phân chia dài. Các phần thông minh dường như là chúng chỉ sử dụng phép chia cho chữ số đầu tiên, a1, và tránh phải sử dụng dấu khác (x) theo cách tương tự bằng cách áp dụng chúng trong bước tiếp theo bằng cách trừ đi sản phẩm (chống lại một phần thương) từ phần còn lại tạm thời.

Điều này có thể được thực hiện hợp lệ và luôn hoạt động có thể do thực tế là "chữ số" (cơ sở 100, trong trường hợp này) không phải là số thực và có thể thừa nhận hợp pháp các giá trị lớn hơn cơ sở của chúng. tức là trên 100) và thậm chí ít hơn 0. Điều này cho phép sự linh hoạt lớn hơn trong thời gian ứng dụng của mỗi "chữ số" đối với hoạt động như, ví dụ, trì hoãn việc áp dụng các chữ số thứ hai của số chia (a (x> 1)) cho đến sau khi một phần thương được tạo ra từ phân chia của bước trước bởi một (1), do đó cho phép chúng được áp dụng như một phép trừ sản phẩm, chứ không phải là phép toán phân chia.

Answer 2

Đây là một thuật toán cực kỳ thông minh. Tôi không thể tưởng tượng như thế nào ol 'JF quản lý để có được hld của nó kể từ khi mối quan hệ therecurrence là vô cùng khó khăn để xem ngay cả khi bạn biết nó tồn tại. Theo ý kiến ​​của tôi, ông đã chính thức hóa một phương pháp mà ông đã sử dụng để chia tay lâu dài - ông phải thực hiện rất nhiều phép tính bằng tay trong thời đại trước máy tính kỹ thuật số, và ông có thể thích sử dụng quy tắc trượt hơn.

Đúng là người ta có thể mơ hồ thấy đường viền của phương pháp khi bắt đầu thuật toán phân chia dài tiêu chuẩn, nhưng đó là đầu mối duy nhất. Bạn có thể tìm kiếm lâu dài và khó khăn cho sự tái diễn này mà không nhìn thấy nó. Có rất nhiều con số liên quan - nó bị bối rối khi nhìn vào các mối quan hệ.

Có một trực giác khác thu được từ việc nghiên cứu luồng dữ liệu trong thuật toán nhân chuẩn. Nếu bạn viết nó ra trong phần cứng máy tính, bạn có thể thấy rằng một mảng vuông của các đơn vị nhân 8 bit có hai số 32 bit được sắp xếp dọc theo cạnh dưới cùng và bên phải của chúng và di chuyển dữ liệu lên và sang trái, thoát ở cạnh trên của mảng trong câu trả lời 64 bit. Đơn vị ngoài cùng bên trái trên cùng cung cấp các số TWO (8 bit) hàng đầu của sản phẩm, sử dụng các chữ số trên cùng của các phép nhân và chuyển từ phần còn lại của mảng sang bên phải của nó. ĐƯỢC? Vâng, hãy tưởng tượng mảng chạy ngược lại để lấy đầu vào là 64-bit chia dọc theo cạnh trên cùng và một số chia 32 bit, nói dọc theo cạnh bên phải của mảng. Sau đó, nó xuất ra thương hiệu 32 bit dọc theo cạnh dưới cùng (phần còn lại cần phải được tạo ra quá .. quên aboutit cho mo). Bây giờ đơn vị bên trái trên cùng trong mảng mất IN hai chữ số đầu của cổ tức từ phía trên cùng của mảng, chữ số trên cùng của số chia từ phía bên tay phải của mảng, và phát ra chữ số hàng đầu của DOWNWARDS thương vào mảng (và ra phía dưới) và phần còn lại RIGHTWARDS vào mảng.

Whew! Đó là chỉ cho đầu ra chữ số đầu tiên. Nó chỉ là khởi đầu. Fourier's thiên tài đã được nhìn thấy như thế nào người ta có thể ăn trong dư dư tích lũy để giữ cho đầu vào giới hạn chỉ ba (nói 8-bit) chữ số, và outut tại chỉ hai (nói 8-bit) chữ số cho mỗi đơn vị trong sửa đổi mảng nhân chạy ngược lại (mà chúng ta có thể gọi một mảng phân chia bây giờ).

Và tất nhiên, đó là cách chúng tôi có thể phân chia phần cứng, không yêu cầu mã vi mô, trong ALU của máy tính.

Ít nhất, tôi cho rằng phương pháp này được sử dụng trong đó microcode đã được sử dụng để mua thêm một vài tỷ bóng bán dẫn. Tôi không thuộc về nội thất của các CPU mới nhất, nhưng chúng có các bóng bán dẫn để đốt cháy.