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
\>>

@ 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 »