SMARANDACHE ALGORITHMS
1) MULTIPLICATION
Another algorithm to multiply two integer numbers, A and B:
- let k be an integer >= 2;
- write A and B on two different vertical columns: c(A), respectively
c(B);
- multiply A by k, and write the product A on the column c(A);
1
- divide B by k, and write the integer part of the quotient B
1
on the column c(B);
... and so on with the new numbers A and B ,
1 1
untill we get a B < k on the column c(B);
i
Then:
- write another column c(r), on the right side of c(B), such that:
for each number of column c(B), which may be a multiple of k plus
the rest r (where r = 0, 1, 2, ..., k-1),
the corresponding number on c(r) will be r;
- multiply each number of column A by its corresponding r of c(r),
and put the new products on another column c(P) on the right side
of c(r);
- finally add all numbers of column c(P).
AxB = the sum of all numbers of c(P).
Remark that any multiplication of integer numbers can be done
only by multiplication with 2, 3, ..., k, divisions by k, and additions.
This is a generalization of Russian multiplication (when k=2).
Smarandache multiplication is usefull when k is very small, the best values
being for k=2 (Russian multiplication -- known since Egyptian time), or k=3.
If k is greater than or equal to min {10, B}, this multiplication is trivial
(the obvious multiplication).
Example 1 (if we choose k=3):
73x97= ?
x3 | /3 |
-------|------|-------------
c(A) | c(B) | c(r) | c(P)
-------|------|------|------
73 | 97 | 1 | 73
219 | 32 | 2 | 438
657 | 10 | 1 | 657
1971 | 3 | 0 | 0
5913 | 1 | 1 | 5913
---------------------|------
| 7081 total
therefore: 73x97=7081.
Remark that any multiplication of integer numbers can be done
only by multiplication with 2, 3, divisions by 3, and additions.
Example 2 (if we choose k=4):
73x97= ?
x4 | /4 |
-------|------|-------------
c(A) | c(B) | c(r) | c(P)
-------|------|------|------
73 | 97 | 1 | 73
292 | 24 | 0 | 0
1168 | 6 | 2 | 2336
4672 | 1 | 1 | 4672
---------------------|------
| 7081 total
therefore: 73x97=7081.
Remark that any multiplication of integer numbers can be done
only by multiplication with 2, 3, 4, divisions by 4, and additions.
Example 3 (if we choose k=5):
73x97= ?
x5 | /5 |
-------|------|-------------
c(A) | c(B) | c(r) | c(P)
-------|------|------|------
73 | 97 | 2 | 146
365 | 19 | 4 | 1460
1825 | 3 | 3 | 5475
---------------------|------
| 7081 total
therefore: 73x97=7081.
Remark that any multiplication of integer numbers can be done
only by multiplication with 2, 3, 4, 5, divisions by 5, and additions.
The Smarandache multiplication becomes less usefull when k increases.
Look at another example (4), what happens when k=10:
73x97= ?
x10 | /10 |
-------|------|-------------
c(A) | c(B) | c(r) | c(P)
-------|------|------|------
73 | 97 | 7 | 511 (=73x7)
730 | 9 | 9 | 6570 (=730x9)
---------------------|------
| 7081 total
therefore: 73x97=7081.
Remark that any multiplication of integer numbers can be done
only by multiplication with 2, 3, ..., 9, 10, divisions by 10, and
additions --
hence we obtain just the obvious multiplication!
[From the book: "Some Notions and Questions in Number Theory", by
C.Dumitrescu & V.Seleacu, Erhus Univ. Press, Glendale, 1994,
Section #110 ("Smarandache Multiplication").]
2) DIVISION BY k^n
Another algorithm to divide an integer numbers A by k^n, where k, n are
integers >= 2:
- write A and k^n on two different vertical columns: c(A), respectively
c(k^n);
- divide A by k, and write the integer quotient A on the column c(A);
1
- divide k^n by k, and write the quotient q = k^(n-1)
1
on the column c(k^n);
... and so on with the new numbers A and q ,
1 1
untill we get q = 1 (= k^0) on the column c(k^n);
n
Then:
- write another column c(r), on the left side of c(A), such that:
for each number of column c(A), which may be a multiple of k plus
the remainder r (where r = 0, 1, 2, ..., k-1),
the corresponding number on c(r) will be r;
- write another column c(P), on the left side of c(r), in the following
way: the element on line i (except the last line which is 0) will
be k^(i-1);
- multiply each number of column c(P) by its corresponding r of c(r),
and put the new products on another column c(R) on the left side
of c(P);
- finally add all numbers of column c(R) to get the final remainder R ,
n
while the final quotient will be stated in front of c(k^n)'s 1.
Therefore:
A/(k^n) = A and remainder R .
n n
Remark that any division of an integer number by k^n can be done
only by divisions to k, calculations of powers of k,
multiplications with 1, 2, ..., k-1, additions.
Smarandache division is usefull when k is small, the best values being when
k is an one-digit number, and n large.
If k is very big and n verry small, this division becomes useless.
Example 1 :
1357/(2^7) = ?
| /2 | /2 |
---------------------|------|--------|
| c(R) | c(P) | c(r) | c(A) | c(2^7) |
|------|------|------|------|--------|
| 1 | 2^0 | 1 | 1357 | 2^7 | line_1
| 0 | 2^1 | 0 | 678 | 2^6 | line_2
| 4 | 2^2 | 1 | 339 | 2^5 | line_3
| 8 | 2^3 | 1 | 169 | 2^4 | line_4
| 0 | 2^4 | 0 | 84 | 2^3 | line_5
| 0 | 2^5 | 0 | 42 | 2^2 | line_6
| 64 | 2^6 | 1 | 21 | 2^1 | line_7
| | | -------- |
| | | | 10 | 2^0 | last_line
|------|-------------|------|---------
| 77 |
Therefore: 1357/(2^7) = 10 and remainder 77.
Remark that the division of an integer number by any power of 2 can be
done only by divisions to 2, calculations of powers of 2,
multiplications and additions.
Example 2 :
19495/(3^8) = ?
| /3 | /3 |
---------------------|-------|--------|
| c(R) | c(P) | c(r) | c(A) | c(3^8) |
|------|------|------|-------|--------|
| 1 | 3^0 | 1 | 19495 | 3^8 | line_1
| 0 | 3^1 | 0 | 6498 | 3^7 | line_2
| 0 | 3^2 | 0 | 2166 | 3^6 | line_3
| 54 | 3^3 | 2 | 722 | 3^5 | line_4
| 0 | 3^4 | 0 | 240 | 3^4 | line_5
| 486 | 3^5 | 2 | 80 | 3^3 | line_6
| 1458 | 3^6 | 2 | 26 | 3^2 | line_7
| 4374 | 3^7 | 2 | 8 | 3^1 | line_8
| | | --------- |
| | | | 2 | 3^0 | last_line
|------|-------------|-------|---------
| 6373 |
Therefore: 19495/(3^8) = 2 and remainder 6373.
Remark that the division of an integer number by any power of 3 can be
done only by divisions to 3, calculations of powers of 3,
multiplications and additions.
From the book:
[1] Dumitrescu, C., Seleacu, V., "Some Notions and Questions in Number
Theory", Erhus Univ. Press, Glendale, 1994,
Section #111 {"Smarandache Division by k^n, (k, n >= 2)"}.