HP Forums
Programming puzzle: Symplifying (simple) fractions containing square roots - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Programming puzzle: Symplifying (simple) fractions containing square roots (/thread-8165.html)



Programming puzzle: Symplifying (simple) fractions containing square roots - pier4r - 04-14-2017 07:28 PM

Source. I did not post this in the thread dedicated to my clumsy explorations because I thought it may be interesting to see it solved with as little "existing aid as possible" (I'm looking at you GCD) and on calculators that I regard as requiring more effort than the hp 50g to be coded (the ones that do not have a quick interface with the PC). In other words, let's say that one cannot use functions that are designed to produce exact output with flags -3 and/or -5 cleared.

Quote:Description

Simplify square roots in the form \( \frac{a \cdot \sqrt{b} }{c \cdot \sqrt{d}} \). A simplified radical should have no square roots in the denominator and no number in a square root should have a square factor. For example, the input 2 5 5 10 for a b c d, respectively, should simplify to 1 2 5 where a=1, b=2, and c=5.
Output description

a b c

(d should not exist after simplifying)
Challenge input

45 1465 26 15

Challenge output

15 879 26


If someone wants to propose variants / other inputs (maybe to test speed), that is welcomed.

my solution so far, I do use FACTORS as built in function, and nothing else hopefully. With GCD it would have been way shorter and faster.
Code:

%%HP: T(0)A(D)F(.);
@ alternative found online %%HP: T(3)A(R)F(.);
@ You may edit the T(0)A(D)F(.) parts.
@ The earlier parts of the line are used by Debug4x.

@ in npp, just select language "normal" to get rid of the highlight.

DIR

  c20170412
  DIR
  
  factorsFsetUnset
  @to set the flag and unset it around factors otherwise the main program
  @is affected
  \<<
    @input, a number
    @output, factors.
    
    -3 CF
      @exact mode
    
    @the number should be converted now in exact mode
    \->Q
    FACTORS
    
    -3 SF
      @numerical mode
  \>>
  
  
  @ www.reddit.com/r/dailyprogrammer/comments/64y4cf/20170412_challenge_310_intermediate_simplifying/
  @ Description 
  @ 
  @ Simplify square roots in the form (a sqrt(b))/(c sqrt(d)). A simplified 
  @ radical should have no square roots in the denominator and no number in 
  @ a square root should have a square factorV. For example, the input 2 5 5 
  @ 10 for a b c d, respectively, should simplify to 1 2 5 where a=1, b=2, 
  @ and c=5. Output description 
  @ 
  @ a b c 
  @ 
  @ (d should not exist after simplifying) Challenge input 
  @ 
  @ 45 1465 26 15 
  @ 
  @ Challenge output 
  @ 
  @ 15 879 26 
  @ 
  @ Credit 
  @ 
  @ This challenge was suggested by user /u/alchzh on 
  @ /r/dailyprogrammer_ideas, many thanks. If you have an idea, please share 
  @ it there and we might use it! 
  cRootSol
  \<<
    45. 1465. 26. 15. @ a b c d , for quick testing. reals.
    0 @factorsListV1
    0 @factorsListV2
    0 @factorsListNumEl
    1 @cdProd
    1 @bdProd
    1 @numeratorProd
    1 @rootProd
    0 @factorV
    0 @multiplicity
    0 @extrMultiplicity
    0 @maxMultiplicity
    0 @posV
    10 @uFlag1
    0 @sysFlags
    \->
    @external input
    a
    b
    c
    d
    @local var
    factorsListV1
    factorsListV2
    factorsListNumEl
    cdProd
    bdProd
    numeratorProd
      @product outside the root at numerator
    rootProd
    factorV
    multiplicity
    extrMultiplicity
    maxMultiplicity
    posV
    uFlag1
    sysFlags
    @output
    @3: numerator value, outside the root
    @2: numerator value in the root
    @1: denominator value
    \<<
      RCLF 'sysFlags' STO
      
      @set flags to avoid exact fractions
      @we have to set, unset for factors,
      -3 SF
      -105 SF
    
      @so we know that  ( a sqrt (b) ) / ( c sqrt (d) )
      @can be rewrtitten as 
      @[( a * sqrt (b) ) / ( c * sqrt (d) )] * ( sqrt(d) / sqrt (d) )
      @giving back
      @( a * sqrt (b*d) ) / ( c * d )
      @from sqrt (b*d) we need to extract the proper factors. (and FACTORS is a good command)
      
      c d * 'cdProd' STO
      
      @we extract what can be extracted from the root
      b d * factorsFsetUnset
        @ now in the stack there is a list with factors and multiplicity.
        
      OBJ\->
        @list exploded
        @ the number of elements is on the stack on level 1
        
      'factorsListNumEl' STO
        @save num elements
        
      @we know that from an exploded list, the multiplicity is always in position
      @after the factorV, so odd positions since the list is inverted.
      @so we just consume the entries until we are finished
      
      a 'numeratorProd' STO*
        @we start to build the num prod
      uFlag1 CF
        @we use this flag to say if the multiplicity was big enough
        @to extract a factorV.
        
      1 factorsListNumEl
      FOR counter
        IF
          counter 2 MOD 
          0 ==
        THEN
          @ we have an even position, so the factorV
          'factorV' STO
          @we continue to compute the rootProduct
          factorV multiplicity ^ 'rootProd' STO*
            @if the program is correct, the multiplicity of the factorV is 1 or 0
            @within the root.
          
          @we compute the external product
          IF
            uFlag1 FS?
          THEN
            uFlag1 CF
              @for the next iteration
              
            factorV extrMultiplicity ^ 'numeratorProd' STO*
             
            0 'extrMultiplicity' STO
              @reset
          END
        ELSE
          @ we have an odd position, so the multiplicity
          'multiplicity' STO
          IF
            multiplicity 2 \>=
          THEN
            @the factorV can be extracted
            uFlag1 SF
              @we mention this in the flag for the next operation
              
            @ we collect how many times the factorV can be extracted
            WHILE multiplicity 2 \>=
            REPEAT
              1 'extrMultiplicity' STO+
              'multiplicity' 2 STO-
            END
          END
          @multiplicity here is either 0 or 1.
        END
      NEXT
      
      @now the product under the root is fine
      @time to simplify the other two terms still using factors.
      @GCD function avoided.
      
      cdProd factorsFsetUnset 'factorsListV1' STO
      numeratorProd factorsFsetUnset 'factorsListV2' STO
      
      1 factorsListV1 SIZE
      FOR counter
        @factors in odd positions
        
        @we get the factor
        factorsListV1 counter GET 'factorV' STO
        
        @we see if it exist in the other factorization
        factorsListV2 factorV POS 'posV' STO
        
        IF
          posV 0 >
           @compare the position
        THEN
          @if the position is non-zero, then the factor exists in
          @both lists, so we can compare the multiplicity
          
          @get the min multiplicity (I could use the GCD actually
          @to make things faster)
          factorsListV1 counter 1 + GET
          factorsListV2 posV 1 + GET
          MIN
          
          @ we get the min factor multiple for both numbers
          factorV SWAP
            @2: factorV
            @1: min multiplicity
          ^
          
          @we divide the numbers
          DUP
            @ 2: factor^minMultiplicity
            @ 1: factor^minMultiplicity
          
          'cdProd' SWAP
            @ 3: factor^minMultiplicity
            @ 2: 'cdProd'
            @ 1: factor^minMultiplicity
          STO/
          
          'numeratorProd' SWAP
            @ 2: 'numeratorProd'
            @ 1: factor^minMultiplicity
          STO/
        END
      2 STEP
      
      @output
      numeratorProd
      rootProd
      cdProd
      
      sysFlags STOF
    \>>
  \>>
  END
  
END



RE: Programming puzzle: Symplifying (simple) fractions containing square roots - Han - 04-14-2017 07:36 PM

Are you aware that the HP50G can handle "exact" integers of "infinite" size (up to the limit of RAM)? The problem can be solved with just a few lines of code since the HP50G handles integers natively.

\[ \frac{a\sqrt{b}}{c\sqrt{d}} = \sqrt{\frac{a^2\cdot b}{c^2\cdot d}} \]

So compute \(\frac{a^2\cdot b }{c^2\cdot d} \) and take the square root. Just make sure you use exact integers as inputs.

EDIT: a b c d SWAP SQ * ROT SQ ROT * SWAP / \( \sqrt{\quad} \)

Extracting the integers is left as an exercise for the reader (but it too is a fairly short snippet of code)


RE: Programming puzzle: Symplifying (simple) fractions containing square roots - pier4r - 04-14-2017 07:41 PM

Yup I did this manually (not exactly your solution though, I just wrote the equation, pressed eval, solved), but that uses the power of the CAS I assume (or some well written numeric functions). This because the evaluating function should know how to avoid the root at the denominator. So I went also on the way to use less CAS as possible, saving myself to write a function like FACTORS though.

edit: in other words, let's say that one cannot use functions that are designed to produce exact output with flags -3 and/or -5 cleared.