Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Multiplication Using +, -, and 1/x


Date: 10/25/2000 at 22:33:27
From: Jonathan Silverman
Subject: Puzzle: mathematical operations

Is there a way to multiply two numbers using the addition, 
subtraction, and reciprocal functions only?

Which means, I guess, express AB in terms of a function of A and B 
using +, -, 1/A and 1/B.

I have a gut feeling that there is a way to do it, but after hours of 
juggling, I couldn't find the answer.

Please try to quench my curiosity.

Jonathan


Date: 10/25/2000 at 22:56:01
From: Doctor Peterson
Subject: Re: Puzzle: mathematical operations

Hi, Jonathan.

Here's a place to start:

      1     1    A + B
     --- + --- = -----
      A     B     AB

See if that leads you to a formula for AB using only "+" and 
"reciprocal."

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   


Date: 10/25/2000 at 23:20:26
From: Jonathan Silverman
Subject: Reply

Thanks for your prompt reply.

I had already tried the step you suggested, to start from 1/a + 1/b = 
(a+b)/ab and further use + and 1/x operations, but it did not lead me 
to anything.

Could you please help me a little more? This problem has been in my 
head now for a long time.

Jonathan


Date: 10/26/2000 at 16:52:41
From: Doctor Rick
Subject: Re: Again puzzle: mathematical operations

Hi, Jonathan.

We're still thinking about your problem, which we misinterpreted at 
first. In the meantime, I have a question and some comments. 

The question is: Was this problem posed to you as a problem with a 
known solution, or are you just hoping there is a solution?

I wonder also, is an iterative algorithm acceptable, as opposed to a 
closed-form identity for AB? You'll see why I ask in a moment.

One comment regards your interpretation of the problem. The solution 
isn't necessarily restricted to +, -, 1/A, and 1/B. It could contain, 
for instance, 1/(A+B), or the reciprocal of any function of A and B 
(provided that function contains only +, -, and other reciprocals).

When you say you were advised to "start from 1/a + 1/b = (a+b)/ab and 
further use + and 1/x operations," this may be a misunderstanding. The 
idea was not to take this expression and do more operations on it, but 
to solve it for ab and see if this leads anywhere.

     ab = (a+b) * 1/(1/a + 1/b)

This involves additions and reciprocals, but unfortunately it also 
involves a multiplication. As of now, I don't see what you could do 
with it.

Here is my main comment. Historically, peoples have used various 
algorithms for multiplication. You can see two such algorithms, among 
the earliest known, on this Web page:

   Babylonian and Egyptian mathematics
   MacTutor History of Mathematics Archive
   http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Babylonian_and_Egyptian.html   

The Babylonian algorithm makes use of a closed-form identity,

     A * B = ((A + B)/2)^2 - ((A - B)/2)^2

By this means, multiplication of integers can be reduced to taking the 
difference between two entries in a table of squares. Entry N of the 
table has the value (N/2)^2.

The Egyptian algorithm is an iterative method, like our method of 
multiplication, but it does not require memorization of multiplication 
tables. The only operations involved are addition and subtraction. 
That makes it a solution to your problem, if iterative methods are 
accepted. It's probably not what you want, because it doesn't make use 
of reciprocals, but it's fascinating. This ancient method also has 
strong connections to the method used in binary computers.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   


Date: 10/26/2000 at 17:42:29
From: Jonathan Silverman
Subject: Re: Puzzle: mathematical operations

Thanks for your comments, Dr. Rick. I think I better rephrase the 
question in this way:

Suppose we have a calculator with just the operator buttons +, - and 
1/x. Can we use this calculator to perform multiplication?

I think now it will be clear why I wanted to find a closed identity 
for AB. But the problem doesn't say there has to be solution. I will 
just have to be content with an explanation that there is no solution.

BUT the Babylonian and Egyptian methods are excellent. I enjoyed 
reading them immensely. Especially the Egyptian method can be 
performed iteratively using a piece of paper, pen and the calculator, 
assuming the person does not know how to multiply, without using 
square tables.

But we can do multiplication the long way on this calculator. For 
example, to find 50*20, we add 50 twenty times using the + button 
only.

It will be great if we can find a closed identity for AB to compute it 
using our faulty calculator, that is, if it exists.

Thanks!
Jonathan
    


Date: 10/14/2013 at 23:08:45
From: Bob
Subject: Multiplication Using +, -, and 1/x

I just came across this Dr. Math question from October 2000 and was
surprised that the answer had never been provided.

I thought of and solved it about 30 years ago in the following form:

Write an exact expression for the ratio e/pi containing only the constants
e, pi, and 1, and using only the operations of adding, subtracting, and
taking the reciprocal.

Going in, it's not clear whether the problem even has a solution -- but I
used letters for intermediate results to make it easier to write it this
way:

   e/pi = 1/r + 1/r - 1 - 1/pi - e
   
Here,
   
   r = 1/(e + 1) + 1/s - 1/t
   
   s = 1 + 1/pi
   
   t = 1 + 1/u + 1/v
   
   u = pi + 1/e
   
   v = e + 1/pi



