Арифметика местоположения

Арифметика местоположения (лат. arithmeticae localis ) — это аддитивные (непозиционные) двоичные системы счисления , которые Джон Нейпир исследовал как метод вычислений в своем трактате «Рабдология» (1617), как в символическом виде, так и на сетке, напоминающей шахматную доску .

система счисления фактически является непозиционной . Терминология Нэпьера, основанная на использовании позиций фишек на доске для представления чисел, потенциально вводит в заблуждение, поскольку в современном словаре

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

Однако при воспроизведении на доске этот новый метод не требовал мысленных вычислений методом проб и ошибок или сложного запоминания переноса (в отличие от вычислений по основанию 10). Он был настолько доволен своим открытием, что сказал в предисловии:

его можно было бы назвать скорее развлечением, чем трудом, поскольку он выполняет сложение, вычитание, умножение, деление и извлечение квадратных корней исключительно путем перемещения счетчиков с места на место. ^[1]

Цифры местоположения

Двоичная система счисления еще не была стандартизирована, поэтому Нэпьер использовал то, что он называл цифрами местоположения для представления двоичных чисел . Система Нейпира использует знаково-значительную запись для представления чисел; он использует последовательные буквы латинского алфавита для обозначения последовательных степеней двойки: a = 2. ⁰ = 1, б = 2 ¹ = 2, с = 2 ² = 4, д = 2 ³ = 8 и = 2 ⁴ = 16 и так далее.

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

87 = 1 + 2 + 4 + 16 + 64 = 2 ⁰ + 2 ¹ + 2 ² + 2 ⁴ + 2 ⁶ = абсцег

Используя обратный процесс, цифру местоположения можно преобразовать в другую систему счисления. Например, при преобразовании в десятичное число:

абдгкл = 2 ⁰ + 2 ¹ + 2 ³ + 2 ⁶ + 2 ¹⁰ + 2 ¹¹ = 1 + 2 + 8 + 64 + 1024 + 2048 = 3147

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

Сокращенная и расширенная форма

Как и в любой системе счисления, использующей обозначение знака (но не в системе, использующей позиционное обозначение ), цифры (буквы) могут повторяться так, что несколько цифр могут представлять одно число. Например:

абвв = акк = объявление = 9

Кроме того, порядок цифр не имеет значения. Например:

abbc = bbca = bcba = ... = 9

Поскольку каждая цифра в цифре местоположения представляет собой удвоенное значение ее следующей младшей цифры, замена любых двух вхождений одной и той же цифры на одну из следующих по старшинству цифр не меняет числовое значение цифры. Таким образом, повторное применение правил замены aa → b , bb → c , cc → d и т. д. к номеру местоположения удаляет все повторяющиеся цифры из этого числа.

Нэпьер назвал это аббревиатурой процесса , а полученную в результате цифру местоположения - сокращенной формой этой цифры; он назвал числительные, содержащие повторяющиеся цифры, расширенными формами . Каждое число может быть представлено в уникальной сокращенной форме, независимо от порядка его цифр (например, abc , bca , cba и т. д. все представляют число 7).

Арифметика

Добавление

Цифры местоположения позволяют использовать простой и понятный алгоритм сложения:

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

Например, чтобы сложить 157 = acdeh и 230 = bcfgh , соедините цифры последовательно:

acdeh + bcfgh → acdehbcfgh

переставьте цифры предыдущего результата (поскольку цифры acdehbcfgh расположены не в порядке возрастания):

acdehbcfgh → abccdefghh

и сократите предыдущий результат:

abccdefghh → abddefghh → abeefghhh → abffghh → abgghh → abhhh → abhi

Конечный результат abhi равен 387 ( abhi = 2 ⁰ + 2 ¹ + 2 ⁷ + 2 ⁸ = 1 + 2 + 128 + 256 = 387); тот же результат достигается путем сложения 157 и 230 в десятичной системе счисления.

Вычитание

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

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

Несколько примеров показывают, что это проще, чем кажется:

• Вычтите 5 = ac из 77 = acdg :

акдг - ак = ак дг = дг = 8+64 = 72.

• Вычтите 3 = ab из 77 = acdg :

акдг - аб = аббдг - аб = аб бдг = бдг = 2+8+64 = 74.

• Вычтите 7 = abc из 77 = acdg :

acdg - abc = abbccg - abc = ab b c cg = bcg = 2+4+64 = 70.

