Какая логика стоит за алгоритмом деления Фурье?

Question

из Википедии: деление Фурье .

Вот скриншот того же самого: ( просмотр в полном разрешении )

Какова логика этого алгоритма?

Я знаю, что это можно использовать для деления очень больших чисел, но как именно это работает?

Answer 1

это, кажется, умное преобразование алгоритма длинного деления. Кажется, что умными частями является то, что они используют только операцию деления для первой «цифры», a1, и избегают необходимости использовать другие a (x) таким же образом, применяя их на следующем шаге, вычитая их произведение (против частного отношения) из промежуточного остатка.

То, что это действительно может быть сделано и что оно всегда работает, возможно, связано с тем, что «цифры» (в данном случае база 100) не являются реальными цифрами и могут на законных основаниях принимать значения, которые больше, чем их база (т.е. более 100) и даже меньше нуля. Это обеспечивает большую гибкость во времени применения каждой «цифры» к операции, как, например, откладывание применения вторичных цифр делителя (a (x> 1)) до тех пор, пока частичное частное не будет создано из деление предыдущего шага на (1), что, в свою очередь, позволяет применять их как вычитание продукта, а не как операцию деления.

Answer 2

Это чрезвычайно умный алгоритм. Я не могу себе представить, как Э.Ф. удалось получить от него информацию, поскольку отношение к текущей ситуации чрезвычайно трудно увидеть, даже если вы знаете, что оно существует. По моему мнению, он формализовал метод, который он использовал, чтобы сделать разделение от руки - он, должно быть, сделал огромное количество вычислений вручную в эпоху, предшествующую цифровым калькуляторам, и он, вероятно, предпочел быть точным, чем использовать правило скольжения, просто чтобы быть уверенным.

Это правда, что смутно можно увидеть схему метода в начале стандартного алгоритма длинного деления, но это единственная подсказка. Вы можете долго и усердно искать это повторение, не видя его. Вовлечено так много чисел - это сбивает с толку, глядя на отношения.

Существует еще одна интуиция, которую можно извлечь из изучения потока данных в стандартном алгоритме умножения. Если вы напишите это на компьютерном оборудовании, вы увидите, что квадратный массив 8-битных мультипликативных единиц берет два 32-битных числа, расположенных вдоль их нижней и правой сторон, и перемещает данные вверх и влево, выходя из верхнего края поля. массив в 64-битном ответе. Самый верхний левый блок доставляет две верхние (8-битные) цифры продукта, используя верхние цифры мультипликаторов, и переносит их из остальной части массива вправо. ОК? Хорошо, представьте, что массив работает в обратном порядке, чтобы в качестве входных данных взять 64-разрядную делитель по верхнему краю и 32-разрядный делитель, скажем, по правому краю массива. Затем он выводит 32-битный фактор по нижнему краю (остаток должен быть сгенерирован тоже .. забудьте об этом для mo). Теперь самая верхняя левая единица в массиве принимает две верхние цифры делимого из верхней части массива, верхнюю цифру делителя с правой стороны массива и испускает верхнюю цифру частного DOWNWARDS массив (и из нижней части) и остаток ВПРАВО в массив.

Уф! Это было только для выхода первой цифры. Это только начало. Гениальность Фурье заключалась в том, чтобы увидеть, как можно вводить накопительные остатки, чтобы ограничить входные данные только тремя (скажем, 8-разрядными) цифрами, а выход - только двумя (скажем, 8-разрядными) цифрами для каждой единицы в модифицированном мультипликативный массив работает в обратном порядке (который мы можем теперь назвать массивом деления).

И, конечно, именно так мы можем проводить аппаратное деление без микрокода в компьютерном ALU.

По крайней мере, я предполагаю, что этот метод используется, когда микрокод был исключен в пользу еще нескольких миллиардов транзисторов. Я не знаком с внутренностью последних процессоров, но у них есть транзисторы для записи.