Date: 10/15/2013 at 10:52:54
From: Doctor Peterson
Subject: Re: Multiplication Using +, -, and 1/x

Hi, Bob.

It took a little work to put this together and see that it really does
what you say. For clarity, I'll use prime notation (e.g., a') to represent
taking the reciprocal, and then carry out the proof.

Suppose we want to find x/y. Working from bottom to top of your
explanation, you've done the following steps:

       on calculator                            simplified

   v = x + y'                       = x + 1/y = (xy+1)/y

   u = y + x'                       = y + 1/x = (xy+1)/x

   t = 1 + u' + v'  = 1 + x/(xy+1) + y/(xy+1) = (xy+1+x+y)/(xy+1)
  
So,

   t = 1 + (y+x')' + (x+y')'                  = (x+1)(y+1)/(xy+1)

   s = 1 + y'                       = 1 + 1/y = (y+1)/y

   r = (x+1)' + s' - t'
     = 1/(x+1) + y/(y+1) - (xy+1)/((x+1)(y+1)
     = [(y+1) + (x+1)y - (xy+1)]/((x+1)(y+1))
     = [y + 1 + xy + y - xy - 1]/((x+1)(y+1)) = 2y/((x+1)(y+1))

Final result:

   r' + r' - 1 - y' - x = 2(x+1)(y+1)/(2y) - 1 - 1/y - x
                        = (x+1)(y+1)/y - y/y - 1/y - xy/y
                        = [xy + x + y + 1 - y - 1 - xy]/y
                        = x/y

If we put it all together into one calculation (that is, don't allow our
calculator to have storage registers), it is

   x/y = r' + r' - 1 - y' - x

       = [(x+1)' + s' - t']' + [(x+1)' + s' - t']' - 1 - y' - x

       = [(x+1)'+(1+y')'-(1+(y+x')'+(x+y')')']' +
         [(x+1)'+(1+y')'-(1+(y+x')'+(x+y')')']' - 1 - y' - x

I'm impressed!

But I wonder if someone out there has a shorter solution. We may find out ...

I'm very curious how you came up with this. It looks like you carried out
some of the thoughts I had the first time around, so many years ago, but
wasn't able to bring to completion. I can see some important tricks that
probably guided your thinking, working from both ends of the problem; but
I didn't have the patience or confidence in the possibility of doing it
that you must have had.

- Doctor Peterson, The Math Forum
  
  


Date: 10/15/2013 at 13:44:18
From: Bob
Subject: Thank you (Multiplication Using +, -, and 1/x)

Thanks.

You can make it slightly shorter by giving the result for xy (as in the
original question), which lets you replace y' with y (and y with y').

I came up with it by playing around with various expressions until it fell
out. It was long enough ago that I don't remember any specific steps.



Date: 10/15/2013 at 16:30:33
From: Doctor Peterson
Subject: Re: Thank you (Multiplication Using +, -, and 1/x)

Hi, Bob.

Yes, I'd neglected to look at the multiplication question itself. Here's
your division (using one level of stored value):

   z = (x + 1)'  +  (1 + y')' - (1 + (y + x')' + (x + y')')'

   x/y = z' + z' - 1 - y' - x

Changing this to a multiplication,

   xy = x/y' = z' + z' - 1 - y - x

Here,

   z = (x + 1)' + (1 + y)' - (1 + (y' + x')' + (x + y)')'

This slightly altered version makes it neater:

   z = (x + 1)' + (y + 1)' - ((x' + y')' + (x + y)' + 1)'

   xy = z' + z' - x - y - 1

Here's the proof for this version:

        1     1           1             1     1           1
   z = --- + --- - ----------------- = --- + --- - -----------------
       x+1   y+1     1       1         x+1   y+1    xy       1
                   ----- + ----- + 1               ----- + ----- + 1
                   1   1   x + y                   x + y   x + y
                   - + -
                   x   y

         1       1         x + y          1       1         x + y
     = ----- + ----- - -------------- = ----- + ----- - --------------
       x + 1   y + 1   xy + x + y + 1   x + 1   y + 1   (x + 1)(y + 1)

       (y + 1) + (x + 1) - (x + y)         2
     = --------------------------- = --------------
             (x + 1)(y + 1)          (x + 1)(y + 1)

          (x + 1)(y + 1)   (x + 1)(y + 1)
   PROD = -------------- + -------------- - x - y - 1
                2                2

        = (x + 1)(y + 1) - x - y - 1

        = xy + x + y + 1 - x - y - 1 = xy

That makes it almost seem simple!

Now, staring at that a bit, it occurs to me to replace x and y with x - 1
and y - 1 so that the final step would be merely z' + z':

   z = x' + y' - (((x - 1)' + (y - 1)')' + (x - 1 + y - 1)' + 1)'

   PROD = z' + z'

The proof becomes:

       1   1             1             1   1              1
   z = - + - - --------------------- = - + - - ----------------------
       x   y       1         1         x   y   (x-1)(y-1)     1
               --------- + ----- + 1           ---------- + ----- + 1 
                1     1    x+y-2                 x+y-2      x+y-2
               --- + ---
               x-1   y-1

        1     1       x + y - 2         1     1    x + y - 2
     = --- + --- - ----------------  = --- + --- - ---------
        x     y    xy-x-y+1+1+x+y-2     x     y       xy

       y + x - (x + y - 2)    2
     = ------------------- = --
                xy           xy

          xy   xy
   PROD = -- + -- = xy
           2    2

