The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

[OT?] Mini-challenge
Message #1 Posted by Eduardo Duenez on 23 Feb 2008, 11:57 p.m.

I run a math problem-solving seminar for college students and we ran across this problem in yesterday's session. Since it is loosely related to calculators and I don't know a very simple solution, I'm proposing it as a mini-challenge.

If you have a calculator that can *only* add, subtract and reciprocate ("1/x" key), but not multiply or divide, is it still possible to multiply two numbers?

I know one solution and I'm willing to share it, but let's give it a day or two and see what you all have to say...

Eduardo

      
Re: [OT?] Mini-challenge
Message #2 Posted by Allen on 24 Feb 2008, 12:56 a.m.,
in response to message #1 by Eduardo Duenez

This is the same as a micro-processor multiply where you basically use one number as the loop counter and re-use the other as the addend. Example: Multiply 4 by 5: 

 
4     ; first occurance
4 +   ; second etc... 
4 +
4 +
4 +   ; nth occurance (here the 5th) 
====
20
so 4x5=20.

Is this what you mean? Obviously this only works well if at least one number is an integer.

For non-integers it is a little more difficult. Repeat the above process for the integer part of A multiplied by B , then use your slide rule :-) to multiply the fractional part of A by B and add the partial sum to the former with the calculator. :) haaa! (an age-appropriate post for the forum, yes?)

            
Re: [OT?] Mini-challenge
Message #3 Posted by Mad Dog ebaycalcnut on 24 Feb 2008, 10:06 a.m.,
in response to message #2 by Allen

Use the calculator as a straightedge and do multiplication using this method:

Neat video on using lines to do multiplication

                  
Re: [OT?] Mini-challenge
Message #4 Posted by Howard Lazerson on 24 Feb 2008, 4:18 p.m.,
in response to message #3 by Mad Dog ebaycalcnut

SAW THE VIDEO, BABBAGE WOULD HAVE LOVED IT!

      
Re: [OT?] Mini-challenge
Message #5 Posted by Egan Ford on 24 Feb 2008, 2:31 a.m.,
in response to message #1 by Eduardo Duenez

If A and B were decimal numbers, and C = AB, then, C=A(I + F), where I is the integer part and F the fractional part. You can add up A, I times, then you are left with AF, where F is < 1. If R = 1/F, then AF = A/R. You can then use division by subtraction to add to that to AI. Then you have the repeated processes of adding up the remainder 10 times and doing division by subtraction to get more fractional digits.

Dismal process. I'd use pen and paper to multiply the two numbers.

Edited: 24 Feb 2008, 3:05 a.m. after one or more responses were posted

            
Re: [OT?] Mini-challenge
Message #6 Posted by Allen on 24 Feb 2008, 2:36 a.m.,
in response to message #5 by Egan Ford

This is why I think all calculators should have LOG and ALOG. Then you could use LOG(A)+LOG(B)= A*B or with division: LOG(A)-LOG(B)= A/B.

                  
Re: [OT?] Mini-challenge
Message #7 Posted by Marcus von Cube, Germany on 24 Feb 2008, 3:48 a.m.,
in response to message #6 by Allen

Quote:
This is why I think all calculators should have LOG and ALOG. Then you could use LOG(A)+LOG(B)= A*B or with division: LOG(A)-LOG(B)= A/B.
You need to ALOG your results! ;)

ALOG(LOG(a)+LOG(b))=ab

      
Re: [OT?] Mini-challenge
Message #8 Posted by Namir on 24 Feb 2008, 5:31 a.m.,
in response to message #1 by Eduardo Duenez

This may seem to be a long shot, but here we go.

Treat each number as a polynomial that adds each terms that are made up of each digit (or zero) multiplied by a positive or negative power of ten. This polynomial representation will handle real numbers with fraction.

To multiple the two number collect like terms (with the same resulting power of tens). Each term has one or more product of integers to be multiplied. Use repeated addition to perform multiplication. Maintaining a running total. If you have a running total greater than 9 then you need to carry over the grand sum - 10 to the term with the next power of ten. You start with the smallest power of ten and work your way up.

This method uses ONLY addition but it's a bit messy!!!

Namir

      
Suggestions/clarification
Message #9 Posted by Eduardo Duenez on 24 Feb 2008, 2:48 p.m.,
in response to message #1 by Eduardo Duenez

I've seen the contributed ideas so far and I think it's probably good to clarify the challenge a bit.

It *is* possible to compute the product xy of two numbers x,y using only addition, subtraction, and reciprocation. For instance, one could use the standard algorithm that multiplies every digit of x by every digit of y---this would require nothing but repeated addition. However, if this were implemented, say, as a program, then that program would need to access each digit of x,y and contain the multiplication tables (e.g., the programmer would need to tell the program that 4 times 5 is 20, and so on!) This is a valid answer given the way the problem was phrased, but it's not what I had in mind when asking the question.

