Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

I hate fractions!


  • Please log in to reply
3 replies to this topic
Invalid User
  • Members
  • 447 posts
  • Last active: Mar 27 2012 01:04 PM
  • Joined: 14 Feb 2005
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.


;----------------------------------------
;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
}

my lame sig :)

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Nice work! Since it was requested: here are a few mods.
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.

Invalid User
  • Members
  • 447 posts
  • Last active: Mar 27 2012 01:04 PM
  • Joined: 14 Feb 2005
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.
my lame sig :)

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
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).
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
}