Удвоение, деление пополам, нечетное и четное

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

Удвоение осуществляется путем прибавления числа к самому себе, что означает удвоение каждой его цифры. Это дает расширенную форму, которую при необходимости необходимо сокращать. Эту операцию можно выполнить за один шаг, заменив каждую цифру числа на следующую большую цифру. Например, дубль a — это b , дубль b — c , дубль ab — bc , дубль acfg — bdgh и т. д.

Точно так же умножение на степень двойки — это просто перевод цифр. умножение на c Например, = 4 означает преобразование цифр a → c , b → d , c → e ,...

Уполовинивание — это процесс, обратный удвоению: каждая цифра заменяется следующей меньшей цифрой. Например, половина bdgh — это acfg .

Сразу видно, что это возможно только в том случае, если число, которое нужно разделить пополам, не содержит a (или, если число расширено, нечетное число a s). Другими словами, сокращенная цифра является нечетной, если она содержит букву « а» , и даже если она не содержит.

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

Умножение

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

Умножение однозначного числа на другое однозначное число — простой процесс. Поскольку все буквы обозначают степень двойки, умножение цифр аналогично сложению их показателей. Это также можно рассматривать как поиск индекса одной цифры в алфавите ( a = 0, b = 1, ...) и увеличение другой цифры на эту сумму в терминах алфавита ( b + 2 => d ). .

Например, умножьте 4 = c на 16 = e

в * е = 2^2 * 2^4 = 2^6 = г

или...

AlphabetIndex ( c ) = 2, поэтому... e => f => g

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

Например, умножьте 238 = bcdfgh на 13 = acd.

а	bcdfgh
с	Defhj
д	Эфгык

Результатом является сумма в правом столбце bcdfgh defhij efgijk = bcddeefffgghhiijjk = bcekl = 2+4+16+1024+2048 = 3094.

Интересно отметить, что левый столбец также может быть получен последовательными половинками первого числа, из которых удалены четные числа. В нашем примере acd , bc (четный), ab , a . Заметив, что правый столбец содержит последовательные дубли второго числа, можно понять, почему крестьянское умножение является точным.

Отделение, остаток

Деление можно осуществлять последовательными вычитаниями: частное — это количество раз, когда делитель можно вычесть из делимого, а остаток — это то, что осталось после всех возможных вычитаний.

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

Фактически, это то, что мы делаем в методе длинного деления .

Сетка

В арифметике местоположения используется квадратная сетка, где каждый квадрат сетки представляет значение. Две стороны сетки отмечены значкомвозрастающие степени двойки. Любой внутренний квадрат можно идентифицировать по двум числам на этих двух сторонах, одно из которых находится вертикально под внутренним квадратом.квадрат, а другой — крайний справа. Значение квадрата является произведением этих двух чисел.

Пример сетки

						32
						16
						8
		32				4
						2
						1
32	16	8	4	2	1

Например, квадрат в этом примере сетки представляет собой 32, поскольку он является произведением 4 в правом столбце и 8 в нижней строке. Сама сетка может быть любого размера, а большие сетки просто позволяют нам обрабатывать большие числа.

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

Добавление

Сначала выложите двоичное число в строку, используя счетчики, представляющие единицы в числе. Например, число 29 (= 11101 в двоичном формате) будет размещено на доске следующим образом:

11101 (= 29) в одной строке

0	1	1	1	0	1

Число 29 — это, очевидно, сумма значений квадратов, на которых стоят фишки. Теперь наложите второе число на этот ряд. Скажем, мы поместим на него 9 (= 1001 в двоичном формате) вот так.

Наложение 1001 (= 9)

0	0	1	0	0	1

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

←

У нас все еще есть еще один квадрат с двумя фишками, поэтому мы делаем это еще раз:

←

Но замена этой пары создала еще один квадрат с двумя фишками, поэтому мы заменяем в третий раз:

Результат 100110 = 38

	←
1	0	0	1	1	0

Теперь в каждом квадрате есть только один счетчик, и считывание результата в двоичном формате 100110 (= 38) дает правильный результат.

Вычитание

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

Давайте посмотрим, как можно вычесть 12 из 38. Сначала поместите 38 (= 100110 в двоичном формате) в строку, а затем поместите под ней 12 (= 1100 в двоичном формате):

						38
						12

Для каждого счетчика в нижней строке, над которым есть счетчик, удалите оба счетчика. Мы можем удалить одну такую ​​пару на доске,в результате чего:

			↓
			↓

Теперь нам нужно «одолжить» фишки, чтобы избавиться от оставшегося внизу счетчика. Сначала замените крайний левый счетчик в верхнем ряду двумя справа:

→

Теперь замените один из двух счетчиков еще двумя справа от него, получив:

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

11010 = 26

		↓

и зачитайте 26, окончательный результат.

Некоторые свойства сетки

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

		256				32
	256				16	16
256				16		8
			16			4
		16				2
	16					1
32	16	8	4	2	1

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

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

32 ÷ 8

						32
						16
						8
			→	→	→	4
						2
						1
32	16	8	4	2	1

Найдите делимое 32 вдоль правой стороны и делитель 8 у нижнего края сетки. Продлите диагональ от делимого и найдите квадрат в том месте, где она пересекает вертикальную линию делителя. Частное находится в правом конце сетки от этого квадрата, который в нашем примере равен 4.

Почему это работает? Перемещение по диагонали не меняет значения; значение квадрата на пересечении по-прежнему является дивидендом. Но мы также знаем, что это произведение квадратов вдоль нижнего и правого края. Поскольку квадрат на нижнем краю — это делитель, квадрат на правом краю — это частное.

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

Умножение

Чтобы умножить пару двоичных чисел, сначала отметьте два числавнизу и справа от сетки. Скажем, мы хотимумножьте 22 (= 10110) на 9 (= 1001).

10110 * 1001

						1
						0
						0
						1
	1	0	1	1	0

Теперь разместите жетоны на каждом «пересечении» вертикали игоризонтальные ряды единиц в каждом числе.

						1
						0
						0
						1
	1	0	1	1	0

Обратите внимание, что каждая строка счетчиков в сетке представляет собой просто22 умножить на некотороесила двух. Фактически, общая стоимость жетонов равнасумма двух строк

22*8 + 22*1 = 22*(8+1) = 22*9

Таким образом, фишки на доске на самом деле представляют продукт.из двух чисел, за исключением того, что невозможно «прочитать»ответь пока.

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

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

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

	←

Наконец, замените две стойки в углу на одну над ней.и «прочитать» двоичное число в форме буквы L, начиная сверхний левый вниз в нижний левый угол, а затем ввнизу справа.

Результат 11000110

1
1
	↑
	0	0	0	1	1	0

Прочтите счетчики вдоль буквы L, но не считайте дважды угловой квадрат.Вы прочтете двоичный результат 11000110 = 198, что действительно равно 22*9.

Почему мы можем читать двоичные числа в форме буквы L?нижний ряд — это, конечно, только первые шесть степеней двойки, нообратите внимание, что в крайнем левом столбце указаны следующие пять степенейдва. Таким образом, мы можем напрямую считать 11-значное двоичное число изL-образный набор из 11 квадратов, лежащих слева и снизустороны сетки.

1024	↓
512	↓
256	↓
128	↓
64	↓
	→	→	→	→	→	→
	32	16	8	4	2	1

Наша маленькая сетка 6x6 может умножать числа только до 63 каждое, и вВ общем, сетка n x n может умножать два числа каждое до2 ^н -1. Масштабируется очень быстро, поэтому на доске по 20 чисел на каждой стороне.Например, может умножать числа каждое до чуть более миллиона.

Разделение

Мартин Гарднер представил немного более простую для пониманияверсия ^[2] метода деления Непера, который и естьпоказано здесь.

Деление работает почти так же, как умножение. Скажем, мы хотимчтобы разделить 485 на 13. Сначала поместите счетчики для 485 (= 111100101) вдольнижний край и отметку 13 (= 1101) по правому краю. Чтобы сохранитьпространство, мы просто посмотрим на прямоугольную часть доски, потому чтоэто все, что мы на самом деле используем.

485 ÷ 13

									1
									1
									0
									1

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

									1
									1
									0
									1
			↑

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

									1
					?				1
									0
					?				1

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

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

									1
									1
									0
									1
		→

а затем переместите один по диагонали к вершине столбца и переместитееще одна фишка, расположенная на краю доски, на свое место.

									1
						?			1
									0
									1
						↑

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

									1
						?			1
									0
									1
			→

и теперь переместим один жетон по диагонали туда, куда мы хотим.

									1
									1
									0
									1

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

									1
							?		1
									0
							?		1

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

									1
								?	1
									0
									1
				→				↑

У нас все еще есть недостающий квадрат, но мы просто снова удваиваем ставку и двигаемся.счетчик в это место и в конечном итоге

			1	0	0	1	0	1
									1
									1
									0
									1
					→

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

Результат «считывается» со столбцов — каждый столбец со счетчикамирассматривается как 1, а пустые столбцы равны 0. Таким образом, результат:100101 (= 37), а остаток — двоичное значение любых счетчиков.все еще осталось по нижнему краю. На третьем есть один счетчикстолбец справа, поэтому мы читаем его как 100 (= 4) и получаем 485÷ 13 = 37 с остатком 4.

Квадратные корни

Метод Нейпира

Объяснение Нэпьера о том, как формировать квадрат на каждом последующем этапе, на странице 149 рабдологии.

Этот процесс требует добавления фишек на счеты (доску), чтобы получить квадратные фигуры. В верхней части страницы 149 показаны диаграммы, объясняющие этот процесс. Начните с размещения одной фишки на доске (на самом деле она будет стоять на одном из пунктирных квадратов). Добавление трех других счетчиков рядом (или с пустыми строками и столбцами между ними и первым помещенным) приведет к появлению еще одной квадратной фигуры на счетах. Аналогично, добавление к этому еще пяти счетчиков (с показанными пустыми строками и столбцами или без них) приведет к еще большему квадрату. Возьмите число, которое необходимо учитывать, и поместите вдоль одного поля счетчики, обозначающие его значение. От позиции самой большой фишки этого значения следуйте по диагональным линиям (ходам слона) по доске, пока не дойдете до квадрата с точкой. Поместите фишку на этот квадрат. Вычтите значение, представленное этим единственным счетчиком, из исходного числа в поле. Добавьте три (пять, семь, ... для последующих шагов), чтобы создать квадрат на доске, и вычтите значение добавляли счетчики к числу на полях до тех пор, пока число не станет слишком большим, чтобы его можно было вычесть, или до тех пор, пока на доске не останется места. На доске у вас должен остаться большой квадрат фишек (возможно, с пустыми строками и столбцами между ними). Переместите один из счетчиков в каждой строке квадрата на край, и положения этих краевых счетчиков дадут квадратный корень из числа.

Пример извлечения квадратного корня из 1238 с использованием метода Напьера для поиска квадратных корней, представленный в книге «Рабдология» на странице 151.

Нэпьер приводит пример определения квадратного корня из 1238.Самый большой счетчик находится в позиции 1024, поэтому первый счетчик помещается в точку, найденную путем перемещения вниз по диагонали 1024 (в позиции 32,32). Вычитание этого значения (1024) из исходного числа оставляет счетчики равными 128. 64, 16, 4 и 2 (= 214). Размещение трех фишек на доске, чтобы сформировать квадрат с первой фишкой, но значение которого все еще можно вычесть из 214, приводит к появлению фишек в позициях 32,2; 2,2; и 2,32 (значения которых равны 64, 4 и 64, что при вычитании из остатка 214 = 82. Следующий квадрат, который можно составить из пяти фишек, но значения этих пяти фишек все еще можно вычесть из 82, приводит к фишкам в позициях 32,1; 2,1; 1,1; 1,2; и 1,32. Значения этих пяти счетчиков в сумме составляют 69, что при вычитании из 82 дает остаток 13.Поскольку на доске больше нет места, нам приходится остановиться. Переместите по одному счетчику из каждой строки на край (строки 32, 2 и 1), и это значение (35) представляет собой требуемый квадратный корень или, по крайней мере, целую его часть (фактическое значение равно 35,1852....).

Пример извлечения квадратного корня из 2209 с использованием метода Напьера для поиска квадратных корней, представленный в книге «Рабдология» на странице 153.

Нэпир приводит второй пример вычисления квадратного корня из 2209 (= 47).

См. также

• Оно живет

Ссылки

1. ^ Джон Нэпьер; перевод Уильяма Фрэнка Ричардсона; введение Робина Э. Райдера (1990). Рабдология . МТИ Пресс. ISBN   0-262-14046-2 .
2. ^ Мартин Гарднер (1986). Завязанные пончики и другие математические развлечения . WH Фриман и компания. ISBN   0-7167-1794-8 .

Специфический

Внешние ссылки

• Javascript-симуляция арифметики местоположения