So here's the challenge, rephrased:

Find a procedure to multiply two numbers x,y using only a finite number of additions, subtractions, and reciprocations. The proposed algorithm should only perform operations on the numbers x,y themselves (not, say, on isolated digits thereof).

I assure you all that the problem as stated has a solution, and I think it's quite interesting and not at all obvious. I'll post a slightly more helpful hint in a day or two if nobody has figured the problem out yet...

Eduardo

Edited: 24 Feb 2008, 2:50 p.m.

            
Re: Suggestions/clarification
Message #10 Posted by Paul Dale on 24 Feb 2008, 5:35 p.m.,
in response to message #9 by Eduardo Duenez

Not useful as far as I can tell, but the multiplication is done kind of:

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

Can anyone think of a way to isolate the xy term?

- Pauli

                  
Re: Suggestions/clarification
Message #11 Posted by Namir on 24 Feb 2008, 9:58 p.m.,
in response to message #10 by Paul Dale

How did you go from x * y to 1/(1/x + 1/y)?

                        
Re: Suggestions/clarification
Message #12 Posted by Paul Dale on 24 Feb 2008, 10:04 p.m.,
in response to message #11 by Namir

Quote:
How did you go from x * y to 1/(1/x + 1/y)?

I didn't. That is the bit I haven't worked out. I was trying to get x * y from the operations available...

- Pauli

            
Re: Suggestions/clarification
Message #13 Posted by Thomas Klemm on 26 Feb 2008, 3:55 a.m.,
in response to message #9 by Eduardo Duenez

I only have a solution for the special case that both x and y are positive integers which are relatively prime.

Using the Euclidean algorithm we can find two integers p and q such that:

p * x + q * y = 1

Dividing both sides by x * y yields:

    1       1     1
p * - + q * - = -----
    y       x   x * y

If we perform the Euclidean algorithm with 1/x and 1/y instead of x and y we end up with 1/(x*y) as "GCD".

As an example multiply 5 * 7:

1   1    2
- - - = --
5   7   35

1    2    3
- - -- = -- 
7   35   35

 3    2    1
-- - -- = --
35   35   35

 2    1    1
-- - -- = --
35   35   35

 1    1    
-- - -- = 0
35   35 

        1
      ----
35 =    1
       --
       35
                  
Re: Suggestions/clarification
Message #14 Posted by Namir on 26 Feb 2008, 8:52 a.m.,
in response to message #13 by Thomas Klemm

In a previous message, Eduardo hinted at some algorithm that works with all integer and real numbers. So it's back to the drawing board for all of us.

I am very curious to see the solution.

Namir

                  
Re: Suggestions/clarification
Message #15 Posted by Paul Dale on 26 Feb 2008, 3:16 p.m.,
in response to message #13 by Thomas Klemm

Isn't the Euclidean gcd algorithm usually done using a mod operation. i.e. division?

I know it can be done via repeated subtraction but isn't the point of this exercise to not do that? Otherwise, repeated addition gives us the multiplication...

- Pauli

      
Spoiler alert: Hints
Message #16 Posted by Eduardo Duenez on 26 Feb 2008, 2:01 p.m.,
in response to message #1 by Eduardo Duenez

OK, I think it's time to post a hint or two to the original problem. As I slightly hinted at before, it is actually possible to write an algebraic formula in x,y which simplifies to the product xy and involves nothing but addition, subtraction and reciprocation. It's actually possible to obtain infinitely many different such formulae so the problem does *not* have a unique solution. In fact, part of my motivation for posting the challenge here was to see if other forumites would come up with a shorter formula...

Now, this fact by itself is not much of a hint. In fact Paul Dale and Namir seem to have already thought a bit along these lines. The formula I found is rather complicated and I cannot see how it could be easily guessed or obtained directly just trying to play with the variables x,y and the three available operations. Which brings me back to the hint...

* First try to find an algebraic formula that computes the *square* of a number x using the three allowed operations. This is the special case of the challenge when the two numbers are equal, and it's much easier because one needs to worry about only *one* variable, and not two. (Actually, what is needed in order to solve the problem the way I did is to find *half* of the square of x.) This problem is still a bit of a challenge, but far less so than the original one.

* Now your calculator, for all practical purposes, can add, subtract, reciprocate, and *square* (really, square and divide by 2). Use these operations to find the product xy. This part is easy.

Ultimately the two steps can be combined into a single and somewhat complicated-looking algebraic formula that solves the problem. When someone figures out how to solve the original problem (or in a couple of days if nobody does) I will post my original solution along with an HP-35s program implementing it.

