the Russe in C Several algorithms for multiplication. One quite interesting and surprising is the multiplication the russe. This algorithm is not to be very educational, in fact is not taught in schools, since it only requires to divide and multiply by 2. In essence, knowing table 2, and of course, know how to add, and it works!. algorithm and example The best way to understand how the algorithm is a example. Let's multiply 35 * 91: the result should be 3185. What you do is take the multiplying and dividing by 2 while the result is greater than 1. With the multiplier is the opposite, multiply by 2. The numbers are those parts add up right where the left side is odd. In other words, add up those numbers multiply column where the column is odd divisions. A pseudocode would be something like: |
russe (x, y)
begin while (x> = 1)
do if (x a 2) THEN | more than + = y; |
endif x = x / 2;
y = y * 2;
end
tentador implementation
Result and algorithm. It's simple. If we consider that the multiplications and divisions by 2 are made by shifts to the left and right respectively, it is very easy.
An improvement to this is to put the smallest number as multiplying because so we can save a few iterations. _______________________________________________________
/ * russe.c - multiplication algorithm to
russe
* Author: Juan Jose Fumero Alfonso
* Compile: gcc-O3 russe.c -o russe
*/
#include <stdlib.h> #include <unistd.h>
/* getopt */
#define AUTHOR "Juan José Fumero Alfonso"
void | author () { | printf (
"Author: %s
\n
"
, AUTHOR);
}
void
version () { printf (
"Multiplicación a la Russe, version 0.2
void
help () {
printf (
"
\t
$ ./russe -[-hva] x <number1> -y <number2>
\n
"
);
printf (
-v: print version
\n
"
) printf ( " \\ t -a: print author \\ n " ) printf ( " \\ t -h: show this help \\ n " );} |
/ * function that performs the russe multicación * / int
mrusse (
AUXA int, int
auxb) {
int mult =
0; while
(auxa> = a ) {if
((auxa%
2) == 1
) { than + = auxb;}
auxa = auxa>>
a
; auxb auxb = \u0026lt;\u0026lt;
a ;}
return more;}
/ * Input the two numbers to multiply from the line of
* commands * /
int main ( int argc, char
** argv) { / * Collection numbers ie * /
int x, y; flgn1 int = 0
, flgn2 = 0 ; int opt;
while ((opt = getopt(argc, argv, ":havx:y:" )) != - 1 ) {
switch (opt) { case 'h' : help();
return
0 ;
break ; case 'v' :
version(); return 0
; break;
case 'a' : author ();
return 0
;
break ;
case 'x' :
/ * collection of numbers * /
flgn1 = 1
;
x = atoi (optarg); break
;
case 'and' :
/ * collection of numbers * / flgn2 = 1 ;
y = atoi (optarg); break;
default: / * '? " * /
help (); exit (EXIT_FAILURE); }}
if ((flgn1 == 0) & & (== Flgn2
0)) { fprintf (stderr, "Error in numbers \\ n "
)
return - a ; }
int = mrus than (x, y); printf ( "
\\ t % i *% i =% i
\\ n " , x, y, long); return
0;} _______________________________________________________
The main function is mrusse , which is what makes the multiplication by software. The rest is just to allow various input options to the program. Usage:
$. / Russe-x 35-and 91
Use option-h for assistance.