Conversions allow calculate much smaller values.
1) Power k of base P.
A divisor has k digits in base P. When we change base into P^k, a divisor becomes one-digit number. They old digits split into one bigger digit in new system. Let i is a natural number or 0. We group digits:
a_{ki+k-1}*P^{ki+k-1} + ... + a_{ki+1}*P^{ki+1} + a_{ki}*P^{ki} = (a_{ki+k-1}*P^{k-1}+...+a_{ki+1}*P+a_{ki})*P^{ki}
Example:
Decimal system. Let change into a system with base P=1000=10^3. Split neighboring three digits into one as follow:
N = 9876543210.
New base P=1000 put N =
9 876 543
210, it has only four digits, three of them have three digits in decimal system.
2) Multiply base P by k
Every digit divide by power k^i, which is position of digit a_i.
a_n*P^n + ... + a_1*P + a_0 = a_n*k^{-n}*Q^n +...+a_1*k^{-1}*Q + a_0
where Q = P*k.
There are some method to avoid fraction. In most of them they are shift remainder from division a_i from k to less significant digit.
We can add P into digit, that changes value of N. Below is a method, it saves values of N.
Let use two lists B=[a_n], A=[a_{n-1}, ..., a_1, a_0] and use current algorithm:
1.multiply k*P with remainders by division digit by k and move they to next number of list, last number put into C;
2. divide all digits from B by k - it's possible now (write as []/5#[step 3.]);
3. take first digit from A, put it at the end of B increased by P*C;
4. stop when A is empty, else goto 1.
In list B is number with base kP, in list A is number with base P.
Example:
Decimal system
Write number N = 6542 with base P=50. k=5 (=50/10)
start: B=[6], C=?, A=[5,4,2]
B=[5]/5#[1*10+5]=[1,15], C=1, A=[4,2]
B=[0,65]/5#[4]=[0,13,4], C=0, A=[2]
B=[0,10,150]/5#[4*10+2]=[0,2,30,42], C=4, A=[]
From list B comes number N = 2 30 42 with base P=50.
There is other way to get a number in such system. In digits are multiples like above, and remainders shifts and increase less significant digit.
A list contains the first digits the last of them is separate. This digits moves out list into list of digits of number N. Now all values in list are divided by k. Use recursion until list is empty or has zeros only. A number N contains digits they abandon list, it is in new base.
Example anew:
Decimal number N=6542 into base P=5*10.
[6, 5, 4 | 2] = [5, 15, 0 | 42] = 5*[1, 3, 0] 42
[1, 3 | 0] = [0, 10 | 30] = 5*[0, 2] 30
[0 | 2] = [0] 2
It is number N = 2 30 42 with base 50.
3) Add integer k to base P
Expression a_n*P^n+...+a_1*P+a_0 transforms into
b_m*(P+k)^m+...+b_1*(P+k)+b_0
Let use two list B=[a_n], A=[a_{n-1},...,a_1, a_0] like above.
1. move first digit from A to the end of B;
2. for all digits in B do:
this = this - k*previous,
if previous doesn't exists, take 0
3. repair digits by addiction, subtraction (P+k) and decrement / increment previous number (they are in colour in example);
4. stop when A is empty, else goto 1.
This method is a kernel of [PU] or [PD]. It works especially good with bigger values P. There is number in list B with base (P+k).
Example:
Decimal system.
Number N = 951 transform to base P=8. Calculate k=8-10=-2.
start: B=[9], A=[5,1]
B = [9, 5-(-2)*9] = [9, 23] = [0+
1,9-
8+
2, 23-
2*8] = [1,3,7], A=[1]
B=[1, 3-(-2)*1, 7-(-2)*3, 1-(-2)*7] = [1,5+
1,
8-8+5+
1,
8-8+7] = [1,6,6,7], A=[]
There is number N = 01667 in list B, in decimal system still N = 951.
