The Museum of HP Calculators

HP Forum Archive 21

[ Return to Index | Top of Index ]

A quickie: improve the HP 50g IABCUV function
Message #1 Posted by Peter Murphy (Livermore) on 1 Feb 2013, 7:15 p.m.

Asked to find nonnegative integers such that 79x + 179y = 7319, one turns to the HP 50g, only to find that its IABCUV function, given A B C = 79 179 7319, delivers U = 248846, V = -109785; that's a solution, but not the one in nonnegative integers.

Given the output of IABCUV, it would be nice to have a straightforward way -- a little postprocessor program -- to find the (U,V) pair closest to (0,0), which would be the most general improvement and would presumably yield or come close to the desired solution, (36,25). How might that be done?

      
Re: A quickie: improve the HP 50g IABCUV function
Message #2 Posted by C.Ret on 2 Feb 2013, 3:11 a.m.,
in response to message #1 by Peter Murphy (Livermore)

Quote:
[...] to find the (U,V) pair closest to (0,0),[...]?

Hi,

Is that indicating that the only expected pair (x,y) out of solutions set { (66,3) (53,14) (40,25) (27,36) (14,47) (1,58) } of equation 11x + 13y = 765 is (27,36) ?

Edited: 2 Feb 2013, 3:15 a.m.

            
Re: A quickie: improve the HP 50g IABCUV function
Message #3 Posted by Thomas Klemm on 2 Feb 2013, 5:53 a.m.,
in response to message #2 by C.Ret

Calculate exact solution

(x, y) = t (11, 13) as it is orthogonal to the line
t (112 + 132) = 765
290 t = 765
t = 2.6379
(x, y) = (29.02, 34.29)

Find closest integer solution

66 + 13 k = 29.02
k = - 2.84

Now round that to the closest integer: k = - 3 x = 66 - 13 * 3 = 27

Similar: y = 3 + 11 * 3 = 36

Kind regards
Thomas

                  
Re: A quickie: improve the HP 50g IABCUV function
Message #4 Posted by David Hayden on 2 Feb 2013, 9:09 a.m.,
in response to message #3 by Thomas Klemm

Thomas, can you elaborate on your solution. I'm trying to understand it.

Quote:
(x, y) = t (11, 13) as it is orthogonal to the line
t (112 + 132) = 765

How does the first equation relate to the original post? What do you mean by "it is orthogonal to the line?" How do you get from the first equation to the second?
Quote:
66 + 13 k = 29.02

Where does this equation come from?

Thanks, Dave

                        
Re: A quickie: improve the HP 50g IABCUV function
Message #5 Posted by Thomas Klemm on 2 Feb 2013, 10:03 a.m.,
in response to message #4 by David Hayden

The equation 11x + 13y = 765 describes a line. You can interpret the left hand side of the equation as a scalar product: (11, 13)(x, y) = 765. So you're looking for all the points (x, y) that have the same value when scalar multiplied with the vector (11, 13). These points are on a line that is perpendicular to the vector (11, 13). Or you just know the fact that the vector made of the coefficients is orthogonal to the line.

So I crosscut the line with the orthogonal line through the origin (0, 0): (x, y) = (11t, 13t) for a parameter t. Insert that into the equation of the line and solve for t. This will give you the exact solution: the point on the line which is closest to (0, 0).

Now for the closest integer solution you can just start with any of them like (66, 3). To get the other integer solutions you can just add multiples of the vector (13, -11). This vector is parallel to the line. So I'm trying to figure out which integer multiple of (13, -11) I have to add to (66, 3) to be as close as possible to the exact solution. You can find that factor based on x-coordinates or y-coordinates or even on the length of the vectors: you will always end up with the same factor.

Probably I should have solved the example of the initial post. Okay then, here we go:

Calculate exact solution

(x, y) = t (79, 179) as it is orthogonal to the line
t (792 + 1792) = 7319
38282 t = 7319
t = 0.1912
(x, y) = (15.10, 34.22)

Find closest integer solution

248846 + 179 k = 15.10
k = - 1390.12

Now round that to the closest integer: k = - 1390 x = 248846 - 179 * 1390 = 36

Similar: y = - 109785 + 79 * 1390 = 25

Kind regards
Thomas

                              
Re: A quickie: improve the HP 50g IABCUV function
Message #6 Posted by C.Ret on 3 Feb 2013, 3:14 p.m.,
in response to message #5 by Thomas Klemm

Thanks Thomas for this great explainations and demonstration.

I have used a more 'brute' & 'naïve' approache, I first brougth out a code listing all positive interger coordinate solution.

