Egyptian algorithm implementation in java

Question

I want to find multiplication of two numbers in Java recursively using only addition, subtraction and comparison. So, I googled, and I found an Egyptian Algorithm that meets the requirements of the question.

However, I am not sure how to find the result of the multiplication after reaching the base case .

Example:

 13 x 30 1 -- 30 2 -- 60 4 -- 120 8 -- 240 //we stop here because the double of 8 is larger than 13 

To find the result, we add the numbers from the left column equal to 13, which they are 1+4+8 , and on the other hand we add its opposite numbers from the right column , which they are 30+120+240 = 390 , which is the result.

And now how to program the last part? how to check which numbers to add? I hope you guys understand my point. Hints are needed only.

Answer 1

Ok, I did this using the Brute Force algorithm. This is BigO- (n). I am sure that there is a more efficient way to implement it. Presently. I agree with that.

Thanks guys!

Answer 2

Here's the pseudo code to solve the problem:

 function egyptian(left, right) prod := 0 while (left > 0) if (left is odd) prod := prod + right left := halve(left) right := double(right) return prod 

In principle, instead of waiting until the end, it is easier to check each line of the template as it is created and summarize if it belongs in the output. I discuss this algorithm on my blog .

Answer 3

Loop through the generated results in reverse order

Each time, if your remainder of the factor (which starts with your multiplier) is greater than the number in the left column, subtract the left column from your factor and add the right column to your result (which starts from zero).

Answer 4

You may have found this Wikia article.

Look at the last part of the section called "decomposition." You will find a sub-algorithm that you must implement.