Is this possible guys? This is homework I have, and my teacher obviously believes it is, but it seems to me that it's impossible not to use addition or multiplication outside of the short-multiplication method.
Write (and provide a tester for) a recursive algorithm:
int multiply(int x, int y)
to multiply two positive integers together without using the * operator. Do not just add x to itself y times!!!
(Hint: Write a recursive method that will multiply an integer by a value in the range 0 .. 10. Then write a second recursive method to implement the multiplication algorithm you learned to multiply multi-digit numbers in elementary school.)
My issue is that once you break down any multi digit number and starting adding those together you have to use multiplication of numbers greater than 10, i.e 22 * 6 is 2 * 6 + 20 * 6 ... so am I totally missing something?
EDIT I guess I should have added this is the code I have,
public int mult(int x, int y){
return x == 0 ? 0 : (mult(x-1, y) + y);
}
which is perfect, but as far as I understand the instructions, that's breaking do not just add x to itself y times. I personally believe it isn't, but my teacher hasn't been very clear, and I'd like to know if there's some other way that I havn't thought of, sorry for the confusion.
My interpretation of the assignment is that the teacher would like the student to implement a recursive algorithm to perform Grid method multiplication (the kind we learn in elementary school).
For example, multiplying 34 x 13 would be done like so...
34
* 13
====
12
90
40
+300
====
442
I didn't have easy access to a Java development environment, so I wrote the code in C# but the algorithm should be simple enough to convert into Java.
public int Multiply(int x, int y)
{
if (x < 0) throw new ArgumentException("must be positive integer", "x");
if (y < 0) throw new ArgumentException("must be positive integer", "y");
if (x == 0 || y == 0) return 0; // obvious quick-exit condition
// integer division
int xDivBy10 = x / 10;
int yDivBy10 = y / 10;
bool xIsSingleDigit = xDivBy10 == 0;
bool yIsSingleDigit = yDivBy10 == 0;
// base case
if (xIsSingleDigit && yIsSingleDigit)
{
return MultiplySingleDigits(x, y);
}
// otherwise, use grid multiplication recursively
// http://en.wikipedia.org/wiki/Grid_method_multiplication
if (xIsSingleDigit) // y must not be a single digit
{
return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10);
}
if (yIsSingleDigit) // x must not be a single digit
{
return (Multiply(xDivBy10, y) * 10) + Multiply(x % 10, y);
}
// else - x and y are both numbers which are not single digits
return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10); // the same code as the "if (xIsSingleDigit)" case
}
// technically, this algorith can multiply any positive integers
// but I have restricted it to only single digits as per the assignment's requirements/hint
private int MultiplySingleDigits(int x, int y)
{
if (x < 0 || x > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "x");
if (y < 0 || y > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "y");
if (x == 0 || y == 0) return 0; // base case
return x + MultiplySingleDigits(x, y - 1);
}
NOTES:
* operator but not for actually multiplying x and y, it is used to increase other sub-products by multiples of 10