I'm not sure which is nicer; there may well be a further simplification.

But here's one more thought: this method doesn't work if x or y is 0 or 1,
or if their sum is 2. The previous version doesn't work if x or y is 0 or
-1, or if they are opposites. So neither is perfect; and this is a natural
consequence of having to work with the reciprocal.

- Doctor Peterson, The Math Forum
  
  


Date: 10/15/2013 at 19:15:44
From: Bob
Subject: Thank you (Multiplication Using +, -, and 1/x)

Your final formula looks neat to me. And the cases where it breaks down
are trivial cases where we don't need the formula to figure the product.
If x or y is 0 or 1 or -1, it's obvious. Otherwise, if x + y = 2, 
xy = x + x - x^2, which we can calculate because 
x^2 = (x' - (x + 1)')' - x.



Date: 10/15/2013 at 22:21:47
From: Doctor Peterson
Subject: Re: Thank you (Multiplication Using +, -, and 1/x)

Hi, Bob.

That's a nice addition: You can use my final formula if x is not equal to
0, 1, or 2 - y, and in those exceptional cases,

   if x = 0 or y = 0,      then      xy = 0

   if x = 1,               then      xy = y

   if y = 1,               then      xy = x

   if x + y = 2,           then      xy = x + x + x - (x' - (x + 1)')'

That last expression comes about because it is equal to

             1
   3x - ----------- = 3x - x(x + 1) = 2x - x^2 = x(2 - x) = xy
         1      1
        --- - -----
         x    x + 1

- Doctor Peterson, The Math Forum
  



Date: 10/16/2013 at 02:40:57
From: Bob
Subject: Thank you (Multiplication Using +, -, and 1/x)

To be picky, x = -1 is also a special case due to the (x + 1)' in your
last expression.



Date: 10/16/2013 at 16:45:19
From: Doctor Peterson
Subject: Re: Thank you (Multiplication Using +, -, and 1/x)

Maybe you're referring to the version before the last, unless I'm really
missing something. I meant the VERY last:

   z = x' + y' - (((x - 1)' + (y - 1)')' + (x - 1 + y - 1)' + 1)'

   PROD = z' + z'

The only denominators I see there or in the process of simplification are
x, y, x - 1, y - 1, and x + y - 2.

As a check, let's calculate the product of -1 and -1 and see if it fails:

   z = (-1)' + (-1)' - (((-1-1)' + (-1-1)')' + (-1-1+-1-1)' + 1)'
     =  -1   +  -1   - (( -0.5   +  -0.5  )' +     (-4)'    + 1)'
     =  -1   +  -1   - (       -1            +     -0.25    + 1)'
     =  -1   +  -1   - (-0.25)'
     =  -1   +  -1   - (-4)
     =  2

   PROD = z' + z' = 2' + 2' = 0.5 + 0.5 = 1

In the next to last version, the excluded values are 0, -1, and x + y = 0.

- Doctor Peterson, The Math Forum
  



Date: 10/16/2013 at 17:27:06
From: Bob
Subject: Thank you (Multiplication Using +, -, and 1/x)

Your "last expression" is the one for the special case x + y = 2. What
happens when you use it to get the product of 3 and -1?



Date: 10/16/2013 at 17:59:34
From: Doctor Peterson
Subject: Re: Thank you (Multiplication Using +, -, and 1/x)

Hi, Bob.

OK, I see -- you weren't saying that the general formula itself needs a
special case for -1, but that the special case for 2 + y = 2 itself needs
a special case, because IT doesn't work for -1. I took "last expression"
to mean "final formula," rather than what I had just called the "last
expression" in the previous message. And before that, your first mention
of -1 being treated as a special case came before you stated the formula
including x + 1, which is the only thing that makes -1 (sometimes, and for
x only) a special case.

As it stands, we have this:

If x and y are not 0, 1, or -1, and x + y is not 2, then

   z = x' + y' - (((x - 1)' + (y - 1)')' + (x - 1 + y - 1)' + 1)'
   PROD = z' + z'

If x = 0 or y = 0, then

   PROD = 0

If x = 1, then

   PROD = y

If y = 1, then

   PROD = x

If x = -1, then

   PROD = -y

If x + y = 2 and x is not -1, then

   PROD = x + x + x - (x' - (x + 1)')'

But something else just occurred to me. The problem doesn't say that the
negation key (as opposed to subtraction) is usable. So you might have to
use "0 - x" instead of "-x" (and negative numbers for input would have to
have been entered the same way).

- Doctor Peterson, The Math Forum
  



Date: 10/16/2013 at 18:31:18
From: Bob
Subject: Thank you (Multiplication Using +, -, and 1/x)

Needing "0 - x" didn't occur to me, and someone will probably object if
you don't mention it.

Associated Topics:
High School Number Theory
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/