« -> a b c                   // Expected a < b < c
   «
     0 c b / FOR y           // Init y loop from c/b  (y can't be bigger than c/b or x will be negative
        c b y * -            // Prepare computation of x = (c - b.y ) / a
        a                   
        IF
           DUP2 MOD          // Test if x is integer
        THEN
           DROP2             // Delete potential x when non integer
        ELSE
           / y R->C          // Express integer positive coordinate as (x,y)
        END
     NEXT
   »
»

Then , I add-on a test to keep in stack and return only the best candidate; that is the closest point to the orgine (0,0) :

« -> a b c                   // Expected a < b < c
   «
     c c R->C                // Init nearest (0,0) point with a far far far away point
     0 c b / FOR y           // Init y loop from c/b  (y can't be bigger than c/b or x will be negative
        c b y * -            // Prepare computation of x = (c - b.y ) / a
        a                   
        IF
           DUP2 MOD          // Test if x is integer
        THEN
           DROP2             // Delete potential x when non integer
        ELSE
           / y R->C          // Express integer positive coordinate as (x,y)
           IF
              DUP2 
              ABS SWAP ABS   // Compute distances to origine (0,0)of actual (x,y) and best candidate  
              <              // Compare with previous best point
           THEN 
              SWAP           // save actual (x,y) point when closer to origine (0,0)
           END
           DROP              // Erase false canditate
        END
     NEXT
   »
»

Edited: 3 Feb 2013, 5:22 p.m. after one or more responses were posted

                                    
Re: A quickie: improve the HP 50g IABCUV function
Message #7 Posted by Thomas Klemm on 3 Feb 2013, 4:36 p.m.,
in response to message #6 by C.Ret

You may have noticed that the calculation could still be simplified:

It's not necessary to compute the point of intersection M. We are only interested in the distance PM. And that's the projection of the vector u onto the blue line:

Now we divide that by v and round the result to the closest integer k :

Finally we subtract k times the vector v from the vector u to get as close as possible to M:

That's what these lines in the program do:

\<< u v DUP2 DOT
  v DUP DOT /
  0 RND * -
\>>

Thanks for your interest
Thomas


The equation of the line in the sketch is:

The vector n is perpendicular to the blue line:

Whereas the vector v is parallel to the blue line:

The vector u is one of the integer solutions. Here it's not the result of IABCUV because that would not fit on the drawing:

Plug all the data into the formula above:

Thus we end up with k = 2:

Edited: 3 Feb 2013, 5:49 p.m.

                                    
Re: A quickie: improve the HP 50g IABCUV function
Message #8 Posted by Thomas Klemm on 3 Feb 2013, 6:30 p.m.,
in response to message #6 by C.Ret

Now I realized that I didn't read the requirement thoroughly:

Quote:
find nonnegative integers

But then:

Quote:
to find the (U,V) pair closest to (0,0)

What should be the result for 2x + 5y = 13?

My program will return [ -1 3 ] while your program probably returns [ 4 1 ]. My solution is closest to (0,0) while your solution is nonnegative.

Cheers
Thomas

Edited: 3 Feb 2013, 6:31 p.m.

                                          
Re: A quickie: improve the HP 50g IABCUV function
Message #9 Posted by C.Ret on 4 Feb 2013, 2:58 a.m.,
in response to message #8 by Thomas Klemm

Quote:
What should be the result for 2x + 5y = 13?

My program will return [ -1 3 ] while your program probably returns [ 4 1 ]. My solution is closest to (0,0) while your solution is nonnegative.


You are right, my programs list (4,1) as the only possible 'positive' integer position.

The trick is as we ask x and y to be positive solutions, the field of investigations is limited to 0 < x < c/a and 0 < y < c/b.

If one manage to organise coefficients such as a < b < c, then scanning over y is faster as fewer integer solutions are possible.

Edited: 4 Feb 2013, 3:00 a.m.

                                                
Re: A quickie: improve the HP 50g IABCUV function
Message #10 Posted by Thomas Klemm on 4 Feb 2013, 4:21 a.m.,
in response to message #9 by C.Ret

We could however combine both ideas:

  1. Find closest integer solution with my program
  2. While the solution is negative subtract vector v

This will be faster than scanning over y. So in this particular case since [ -1 3 ] is negative subtract [ -5 2 ] and you will end up with the nonnegative solution [ 4 1 ].

In order to avoid an infinitive loop we'd have to check that a <= c and b <= c.

Cheers
Thomas

Edited: 4 Feb 2013, 4:23 a.m.

      
Re: A quickie: improve the HP 50g IABCUV function
Message #11 Posted by Gilles Carpentier on 2 Feb 2013, 7:41 p.m.,
in response to message #1 by Peter Murphy (Livermore)

Probably not the more efficient but (in _exact_ mode) :

