Алгоритм перевода из p-ичной в (p±1)-ичную систему

Выдержки из «Простые алгоритмы переводов p→p-1 и p→p+1»[1].

Вычеты и неполные частные

$A,p,k\in \mathbb{N}$ , $p\ge 2$ ,   $0\le k\le p-2$

${\{A\}}_p$ — наименьший неотрицательный вычет по основанию $p$ , удовлетворяющий условию $0\le {\{A\}}_{(p,k)}\le p-1$

${[A]}_p$ — неполное частное по основанию $p$ , определяемое из соотношения $A=p\cdot {[A]}_p+{\{A\}}_p$ .

${\{A\}}_{(p,k)}$ — наименьший неотрицательный вычет по основанию $(p,k)$ , удовлетворяющий условию $-k\le {\{A\}}_{(p,k)}\le p-k-1$

${[A]}_{(p,k)}$ — неполное частное по основанию $(p,k)$ , определяемое из соотношения $A=p\cdot {[A]}_{(p,k)}+{\{A\}}_{(p,k)}$ .

Алгоритмы деления на p±1

${[{(a_n\dots a_0)}_p]}_{(p\pm 1)}={(b_n\dots b_0)}_p$ ,

${\{{(a_n\dots a_0)}_p\}}_{(p\pm 1)}=c_0$ ,

где $b_i(i=n,n-\mathrm{1,}\dots ,0)$ и ${с}_0$ определяются формулами

$b_i=c_{i+1}+{[a_i\mp c_{i+1}]}_{p\pm 1}$ ,

$c_i={\{a_i\mp c_{i+1}\}}_{p\pm 1}$ ,

$c_{n+1}=0$

Пример перевода из десятичной системы счисления в девятеричную

   1234
c 01361
b  0137
c  0142
b   015
c   016
b    01
c     1
b     0

${1234}_{10}\to {1621}_9$

Пример перевода из девятеричной системы счисления в десятичную

   1621
c 01574
b  0146
c  0133
b   013
c   012
b    01
c     1
b     0

${1621}_9\to {1234}_{10}$

Литература

1. Рамиль Альварес Х. Простые алгоритмы переводов p→p-1 и p→p+1. — В кн.: Вычислительная техника и вопросы кибернетики, вып. 7. Изд-во МГУ, 1970