Как компьютер умножает числа

В среду в 9:00 физический носитель файла DBFile1 был поврежден. Какие шаги вы предпримете для восстановления базы данных за отведенное время? Вы не можете создать резервную копию текущего журнала транзакций.

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

Основные моменты этой главы включают следующее:

Когда вы набираете клавиши на клавиатуре, ваш компьютер принимает двоичные значения, представляющие данные.

Код ASCII определяет двоичные шаблоны для каждого символа, представляемого компьютером.

Самые ранние компьютеры программировались с помощью проводов.

FORTRAN и COBOL многие годы были предпочтительными языками для науки и бизнеса.

На протяжении многих лет правительство предпочитало использовать ADA.

Хранение программ и данных

Когда вы печатаете на клавиатуре, как вы думаете, что происходит, когда вы нажимаете клавиши? Уходит ли буква A куда-то в память компьютера, когда вы нажимаете клавишу A? Так и должно быть, иначе компьютер никогда не сможет запомнить содержимое вашей программы. Компьютер хранит A, но не в том формате, в котором вы могли бы ожидать. Компьютер хранит только представление буквы A. Во всех смыслах буква A находится в памяти, но не выглядит так, как вы думаете.

Причина, по которой требуется восемь переключателей, заключается в том, что если бы их было меньше, то не хватило бы комбинаций включенных и выключенных состояний для представления всех возможных символов (прописных, строчных, цифр и специальных символов, таких как %, ^, и *).

Помните, что ваш компьютер — это не что иное, как тысячи выключателей, которые включают и выключают электричество. Каждый символ на вашем компьютере представлен комбинацией переключателей включения и выключения. Программисты обычно называют выключатель «1» (единица), а «выкл» — 0 (ноль). Поскольку эти переключатели имеют только два значения, программисты называют 0 и 1 двоичными цифрами или битами для краткости. Всего на каждый символ в вашем компьютере приходится восемь бит, и восемь бит известны как байт. Таким образом, для представления каждого символа памяти требуется восемь битов (восемь переключателей включения и выключения), и, следовательно, символ представляет собой байт.

Несколько лет назад кто-то записал различные комбинации восьми единиц и нулей от 00000000 до 11111111 и присвоил каждой из них уникальный символ. Таблица символов была стандартизирована и сегодня известна как Таблица ASCII (произносится как аск-и, поэтому, если вы не знаете-и, вы можете использовать ASCII). Таблица 3.1 показывает частичный список таблицы ASCII. ASCII расшифровывается как Американский стандартный код для обмена информацией.

Таблица 3.1. Значения ASCII представляют символы

Каждому из значений ASCII соответствует соответствующее десятичное число. Эти значения показаны справа от восьмибитных значений в таблице 3.1. Следовательно, даже если компьютер представляет символ ? как 00111111 (два выключателя с шестью включенными), вы можете с помощью программирования обратиться к этому значению ASCII как 63, и ваш компьютер будет знать, что вы имеете в виду 00111111. Одно из преимуществ языков программирования высокого уровня заключается в том, что они часто позволяют вам используйте более простые (для людей) десятичные значения, а язык программирования преобразует значение в восьмибитное двоичное значение, используемое внутри компьютера.

Как видно из значений ASCII в таблице 3.1, каждый символ в компьютере, будь то прописные и строчные буквы, и даже пробел, имеет свое собственное уникальное значение ASCII.Уникальный код ASCII — это единственный способ, с помощью которого компьютер может различать символы. Некоторые мейнфреймы используют аналогичную систему, которая называется таблица EBCDIC, произносится как eb-se-dik.

Вспомните внутреннее хранилище отдельных символов, описанное ранее в этом разделе. Когда вы нажимаете букву А, эта А не сохраняется в вашем компьютере; вместо этого сохраняется ASCII-значение A. Как видно из значений ASCII в предыдущей таблице, буква A представлена ​​как 01000001 (все восемь переключателей, кроме двух, выключены в каждом байте памяти, содержащем букву A).

Как показано на рис. 3.1, когда вы нажимаете букву A на клавиатуре, в память попадает не буква A, а значение ASCII 01000001. Компьютер сохраняет этот шаблон включения и выключения в этой ячейке памяти до тех пор, пока там остается буква А. Что касается вас, то в памяти буква А остается как буква А, но теперь вы точно знаете, что происходит. Если вы печатаете программу, которую только что набрали, и компьютер готов напечатать символ, хранящийся в этой ячейке памяти, центральный процессор компьютера отправляет код ASCII для буквы A на принтер. Непосредственно перед печатью принтер знает, что его вывод должен быть удобочитаемым для людей, поэтому он ищет 01000001 в своей собственной таблице ASCII и печатает букву А на бумаге. С того момента, как буква А покинула клавиатуру, и до момента, когда она была напечатана, это была вовсе не буква А, а просто комбинация восьми единиц и нулей, представляющая букву А.

