Showing posts with label multiplication. Show all posts
Showing posts with label multiplication. Show all posts

Thursday, March 01, 2007

Follow up: A fun way to multiply numbers

Here's python code to multiply numbers as mentioned in the A fun way to multiply numbers blog entry.

NOTE: I am not a python expert, so there could be some obvious bugs in this simple piece of code. As always use at your own risk.


print "Input the first number"
a=input()
print "Input the next number to be multiplied with %d" %a
b=input()
res=0
while a:
if a & 0x1:
res = res + b
a = a >> 1
b = b << 1

print "The result is %d\n" %res

A fun way to multiply numbers



Reading through the algorithms book by Papadimitriou, et. al has been great fun. I learn a great fun way to multiply (apparently known from ancient times). Let's say we intend to multiply 13 and 23, the procedure is quite straight forward. Write down 13 and 23 besides each other
13 23
6 46
3 92
1 184

The first column is divided by two (with rounding) and the second one is multiplied by two


13 23
6 46
3 92
1 184

Strike out the numbers with even numbers in the first column

Now we just add up the numbers in the right column to obtain 299. That's quite easy right? The really cool thing about this approach is that is easy to implement using computers (hint: left shift and right shift multiply and divide the number by 2 (with rounding taken care of))

privacy

Some of the policy from the app automation refers to https://rclone.org/privacy/ if you are a general blog reader, follow Google's polic...