Простаферетическая функция

Простаферетическая функция задаётся выражением  $p(n)=\left[{\frac {n^{2}}{4}}\right]$,  где  $~\left[~\right]$  — целая часть.

Основное свойство

Позволяет заменить умножение целых чисел вычитанием:

$~m\cdot n=p(m+n)-p(m-n)$

Доказательство

$~m\cdot n={\frac {(m+n)^{2}}{4}}-{\frac {(m-n)^{2}}{4}}$  (поляризационное тождество)

$~=\left[{\frac {(m+n)^{2}}{4}}\right]-\left[{\frac {(m-n)^{2}}{4}}\right]$  (дробные части совпадают)

$~=p(m+n)-p(m-n)$

Применение

При вычисления вручную

Использование простаферетической функции при вычислениях вручную позволяет резко сократить объём используемых таблиц. Так, таблица умножения чисел от 1 до 1000 должна включать 1 000 000 значений (или 500 500 значений с учётом коммутативности умножения), в то время как таблица простаферетической функции должна содержать всего 2001 значение.

Таблица умножения чисел от 11 до 99 в «Четырёхзначных математических таблицах» Брадиса занимает 23 страницы, таблица же значений от $~p(1)$  до $~p(198)$  уместилась бы, по-видимому, на 1 странице.

В архитектуре процессоров

Функция позволяет заменить умножение 5-ю быстрыми операциями процессора: сложение — выборка из таблицы в ПЗУ — вычитание — выборка — вычитание. В случае возможности распараллеливания необходимое время работы уменьшается до 3 операций:

• вычисления  $~m+n$  и  $~m-n$
• выборки  $~p(m+n)$  и  $~p(m-n)$  из ПЗУ
• вычисление  $~p(m+n)-p(m-n)$

История

В Европе вычисления с применением простаферетической функции были разработаны во второй половине XVI в., и до появления логарифмических таблиц применялись для ускорения астрономических вычислений, например в обсерватории Тихо Браге на острове Гвен

Сноски

Шаблон:Rq