|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[206] сложения с запоминанием переносов для хранения промежуточных результатов: на каждом шаге к сумме и + v надо добавить очередное частичное произведение, т. е. надо сложить три числа - и получить ответ в виде суммы двух.) Шаг алгоритма включает сдвиги а и Ь (как и в медленном алгоритме), а также изменение и и v. Если = 1, то = parity(Ъ\\ v) при i = 0,1, 2,... , 2га - 1 и (j+i) ( majority(b\3}1, uf}x, uj-i) если 1 i 2га - 1 У0 если г = О Если же а = 0, то М-7) заменяется на 0: и\3+1) = parity (0, uf\ v\3)) при i = 0,1, 2,... , 2га - 1 и (j+i) j majority, uf}x, uj-i) если 1 г 2га - 1 [0 если г = 0 Всего производится 2га - 1 шаг, причём при j га имеем а) = 0 и и(Л = а • Ь. С этого момента сумма и + и не меняется, а лишь перераспределяется между и и и. Наконец, и становится равным 0 и сумма оказывается в и: поскольку t>(2n 1) = 0 (см. упражнение 29-4.3), и(2п 1) = а • Ь. (Таким образом, начиная с га-го шага по существу происходит сложение двух чисел.) Так как каждый шаг занимает время 0(1), общее время работы составляет (2га - 1)0(1) = 0(га). Размер схемы по-прежнему равен 0(га). Упражнения 29.4-1 Используя русский народный алгоритм, перемножьте а = (101101) и Ь = (011110). Как это выглядит в двоичной и десятичной системах? 29.4-2 Докажите инварианты (29.6) и (29.7). 29.4-3 Докажите, что при быстрой реализации одномерного умножителя г/2""-1) = 0. 29.4-4 Объясните, почему матричный умножитель можно рассматривать как развёрнутый (в пространстве вместо времени) вариант быстрого одномерного умножителя. 29.4-5 Пусть на вход поступают значения х\,Х2, (по одному за такт), а в нашем распоряжении имеется функциональные элементы, вычисляющие максимум своих двух входов, и регистры. Для фиксированного га постройте схему размера О (га), которая за время 0(1) вычисляет yt = max Xi (максимум из га наиболее свежих элементов) 29.4-6* (Продолжение) То же самое, если есть только O(lgra) элементов «максимум». 29.5. Задачи 29-1. Схемы для деления Деление можно свести к сложению и умножению с помощью метода Ньютона (Newton iteration). Ясно, что достаточно построить схему для вычисления обратного элемента (так как умножитель у нас уже есть). Пусть фиксировано число ж, и мы хотим вычислить 1/ж. Рассмотрим последовательность уо, У\, У2, , Для которой у1+1 = 2уг - xyf Пусть ж - га-значная двоичная дробь, 1/2 ж 1. Мы хотим вычислить 1/ж с точностью до га знаков (вообще-то 1/ж скорее всего будет бесконечной десятчиной дробью). a.Пусть \yi - 1/ж е для некоторого е > 0. Докажите, что \уг + 1 - 1/ж £2. b.Укажите начальное значение усь Для которого \yk - l/x\ 2 при всех к 0. Какое к нужно взять, чтобы получить ответ с точностью до п знаков? c.Постройте схему, вычисляющую по га-разрядному числу ж число 1/ж с точностью до га знаков за время 0(lg2ra). Попытайтесь добиться размера 0(ra2lgra). [Витя: кажется, beat означает лучшую чем - но надо проверить, проявив little cleverness] 29-2. Пропозициональные формулы для симметричных булевых функций. Функция га аргументов f(xi, ж2,... , хп) называется симметричной (symmetric), если для любой перестановки тг чисел 1,2,... , га f{xli x2i • • • i Хп) - У (Ж7г(1) ? xtt(2)i • • • 1 х-к(п) Оказывается, любая симметричная булева функция га аргументов (аргументы и значение принадлежит {0,1}) может быть выражена пропозициональной формулой, т. е. формулой, содержащей только Ж1,... ,хп, скобки и знаки операций ->, А и V, причём длина этой формулы полиномиально зависит от га. Для начала мы построим для симметричной функции схему глубины О (lgra), а затем и искомую формулу. Все схемы предполагаются составленными из элементов AND, OR и NOT. a.Постройте схему глубины О (lgra) для для функции большинства (majority function) Г 1 если х\ + Ж2 + ... + хп > га/2 majority,, (ж 1,... , хп) = < { О иначе (Указание: постройте дерево сумматоров.) b.Пусть существует схема глубины d, вычисляющая данную булеву функцию /. Покажите, что тогда для / существует формула длины 0(2d) (в частности, для функции большинства существует формула полиномиальной длины). c.Покажите, что симметричная логическая функция может быть записана как функция суммы своих аргументов. d.Докажите, что для каждой симметричной булевой функции га аргументов существует схема глубины О (lgra). e.Докажите, что для любой симметричной булевой функции га аргументов существует формула, длина которой ограничена полиномом от га (единым для всех функций) 29.6. Комментарии Большинство книг по арифметическим схемам обращают больше внимание на практивескую реализацию схем, чем на лежащие в их основе алгоритмы. Книга Сэведжа [173] - одна из немногих книг, посвященная алгоритмическим вопросам. Легко читаются книги Каванага [39] и Ванга [108] более инженерного содержания. Среди других хороших книг можно назвать книги Хилла и Петерсона [96], а также Кохави [126] (с уклоном в теорию формальных языков). История арифметических алгоритмов изложена в книге Айкена и Хоппера [7]. Сложение столбикоми появилось не позже абака (которому более 5000 лет). Первое механическое устройство, его реализующее, было создано Б. Паскалем в 1642 году. Вычислительное устройство, позволяющее умножать повторными сложениями, было разработано независимо С. Морландом (S. Morland, 1666) и Г. В. Лейбницем (1671). «Русский народный алгоритм», как пишет Кнут [22], был известен египетским математикам ещё в 1800 г. до и. э. Идея трёх возможных типов переноса использовалась в релейной вычислительной машине, построенной в Гарварде в 40-е годы нашего века [180]. Алгоритм с предвычислением переносов одними из первых описали Вайнбергер и Смит [199], но их алгоритм требовал элементов с большим числом входов. Алгоритм сложения |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||