Post Reply 
Programming puzzle: Symplifying (simple) fractions containing square roots
04-14-2017, 07:28 PM (This post was last modified: 04-14-2017 07:46 PM by pier4r.)
Post: #1
Programming puzzle: Symplifying (simple) fractions containing square roots
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

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-14-2017, 07:36 PM (This post was last modified: 04-14-2017 07:44 PM by Han.)
Post: #2
RE: Programming puzzle: Symplifying (simple) fractions containing square roots
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)

Graph 3D | QPI | SolveSys
Find all posts by this user
Quote this message in a reply
04-14-2017, 07:41 PM (This post was last modified: 04-14-2017 07:45 PM by pier4r.)
Post: #3
RE: Programming puzzle: Symplifying (simple) fractions containing square roots
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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)