|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[11] Как вычисляются квадратные корни? Наиболее часто применяется Ньютонов метод последовательных приближений, который основан на том, что имея некоторое неточное значение y для квадратного корня из числа x, мы можем с помощью простой манипуляции получить более точное значение (более близкое к настоящему квадратному корню), если возьмем среднее между y и x/y.21 Например, мы можем вычислить квадратный корень из 2 следующим образом: предположим, что начальное приближение равно 1. Приближение Частное x/y 1 1.5 1.4167 1.4142 2 Т ~ 2 L5 1.5 2 1.4167 1.3333 1.4118 Среднее 2 + 1 2 1.3333+ 1.5 2 1.4167+1.4118 2 1.4167 1.4142 Продолжая этот процесс, мы получаем все более точные приближения к квадратному корню. Теперь формализуем этот процесс в терминах процедур. Начнем с подкоренного числа и какого-то значения приближения. Если приближение достаточно хорошо подходит для наших целей, то процесс закончен; если нет, мы должны повторить его с улучшенным значением приближения. Запишем эту базовую стратегию в виде процедуры: (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) Значение приближения улучшается с помощью взятия среднего между ним и частным подкоренного числа и старого значения приближения: (define (improve guess x) (average guess (/ x guess))) 2 где (define (average x y) (/ (+ x y) 2)) которых строятся программы) к декларативным (которые можно использовать для рассуждений). Связана с этим и такая важная область современных исследований по проектированию языков программирования, как исследование так называемых языков сверхвысокого уровня, в которых программирование на самом деле происходит в терминах декларативных утверждений. Идея состоит в том, чтобы сделать интерпретаторы настолько умными, чтобы, получая от программиста знание типа «что такое», они были бы способны самостоятельно породить знание типа «как». В общем случае это сделать невозможно, но есть важные области, где удалось достичь прогресса. Мы вернемся к этой идее в главе 4. 21 На самом деле алгоритм нахождения квадратного корня представляет собой частный случай метода Ньютона, который является общим методом нахождения корней уравнений. Собственно алгоритм нахождения квадратного корня был разработан Героном Александрийским в первом веке н.э. Мы увидим, как выразить общий метод Ньютона в виде процедуры на Лиспе, в разделе 1.3.4. Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение. Следующий вариант сойдет для иллюстрации, но на самом деле это не очень хороший тест. (См. упражнение 1.7.) Идея состоит в том, чтобы улучшать приближения до тех пор, пока его квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска (здесь 0.001):22 (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) Наконец, нужно с чего-то начинать. Например, мы можем для начала предполагать, что квадратный корень любого числа равен 1: 23 (define (sqrt x) (sqrt-iter 1.0 x)) Если мы введем эти определения в интерпретатор, мы сможем использовать sqrt как любую другую процедуру: (sqrt 9) 3.00009155413138 (sqrt (+ 100 37)) 11.704699917758145 (sqrt (+ (sqrt 2) (sqrt 3))) 1.7739279023207892 (square (sqrt 1000)) 1000.000369924366 Программа sqrt показывает также, что того простого процедурного языка, который мы описали до сих пор, достаточно, чтобы написать любую чисто вычислительную программу, которую можно было бы написать, скажем, на Си или Паскале. Это может показаться удивительным, поскольку в наш язык мы не включили никаких итеративных (циклических) конструкций, указывающих компьютеру, что нужно производить некое действие несколько раз. Sqrt-iter, с другой стороны, показывает, как можно выразить итерацию, не имея никакого специального конструкта, кроме обыкновенной способности вызвать процеду- 24 22Обычно мы будем давать предикатам имена, заканчивающиеся знаком вопроса, чтобы было проще запомнить, что это предикаты. Это не более чем стилистическое соглашение. С точки зрения интерпретатора, вопросительный знак - обыкновенный символ. 23Обратите внимание, что мы записываем начальное приближение как 1.0, а не как 1.Во многих реализациях Лиспа здесь не будет никакой разницы. Однако интерпретатор MIT Scheme отличает точные целые числа от десятичных значений, и при делении двух целых получается не десятичная дробь, а рациональное число. Например, поделив 10/6, получим 5/3, а поделив 10.0/6.0, получим 1.6666666666666667. (Мы увидим, как реализовать арифметические операции над рациональными числами, в разделе 2.1.1.) Если в нашей программе квадратного корня мы начнем с начального приближения 1, а x будет точным целым числом, все последующие значения, получаемые при вычислении квадратного корня, будут не десятичными дробями, а рациональными числами. Поскольку при смешанных операциях над десятичными дробями и рациональными числами всегда получаются десятичные дроби, то начав со значения 1.0, все прочие мы получим в виде десятичных дробей. 24Читателям, которых заботят вопросы эффективности, связанные с использованием вызовов процедур для итерации, следует обратить внимание на замечания о «хвостовой рекурсии» в разделе 1.2.1. Упражнение 1.6. Лиза П. Хакер не понимает, почему if должна быть особой формой. «Почему нельзя просто определить ее как обычную процедуру с помощью cond?» - спрашивает она. Лизина подруга Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версию if: (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) Ева показывает Лизе новую программу: (new-if (= 2 3) 0 5) 5 (new-if (= 1 1) 0 5) 0 Обрадованная Лиза переписывает через new-if программу вычисления квадратного корня: (define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратных корней? Объясните. Упражнение 1.7. Проверка good-enough?, которую мы использовали для вычисления квадратных корней, будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел. Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативный подход к реализации good-enough? состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение. Верно ли, что на больших и маленьких числах она работает лучше? Упражнение 1.8. Метод Ньютона для кубических корней основан на том, что если y является приближением к кубическому корню из x, то мы можем получить лучшее приближение по формуле х/у2 + 2у 3 С помощью этой формулы напишите процедуру вычисления кубического корня, подобную процедуре для квадратного корня. (В разделе 1.3.4 мы увидим, что можно реализовать общий метод Ньютона как абстракцию этих процедур для квадратного и кубического корня.) |
Среды: 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 | ||