Wiki Home

Reducing Fractions Using Euler's Method


Namespace: WIN_COM_API
A brute force algorithm utilizing the MOD() function is fine when you need to reduce something such as 6/8, but imagine how many iterations it would take to reduce 12465/1750490. I was working on a problem like this for one of my projects and came across "Euler's Method" while searching the web. (Some Background on Leonhard Euler)

I decided to implement his method in VFP and the result shows the pure genius Leonhard Euler possessed. Here's the code...

?ReduceFraction("625/7850")
?ReduceFraction("3 32/14")
?ReduceFraction("5 12465/1750490") && would take far too long with numerator count down method

*********************************
FUNCTION ReduceFraction(tcFraction)
*********************************
    *CB* Based on Euler's Method

LOCAL lnWholeNumber, lnNumerator, lnDenominato, ;
lcFraction, lnSpaceAt, lnCounter, lnSmallNumber, ;
lnRemainder, lnLargeNumber, lcReturn
*CB* lnTotalIterations = 0
lcFraction = STRTRAN(ALLTRIM(tcFraction),"-", " ") && Users sometimes use keypad substituting "-" for " " such as 6-1/4
lnSpaceAt = AT(" ", lcFraction)
IF lnSpaceAt > 0
lnWholeNumber = INT(VAL(lcFraction))
lcFraction = SUBSTR(lcFraction,lnSpaceAt + 1)
ELSE
lnWholeNumber = 0
ENDIF

lnNumerator = INT(VAL(lcFraction))
lnDenominator = INT(VAL(SUBSTR(lcFraction, AT("/", lcFraction) + 1)))

IF lnNumerator > lnDenominator && 3 32/14 needs to become 5 4/14 before we proceed
lnWholeNumber = lnWholeNumber + INT(lnNumerator/lnDenominator)
lnNumerator = MOD(lnNumerator, lnDenominator)
ENDIF

lnLargeNumber = lnNumerator

*!* Note by Cesar Ch.
*!* Changed this instruction
*!* Original was : lnRemainder = MOD(lnDenominator, lnNumerator)
*!* Caused error when the remainder of the division between numerator and denominator was 0
lnRemainder = IIF(lnNumerator = 0, 0,MOD(lnDenominator, lnNumerator))

lnSmallNumber = lnNumerator

DO WHILE lnRemainder != 0
*CB* lnTotalIterations = lnTotalIterations + 1
lnSmallNumber = lnRemainder
lnRemainder = Mod(lnLargeNumber, lnSmallNumber)
ENDDO

lnNumerator = lnNumerator / lnSmallNumber
lnDenominator = lnDenominator / lnSmallNumber

IF lnWholeNumber > 0
lcReturn = ALLTRIM(STR(lnWholeNumber)) + " "
ELSE
lcReturn = ""
ENDIF
IF lnNumerator > 0 AND lnDenominator > 0
lcReturn = lcReturn + ALLTRIM(STR(lnNumerator)) + "/" + ALLTRIM(STR(lnDenominator))
ENDIF
*CB* ? "Total Iterations: " + alltrim(str(lnTotalIterations)) + " Fraction: "
RETURN lcReturn
ENDFUNC

-- Craig SBoyd



Cool. I've been playing around with Newton's laws and I think the following algorithm is based on Euler's Approximation:

http://cosmik-debris.net/science/newton.htm

Here are some tools to play with it and see the results visually:

http://cosmik-debris.net/science/universe.exe (32kb)
http://cosmik-debris.net/science/vfp8.exe (10mb)

More info:

http://en.wikipedia.org/wiki/Euler_method
http://en.wikipedia.org/wiki/Euler_approximation
--MikeHelland

Category Code Samples
( Topic last updated: 2006.03.08 09:13:44 AM )