Eduardo

            
Re: Spoiler alert: Hints
Message #17 Posted by Paul Dale on 26 Feb 2008, 3:43 p.m.,
in response to message #16 by Eduardo Duenez

Quote:
* First try to find an algebraic formula that computes the *square* of a number x using the three allowed operations.

I can do this bit pretty easily:

    1    1    x + 1 - x      1
    - - --- = --------- = -------
    x   x+1    x^2 + x    x^2 + x

Take the reciprocal and subtract x gives us:

     2      1
    x  = ------- - x
         1    1
	 - - ---
	 x   x+1

Now how to extend this to the product of two numbers...

- Pauli

            
Re: Spoiler alert: Hints
Message #18 Posted by Paul Dale on 26 Feb 2008, 4:47 p.m.,
in response to message #16 by Eduardo Duenez

Quote:
* Now your calculator, for all practical purposes, can add, subtract, reciprocate, and *square* (really, square and divide by 2). Use these operations to find the product xy. This part is easy.

Got this now:

    (x + y)^2   x^2   y^2
    --------- - --- - --- = x * y
        2        2     2

All that remains is to figure out an x^2/2 formula using the available functions or a formula for x * y using x^2 instead of x^2/2.

- Pauli

                  
Re: Spoiler alert: Hints
Message #19 Posted by Paul Dale on 26 Feb 2008, 5:02 p.m.,
in response to message #18 by Paul Dale

Turns out it is easy to go from my formula for x^2 to x^2/2:

        1
    --------- = x^2/2
     1     1
    --- + ---
    x^2   x^2

Problem solved.

- Pauli

                        
Re: Spoiler alert: Hints
Message #20 Posted by Paul Dale on 26 Feb 2008, 5:53 p.m.,
in response to message #19 by Paul Dale

A HP-15C program to multiply the X and Y registers using only -, + and 1/x:

    001-42,21,11    LBL A
    002-   44  0    STO 0
    003-   44  1    STO 1
    004-      34    X<>Y
    005-44,40, 1    STO+ 1
    006-   32  0    GSB 0
    007-   44  2    STO 2
    008-   45  0    RCL 0
    009-   32  0    GSB 0
    010-44,40, 2    STO+ 2
    011-   45  1    RCL 1
    012-   32  0    GSB 0
    013-45,30, 2    RCL- 2
    014-  43  32    RTN

    015-42,21, 0    LBL 0
    016-  43  20    x=0?
    017-  43  32    RTN
    018-   44  3    STO 3
    019-      15    1/x
    020-       1    1
    021-45,40, 3    RCL+ 3
    022-  43  20    x=0?
    023-   22  1    GTO 1
    024-      15    1/x
    025-      30    -
    026-      15    1/x
    027-45,30, 3    RCL- 3
    028-      15    1/x
    029-      36    ENTER
    030-      40    +
    031-      15    1/x
    032-  43  32    RTN

    033-42,21, 1    LBL 1
    034-      48    .
    035-       5    5
    036-  43  32    RTN

- Pauli

edit: fixed program based on Namir's feedback below

Edited: 27 Feb 2008, 8:32 p.m.

      
Re: [OT?] Mini-challenge
Message #21 Posted by Valentin Albillo on 26 Feb 2008, 4:21 p.m.,
in response to message #1 by Eduardo Duenez

Hi, Eduardo:

    The following code will multiply two numbers X, Y, using just addition, subtraction, and reciprocal ( INV):

    
     X+Y > U
     X-Y > V
     INV(INV(1+INV(U))+INV(1-INV(U))-2)+INV(2) > A
     INV(INV(1+INV(V))+INV(1-INV(V))-2)+INV(2) > B
     INV(INV(A)+INV(A))-INV(INV(B)+INV(B))

    where "INV" is the reciprocal, and ">" is the assignment operation (STO in the HP35S, or U = X+Y in BASIC).

    The expression is mathematically exact but accuracy is quickly lost for actual numerical computations involving large arguments.

Best regards from V.

            
Re: [OT?] Mini-challenge
Message #22 Posted by Paul Dale on 26 Feb 2008, 5:01 p.m.,
in response to message #21 by Valentin Albillo

Beaten to the finish again!

- Pauli

            
Re: [OT?] Mini-challenge
Message #23 Posted by Namir on 27 Feb 2008, 4:52 a.m.,
in response to message #21 by Valentin Albillo

Cool formula, except x and y cannot be such that U and/or V are either 0 or 1. Thus you cannot calculate squares and values for x*(x-1) and x*(x-1). I feel that this limitation is significant (especially for calculating squares)

Are there any other set of equations that work for all values of x and y?

Namir

Edited: 27 Feb 2008, 9:17 a.m.

                  
Re: [OT?] Mini-challenge
Message #24 Posted by Paul Dale on 27 Feb 2008, 3:27 p.m.,
in response to message #23 by Namir

