Russian Peasant Multiplication Python 3.3

Question

I need help with a program in python 3.3 that is supposed to do Russian peasant multiplication/ancient Egyptian multiplication. The assignment says," If "A" and "B" are the two integers to be multiplied, we repeatedly multiply "A" by 2 and divide "B" by 2, until "B" cannot divide any more and is not zero (integer division). During each set of multiplying "A" and dividing "B", if the value of "B" is an odd number, you add whatever the "A" value is to a total. At the end, the sum of all the "A" values (when "B" is odd) should be equal to the product of the original "A" and "B" inputs. In short, sum up all the "A" values for which "B" is odd and it will be equal (or close) to the product of "A" and "B".

edit

I may have phrased some of the question wrong.

Here is an example:

If "A" is 34, and "B" is 19, multiplying "A" by two and dividing "B" by two each line.

"A" "B"

(34) (19) ("B" is odd, add "A" to total)

(68) (9) ("B" is odd, add "A" to total)

(136) (4) ("B" is even, ignore "A" value)

(272) (2) ("B" is even, ignore "A" value)

(544) (1) ("B" is odd, add "A" to total)

When you sum all the values of "A" for which "B" is odd, you get (34 + 68 + 544 = 646), which is equal to just multiplying "A" and "B", (34 * 19 = 646).

The part I'm having trouble with is adding "A" to a total whenever "B" is an odd number.

This is what I have so far,

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

while y != 0:
    if (y%2 != 0):
        x*2
        y//2
        answer == answer + x
    if (y%2 == 0):
        x*2
        y//2
print("the product is",(answer))

I'm very new to python and programming, so any help and/or explanations of why its wrong would be greatly appreciated.

Caramelize

Your code doesn't reassign either y or x. You need to replace x*2 and y//2 with x = x*2 and y = y//2 respectfully. – Apposition

Nevermind. I think I just misunderstood your explanation. – Hap

You are not assigning to answer either. You are testing if answer is equal to answer + x. Use a single = to assign, or better yet, use in-place addition: answer += x. – Theophany

Make 2 a variable so you can test if it works with other values. Extra points may be given – Stibnite

how can i make it repeat the program when i ask the user if they want to run the code again with new inputs? – Caramelize

Answer 1

you need to add x to answer first, then update x

here is the correct code

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

while y != 0:
   if (y%2 != 0):
      answer=answer+x
      x=x*2
      y=y//2
   if (y%2 == 0):
      x=x*2
      y=y//2

print("the product is",(answer))

Bitters

Calculation of the next x and the next y is the same in both if commands. This way, it can be moved outside the if (the values are calculated in each loop and always the same way). Then the second if becomes empty and can be removed. Then the y % 2 != 0 is the same (but more obscured version) as y % 2 == 1. The later is just explicit conversion to bool, while the y % 2 is the value that will be interpreted as True in boolean context. – Matamoros

I knew that when I wrote that answer. I was trying to make minimal change to asker's question so that he could understand better where he was wrong. – Bitters

Answer 2

I'm not familiar with the algorithm you are trying to implement, but I have made a few modifications to your code.

x = int(input("What is the first number? "))
y = int(input("What is the second number? "))
answer = 0

# != 0 is redundant: y is True if it is not 0
while y:
    # no need to have parentheses here
    if y % 2:
        # this needs to be an assignment, not a check for equality
        answer += x  # shorthand for answer = answer + x
    # These happen every time, so does not need to be inside the if
    # these also need to be an assignment, not just an expression
    x *= 2
    y /= 2
# total was never defined
print("the product is", (answer))

Mulkey

Answer 3

A side note. Frankly, I did not know about the algorithm until now. The more it surprises me it was used by ancient Egyptians or in old Russia. (Actually, I tend to believe that the Russian origin is more probable as it seem that Slavic nations are directly related to old Etrusks).

The old origin surprises me because it actually is a plain hand-made multiplication that you learned in the basic school. The only difference is that the numbers are converted to binary representation first. Rather machine oriented, isn't it? :)

For the numbers in the question, th 34 in decimal representation is equal to 100010 in binary, the 19 in decimal is 10011 in binary. Now the plain basic school multiplication on paper:

    100010
x    10011
------------
    100010   i.e. 100010 times 1
   100010        1000100 times 1
  000000        10001000 times 0
 000000        100010000 times 0
100010        1000100000 times 1
------------                   ^ binary digits of the multiplier
1010000110                       (reminder of division by 2)
                       ^ adding the zero means multiplying by 2
i.e. sum only when 1 is the reminder of division

It seems that the one who designed the metod (in ancient times) knew what the binary numbers are.

Matamoros

Answer 4

The last time you add x is when y is equal to 1. If you keep halving until the number reaches 0, it will take a very large number of iterations (logically, it will take forever).

Think about 2x2. If you double x to 4, and halve y to 1, x is your answer.

In other words, think of y as how many of x I need to yield answer. Since you can't multiply, only add/double/halve, you have a choice - you can wait until y is 2 and then add doubled value of x, OR you can wait until y is 1 and simply add value of x. The latter is simpler and clearer, that's all.

I think it's clearer in this case to use a while True loop:

def mult2(x, y):
    answer = 0
    while True:
        if y % 2:
            answer += x
        if y < 1:
            break
        x *= 2
        y //= 2
    print("the product is", answer)

Calling function recursively:

def mult2(x, y):
    """aka 'Russian peasant method'; allowed: addition, halving, doubling."""
    if y==1:
        return x
    else:
        add = x if y%2 else 0
        return mult2(x*2, y//2) + add

Saxtuba

Answer 5

the output is a normal mutiplication display. Please share the code where the output is also displayed showing the Russian Peasent method.

Output should be something like this:

If "A" is 34, and "B" is 19,

(34) (19) ("B" is odd, add "A" to total)

(68) (9) ("B" is odd, add "A" to total)

(136) (4) ("B" is even, ignore "A" value)

(272) (2) ("B" is even, ignore "A" value)

(544) (1) ("B" is odd, add "A" to total)

When you sum all the values of "A" for which "B" is odd, you get (34 + 68 + 544 = 646), which is equal to just multiplying "A" and "B", (34 * 19 = 646).

Werra

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Moneywort