Al-Kashi's algorithm
When carrying out calculations in ancient times, they used various "rules" that simplified these calculations. They were the first algorithms. One of these is the al-Kashi’s algorithm. This algorithm was proposed at the very beginning of the 15th century, although similar procedures were also encountered in the Indian mathematical treatise "Chanda-sutra", and in the works of Egyptian mathematicians when considering multiplication.
The al-Kashi’s algorithm calculates the value of x n, where n is a positive number.
Step 1. Enter three values - N = n; y = 1; z = x.
At this moment, the relation xn = y*zn is valid.
Step 2. Divide N by 2, at the same time determine whether N was even before that. If N was even, then go to step 5.
Step 3. Multiply y by z.
Step 4. If N is zero, then the answer is y.
Step 5. Multiply z by itself, Z = z * z.
We return to step 2.
You can consider al-Kashi's algorithm in a different way:
Step 1. We introduce three quantities N = n; y = 0; z = x.
Step 2. Divide N by 2; At the same time, we determine whether N has been so even. If N was even, then go to step 5.
Step 3. Increase y by z.
Step 4. If N is zero, then the answer is y.
Step 5. Add z with yourself, Z = z + z.
We return to step 2.
In this version of al-Kashi's algorithm, in steps 3 and 5, multiplication is replaced by addition, and in step 1 y is not equal to unit, and zero. As a result of the implementation of such a modified al-Kashi’s algorithm, we obtain the product of two numbers n and x: y = n * x.
Al-Kashi’s algorithm is convenient for practical calculations, the method of multiplication, which reduces to simpler operations of doubling, division in half, and addition. This is the method used in calculations on accounts - in Europe it is traditionally referred to as the "peasant method" rather than Al-Kashi's algorithm.