IXY
«
 SOLVEVX EQ-> NIP -1
 DO
  1 + DUP 1. DISP 
  DUP2 'Y' SWAP = SUBST EVAL  
 UNTIL
  DUP TYPE 28. SAME 
  IF DUP NOT THEN NIP END
 END
 SWAP 2 ->LIST NIP
»

111 bytes

Usage : '79*X + 179*Y = 7319'

IXY

-> {36 25}

'33*X + 19*Y = 7319' IXY {212 17}

'33*X + 19*Y = 719' IXY { 12 17 }

etc. If no solution, clic ON ;)

Edited: 2 Feb 2013, 8:24 p.m.

            
Re: A quickie: improve the HP 50g IABCUV function
Message #12 Posted by Thomas Klemm on 3 Feb 2013, 4:37 a.m.,
in response to message #11 by Gilles Carpentier

Quote:
'33*X + 19*Y = 7319' IXY {212 17}

The solution (174,83) is closer to (0,0):

|(212,17)| = 212.68
|(174,83)| = 192.78

Kind regards
Thomas

      
Re: A quickie: improve the HP 50g IABCUV function
Message #13 Posted by Thomas Klemm on 3 Feb 2013, 4:25 a.m.,
in response to message #1 by Peter Murphy (Livermore)

As I don't have a HP-50g I wrote a program for the HP-48GX:

\<< \-> a b c
  \<< (1,0) (0,1) a b
    WHILE
      DUP2 MOD DUP
    REPEAT \-> r
      \<< SWAP r -
        OVER / \-> q
        \<< SWAP ROT
          OVER q * -
        \>>
        ROT r
      \>>
    END
    DROP
    c SWAP /
    SWAP DROP *
    SWAP DROP
    DUP
    c a SQ b SQ + /
    a b R\->C * -
    b a NEG R\->C
    SWAP OVER /
    0 RND * -
  \>>
\>>
These are the solutions to the examples:
79 179 7319:    (36,25)
11  13  765:    (27,36)
33  19 7319:   (174,83)
33  19  719:    (12,17)

For the HP-50g you can probably just use the following:

\<< \-> a b c
  \<< 
    a b c IABCUV R\->C
    DUP
    c a SQ b SQ + /
    a b R\->C * -
    b a NEG R\->C
    SWAP OVER /
    0 RND * -
  \>>
\>>

Cheers
Thomas

      
Re: A quickie: improve the HP 50g IABCUV function
Message #14 Posted by Thomas Klemm on 3 Feb 2013, 6:43 a.m.,
in response to message #1 by Peter Murphy (Livermore)

Just noticed I could simplify the calculation a little:

\<< \-> a b c
  \<< [1 0] [0 1] a b
    WHILE
      DUP2 MOD DUP
    REPEAT \-> r
      \<< SWAP r -
        OVER / \-> q
        \<< SWAP ROT
          OVER q * -
        \>>
        ROT r
      \>>
    END
    DROP
    c SWAP /
    SWAP DROP *
    SWAP DROP
    b NEG a \->V2 \-> u v
    \<< u v DUP2 DOT
      v DUP DOT /
      0 RND * -
    \>>
  \>>
\>>

And this is the improved program for the HP-50g:

\<< \-> a b c
  \<< 
    a b c IABCUV \->V2
    b NEG a \->V2 \-> u v
    \<< u v DUP2 DOT
      v DUP DOT /
      0 RND * -
    \>>
  \>>
\>>

Cheers
Thomas

      
Re: A quickie: improve the HP 50g IABCUV function
Message #15 Posted by Thomas Klemm on 3 Feb 2013, 9:56 a.m.,
in response to message #1 by Peter Murphy (Livermore)

Nobody complained so far but my solutions don't work unless GCD(a, b) = 1. So here's the fixed program for the HP-48GX:

\<< \-> a b c
  \<< [1 0] [0 1] a b
    WHILE
      DUP2 MOD DUP
    REPEAT \-> r
      \<< SWAP r -
        OVER / \-> q
        \<< SWAP ROT
          OVER q * -
        \>>
        ROT r
      \>>
    END
    DROP
    SWAP DROP
    ROT DROP
    c OVER /
    ROT *
    b NEG a \->V2
    ROT / \-> u v
    \<< u v DUP2 DOT
      v DUP DOT /
      0 RND * -
    \>>
  \>>
\>>

For the HP-50g I have to calculate GCD(a, b) which was probably already calculated for IABCUV:

\<< \-> a b c
  \<< 
    a b c IABCUV \->V2
    b NEG a \->V2
    a b GCD / \-> u v
    \<< u v DUP2 DOT
      v DUP DOT /
      0 RND * -
    \>>
  \>>
\>>

Maybe somebody more familiar with this calculator comes up with a better idea?

Cheers
Thomas


[ Return to Index | Top of Index ]

Go back to the main exhibit hall