Alternate Division Algorythm

[BMAD]

Prove (verify) or disprove the following algorithm for division

The algorithm is quite simple.

1. Write the two numbers (each 2 digits in length) that you are multiplying side by side.

2. Create a column under the number on the right. Each entry should be half of the entry above it, ignoring any fractional amounts (example: if the number 5 is the right column, the number below it should be 2), stopping when the number 1 appears.

3. Create a column under the number on the left. Each entry should be twice the entry above it. Stop when the left column has the same number of entries as the right column.

4. Cross out any number in the left column whose corresponding number in the right column is even.

5. Add the numbers in the left column which are not crossed out.

The number you find in step 5 is the product of the two numbers you started with!

Example:

32 25

64 12

128 6

256 3

512 1

-------

800

So 32 x 25 = 800.

Edited July 20, 2013 by BMAD

[DeGe]

Effectively, you are adding the numbers on the left. Now, all the numbers on the left are doubles (even) except the first number that you start with. So, irrespective of the number you have on the right, the addition on the left will be odd if you start with an odd number on the left.

Therefore, this algorithm is not correct.

[BMAD]

Try an odd case and see if you are correct.

[BMAD]

Just realized that I meant multiplication in the title, lol...oops

[Barcallica]

Effectively, you are adding the numbers on the left. Now, all the numbers on the left are doubles (even) except the first number that you start with. So, irrespective of the number you have on the right, the addition on the left will be odd if you start with an odd number on the left.

Therefore, this algorithm is not correct.

That is not true.

if the first number number on the right is even then that row will be crossed, leaving sum of left column even not odd. So it works in every possible pair.

Actually this has nothing to do with the number on the left. And also has something to with the fact that every number can be put as sum of exponents of 2.

[BMAD]

Excellent...continue

[Barcallica]

what we are doing on the right side is what we do to convert from decimal to binary. So what we are trying to prove is "if n in decimal equals a

₁a₂....a_k in binary then prove in decimal n=a₁*2^k-1+a₂*2^k-2......+a_k-1*2+a_k, which is another way we convert dec to bin. Maybe someone help me proving this conversion methods???

[BMAD]

what we are doing on the right side is what we do to convert from decimal to binary. So what we are trying to prove is "if n in decimal equals a

₁a₂....a_k in binary then prove in decimal n=a₁*2^k-1+a₂*2^k-2......+a_k-1*2+a_k, which is another way we convert dec to bin. Maybe someone help me proving this conversion methods???

this is one approach

i found it easier to prove it geometrically

[Barcallica]

what we are doing on the right side is what we do to convert from decimal to binary. So what we are trying to prove is "if n in decimal equals a

₁a₂....a_k in binary then prove in decimal n=a₁*2^k-1+a₂*2^k-2......+a_k-1*2+a_k, which is another way we convert dec to bin. Maybe someone help me proving this conversion methods???

this is one approach

i found it easier to prove it geometrically

Interesting, I have no idea how you could connect it to geometry.

[BMAD]

Let's examine a case where a power of 2 is one of the numbers say.... 8 x 9

equivalently we can write it 9 x 8 so,

9 8

18 4

36 2

72 1

so the answer is 72.

Notice that

9 x 8

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

x x x x x x x x

18 x 4

x x x x x x x x x x x x x x x x

x x x x x x x x x x x x x x x x

x x x x x x x x x x x x x x x x

x x x x x x x x x x x x x x x x

36 x 2

x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

72 x 1

x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

Notice that if one of the numbers is a power of two, then i am simply playing with factors of 72 until i arrive at the identity of 72 x 1 = 72

Similarly this method can be applied to the other cases to verify. Other cases being (odd & even but not power of two); (odd & odd); and (even but not power of two & even but not power of two)

Remember this method only extends to integers > 0