I think it unlikely that a set of equations exist that always work. The very nature of 1/x means there will be points that go infinite.

My 15c program handles these cases, BTW :-)

- Pauli

                        
Error in 15C program???
Message #25 Posted by Namir on 27 Feb 2008, 8:05 p.m.,
in response to message #24 by Paul Dale

Paul,

I don't have a physical HP-15C, but I tried your program with 2 different emulators for th HP15C. Neither emulator gave a correct answer. I checked the listings in both case and they matched what you have listed. Can you please check yur program? Am I doing something wrong? Anyone else tried Paul's program?

Namir

Edited: 27 Feb 2008, 8:07 p.m.

                              
Re: Error in 15C program???
Message #26 Posted by Paul Dale on 27 Feb 2008, 8:34 p.m.,
in response to message #25 by Namir

Namir, you are quite right there is an error in the program listing above. I've fixed it in place so see above. Silly typo when I converted LBL 0 from stack based to register based (the latter being shorter). This subroutine calculates x^2/2.

I typed the program into my 35s and it seems to work.

- Pauli

Edited: 27 Feb 2008, 8:35 p.m.

                                    
Re: Error in 15C program???
Message #27 Posted by Namir on 27 Feb 2008, 9:49 p.m.,
in response to message #26 by Paul Dale

Paul,

Your program now works AND handles squares and near-squares as you mentioned in an earlier post.

Namir

                                          
Re: Error in 15C program???
Message #28 Posted by Paul Dale on 28 Feb 2008, 4:08 p.m.,
in response to message #27 by Namir

Squares and near squares aren't the degenerate cases for my solution. The special cases are when x, y or (x+y) are 0 or -1. Hence the conditional tests in the subroutine from LBL 0.

Also, as Valentin noted, the accuracy falls off badly.

- Pauli

      
Re: [OT?] Mini-challenge
Message #29 Posted by Eduardo Duenez on 4 Mar 2008, 11:57 p.m.,
in response to message #1 by Eduardo Duenez

Congratulations to Valentin and Paul Dale on independently finding solutions to the challenge.

The solution I found is identical to the one posted by Valentin, at least as far as I can tell. The main identity is:

1/(1/(x-1)-1/(x+1)) + 1/2=x^2/2

This is valid for all x except 0, 1, -1.

As remarked by Valentin, this formula is numerically bad when x is either very close to 0 or large in absolute value.

To go from this to the product xy we use the following "polarization identity" (very useful in the theory of inner products from linear algebra):

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

The two formulas above could be combined into a single, rather long one valid whenever x, y and x+y are neither 0, 1, nor -1. If either of these occur then the value of u^2/2 has to be handled separately.

The following HP 35s program handles all the cases (but does not deal with issues of loss of numerical accuracy). Moreover, it is written in such a way that, from the point of view of the stack, it works just like the multiplication key, that is, x,y are taken from the stack, and their product is returned to the X-level without disturbing the original contents of the Z & T registers. To achieve tis goal it uses STO/RCL arithmetic extensively (but only the +/- operations so, in principle, everything could be done just adding and subtracting plus possibly keeping track of intermediate results on paper or in memory).

The listing follows

S001 LBL S
S002 x=0?
S003 GTO S031
S004 x<0?
S005 +/-
S006 STO M
S007 CLx
S008 1
S009 RCL- M
S010 x=0?
S011 GTO S033
S012 +/-
S013 1/x
S014 STO S
S015 CLx
S016 1
S017 RCL+ M
S018 1/x
S019 STO- S
S020 CL x
S021 RCL S
S022 1/x
S023 STO S
S024 CLx
S025 2
S026 1/x
S027 STO+ S
S028 CLx
S029 RCL S
S030 RTN
S031 STO S
S032 RTN
S033 CLx
S034 1
S035 STO S
S036 RTN

P001 LBL P
P002 STO X
P003 x<>y
P004 STO Y
P005 +
P006 XEQ S001
P007 STO P
P008 CLx
P009 RCL X
P010 XEQ S001
P011 STO- P
P012 CLx
P013 RCL Y
P014 XEQ S001
P015 STO- P
P016 CLx
P017 RCL P
P018 RTN

XEQ S replaces x with x^2/2 and also stores this in S (uses M for temporary storage). LN=112, CK=8715.

XEQ P takes x,y and returns xy and stores it in P (also uses variables X,Y for temporary storage). LN=54, CK=7B85.

I hope you found this problem interesting. Though I mostly see it as a challenging exercise in algebra, the solution nonetheless illustrates beautifully how to go from a particular case (squaring) to the general one (multiplying arbitrary numbers).

Eduardo

[ Return to Index | Top of Index ]

Go back to the main exhibit hall