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
 pier4r Senior Member Posts: 2,193 Joined: Nov 2014
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 :)
04-14-2017, 07:36 PM (This post was last modified: 04-14-2017 07:44 PM by Han.)
Post: #2 Han Senior Member Posts: 1,882 Joined: Dec 2013
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
04-14-2017, 07:41 PM (This post was last modified: 04-14-2017 07:45 PM by pier4r.)
Post: #3
 pier4r Senior Member Posts: 2,193 Joined: Nov 2014
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 :)
 « Next Oldest | Next Newest »