Alternate Division Algorythm

10 posts in this topic

Posted (edited) · Report post

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 by BMAD
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

Try an odd case and see if you are correct.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

Excellent...continue

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

1a2....ak in binary then prove in decimal n=a1*2k-1+a2*2k-2......+ak-1*2+ak, which is another way we convert dec to bin. Maybe someone help me proving this conversion methods???
0

Share this post


Link to post
Share on other sites

Posted · Report post

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

1a2....ak in binary then prove in decimal n=a1*2k-1+a2*2k-2......+ak-1*2+ak, 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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

1a2....ak in binary then prove in decimal n=a1*2k-1+a2*2k-2......+ak-1*2+ak, 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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.