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)"}.