Таблица ASCII не сильно отличается от других типов кодированных таблиц, о которых вы, возможно, слышали. Азбука Морзе представляет собой таблицу представлений букв алфавита. Вместо единиц и нулей код использует комбинации тире и точек для представления символов. Штрихи и точки обозначают длину радиосигналов, которые люди отправляют или принимают. Буквы SOS представлены ТОЧКА-ТОЧКА-ТОЧКА ТИРЕ-ТИРЕ-ТИРЕ ТОЧКА-ТОЧКА-ТОЧКА.

Я изучал сумматоры и пытался понять, как компьютеры умножают числа. Я не видел ничего похожего на сумматор, который работает для умножения, и единственный способ, который я мог придумать, - это перебирать число через сумматор множество раз, например, 5x3 будет 5 + 5 + 5. Но попытка сделать это с двумя числами, равными 10 15, на самом деле не сработает, тогда как мой телефон может сделать это мгновенно. Так как же они это делают?

Простой алгоритм работает, используя двоичное представление одного из чисел (это легко, потому что числа уже хранятся в двоичном формате внутри компьютера). Например, если b равно 00100011 в двоичном формате, то:

a * b = a * 00100011 = a * 00100000 + a * 00000010 + a * 00000001

Теперь умножение двоичного числа a на двоичное число вида 1000.…0 работает путем добавления нулей в конец a:

а * b = а00000 + а0 + а

А теперь у вас есть простое дополнение.

Хммм, это алгоритм, использующий двоичный код, не обязательно, что его использует современный ЦП. Примитивный множитель будет использовать что-то вроде алгоритма Бута, более современный будет использовать что-то вроде деревьев Уоллеса или множителя Дадда. И, конечно же, это целочисленные алгоритмы, для вычислений с плавающей запятой (или операций с плавающей запятой в целом) есть совершенно другая часть ЦП, предназначенная для той, которая использует совершенно другие методы.

Я не видел ничего похожего на сумматор, работающий на умножение,

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

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

Однако помните, что вычисления работают по основанию 2, а размер целого числа конечен. например, 32-битная машина сможет умножать только числа меньше 2 32. Таким образом, мы знаем, что в предложенном вами алгоритме потребуется 2 32 последовательных сложения, чтобы вычислить максимально возможное умножение.

Однако мы можем упростить. Поскольку целые числа имеют основание 2, любое умножение на 2 на самом деле является логическим сдвигом влево. т. е. все двоичные цифры сдвигаются влево на 1, а старший разряд становится равным 0. Используя это, мы можем упростить алгоритм последовательного сложения до

т.е. для каждого установленного бита в операнде 2 добавить операнд 1, сдвинутый влево на позицию установленного бита.это дает нам только 32 операции вместо 2 32.

Кроме того, если сложность проекта не является проблемой, все эти 32 операции могут выполняться параллельно в ALU, поэтому мы получаем огромное сложение из 32 целых чисел. конечно, это не рекомендуется, так как это пустая трата места на чипе.

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

Есть и другие способы реализовать это, и это очень интересная тема. Если вы хотите узнать больше, есть книга под названием «Организация и архитектура компьютерных систем» Джона Д. Карпинелли, которая углубляется в мир проектирования процессоров. Он предлагает множество отличных идей для индивидуального дизайна сердечника. Я очень рекомендую эту книгу и дешевую плату разработки Altera/Xilinx FPGA (лично у меня есть Altera DE1 для экспериментов).

P.S. Извиняюсь за плохие объяснения/примеры. Но если вы думаете, что это сбивает с толку, держитесь подальше от разделения. ха-ха.

Компьютеры превращают каждое число в двоичное. Числа, которые мы используем, выражены в базе 10. Каждые 10 единиц равняются 1 десятку, каждые 10 десятков равняются 1 сотне и так далее. В двоичном формате вы поднимаетесь на единицу каждые 2 числа. Таким образом, 2 единицы равны 1 двойке, 2 двойки равны 1 4 и так далее. Например, число 9 будет 1001 в двоичном формате: 1 единица, 0 двоек, 0 четверок и 1 восьмерка. 1 + 8 = 9. Компьютеры делают это, потому что проще проектировать схемы, которые имеют только значения 1 или 0, чем схемы с 10 отдельными значениями каждая.

