;---------------------------------------- ;Returns O if not Fraction, 1 if is. IsFraction(N) { If N Not Contains %A_Space% If N Contains / { StringSplit, N, N, / If N0 = 2 Return "1" } Return "0" } ;---------------------------------------- ;Turns a decimal into a fraction. Not Reduced DeciToFraction(D) { StringSplit, D, D, . W = %D1% N = %D2% StringLen, NLen, N Loop, %NLen% { Z = %Z%0 } D = 1%Z% R = %W% %N%/%D% Return R } ;---------------------------------- ;Returns reduced result of dividing F1 by F2 DivFraction(F1,F2) { F1 := Fraction(F1) F2 := Fraction(F2) StringSplit, F1_, F1, / ;Split and define Nu and De of each F StringSplit, F2_, F2, / Nu1 = %F1_1% De1 = %F1_2% Nu2 = %F2_1% De2 = %F2_2% Nu2 = %De2% De2 = %F2_1% Fr1 = %Nu1%/%De1% Fr2 = %Nu2%/%De2% R := MultiFraction(Fr1,Fr2) Return R } ;---------------------------------------------- ;Returns Reduced result of mulitplying F2 with F2 MultiFraction(F1,F2) { F1 := Fraction(F1) F2 := Fraction(F2) StringSplit, F1_, F1, / ;Split and define Nu and De of each F StringSplit, F2_, F2, / Nu1 = %F1_1% De1 = %F1_2% Nu2 = %F2_1% De2 = %F2_2% Nu := Nu1 * Nu2 De := De1 * De2 R = %Nu%/%De% R := Reduce(R) R := MixNum(R) Return R } ;------------------------------------------ ;Least Common Multiple function, Returns LCM of N1 and N2 LCM(N1,N2) { N1i := N1**2 Loop, %N1i% { N := N1 * A_Index List1 = %List1%,%N% } N2i := N2**2 Loop, %N2i% { N := N2 * A_Index If N In %List1% Return N } } ;------------------------------------------ ;AddFraction Function, add fraction1 with fraction. ;Returns mixed number if possible, reduced AddFraction(F1,F2) { F1 := Fraction(F1) ;Convert to improper fractions F2 := Fraction(F2) StringSplit, F1_, F1, / ;Split and define Nu and De of each F StringSplit, F2_, F2, / Nu1 = %F1_1% De1 = %F1_2% Nu2 = %F2_1% De2 = %F2_2% Nu1 := Nu1 * De2 Nu2 := Nu2 * De1 De := De1 * De2 Nu := Nu1 + Nu2 R = %Nu%/%De% R := Reduce(R) R := MixNum(R) Return R } ;------------------------------------------ ;SubFraction Function, subtract fraction2 from fraction1. ;Returns mixed number if possible, reduced SubFraction(F1,F2) { F1 := Fraction(F1) ;Convert to improper fractions F2 := Fraction(F2) StringSplit, F1_, F1, / ;Split and define Nu and De of each F StringSplit, F2_, F2, / Nu1 = %F1_1% De1 = %F1_2% Nu2 = %F2_1% De2 = %F2_2% Nu1 := Nu1 * De2 Nu2 := Nu2 * De1 De := De1 * De2 Nu := Nu1 - Nu2 R = %Nu%/%De% R := Reduce(R) R := MixNum(R) Return R } ;---------------------------------------------------------------------- ;Reduce function reduces fraction. Reduce(N) { If N Contains %A_Space% { StringSplit, NA, N, %A_Space% W = %NA1% N = %NA2% } StringSplit, NA, N, `/ Nu = %NA1% De = %NA2% GCD := GCD(Nu,De) Nu := Nu / GCD De := De / GCD If Nu = %De% { If W = W = 0 R := W + 1 Return R } If De = 1 { If W = W = 0 R := W + Nu Return R } R = %W% %Nu%/%De% Return R } ;----------------------------------------------------------------------- ;Greatest Common Denominator ;Returns the GCD of N1 and N2 ;If N1 = N2 the returned value will be equal to N1 and N2 as they are Equal, respecfully ;That is the sets of Common factors are equal ;For ex: If 9 and 9 are compared, 9 is returned ; If 12 and 12 are compared, 12 is returned respectfully GCD(N1,N2) { NL = 1,2,3,4,5,6,7,8,9 ;CFL is Common Factor List Loop, 2 { I := N%A_Index% LInt := A_Index Loop, %I% { R := N%LInt% / A_Index StringSplit, R, R, . If R2 Not Contains %NL% ;Use this method so second array not needed to check how many items list ;for trimming comma(s) { If CFL%LInt% = CFL%LInt% = %R1% Else CFL%LInt% := R1 "," CFL%LInt% } } } Sort, CFL1, R N D, Sort, CFL2, R N D, StringSplit, CL, CFL1, `, Loop, %CL0% { Factor := CL%A_Index% If Factor = 1 Continue If Factor In %CFL2% Break } If Factor Not In %CFL2% Return "1" Return Factor } ;------------------------------------------------ ;PriComp Function: Figures if number is Prime or Composite ;Returns -1 if N is not a digit ;Returns 0 if Prime number ;Returns 1 if Composite number PriComp(N) { If N Is Not Digit Return "-1" NL = 1,2,3,4,5,6,7,8,9 ;CFL is Common Factor List Loop, %N% { R := N / A_Index StringSplit, R, R, . If R2 Not Contains %NL% ;Use this method so second array not needed to check how many items list ;for trimming comma(s) { If CFL = CFL = %R1% Else CFL = %R1%,%CFL% } } StringSplit, CFLN, CFL, `, If CFLN0 <= 2 Return "0" Return "1" } ;-------------------------------------------------------- ;Converts a improper fraction to a mixed number. ;Format: N/D. Ex: 12/6 MixNum(N) { StringSplit, P, N, / Nu = %P1% De = %P2% Wn := Nu / De Wn := Floor(Wn) Fr := Mod(Nu,De) If Fr = 0 Return %Wn% Result = %Wn% %Fr%/%De% Return Result } ;-------------------------------------------------------- ;Least Common Denominator ;Returns the LCD of N1 and N2 LCD(N1,N2) { NL = 1,2,3,4,5,6,7,8,9 If N1 = %N2% Return "1" ;CFL is Common Factor List Loop, 2 { I := N%A_Index% LInt := A_Index Loop, %I% { R := N%LInt% / A_Index StringSplit, R, R, . If R2 Not Contains %NL% ;Use this method so second array not needed to check how many items list ;for trimming comma(s) { If CFL%LInt% = CFL%LInt% = %R1% Else CFL%LInt% := R1 "," CFL%LInt% } } } Sort, CFL1, N D, Sort, CFL2, N D, StringSplit, CL, CFL1, `, Loop, %CL0% { Factor := CL%A_Index% If Factor = 1 Continue If Factor In %CFL2% Break } If Factor Not In %CFL2% Return "1" Return Factor } ;------------------------------------------------------------ ;Fraction function turns mixed number into a improper fractions ;N formats is W N/D ;Ex: 12 2/3 ;Formula is: ; [(W*D) + N] / D Fraction(N) { If N Not Contains %A_Space% Return N StringSplit, WN, N, %A_Space% StringSplit, FN, WN2, / W = %WN1% N = %FN1% D = %FN2% N := W * D + N Result = %N%/%D% Return Result ListVars } ;--------------------------------------------------------- ;Returns list of common factors of N CommonFactor(N) { NL = 1,2,3,4,5,6,7,8,9 ;CFL is Common Factor List Loop, %N% { R := N / A_Index StringSplit, R, R, . If R2 Not Contains %NL% ;Use this method so second array not needed to check how many items list ;for trimming comma(s) { If CFL = CFL = %R1% Else CFL = %R1%,%CFL% } } Return CFL }
I hate fractions!
Started by
Invalid User
, Sep 07 2005 04:50 AM
3 replies to this topic
For those of us who would like to take fractions, and burn them! I didnt take much time to document them, but they should be pretty self explanitory. Questions, comments and (Optimizations(Lazslo?)) feed back welcome.
#1
-
Posted 07 September 2005 - 04:50 AM
my lame sig
Nice work! Since it was requested: here are a few mods.
Checking if N is prime we only need to try all the small divisor candidates up to sqrt(N), because if N = u*v, u and v cannot be both greater than sqrt(N). To keep the script short I made trial divisions with all the integers at most sqrt(N), although 2 and the odd numbers were enough. (Or 2,3 and the numbers not divisible by 2 or 3. This way you can speed up the test three fold.) More sophisticated tests, like the Miller-Rabin primality test require complicated programming.
Factoring N is done recursively. If N is prime, itself is the only divisor (and 1). If we find a proper divisor of N, attach it to the list of divisors and get the factors N//i.
IsFraction(N) ;Returns 0 if not Fraction, 1 if is. { StringGetPos i, N, / IfLess i,0, Return 0 ; no / StringLeft L, N, i If L is not Integer Return 0 ; left of / is not integer StringTrimLeft R, N, i+1 If R is not Integer Return 0 ; right of / is not integer Return 1 } DeciToFraction(D) ;Turns a decimal into a fraction. Not Reduced { R = 1 Loop { If (Ceil(D) = D) break D *= 10 R *= 10 } Return Ceil(D) "/" R } LCM(N1,N2) ; Least Common Multiple of N1 and N2 { Return N1*N2//GCD(N1,N2) } GCD(N1,N2) ; Greatest Common Divisor of N1 and N2 (Euclidean algorithm) { Loop { IfEqual N2,0, Return N1 N1 := N1 - (N1//N2)*N2 IfEqual N1,0, Return N2 N2 := N2 - (N2//N1)*N1 } } IsPrime(N) ; -1 if N is not a digit; 1 if Prime or 1; 0 if Composite { If N Is Not Digit Return -1 If N in 1,2,3,5,7,11 ; often called cases directly Return 1 If N in 0,4,6,8,9,10 Return 0 Loop % Ceil(Sqrt(N))-1 { i := A_Index + 1 If ((N//i)*i = N) ; N is divisible by i Return 0 } Return 1 } MixNum(N) ; improper fraction to a mixed number. Ex: "13/6" -> "2+1/6" { StringSplit, P, N, / R := P1//P2 IfEqual R,0, Return N P1 -= R*P2 IfEqual P1,0, Return R Return R "+" P1 "/" P2 ; Mixed numbers have + instead of Space, allowing formatted input } Factor(N) ; list of factors { N := Abs(N) IfLess N,4, Return N Loop % Ceil(Sqrt(N))-1 { i := A_Index + 1 If ((N//i)*i = N) ; N is divisible by i Return i "," Factor(N//i) ; Recursively on reduced part } Return N }Some of the functions just use different AHK commands, others are tricky. GCD uses Euclid's famous algorithm, which is based on the observation that GCD(x,y) = GCD(x-y,y). This is true, because the common factors are the same. Repeat this subtraction as many times as you can, that is x//y times, reducing the pair of input from (x,y) to (x-(x//y)*y, y). Now do the same with y, subtracting from it the new x'.
Checking if N is prime we only need to try all the small divisor candidates up to sqrt(N), because if N = u*v, u and v cannot be both greater than sqrt(N). To keep the script short I made trial divisions with all the integers at most sqrt(N), although 2 and the odd numbers were enough. (Or 2,3 and the numbers not divisible by 2 or 3. This way you can speed up the test three fold.) More sophisticated tests, like the Miller-Rabin primality test require complicated programming.
Factoring N is done recursively. If N is prime, itself is the only divisor (and 1). If we find a proper divisor of N, attach it to the list of divisors and get the factors N//i.
#2
-
Posted 07 September 2005 - 04:47 PM
Thanks, looks great. I wish I had some schooling in algorithms. Perhaps you could link me to a few sites on it, or recommended reading.
#3
-
Posted 07 September 2005 - 06:33 PM
my lame sig
In case you are interested, here is another version of the Euclidean greatest common divisor algorithm. It uses Mod() instead of integer division and then swaps the parameters for the next iteration. The first version uses less memory (interesting at huge numbers only) but somewhat longer code. Swapping values could be done in real life © with pointer manipulations, so there is no significant difference in the running time.
Also included the threefold speedup for IsPrime(). The first tried divisor is 5, which gets increased by 2 and then by 4, in a cycle (5,7, 11,13, 17,19, 23...). This way we jump over the divisor candidates which are a multiple of 2 or 3.
It is even faster to generate all the prime numbers up to sqrt(N), and use only those as divisor candidates. The table can be reused if many numbers need to be checked for primality. (For small numbers the best is to see if they are in a sufficiently large table of primes.) This prime table can be generated by Eratosthenes' sieve, as coded below in the Primes() function. Only odd numbers are considered (double speed, half memory).
Also included the threefold speedup for IsPrime(). The first tried divisor is 5, which gets increased by 2 and then by 4, in a cycle (5,7, 11,13, 17,19, 23...). This way we jump over the divisor candidates which are a multiple of 2 or 3.
It is even faster to generate all the prime numbers up to sqrt(N), and use only those as divisor candidates. The table can be reused if many numbers need to be checked for primality. (For small numbers the best is to see if they are in a sufficiently large table of primes.) This prime table can be generated by Eratosthenes' sieve, as coded below in the Primes() function. Only odd numbers are considered (double speed, half memory).
GCD(N1,N2) ; Greatest Common Divisor of N1 and N2 (Euclidean algorithm) { Loop { IfEqual N2,0, Return N1 N := Mod(N1,N2) N1 = %N2% N2 = %N% } } IsPrime(N) ; Return -1 if N is not Integer, 1 if Prime or 1, 0 if composite or 0 { If N is not Integer Return -1 If N in 1,2,3,5,7,11 ; often called cases directly Return 1 If N in 0,4,6,8,9,10 Return 0 If (Mod(N,2)=0 or Mod(N,3)=0) Return 0 c:= Floor(Sqrt(N)*1.000000001) ; against rounding errors i = 5 j = 2 Loop { IfGreater i,%c%, Return 1 If (Mod(N,i) = 0) ; N is divisible by i Return 0 i += j j := 6-j } } Primes(N) ; returns a list of primes up to N > 1 { Primes = 2 ; First is the even prime 2 i = 3 Loop % (N-1)//2 { IfNotEqual P%i%,0, { ; Not marked as composite: Prime is found Primes = %Primes%,%i% j := i*i ; Small multiples are already marked Loop { IfGreater j,%N%, Break P%j% = 0 ; Mark multiples as composite j += i } } i += 2 ; next odd number } Return Primes }
#4
-
Posted 07 September 2005 - 08:21 PM