Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Рекурсивный алгоритм умноженияПреимущество приведенных в данном параграфе программ заключается в том, что их текст является коротким и «прозрачным», а, следовательно, отладка подобной программы не составляет особого труда. Однако существует и более эффективный рекурсивный алгоритм умножения. Пусть х и у — два n-разрядных десятичных числа и пусть n — некоторая натуральная степень числа 2. Разобьем числа х и у на 2 равные группы, обозначив левые (старшие) цифры чисел х1 и yl соответственно, а правые (младшие) — х2 и у2. Тогда
x×y = (x1×10n/2 + x2)(yl×10n/2 + y2) = = x1× yl×10n + (x1× y2+x2×yl)×10n/2 + x2×y2
То есть умножение двух чисел, каждое из которых имеет не более n разрядов, мы свели к трем действиям умножения чисел в два раза меньшей длины, сдвигу результатов такого умножения на соответствующее число разрядов влево и сложению длинных чисел. Однако, числа (x1+x2)и (у1+y2), вообще говоря, имеют n/2+1 разряд и поэтому их произведение нельзя вычислить непосредственным рекурсивным применением нашего алгоритма. Поэтому, чтобы сделать алгоритм универсальным, перепишем его для произвольного числа n, обозначив буквой т остаток от деления п на 2:
х×у = (x1×10[n/2]+m + х2)(у1×10[n/2]+m + у2) = = x1×y1×10n+m + (x1×y2 + x2×y1)×10[n/2]+m + х2×у2 = = x1×y1×10n+m + ((x1+x2)(y1+y2)-x1×y1 - х2×y2)×10[n/2]+m + х2×у2
Теперь возможна рекурсивная реализация данного алгоритма. Если же при некотором рекурсивном вызове п окажется меньше пяти, то умножение х и у уже можно произвести непосредственно в рамках четырехбайтного целого типа. Доказано, что с ростом п такой алгоритм является асимптотически более быстрым, нежели умножение «столбиком», однако его реализация более громоздкая и в ней приходится использовать несколько дополнительных массивов, что уменьшает максимальную длину чисел, для которых этот алгоритм может быть применен.
|