Дополнение

В компьютерах запрограммированы основные математические операции, такие как сложение и вычитание. Добавление в двоичном формате чрезвычайно просто. Если у вас есть 2 числа со значением 1, вы сохраняете 0 и переносите 1. В противном случае вы записываете большее из двух чисел в этот слот. Например, если вы сложите 5 + 4, вы получите: 0101 + 0100. В первом слоте у вас есть 1 + 0, поэтому вы сохраняете большее число, 1. Во втором слоте у вас есть два 0, поэтому вы сохраняете 0 (поскольку оба числа одинаковы. В третьем слоте у вас есть две единицы, поэтому вы сохраняете 0 и несете 1. В итоге вы получите число 1001 или 9.

Умножение.

Компьютеры используют длинное умножение, но в двоичном формате. Если компьютер умножает число на 1, он возвращает 1. Это гораздо более простая система, чем 10-кратная, хотя и требует больше шагов. Например, в системе счисления 10 задача 8 * 9 — это простая одношаговая задача без длинного умножения. Однако в двоичном формате каждое число состоит из 4 цифр, а решение состоит из 7 цифр!

Вычитание

Вычитание выполняется в два этапа. Вместо того, чтобы вычитать число, двоичный компьютер добавляет его дополнение, число с единицами, где исходное число имеет нули, и нулями, где исходное число имеет единицы. Например, тогда как 4 — это 0100 в двоичном формате, отрицательное 4 — это 1011. Таким образом, для 7 — 4 мы получаем 0111 + 1011 = 10010. Затем число в самой левой части сдвигается вправо, что дает нам 0011 = 3.< /p>

Разбивая большие числа на более мелкие, исследователи переписали фундаментальное математическое ограничение скорости.

Читать позже

Мэнсин Ли для журнала Quanta

Кевин Хартнетт

Четыре тысячи лет назад вавилоняне изобрели умножение. В прошлом месяце математики усовершенствовали его.

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

"В основном все думают, что метод, который вы изучаете в школе, является лучшим, но на самом деле это активная область исследований", – сказал Йорис ван дер Хувен, математик из Французского национального центра научных исследований и один из соавторы.

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

"В физике есть важные константы, такие как скорость света, которые позволяют описывать всевозможные явления", – сказал ван дер Хувен.«Если вы хотите узнать, насколько быстро компьютеры могут решать определенные математические задачи, умножение целых чисел станет своего рода базовым строительным кирпичиком, относительно которого вы можете выразить такие скорости».

Большинство людей учатся умножать одинаково. Мы складываем два числа, умножаем каждую цифру нижнего числа на каждую цифру верхнего числа и делаем сложение в конце. Если вы умножаете два двузначных числа, в конечном итоге вы выполняете четыре меньших умножения, чтобы получить конечный результат.

Метод начальной школы или «переноска» требует около n 2 шагов, где n – количество цифр в каждом из чисел, которые вы умножаете. Таким образом, для трехзначных чисел требуется девять умножений, а для 100-значных чисел требуется 10 000 умножений.

Метод переноса хорошо работает для чисел, состоящих всего из нескольких цифр, но не работает, когда мы умножаем числа с миллионами или миллиардами цифр (именно это делают компьютеры для точного вычисления числа пи или в ходе глобального поиска большие простые числа). Чтобы умножить два числа с 1 миллиардом цифр, требуется 1 миллиард в квадрате, или 10 18 , умножений, на которые у современного компьютера ушло бы примерно 30 лет.

На протяжении тысячелетий считалось, что не существует более быстрого способа умножения. Затем, в 1960 году, 23-летний русский математик Анатолий Карацуба прошел семинар под руководством Андрея Колмогорова, одного из величайших математиков ХХ века. Колмогоров утверждал, что не существует общей процедуры умножения, требующей менее n 2 шагов. Карацуба подумал, что есть, и через неделю поисков нашел.

Метод Карацубы заключается в разбиении цифр числа и их повторном объединении новым способом, который позволяет заменить большое количество операций умножения небольшим количеством сложений и вычитаний. Этот метод экономит время, поскольку сложение занимает всего 2n шагов, а не n 2 шага.

"Кроме того, вы делаете это на год раньше в школе, потому что это намного проще, вы можете сделать это за линейное время, почти так же быстро, как читать числа справа налево", – сказал Мартин Фюрер, математик из штата Пенсильвания. университета, который в 2007 году создал самый быстрый на тот момент алгоритм умножения.

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

"Некоторые операции умножения можно превратить в сложения, и идея заключается в том, что на компьютерах сложения будут выполняться быстрее", – говорит Дэвид Харви, математик из Университета Нового Южного Уэльса и соавтор новой статьи.< /p>

Метод Карацубы позволил умножать числа, используя только n 1,58 однозначных умножений. Затем в 1971 году Арнольд Шенхаге и Фолькер Штрассен опубликовали метод, способный умножать большие числа за n × log n × log(log n) мультипликативных шагов. , где log n — логарифм n. Для двух миллиардных чисел метод Карацубы потребует около 165 триллионов дополнительных шагов.

Метод Шенхаге и Штрассена, с помощью которого компьютеры умножают огромные числа, имел еще два важных долгосрочных последствия. Во-первых, он представил использование метода из области обработки сигналов, называемого быстрым преобразованием Фурье. С тех пор этот метод стал основой для всех алгоритмов быстрого умножения.

Во-вторых, в той же статье Шенхаге и Штрассен предположили, что должен существовать еще более быстрый алгоритм, чем тот, который они нашли, — метод, который требует только n × log n операций с однозначными числами — и что такой алгоритм будет самым быстрым из возможных. Их предположение было основано на догадке, что такая фундаментальная операция, как умножение, должна иметь более элегантный предел, чем n × log n × log(log n).

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

Неуклюжий метод Шёнхаге и Штрассена n × log n × log(log n) просуществовал 36 лет. В 2007 году Фюрер победил, и шлюзы открылись. За последнее десятилетие математики последовательно находили все более быстрые алгоритмы умножения, каждый из которых приближался к n × log n, не достигая его. А в прошлом месяце туда добрались Харви и ван дер Хувен.

Их метод является усовершенствованием основной работы, которая была сделана до них.Он разделяет цифры, использует улучшенную версию быстрого преобразования Фурье и использует преимущества других достижений, сделанных за последние сорок лет. «Мы используем [быстрое преобразование Фурье] гораздо более агрессивно, используем его несколько раз вместо одного раза и заменяем еще больше умножений сложениями и вычитаниями», — сказал ван дер Хувен.

Алгоритм Харви и ван дер Хувена доказывает, что умножение можно выполнить за n × log n шагов. Однако это не доказывает, что нет более быстрого способа сделать это. Гораздо труднее установить, что это наилучший из возможных подходов. В конце февраля группа ученых-компьютерщиков из Орхусского университета опубликовала статью, в которой утверждала, что если другая недоказанная гипотеза также верна, то это действительно самый быстрый способ умножения.

И хотя новый алгоритм важен теоретически, на практике он мало что изменит, поскольку он лишь незначительно лучше, чем уже используемые алгоритмы. «Лучшее, на что мы можем надеяться, это то, что мы будем в три раза быстрее», — сказал ван дер Хувен. «Это не будет эффектно».

Кроме того, изменился дизайн компьютерного оборудования. Два десятилетия назад компьютеры выполняли сложение гораздо быстрее, чем умножение. Разрыв в скорости между умножением и сложением за последние 20 лет значительно сократился до такой степени, что умножение может быть даже быстрее, чем сложение в некоторых архитектурах микросхем. С некоторым аппаратным обеспечением «вы могли бы выполнять сложение быстрее, задав компьютеру задачу на умножение, что просто безумие», — сказал Харви.

Оборудование меняется со временем, но лучшие в своем классе алгоритмы вечны. Независимо от того, как будут выглядеть компьютеры в будущем, алгоритм Харви и ван дер Хувена по-прежнему будет наиболее эффективным способом умножения.

Этим летом в центре внимания стояла простая математическая задача: 8 ÷ 2(2 + 2) = ? Если вы сначала разделите 8 на 2, вы получите 16, но если вы сначала умножите 2 на (2 + 2), вы получите 1. Итак, какой ответ правильный? Конфликт разгорелся настолько, что попал на страницы The New York Times. И, как видно из раздела комментариев, даже профессионального математика, занимающегося этим вопросом, было недостаточно, чтобы объединить две стороны.

Проблема здесь просто в том, как мы интерпретируем символ деления. Означает ли ÷ деление на одно число сразу после него или на все после него? Это не слишком беспокоит большинство математиков, поскольку они не очень часто используют этот символ. Попросите их решить эту задачу, и они, вероятно, просто превратят все это в задачу на умножение: как только вы решите написать ее как

$латекс 8 \times \frac(2+2)$ или $латекс 8 \times \frac$,

Двусмысленность ушла, и ответ ясен. Как вопрос на умножение, это не особенно интересно.

Но один вопрос об умножении, который математики находят интересным, может вас удивить: как лучше всего умножать?

Предположим, вас попросили умножить 25 на 63. Если вы похожи на большинство людей, вы, вероятно, потянулись бы к калькулятору. Но если бы вы не смогли его найти, вы, вероятно, воспользовались бы стандартным алгоритмом, который выучили в начальной школе, умножив каждую цифру одного числа на каждую цифру другого, а затем сложив произведения:

Если вы умеете считать в уме, вы можете применить другой подход, используя свойство дистрибутивности, чтобы упростить вычисление ответа в уме:

25 × 63 = 25 × (60 + 3) = 25 × 60 + 25 × 3 = 1500 + 75 = 1575.

Оба варианта дают нам правильный ответ, но один способ лучше другого? Возможно, это просто личный выбор. Но есть по крайней мере один способ объективно сравнить методы умножения: Эффективность. Хотя эффективность может означать разные вещи для разных людей в разных контекстах, давайте подумаем об этом с точки зрения компьютера. Сколько времени потребуется компьютеру, чтобы выполнить умножение?

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

Давайте вернемся к нашему примеру 25 × 63 с учетом эффективности.Чтобы вычислить 25 × 63 с помощью стандартного алгоритма, нам пришлось выполнить четыре небольших умножения: 3 × 5, 3 × 2, 6 × 5 и 6 × 2. Малые умножения дали нам наши строки 15, 60, 300 и 1200, что в сумме составило 1575. Важно отметить, что когда мы применяем стандартный алгоритм, 3 × 2 на самом деле 3 × 2 × 10 = 60, 6 × 5 на самом деле 6 × 10 × 5 = 300, а 6 × 2 на самом деле 6 × 10 × 2 × 10 = 1200. Однако мы не считаем умножение на 10 эффективностью нашего алгоритма, так как компьютеру так же легко умножить на 10, как и нам — мы просто сдвигаем цифры. То же самое относится и к умножению на 100, 1000 и т. д.

Таким образом, наше выполнение стандартного алгоритма для вычисления 25 × 63 требует четырех небольших умножений и некоторых дополнений. Как насчет дистрибутивного подхода?

25 × 63 = 25 × (60 + 3) = 25 × 60 + 25 × 3 = 1500 + 75 = 1575.

При вычислении 25 × 60 нам нужно умножить 6 и на 2, и на 5, а при вычислении 25 × 3 нам нужно умножить 3 и на 2, и на 5. Это по-прежнему четыре маленьких умножения. Поскольку каждый метод требует четырех небольших умножений, по нашим простым меркам эти два метода примерно эквивалентны с точки зрения эффективности. Поэтому не должно вызывать удивления тот факт, что стандартный алгоритм на самом деле является всего лишь приложением свойства распределения. Давайте разберемся, почему.

Подумайте о перемножении двух произвольных двузначных чисел «AB» и «CD». Здесь я буду использовать одинарные кавычки для обозначения числа, описываемого его цифрами: «AB» — это число, в котором цифра десятков равна A, а цифра единиц — B. . Другими словами, «AB» — это число 10A + B. Итак, если «AB» — это число 25, A = 2 и B = 5. И если «CD' — число 63, C = 6 и D = 3.

Чтобы найти произведение 'AB' и 'CD', нам нужно умножить два числа 10A + < em>B и 10C + D. Мы можем сделать это, дважды используя свойство distributive:

Вот как это будет выглядеть, если мы подставим исходные числа:

25 × 63 = (10 × 2 + 5) × (10 × 6 + 3)
= 100 (2 × 6) + 10 (2 × 3) + 10 (5 × 6) + 5 × 3
= 1200 + 60 + 300 + 15
= 1575.

Обратите внимание, что все компоненты нашего приложения стандартного алгоритма присутствуют, просто организованы по-другому. И с точки зрения эффективности мы видим точно такие же небольшие умножения, выполняемые в обоих: 3 × 5, 3 × 2, 6 × 5 и 6 × 2. Эти два метода делают по сути одно и то же. В любом случае нам нужно умножить A × C, A × D, B × C и B × D. Эти четыре небольших умножения, по-видимому, устанавливают предел эффективности умножения.

Но в 1960 году русский математик Анатолий Карацуба нашел новый предел, используя собственное применение закона распределения, чтобы найти более эффективный способ умножения. Карацуба заметил, что все четыре небольших умножения, необходимые для вычисления произведения «AB» и «CD», появляются, когда мы умножаем суммы их цифр, A + B и C + D: