Множительный инструмент на основе теоремы Слонимского

В XIX веке существовали интересные инструменты для умножения, построенные на основе теоремы Слонимского. Это «Снаряд для умножения» Слонимского и бруски Иоффе. Об этих инструментах в интернете невозможно ничего прочитать, кроме скудного описания внешнего вида, ни на что ни годного описания методики работы (в стиле «это работало как-то вот так»), заимствованного из книги «История вычислительной техники» И.А. Апокин, Л.Е. Майстров, «Наука» 1990 г. Описание не раскрывает принцип действия приборов. Литературу, на которую ссылается автор книги, достать неприемлемо сложно. Я решил вскрыть алгоритм работы прибора самостоятельно, а для демонстрации — изготовить собственный аналог.

Цель написания статьи

Эта статья для тех, кто, так же, как и я, интересуется историей вычислительной техники.
Теоретически, хорошее описание указанных инструментов должно быть в книге «Приборы и машины для механического производства арифметических действий: Описание устройства и оценка счет. приборов и машин» / В.Г. фон-Бооль. — Москва: типо-лит. т-ва И.Н. Кушнерев и К°, 1896. — 244 с.: ил., черт.; 24.
Но до Ленинской библиотеки, где она хранится, я так и не добрался, впрочем это и не важно. Главное, что в Интернете никакой информации, а я хотел, чтобы она была, потому что, надеюсь, не я один озадачился её поиском.

Почему местом размещения статьи выбран Хабр

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

Исходные данные, которые мне удалось найти

В интернете мне попалось описание интересного математического инструмента, разработанного З.Я. Слонимским.

В середине прошлого века З.Я. Слонимский (1810-1904) предложил простое множительное устройство, основанное на доказанной им теореме. Это устройство позволяло получать произведения любого числа (разрядность которого не превышала разрядности устройства ) на любое однозначное число. Другими словами, это было нечто вроде механической таблицы умножения любого числа на 2, 3, 4,..., 9. Позднее теорема Слонимского была использована при создании другого простого множительного устройства (счетных брусков Иоффе).

На основе своей теоремы Слонимский составил таблицу, состоящую из 280 столбцов – по 9 чисел в каждом. Эта таблица нанесена на цилиндры, являющиеся основным элементом устройства. Цилиндры могут перемещаться в двух направлениях: вдоль оси и вокруг нее. На ось, на которой находится цилиндр, надеты также два мини-цилиндра. На поверхность одного мини-цилиндра нанесены числа от 0 до 9, а на поверхность другого – буквы a, b, c, d и цифры (от 1 до 7).

На крышке прибора находятся 11 рядов окошек считывания, в первом (нижнем) ряду видно устанавливаемое число (множимое). Во втором и третьем рядах окошек при установке множимого появляются буквы и цифры. Их сочетание служит ключом для оператора. Благодаря ему он знает, какой винт и насколько нужно повернуть. После этого в 4-11-м рядах окошек появляются числа: в 4-м ряду – произведение множимого на 2, в 5-м – на 3, в 6 – на 4 и т. д. Таким образом, в нашем распоряжении оказывается произведение множимого на все разряды множителя. Теперь остается обычным способом (на бумаге) сложить эти результаты и получить искомое произведение.

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

Счетные бруски были предложены Иоффе в 1881 г. В 1882 г. на Всероссийской выставке они получили почетный отзыв. Принцип работы с ними основан на теореме Слонимского. Прибор Иоффе состоял из 70 четырехгранных брусков. Это позволило разместить на 280 гранях 280 столбцов таблицы Слонимского. Каждый брусок и каждый столбец были помечены, для чего использовались арабские и римские цифры и буквы латинского алфавита. Латинские буквы и римские цифры служили для указания порядка, в котором нужно было размещать бруски, чтобы получить произведение множимого на одноразрядный множитель. Полученные произведения (а их столько, сколько разрядов во множителе) складывались (точно так же как и при использовании множительного устройства Слонимского) с помощью карандаша и бумаги.

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

Оттуда же:

Бооль, в 1896 г. приходит к следующему заключению:“Бруски Иоффе упрощают умножение чисел еще в большей степени, нежели палочки Непера и их видоизменения. После простых остроумных брусков Люка и Жанойя это лучший из арифметических приборов для умножения ”.

Бруски Люка и Жанойя тоже интересная тема, о которой информации ещё меньше, но, статья не о них.

Некоторый результат дал поиск теоремы Слонимского.
Вот что пишет Вестник Сыктывкарского университета. Сер.1. Вып.13.2011. УДК 512.6, 517.987 «К 200-летию со дня рождения создателей вычислительных машин, представленных к демидовской премии, Х.З. Слонимского и Г. Куммера». В.П. Одинец

1. Пусть имеем натуральное число в системе J с основанием r, записанное поразрядно a_ma_m-1...a₂a₁. Умножим его последовательно на 1, 2, 3, ..., r-1, и полученные произведения подпишем одно под другим с соблюдением правила разрядов. В результате получим m+1 столбцов (свободные места слева заполним нулями), каждый из которых содержит r-1 цифру. Расположение цифр в столбце назовём представлением столбца. Умножение всевозможных чисел на 1, 2, ..., r-1 порождает бесконечное множество представлений. Однако при этом число различных представлений конечно и задаётся формулой

Где φ(n) — функция Эйлера, заданная на множестве N натуральных чисел, значение которой (для любого n ∈ N) равно количеству натуральных чисел, не превосходящих n и взаимно простых с n.

2. Пусть теперь r = 10, т.е. система счисления J десятичная. Тогда произведение любой дроби, заключённой между двумя соседними Фареевыми дробями p_i/q_i и p_i+1/q_i+1 на числа 1, 2, 3, ..., 9 порождает для целых частей полученных чисел то же представление, что и для целых частей последовательности произведений на числа 1, 2, 3,… 9 Фареевой дроби p_i/q_i

Полная статья находится здесь.

Формулировка мне не пригодилась. Доказательство теоремы я искать не стал, так сказать, поверил Слонимскому на слово. Важным для моей задачи моментом этой теоремы было то, что «число различных представлений конечно и задаётся формулой ...». И, как следует из теоремы и из конструкции прибора Слонимского, для десятичной системы существует 280 представлений столбцов.

Таблица Слонимского

Для воссоздания прибора, действующего на основе той же математической идеи, я получил таблицу Слонимского по алгоритму, описанному в вышеуказанной статье.
Я вооружился FireBug и начал вычислять.
Далее в статье будут встречаться фрагменты JavaScript. Этот язык — основа моей профессиональной деятельности, поэтому я использовал его. Тем не менее, я полагаю, что использованные мной формулы достаточно просты, чтобы специфика языка не затрудняла их понимания, а в некоторых местах я специально использовал не принятые в JavaScript приёмы, чтобы сделать код более понятным для программистов на других языках.

Согласно статье, для построения основной таблицы Слонимского для десятичной системы счисления, была взята последовательность Фарея
F(9) = {0, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1}. 28 чисел последовательности F(9), кроме 1, были умножены каждое на ряд чисел от 0 до 9 и взяты только целые части полученных произведений. Полученные столбцы чисел пронумерованы в порядке возрастания чисел Фарея начиная с 0.

Значения таблицы получены по формуле

B[c][r] = Math.floor(F[c]*r);

Здесь c — номер столбца, r — номер строки.

Основная таблица Слонимского (B)
Для получения полной таблицы Слонимского была построена вспомогательная таблица P, представляющая собой таблицу умножения чисел от 0 до 9 в представлении Пифагора.

P[c][r] = c*r;

Каждый столбец таблицы B векторно сложен с каждым столбцом таблицы P. Таким образом получена промежуточная таблица DU, содержащая 280 столбцов.

DU[b*10+p][r] = B[b][r] + P[p][r];

На её основе построены две таблицы U и D, содержащие соответственно цифры разряда единиц и разряда десятков полученных сумм.

  U[c][r] = DU[c][r] % 10;
  D[c][r] = Math.floor(DU[c][r]/10);

Обнаружено, что таблица разряда единиц (U) содержит не повторяющиеся столбцы, тогда как все столбцы таблицы разряда десятков (D) встречаются и в таблице U, и в таблице B.

Таким образом таблица U исчерпывает все порождённые столбцы. Следовательно, она и является полной таблицей Слонимского.

Для удобства дальнейшей работы, я пометил, с каким столбцом таблицы B совпадает каждый столбец таблицы D, и теми же номерами пометил столбцы того же номера таблицы U (строка q обеих таблиц), а для ещё большего удобства ввёл массив Q, содержащий указанные значения, под номерами, соответствующими номерам столбцов в таблицах D и U.

Вскрытие алгоритма

Сперва я обратил внимание на то, что группа столбцов с b=0 таблицы DU — совпадает с таблицей Пифагора.

Второе наблюдение: если выбрать из таблицы U столбцы с p=0, составленная из них таблица совпадает с таблицей B.
Продолжение
Значит каждый столбец D[i] таблицы D входит в таблицу U как столбец у которого b=Q[i], p=0.

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

Тогда я предположил, что q — это номер группы, из которой я должен взять столбец для следующего разряда. Начинать решил с группы 0.
Провёл вычислительный эксперимент с помощью FireBug — вроде как получается.

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

value = (100 + Math.floor(Math.random()*(999-100)))*10 + 1 + Math.floor(Math.random()*(9-1));

Такая формула гарантирует, что будет получено число не меньше 1000 и что в разряде единиц не будет нуля.
При крайней сборке статьи, рандом выдал мне value = 3212.
Возьмём из группы 0 таблицы U столбец 2:

Видим, что для него q = 5. Теперь для следующего разряда возьмём из группы 5 столбец 1:

Для этого столбца q = 1. Продолжим таблицу аналогичным образом, и получим:

Цифры у нас кончились, очередное q = 8. Очевидно, нужно из группы 8 взять нулевой столбец. Получаем:

Легко видеть, что в строках этой таблицы находятся произведения нашего числа 3212 на 0, 1, 2,… 9.

Разбор эксперимента

Труднее было разобраться, почему это работает.
Итак, у нас есть 28 групп (от 0 по 27) по 10 столбцов. Группам присвоены те же номера, что и столбцам таблицы B.
В таблицах DU, U и D в строке b содержится номер группы, в строке p — номер столбца в группе.

Введём функции:
Функция умножения числа на вектор {0; 1; 2; 3; 4; 5; 6; 7; 8; 9} (вектор представлен массивом)

function mul(n){
  var result = new Array(10);
  for(var i=0; i<10; ++i){
    result[i]=n*i;
  }
  return result;
}

Функция векторного сложения двух массивов

function sum(a, b){
  var result = new Array(10);
  for(var i=0; i<10; ++i){
    result[i]=a[i]+b[i];
  }
  return result;
}

Функция получения массива, содержащего значения разряда единиц значений исходного массива

function unit(a){
  var result = new Array(10);
  for(var i=0; i<10; ++i){
    result[i]=a[i] % 10;
  }
  return result;
}

Функция получения массива, содержащего значения разряда десятков значений исходного массива

function deca(a){
  var result = new Array(10);
  for(var i=0; i<10; ++i){
    result[i]=Math.floor(a[i] / 10);
  }
  return result;
}

Нетрудно сравнить формулы и заметить, что каждый столбец таблицы P, это ни что иное, результат функции mul для номера столбца;
столбцы таблиц D и U получены из столбцов таблицы DU с помощью функций unit и deca соответственно;
каждый столбец таблицы DU получен суммированием одного столбца таблицы B и одного столбца таблицы P, что соответствует использованию функции sum.

Вспомним алгоритм умножения в столбик многоразрядного числа на одноразрядное:

Пусть
a_na_n-1...a₁a₀ — множимое, записанное поразрядно;
b — одноразрядный множитель;
с_n+1c_n...c₁c₀ — результат, записанный поразрядно(полагаем, что результат на один разряд длиннее множимого, в большинстве случаев так и будет, в остальных — от ведущего нуля ещё никто не умирал);
m₀, m₁,… m_n — значения, переносимые в старший разряд (при вычислении на бумаге записываются «наверх»);
floor — функция округления вниз;
% — операция получения остатка от деления.
Переменная x будет использоваться как локальная и перевычисляться для каждого разряда.

1. Берём из таблицы умножения (она у каждого из нас в памяти) произведение нулевого разряда множимого на множитель:
x = a₀*b;
разряд единиц числа x без изменений записываем в результат: c₀ = x % 10;
разряд десятков числа х записываем «наверх»: m₀ = floor(x/10).

2. Берём из таблицы умножения произведение первого разряда множимого на множитель и прибавляем к нему значение «сверху»:
x = a₁*b + m₀
разряд единиц — записываем в результат: c₁ = x % 10;
разряд десятков — записываем «наверх»: m₁ = floor(x/10).

3. Аналогично поступаем для разрядов со 2 по n:
x = a_i*b + m_i-1
c_i = x % 10;
m_i = floor(x/10).

4. Полученное при вычислении разряда n значение m_n даст нам последний разряд результата:
c_n+1 = m_n.

Полагаю, все согласны? В описании ошибок нет? Тогда размышляем дальше:

Таблица Слонимского служит для получения произведений произвольного числа на ряд чисел от 0 до 9.
Если бы мы решили умножать в столбик, то умножали бы множимое число десять раз и получили по набору с_n+1c_n...c₁c₀ и m₀, m₁,… m_n для каждого из десяти множителей.
Поскольку мы хотим вскрыть алгоритм Слонимского, введём ещё массив j₀… j_n+1, в котором будем хранить номера столбцов таблицы U, соответствующих столбцам результата умножения.

Для упрощения формы записи, воспользуемся введёнными нами функциями, и пройдёмся по тем же пунктам вышеупомянутого алгоритма:
1. Вычислим
x = mul(a₀);
Очевидно, что x совпадает со столбцом № a₀ таблицы Пифагора (P) и, что интересно, со столбцом p=a₀, b=0 таблицы DU. В таблицах DU, U и D номер столбца вычисляется как b*10+p, следовательно
x = DU[a₀]
Теперь нам нужны единицы, чтобы записать в результат, и десятки, чтобы записать «наверх»:
c₀ = unit(x);
m₀ = deca(x);
в данном случае c₀ и m₀ — массивы.
Обратим внимание, что c₀ получен точно так же, как столбец p=a₀, b=0 таблицы U, а m₀ — как соответствующий столбец таблицы D.
Запишем:
j₀ = a₀;
c₀ = U[j₀];
m₀ = D[j₀].

2. Возьмёмся теперь за следующий разряд. Нам нужно вычислить произведения a₁ на вектор, а затем векторно прибавить к полученному массиву массив m₀:
x = sum(mul(a₁), m₀);
Разбираем эту формулу:
mul(a₁) совпадает со столбцом P[a₁].

В шаге 1 было вычислено:
m₀ = D[j₀].
Вспомним теперь, что для каждого столбца таблицы D найден номер q, под которым этот столбец входит в таблицу B. Этот номер мы для удобства записали в строку q таблиц U и D и в массив Q.
Теперь запишем:
m₀ = D[j₀] = B[Q[j₀]];
Да простят мне программисты и математики такое смешение стилей.

Оба слагаемых разобраны. Теперь вспомним о сумме. Одно из слагаемых является членом таблицы P, а другое — таблицы B. Все суммы на этот случай у нас посчитаны и входят в таблицу DU.
Следовательно, искомый массив должен совпадать со столбцом таблицы DU, для которого p=a₁, b=Q[j₀]:
x = DU[Q[j₀]*10 + a₁].
Теперь нам снова нужны единицы и десятки от членов x:
c₁ = unit(x);
m₁ = deca(x);
и нам в этом снова помогут таблицы U и D.

Подведём итог второго шага:
j₁ = Q[j₀]*10 + a₁;
c₁ = U[j₁];
m₁ = D[j₁].

3. Уже можно подметить закономерность:
x = sum(mul(a_i), m_i-1);
а так как:
mul(a_i) = P[a_i],
m_i-1 = D[j_i-1] = B[Q[j_i-1]];
то:
x = DU[Q[j_i-1]*10 + a_i].
Следовательно:
j_i = Q[j_i-1]*10 + a_i;
c_i = U[j_i];
m_i = D[j_i].

4. Теперь посмотрим, что нам делать с m_n.
Последний перенос разряда это старший разряд результата. Но нам надо выбрать столбец таблицы U.
Проанализируем:
m_n = D[j_n].
D[j_n] входит в таблицу U как столбец b=Q[j_n], p=0, т.е.
D[j_n] = U[Q[j_n]*10].
Следовательно:
j_n+1 = Q[j_n]*10;
c_n+1 = U[j_n+1].
Поскольку никакое произведение одноразрядных чисел не может дать более чем двухразрядное число, массив m_n+1 будет содержать только нули. Вычисление закончено.

Теперь соберём в кучу найденные уравнения для j_i:
j₀ = a₀;
j_i = Q[j_i-1]*10 + a_i;
j_n+1 = Q[j_n]*10.
Они сводятся к одному уравнению
j_i = Q[j_i-1]*10 + a_i,
если принять, что
a_n+1 = 0 (что равносильно приписыванию ведущего нуля к множимому числу),
Q[j_-1] = 0.

Это означает, что чтобы сложить из столбцов таблицы U таблицу произведений числа a_na_n-1...a₁a₀ на одноразрядные числа, нужно каждый раз из группы b=Q[j_i-1] брать столбец p=a_i, причём строка q того же столбца таблицы подскажет нам, какая группа столбцов будет следующей, а начать работу нужно с группы столбцов 0.

Продемонстрированный в эксперименте алгоритм выведен аналитически.

Резюмирую:

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

Материальная реализация

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

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

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

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

Должен заметить, что удобно разместить столбцы на четырёхгранных брусках, как у Иоффе, мне не удалось. Подозреваю, что бруски Иоффе были не такими уж удобными.

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

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

Значение q столбца нанесено на каждой рейке ниже разделительной горизонтальной линии.

Рейки изготовлены из алюминиевой полосы 50х2 мм, которая для этого была напилена электролобзиком примерно по 4-6 мм (слишком узкие браковались, слишком широкие либо подтачивались точильным диском, либо также браковались).
Цифры нанесены гравировальной фрезой.
Для хранения реек был высверлен из соснового бруса 50х40 мм деревянный органайзер. Да, знаю, что можно продумать лучше, но до игры оставалось 2 дня, а силы после гравировки 2800 циферок были на исходе.
Номера групп и столбцов нанесены на органайзер гелевой ручкой.

Из-за загадочных глюков с исчезновением картинок, фотографии добавлены с помощью комментария habrahabr.ru/post/232255/#comment_7940351

Источники

1. Вестник Сыктывкарского университета. Сер.1. Вып.13.2011. УДК 512.6, 517.987 «К 200-летию со дня рождения создателей вычислительных машин, представленных к демидовской премии, Х.З. Слонимского и Г. Куммера». В.П. Одинец;
2. Теорема Слонимского и простые вычислительные устройства на ее основе.

P.S. Да благословит Дух Машины ваш сервер, ибо он пережил отправку почти 200кб кода, а с учётом эскапирования — все 500.