Hi guys,
I'm trying to solve a problem recusrively. I'm asked to multiply two numbers with only using Addition,Subtraction and Comparison.
After looking around the internet, it seems that the Algorithm I should use is Egyptian Algorithm . Click Here
I would like some tips on how to solve this. What's going to be my stopping condition? I know I should stope when I have sum of equal the large number. But how would I check?
Maybe you would do better with the Russion Peasant algorithom - it's basically the same algorithm, but re-arranged so the iterative process and the stopping condition are much more obvious.
I thought about that, but Russion Peasant Uses division and it's not included in the question.
OK, sorry.
I wanted to update my question but it seems it's not possible. Anyway, The stopping condition is going to be when the smallest number reaches to zero.
For example:
13x30
1 -- 30
2 -- 60
4 -- 120
8 -- 240
16 -- 480 //we stope here because 16 is larger than 13
But now the question is, how do I find the result of the multiplication in java. Manually when you do it on paper, you will choose 8+4+1= 13 and their values 30+120+240=390 which is the answer.
How would I do that programatically ?
You need to create a table of double value and at the same time keeping track of the value you need for the total sum. The maximum value of the double value will never go above the multiplication value you want it to be.
/*
i.e. You want to do 13 x 30.
First, check if any of your multiplicand is equal to 0.
If so, return 0 and done with it.
Else, select a multiplicand to work with. (Suggestion is to pick the lower value.)
Now, attempt to create 2 dynamic arrays, one which is the double of 1, 2, 4, ...
and the other is the other multiplicand (for precalculation).
doubleList <- [1] // a dynamic array with 1, could be an ArrayList of Integer
doubleValue <- [theOtherMultiplicand]
Check if the most recent double value is less than the current number you want
to do the break down. Now, go through a loop.
// create table
multiplicand <- one of the selected multiplicand (not the other from dynamic array)
currentDoubleValue <- 1
currentOtherMultiplicand <- theOtherMultiplicand
add currentDoubleValue with currentDoubleValue
add currentOtherMultiplicand with currentOtherMultiplicand
while currentDoubleValue is less than or equal to multiplicand
extend doubleList with (currentDoubleValue)
extend doubleValue with (currentOtherMultiplicand)
add currentDoubleValue with currentDoubleValue
add currentOtherMultiplicand with currentOtherMultiplicand
end while
Now, go through the doubleList from the back to front and start subtracting from
the selected multiplicand
// do the total sum
currentValue <- multiplicand
sum <- 0 // the multiplcation result
index <- size of doubleList - 1
while currentValue is greater than 0
if (currentValue - doubleList[index]) is greater than or equal to 0
add doubleValue[index] to the sum
subtract currentValue with doubleList[index]
end if
decrease index by 1
end while
Now the sum is holding the multiplication result.
PS: The condition of while check only for the currentValue and not index because
index will never go lower than 0 before currentValue is equal to 0.
PSS: This concept should work with positive number multiplication only!
*/
The original requirement calls for a recursive solution, so presumably the list(s) will just become simple variables inside the recursive method. What hurts my brain is that the algorithm is essentially a 2-pass process that presumably maps to the before-the-recursive-call and after-the-recusive-call parts of the recursive method.
If I had more time now I'd get a big sheet of paper and work through a couple of really small examples, if I had more time now...
Yes, that's just a concept of how to work it out in an iterative fashion. :) Need to adapt that to a recursive call by passing at least 2 variables to the call. If use a recursive call, no need dynamic arrays at all. :)
let me try:
let as say you want to multiply 5 with 6.
upon first invocation of the method, add 5 to the first input param (that is five), and subtract one from 6. do this as long as the second param is bigger than 1. this, I believe, would be your recursive method. next time I comment, I write code. But writing code is against the rules, so brace yourselves :P
P.S. upon first invocation of the method, add 5 to the first input param (that is five), and subtract one from 6, and add to this the invocation of the method with 5 remaining the same, and pass for the second parameter whatever you get from 6 - 1 (the second parameter subtracted)
After I tried implementing it, the easiest way to deal with is to pass an integer array containing necessary arguments to the recursive call. That way, you could modify the value inside while going through the build & cumulate the result.
@bibiki, I am not sure how your method works. Still, I can see that it will be very slow because you are dealing with 1 each time...
Thank you so much guys for all this usfual and helpful discussions/answers. And special thanks to @Taywin for her excellent explination as usual.
I think I'm going to try @bibiki's method tomorrow. @Taywin's method I'm sure it will work but after contacting my instructure he said there is no need to use doublelists or tables. This got me thinking, am I even choosing the right algorithm to solve this problem. Will get back to you guys.
@sobias, after I implemented it, I didn't need to build a table but keep tracking the current value and the value after double in one integer inside the array. The array I passed in as argument to the recursive call is size of 4 containing the multiplicand, the cumulative value of the other multiplicant, the value of double index so far, and the sum. The sum will be updated while leaving the recursive call. But when I implemented it, I passed in the first value right away, so I had to adjust the value after the recursive call when a certain condition is met. I will try to draw an example tomorrow.
@taywin, well, the method will be slow. recursion is always slow. But, that is how recursion in this case should be implemented. let us assume the method signature is:
int recursive(int a, int b)
if we implement it recursively, for recursive(5, 6) there should be 6 invocations of the method, and the last to be invoked is the first to be completed... this I believe explains how the method works. the last invocation does not call the method anymore because the 6 must have become 1. I hope this makes any sense now. anyways. kind regards.
Just for fun I did this as well, using the Egyptian Algo. This scales as O(log n) instad of Bibiki's O(n), so it's well worth the effort.
Like Taywin I passed those working values as parameters (not in an array because that was hard to read, and because it was easier when each invocation had its own values, except for the remainder). Including some initialisation its only a dozen lines of very simple code. Interesting project!
Sorry for a little late. @Bibiki, now I see that it is a brute-force algorithm. Yes, your algorithm is correct. :) However, I would have to disagree on "recursion is always slow" statement. The purpose of using recursion is usually for implementation (could be style or readability). The factor that determine how fast/slow of a method is the algorithm used in the implementation. If you enter recursive(1, 10000000), how many loops do you expect it to be with the brute-force algorithm? :) Normally, brute-force algorithm has a problem with scalability. Don't get me wrong. Brute-force is not always bad. Often times, you need to learn from brute-force algorithm, and then develop a better algorithm from it. :)
Anyway, I reimplement the problem by passing regular variables (no array) in attempt to understand with James' implementation. Because of that, I need to call another recursive method inside the first recursive call. The first part is to find the highest 2^n value, and the second is to compute the sum. The pseudo code and example are below.
/*
multiplicand <- one of the multiplier value
theOtherMultiplicand <- the other multiplier value
step <- step index value so far, could be 0 or 1
// keep looking for the highest 2^n value
recursiveBuild(multiplicand, theOtherMultiplicand, step)
if step is less than or equal to zero
recursiveBuild(multiplicand, theOtherMultiplicand, 1) // initial call
end if
dblIdx <- 1
for (int i=1, i less than step, i++)
double the value of dblIdx // build 2^(n-1) comparison index
end for
if (dblIdx+dblIdx) less than or equal to multiplicand
return recursiveBuild(multiplicand, theOtherMultiplicand, step+1)
else
return recursiveSum(multiplicand, theOtherMultiplicand, step, 0)
end if
end recursiveCall
//
recursiveSum(multiplicand, theOtherMultiplicand, step, sum)
if multiplicand is greater than zero
dblIdx <- 1
for i=1, i less than step, i++
double the value of dblIdx // build 2^(n-1) comparison index
end for
if multiplicand is greater than or equal to dblIdx
subtracted multiplicand by dblIdx
innerSum <- theOtherMultiplicand
for i=step-1, i greater than 0, i--
double value of the innerSum // build the sum
end for
add sum with the innerSum
end if
return recursiveSum(multiplicand, theOtherMultiplicand, step-1, sum)
else
return sum
end if
end recursiveSum
7x20
[7, 20, 0]
multiplicand is 7
theOtherMultiplicand is 20
step 0
call recursiveBuild with multiplicand, theOtherMultiplicand, step
[7, 20, 0]
build dblIndex using step, dblIndex = 1
dblIndex+dblIndex <= 7 YES
call recursiveBuild with multiplicand, theOtherMultiplicand, step+1
[7, 20, 1]
build dblIndex using step, dblIndex = 2
dblIndex+dblIndex <= 7 YES
call recursiveBuild with multiplicand, theOtherMultiplicand, step+1
[7, 20, 2]
build dblIndex using step, dblIndex = 4
dblIndex+dblIndex <= 7 YES
call recursiveBuild with multiplicand, theOtherMultiplicand, step+1
[7, 20, 3]
build dblIndex using step, dblIndex = 8
dblIndex+dblIndex <= 7 NO
call recursiveSum with multiplicand, theOtherMultiplicand, step, 0
[7, 20, 3, 0]
multiplicand is greater than 0
build dblIndex using step, dblIndex = 4
multiplicand is greater than dblIndex, subtract, multiplicand is now 3
compute innerSum which is equal to 80 ((20+20)+(20+20))
add innerSum to sum, sum is now 80
call recursiveSum with multiplicand, theOtherMultiplicand, step-1, 0
[3, 20, 2, 80]
multiplicand is greater than 0
build dblIndex using step, dblIndex = 2
multiplicand is greater than dblIndex, subtract, multiplicand is now 1
compute innerSum which is equal to 40 (20+20)
add innerSum to sum, sum is now 120 (80+40)
call recursiveSum with multiplicand, theOtherMultiplicand, step-1, 0
[1, 20, 1, 120]
multiplicand is greater than 0
build dblIndex using step, dblIndex = 1
multiplicand is greater than dblIndex, subtract, multiplicand is now 0
compute innerSum which is equal to 20
add innerSum to sum, sum is now 140 (120+20)
call recursiveSum with multiplicand, theOtherMultiplicand, step-1, 0
[0, 20, 0, 140]
multiplicand is NOT greater than 0
return the sum // <-- 140
*/
Since OP is going with the brute force approach, I guess there's no harm in posting this code....
<snip>
It will multiply any two Java ints with a max of 31 recursions, vs 2 billion for the brute force solution.
<On second thoughts, maybe it's not a good idea to post the complete code here. Let's just say it's very small and fast, and you will get a real kick of satisfaction when you do it yourself. JC>
Thank you so much guys. I've implemented both @bibiki's method and @Taywin methods. However, I find @bibiki's easier although it costs more than @Taywin's . I asked for tips and you gave me more than what I wanted. Really apprecaite it!!
@JamesCherrill I think it's not a good idea to post the code here. I'm sure many will look for this algorethim and the code just ruins the enjoyment of writing it :)
Again Thanks everyone.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.