czardas

Fraction

36 posts in this topic

#1 ·  Posted (edited)

Perform accurate division using real fractions and convert floating point numbers to fractions.

Floating point arithmetic often introduces small inaccuracies. Most of the time this is not a problem, but sometimes it can be. As a workaround, many programmers decide to only use whole numbers for specific calculations - ones which need to return exact results. The fraction 1/3 cannot be represented using a float. You would need a decimal (or floating point variant) of infinite length to give an accurate representation of 1/3. Working with fractions is not entirely straight forward, and at times this can be a little frustrating.

With the functions in this library, there is potential for internal calculations to produce numbers which are out of range. Not withstanding oversights: both input numbers should be less than 16 digits and the difference between the denominator and the divisor should be an order of magnitude less than 10^16, otherwise the function will return an error.

With the exception of Fraction(), all included functions take array parameters. All return values are either arrays or boolean values. Documentation and examples pending.

NEW VERSION requires operator64.au3 found here: https://www.autoitscript.com/forum/topic/176620-operator64/
This is an alpha release -see post 33.

#include-once
#include 'operator64.au3'

; #INDEX# ======================================================================================================================
; Title .........: Fraction
; AutoIt Version : 3.3.14.0
; Language ......: English
; Description ...: Maths functions intended to be used with vulgar fractions.
; Notes .........: In this library, a fraction is defined as two integers stored in a two element array.
;                  Several functions use approximation when internal calculations go out of range.
;                  When an approximation occurs, @extended is set to 1. This return value should be checked in most instances.
;                  -----------------------------------------------------------------------------------------------------------
;                  Input Size Limits for _Fraction()
;                  Unlimited within the confines of AutoIt (approximately) between -1e+308 and +1e+308
;                  Smallest value (approximately) 1e-323
;                  --------------------------------------------------------------------
;                  Negative Output Size Limits for All Functions That Return a Fraction
;                  9223372036854775807 /-1 To -1/ 9223372036854775807 negative range
;                  - 2^63 /1 Out of range
;                  tiny negative values are either rounded down to -1/ 9223372036854775807 or rounded up to 0/-1
;                  ----------------------------------------------------------------
;                  Positive Output Size Limits for Functions That Return a Fraction
;                  1/ 9223372036854775807 To 9223372036854775807 /1 positive range
;                  2^63 /1 Out of range
;                  tiny positive values are either rounded up to 1/ 9223372036854775807 or rounded down to 0/1
; Author(s) .....: czardas, Pheonix XL
; ==============================================================================================================================


; #CURRENT# ====================================================================================================================
; _Fraction
; _FractionAbs
; _FractionAdd
; _FractionApproximate
; _FractionCeiling
; _FractionDivide
; _FractionFloor
; _FractionMod
; _FractionMultiply
; _FractionPower
; _FractionRoot
; _FractionSubtract
; _IsFraction
; _IsFractionNegative
; _Reciprocal
; ==============================================================================================================================


; #INTERNAL_USE_ONLY#===========================================================================================================
; __GCD
; __FloatRatio
; __FloatToDigits
; __Quotient
; __Simplify
; ==============================================================================================================================


; #FUNCTION# ===================================================================================================================
; Name...........: _Fraction
; Description ...: Conversion from float to fraction and whole number division.
; Syntax.........: _Fraction($nDividend [, $nDivisor = 1])
; Parameters.....; $iDividend - Top fractional part
;                  $iDivisor - [Optional] Lower fractional part. The default value is 1.
; Return Values  ; Success - Returns an array of two elements. The first element is the dividend, and the second is the divisor.
;                  Sets @Extended to 1 if rounding or approximation occurs, or if one of the input parameters is a float.
;                  Failure sets @error as follows
;                  |@error = 1 Input contains non-numeric or undefined data.
;                  |@error = 2 The divisor cannot be zero.
;                  |@error = 3 Out of range.
; Author ........: czardas
; Comments ......; Accepts Int32, Int64 and floats. Output ranges are shown in the main header.
; ==============================================================================================================================

Func _Fraction($nDividend, $nDivisor = 1)
    If Not IsNumber($nDividend) Or StringInStr($nDividend, '#') Or _
    Not IsNumber($nDivisor) Or StringInStr($nDivisor, '#') Then Return SetError(1) ; non-numeric input or undefined value

    If $nDivisor = 0 Then Return SetError(2) ; division by zero produces meaningless results

    Local $iExtended = 0 ; will be set to 1 if rounding or approximation occurs, or if one of the input parameters is a float
    $nDividend = __Integer64($nDividend)
    If @error Or $nDividend = 0x8000000000000000 Then $iExtended = 1
    $nDivisor = __Integer64($nDivisor)
    If @error Or $nDivisor = 0x8000000000000000 Then $iExtended = 1

    Local $aFraction[2]
    ; if both the dividend and divisor are negative, then both output values will be positive
    $aFraction[0] = ($nDividend < 0 And $nDivisor > 0) ? -1 : 1
    $aFraction[1] = ($nDivisor < 0 And $nDividend > 0) ? -1 : 1

    If $iExtended Then ; float parameters require preprocessing
        $nDividend = Number($nDividend, 3)
        $nDivisor = Number($nDivisor, 3)
        __FloatRatio($nDividend, $nDivisor)
        If @error Then Return SetError(3) ; out of range
    EndIf

    If $nDividend = 0 Then
        $aFraction[0] = 0
        $aFraction[1] = $nDivisor > 0 ? 1 : -1 ; a fraction may have a value of negative zero (purpose unknown)
        Return $aFraction
    EndIf

    $nDividend = _Abs64($nDividend)
    $nDivisor = _Abs64($nDivisor)

    If $nDividend <> 0 Then __Simplify($nDividend, $nDivisor) ; division by the greatest common divisor

    $aFraction[0] *= $nDividend ; return values may be negative
    $aFraction[1] *= $nDivisor ; as above.
    Return SetExtended($iExtended, $aFraction)
EndFunc ;==> _Fraction


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionAbs
; Description ...: Calculates the absolute value of a fraction.
; Syntax.........: _FractionAbs($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing the absolute values of both dividend and divisor.
;                  Failure sets @error to 1 if the input is not a valid array containing both a dividend and a divisor.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionAbs($aFraction)
    If Not _IsFraction($aFraction) Then Return SetError(1)
    $aFraction[0] = _Abs64($aFraction[0])
    $aFraction[1] = _Abs64($aFraction[1])
    Return $aFraction
EndFunc ;==> _FractionAbs


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionAdd
; Description ...: Calculates the sum of two fractions.
; Syntax.........: _FractionAdd($aFraction1, $aFraction2)
; Parameters.....; $aFraction1 - The first two element array containing a dividend and a divisor.
;                  $aFraction2 - The second two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing the sum of the two fractions.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error = 2 The divisor cannot become zero.
;                  |@error = 3 Out of range.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionAdd($aFraction1, $aFraction2)
    If Not (_IsFraction($aFraction1) And _IsFraction($aFraction2)) Then Return SetError(1)

    Local $iValue_1, $iValue_2, $iDividend, $iDivisor, $iExtended = 0
    If __OverflowDetect('*', $aFraction1[0], $aFraction2[1], $iValue_1) Then $iExtended = 1
    If __OverflowDetect('*', $aFraction1[1], $aFraction2[0], $iValue_2) Then $iExtended = 1
    If __OverflowDetect('+', $iValue_1, $iValue_2, $iDividend) Then $iExtended = 1
    If __OverflowDetect('*', $aFraction1[1], $aFraction2[1], $iDivisor) Then $iExtended = 1

    Local $aAddition = _Fraction($iDividend, $iDivisor)
    If @extended Then $iExtended = 1

    Return SetError(@error, $iExtended, $aAddition)
EndFunc ;==> _FractionAdd


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionApproximate
; Description ...: Approximates the value of a fraction according to limits imposed on the size of the divisor.
; Syntax.........: _FractionApproximate($aFraction, $iMaxDivisor)
; Parameters.....; $aFraction - A two element array containing a valid dividend and divisor.
;                  $iMaxDivisor - The maximum numeric limit for the divisor.
; Return values .: Success - Returns a two element array containing the approximated fraction.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input for $aFraction.
;                  |@error = 2 Invalid input for $iMaxDivisor.
; Author ........: czardas
; Comments ......; Approximates fractions using the method of continued fractions.
; ==============================================================================================================================

Func _FractionApproximate($aFraction, $iMaxDivisor)
    If Not _IsFraction($aFraction) Then Return SetError(1)
    Local $bNegative = @extended

    $iMaxDivisor = _Abs64($iMaxDivisor)
    If @extended Then Return SetError(2, 0, $aFraction)

    Local $aCurrentFraction = _FractionAbs($aFraction)
    If $iMaxDivisor < 1 Or $iMaxDivisor >= $aCurrentFraction[1] Or $aCurrentFraction[1] <= 1 Then Return SetError(2, 0, $aFraction)

    ; determine the terms of the continued fraction
    Local $sFractionOfFraction = ''
    Do
        $sFractionOfFraction &= __Quotient($aCurrentFraction[0], $aCurrentFraction[1]) & ','
        $aCurrentFraction[0] = Mod($aCurrentFraction[0], $aCurrentFraction[1])
        $aCurrentFraction = _Reciprocal($aCurrentFraction)
    Until @error

    Local $aContinued = StringSplit(StringTrimRight($sFractionOfFraction, 1), ',', 2)
    Local $iTry, $iRange, $iMin = 0, $iMax = Ubound($aContinued) -1, $aConvergence[2]

    ; binary search algorithm
    Do
        $aConvergence[0] = 0
        $aConvergence[1] = 1
        $iRange = $iMax - $iMin +1
        $iTry = $iMin + Floor($iRange/2)
        If $iTry > $iMax Then $iTry = $iMax ; added patch

        ; evaluate the significant first few terms of the continued fraction
        If $iTry > 0 Then
            For $i = $iTry To 1 Step -1
                $aConvergence = _FractionAdd($aConvergence, _Fraction(Number($aContinued[$i])))
                $aConvergence = _Reciprocal($aConvergence)
            Next
        EndIf
        $aConvergence = _FractionAdd($aConvergence, _Fraction(Number($aContinued[0])))

        If $aConvergence[1] > $iMaxDivisor Then ; aim was too high - target is lower
            $iMax = $iTry -1
        Else ; aim was too low - target may be higher
            ; log low entry
            $aCurrentFraction = $aConvergence
            $iMin = $iTry +1
        EndIf
    Until $iRange <= 1

    If $bNegative Then $aCurrentFraction[(($aFraction[0] < 0) ? 0 : 1)] *= -1
    Return $aCurrentFraction
EndFunc ;==> _FractionApproximate


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionCeiling
; Description ...: Calculates the ceiling value of a fraction.
; Syntax.........: _FractionCeiling($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array ==> The first element is the ceiling value, and the divisor is always 1.
;                  Failure sets @error as follows
;                  |@error = 1 The input is not a valid array containing a dividend and a divisor.
; Author ........: czardas
; Comments ......; If the fraction is negative, then its ceiling value represents the integer part of the fraction.
; ==============================================================================================================================

Func _FractionCeiling($aFraction)
    If Not _IsFraction($aFraction) Then Return SetError(1)
    Local $bNegative = @extended
    If $aFraction[0] = 0 Then Return $aFraction

    ; for this to work we need to simplify the fraction
    $aFraction = _FractionAbs($aFraction)
    Local $iDividend = $aFraction[0], $iDivisor = $aFraction[1]
    __Simplify($iDividend, $iDivisor)
    If $iDivisor = 1 Then Return _Fraction($iDividend * ($bNegative = 0 ? 1 : -1))

    Local $iCeiling = __Quotient($iDividend, $iDivisor)
    If $bNegative Then Return _Fraction($iCeiling * -1)

    Return _Fraction($iCeiling + 1)
EndFunc ;==> _FractionCeiling


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionDivide
; Description ...: Divides the first fraction by the second.
; Syntax.........: _FractionDivide($aDividend, $aDivisor)
; Parameters.....; $aDividend - The first two element array containing a dividend and a divisor.
;                  $aDivisor - The second two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing the result after division.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error = 2 The divisor cannot become zero.
;                  |@error = 3 Out of range.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionDivide($aDividend, $aDivisor)
    If Not (_IsFraction($aDividend) And _IsFraction($aDivisor)) Then Return SetError(1)

    Local $iValue_1, $iValue_2, $iExtended = 0
    If __OverflowDetect('*', $aDividend[0], $aDivisor[1], $iValue_1) Then $iExtended = 1
    If __OverflowDetect('*', $aDividend[1], $aDivisor[0], $iValue_2) Then $iExtended = 1

    If $aDivisor[0] = 0 Then Return SetError(2)
    Local $aDivision = _Fraction($iValue_1, $iValue_2)
    If @extended Then $iExtended = 1

    Return SetError(@error, $iExtended, $aDivision)
EndFunc ;==> _FractionDivide


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionFloor
; Description ...: Calculates the floor value of a fraction.
; Syntax.........: _FractionFloor($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array ==> The first element is the floor value, and the divisor is always 1.
;                  Failure sets @error as follows
;                  |@error = 1 The input is not a valid array containing a dividend and a divisor.
; Author ........: czardas
; Comments ......; If the fraction is positive, then its floor value represents the integer part of the fraction.
; ==============================================================================================================================

Func _FractionFloor($aFraction)
    If Not _IsFraction($aFraction) Then Return SetError(1)
    Local $bNegative = @extended
    If $aFraction[0] = 0 Then Return $aFraction

    ; for this to work we need to simplify the fraction
    $aFraction = _FractionAbs($aFraction)
    Local $iDividend = $aFraction[0], $iDivisor = $aFraction[1]
    __Simplify($iDividend, $iDivisor)
    If $iDivisor = 1 Then Return _Fraction($iDividend * ($bNegative = 0 ? 1 : -1))

    Local $iFloor = __Quotient($iDividend, $iDivisor)

    If Not $bNegative Then Return _Fraction($iFloor)
    Return _Fraction($iFloor * -1 - 1)
EndFunc ;==> _FractionFloor


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionMod
; Description ...: Performs the modulus operation with two fractions.
; Syntax.........: _FractionMod($aDividend, $aDivisor)
; Parameters.....; $aDividend - The first fraction is the dividend array.
;                  $aDivisor - The second fraction is the divisor array.
; Return values .: Success - Returns a two element array containing the modulus of $aDividend and $aDivisor.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error to:
;                  |@error = 1 Out of bounds - Fraction division failure.
;                  |@error = 2 Out of bounds - Fraction multiplication failure.
;                  |@error = 3 Out of bounds - Fraction subtraction failure.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionMod($aDividend, $aDivisor)
    Local $iExtended = 0, $aDivision = _FractionDivide($aDividend, $aDivisor)
    If @error Then Return SetError(1)
    If @extended Then $iExtended = @extended

    Local $aModulus[2]
    If $aDividend[0] = 0 Then
        $aModulus[0] = 0
        $aModulus[1] = ($aDividend[0] < 0) ? -1 : 1
        Return $aModulus
    EndIf

    Local $aMultiple = _FractionMultiply(_FractionAbs($aDivisor), _FractionFloor(_FractionAbs($aDivision)))
    If @error Then Return SetError(2)
    If @extended Then $iExtended = @extended

    $aModulus = _FractionSubtract(_FractionAbs($aDividend), $aMultiple)
    If @error Then Return SetError(3)
    If @extended Then $iExtended = @extended

    If _IsFractionNegative($aDividend) Then
        If $aDividend[0] < 0 Then
            $aModulus[0] *= -1
        Else
            $aModulus[1] *= -1
        EndIf
    EndIf

    Return SetExtended($iExtended, $aModulus)
EndFunc ;==> _FractionMod


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionMultiply
; Description ...: Calculates the product of two fractions.
; Syntax.........: _FractionMultiply($aFraction1, $aFraction2)
; Parameters.....; $aFraction1 - The first two element array containing a dividend and a divisor.
;                  $aFraction2 - The second two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing the product of the two fractions.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error > 1 Internal calculations went out of range.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionMultiply($aFraction1, $aFraction2)
    If Not (_IsFraction($aFraction1) And _IsFraction($aFraction2)) Then Return SetError(1)

    Local $iValue_1, $iValue_2, $iExtended = 0
    If __OverflowDetect('*', $aFraction1[0], $aFraction2[0], $iValue_1) Then $iExtended = 1
    If __OverflowDetect('*', $aFraction1[1], $aFraction2[1], $iValue_2) Then $iExtended = 1

    Local $aProduct = _Fraction($iValue_1, $iValue_2)
    If @extended Then $iExtended = 1

    Return SetError(@error, $iExtended, $aProduct)
EndFunc ;==> _FractionMultiply


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionPower
; Description ...: Raises a fraction to the power of a fraction.
; Syntax.........: _FractionPower($aFraction, $aPower)
; Parameters.....; $aFraction - The first two element array containing a dividend and a divisor.
;                  $aPower - The second two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing $aFraction to the power of $aPower.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error = 3 Out of range.
;                  |@error = 5 Imaginary fraction detected.
; Author ........: czardas
; Comments ......; Calculating fractional powers of approximated negative fractions leads to ambiguity.
; ==============================================================================================================================

Func _FractionPower($aFraction, $aPower)
    If Not _IsFraction($aPower) Then Return SetError(1)
    Local $bNegative = _IsFractionNegative($aFraction)
    If @error Then Return SetError(1)

    If $bNegative And Mod($aPower[1], 2) = 0 Then Return SetError(5)
    Local $iSign = ($bNegative And Mod($aPower[0], 2) <> 0) ? -1 : 1
    $aFraction = _FractionAbs($aFraction)

    Local $iExtended, $iPower = __WholeNumberDivision($aPower[0], $aPower[1])
    If @extended Then $iExtended = 1

    Local $iDividend
    If $iExtended Then
        $iDividend = $aFraction[0] ^ $iPower
    Else
        $iDividend = _Power64($aFraction[0], $iPower)
        If @extended Then $iExtended = 1
    EndIf

    Local $iDivisor
    If $iExtended Then
        $iDivisor = $aFraction[1] ^ $iPower
    Else
        $iDivisor = _Power64($aFraction[1], $iPower)
        If @extended Then $iExtended = 1
    EndIf

    $aPower = _Fraction($iSign * $iDividend, $iDivisor)
    If @extended Then $iExtended = 1

    Return SetError(@error, $iExtended, $aPower)
EndFunc ;==> FractionPower


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionRoot
; Description ...: Calculates the fractional root of a fraction.
; Syntax.........: _FractionRoot($aFraction, $aRoot)
; Parameters.....; $aFraction - The first two element array containing a dividend and a divisor.
;                  $aRoot - The second two element array containing a dividend and a divisor.
; Return values .: Success - Returns a two element array containing $aFraction to the power of the reciprocal of $aRoot.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error = 3 Out of range.
;                  |@error = 5 Imaginary fraction detected.
; Author ........: czardas
; Comments ......; Calculating fractional roots of approximated negative fractions leads to ambiguity.
; ==============================================================================================================================

Func _FractionRoot($aFraction, $aRoot)
    If Not _IsFraction($aRoot) Then Return SetError(1)
    Local $bNegative = _IsFractionNegative($aFraction)
    If @error Then Return SetError(1)

    If $bNegative And Mod($aRoot[0], 2) = 0 Then Return SetError(5)
    Local $iSign = ($bNegative And Mod($aRoot[1], 2) <> 0) ? -1 : 1
    $aFraction = _FractionAbs($aFraction)

    Local $iExtended, $iRoot = __WholeNumberDivision($aRoot[0], $aRoot[1])
    If @extended Then $iExtended = 1

    Local $iDividend
    If $iExtended Then
        $iDividend = $aFraction[0] ^ (1 / $iRoot)
    Else
        $iDividend = _Root64($aFraction[0], $iRoot)
        If @extended Then $iExtended = 1
    EndIf

    Local $iDivisor
    If $iExtended Then
        $iDivisor = $aFraction[1] ^ (1 / $iRoot)
    Else
        $iDivisor = _Root64($aFraction[1], $iRoot)
        If @extended Then $iExtended = 1
    EndIf

    $aRoot = _Fraction($iSign * $iDividend, $iDivisor)
    If @extended Then $iExtended = 1

    Return SetError(@error, $iExtended, $aRoot)
EndFunc ;==> FractionRoot


; #FUNCTION# ===================================================================================================================
; Name...........: _FractionSubtract
; Description ...: Subtracts the second fraction from the first.
; Syntax.........: _FractionSubtract($aFraction1, $aFraction2)
; Parameters.....; $aFraction1 - The first two element array containing a dividend and a divisor.
;                  $aFraction2 - The second two element array containing a dividend and a divisor (subtracted from $aFraction1).
; Return values .: Success - Returns a two element array containing the resulting fraction.
;                  Sets @Extended to 1 if rounding or approximation occurs.
;                  Failure sets @error as follows
;                  |@error = 1 Invalid input.
;                  |@error = 2 The divisor cannot become zero.
;                  |@error = 3 Out of range.
; Author ........: czardas
; ==============================================================================================================================

Func _FractionSubtract($aFraction1, $aFraction2)
    If Not (_IsFraction($aFraction1) And _IsFraction($aFraction2)) Then Return SetError(1)

    Local $iValue_1, $iValue_2, $iDividend, $iDivisor, $iExtended = 0
    If __OverflowDetect('*', $aFraction1[0], $aFraction2[1], $iValue_1) Then $iExtended = 1
    If __OverflowDetect('*', $aFraction1[1], $aFraction2[0], $iValue_2) Then $iExtended = 1
    If __OverflowDetect('-', $iValue_1, $iValue_2, $iDividend) Then $iExtended = 1
    If __OverflowDetect('*', $aFraction1[1], $aFraction2[1], $iDivisor) Then $iExtended = 1

    Local $aSubtraction  = _Fraction($iDividend, $iDivisor)
    If @extended Then $iExtended = 1
    Return SetError(@error, $iExtended, $aSubtraction)
EndFunc ;==> _FractionSubtract


; #FUNCTION# ===================================================================================================================
; Name...........: _IsFraction
; Description ...: Checks if the input is an array containing two valid integers ==> representing dividend and divisor.
; Syntax.........: _IsFraction($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Returns True if the input matches the criteria, otherwise returns False.
; Author.........: czardas
; Comments ......; Sets @extended to 1 if the fraction is negative.
; ==============================================================================================================================

Func _IsFraction($aFraction)
    If Not IsArray($aFraction) Then Return False
    If Ubound($aFraction,0) <> 1 Or Ubound($aFraction) <> 2 Then Return False
    If Not StringInStr(VarGetType($aFraction[0]), 'Int') Or $aFraction[0] = 0x8000000000000000 Then Return False
    If Not StringInStr(VarGetType($aFraction[1]), 'Int') Or $aFraction[1] = 0x8000000000000000 Then Return False
    Return SetExtended((($aFraction[0] < 0 And $aFraction[1] > 0) Or ($aFraction[0] >= 0 And $aFraction[1] < 0)) ? 1 : 0, True)
EndFunc ;==> _IsFraction


; #FUNCTION# ===================================================================================================================
; Name...........: _IsFractionNegative
; Description ...: Checks if the input array is a negative fraction.
; Syntax.........: _IsFractionNegative($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Returns True if the dividend and the divisor are of the opposite sign, othewise returns False.
;                  Failure sets @error to 1 if the input is not a valid array containing a dividend and a divisor.
; Author.........: czardas
; ==============================================================================================================================

Func _IsFractionNegative($aFraction)
    Local $bNegative, $bIsFraction = _IsFraction($aFraction)
    $bNegative = @extended
    Return SetError(1 - $bIsFraction, 0, ($bNegative = 1))
EndFunc ;==> _IsFractionNegative


; #FUNCTION# ===================================================================================================================
; Name...........: _Reciprocal
; Description ...: Inverts a fraction by swapping the dividend and the divisor.
; Syntax.........: _Reciprocal($aFraction)
; Parameters.....; $aFraction - A two element array containing a dividend and a divisor.
; Return values .: Returns the reciprocal of the fraction.
;                  Failure sets @error as follows
;                  |@error = 1 The input is not a valid array containing a dividend and a divisor.
;                  |@error = 2 The divisor cannot become zero.
; Author.........: czardas
; ==============================================================================================================================

Func _Reciprocal($aFraction)
    If Not _IsFraction($aFraction) Then Return SetError(1)
    Local $iDivisor = $aFraction[0]
    If $iDivisor = 0 Then Return SetError(2)
    $aFraction[0] = $aFraction[1]
    $aFraction[1] = $iDivisor
    Return $aFraction
EndFunc ;==> _Reciprocal


; #INTERNAL_USE_ONLY# ==========================================================================================================
; Name...........: __FloatRatio
; Description ...: Helper function for Fraction() - preprocessing of float parameters to generate two proportional integers.
; Syntax.........: __FloatRatio([ByRef] $nDividend, [ByRef] $nDivisor)
; Parameters.....; $iDividend - Top fractional part
;                  $iDivisor - Lower fractional part
; Return values .: Success - Integer values are returned ByRef.
;                  Failure sets @error as follows
;                  |@error = 1 Out of bounds.
; Author ........: czardas
; Comments ......; No attempt has been made to accomodate for any double precision limitations.
;                  Small innacuracies can affect the 17th and (sometimes) the 16th digit in double precision.
;                  Using floats can easily be avoided by only passing integers to the function _Fraction().
;                  Input positive floats only
; ==============================================================================================================================

Func __FloatRatio(ByRef $nDividend, ByRef $nDivisor)
    If $nDivisor < 0 Then
        $nDividend *= -1
        $nDivisor *= -1
    EndIf

    If $nDivisor <> 1 Then $nDividend /= $nDivisor

    Local $nSignificand, $iExponent, $iDigits = 16 ; might as well grab as many digits as are available
    $nSignificand = __FloatToDigits($nDividend, $iDigits)
    $iExponent = @extended
    $nSignificand = Number($nSignificand, 2) ; Int-64

    While $iExponent < - 18 ; divide the significand by powers of 10
        $iDigits -= 1
        If $iDigits < 0 Then ; too small
            If $nDividend < 1 / (2 * 10 ^ 18) Then ; round down to 0 / 1
                $nSignificand = 0
                $iExponent = 0
            Else ; round up to 1 / 1000000000000000000
                $nSignificand = 1
                $iExponent = 18
            EndIf
            ExitLoop
        EndIf

        $nSignificand = __FloatToDigits($nDividend, $iDigits)
        $iExponent = @extended ; adjust the exponent to accomodate division of the significand
        $nSignificand = Number($nSignificand, 2) ; Int-64
    WEnd

    While $iExponent > 0 ; multiply the significand by powers of 10
        If __OverflowDetect('*', $nSignificand, 10, $nSignificand) Then Return SetError(1) ; too large ~ out of bounds
        $iExponent -= 1 ; adjust the exponent to accomodate multiplication of the significand
        If $iExponent = 0 Then ExitLoop
    WEnd

    $nDividend = $nSignificand ; range 0 to 1000000000000000000
    $nDivisor = _Power64(10, Abs($iExponent)) ; range 10 ^ (0 to 18) ==> powers of 10 only
EndFunc ;==> __FloatRatio


; #INTERNAL_USE_ONLY# ==========================================================================================================
; Name...........: __FloatToDigits
; Description ...: Extracts a specified number of digits from a float.
; Syntax.........: __FloatToDigits($fFloat, $iDigits)
; Parameters.....; $fFloat - The float to extract the digits from.
;                  $iDigits - The number of digits to extract after the floating point (exponential representation).
; Return values .: Success - Returns a 32-bit or 64-bit signed integer.
;                  Sets @extended to the decimal exponent. ==> $fFloat = return value * 10 ^ exponent
;                  Failure sets @error to 1 if the input is not a float or undefined.
; Author ........: czardas
; ==============================================================================================================================

Func __FloatToDigits($fFloat, $iDigits = 14)
    If VarGetType($fFloat) <> 'Double' Or StringInStr($fFloat, '#') Then Return SetError(1)
    Local $iSign = ($fFloat < 0) ? -1 : 1
    ; machine epsilon = 5 × 10^-15, so the final two digits (16 and 17) could be highly innacurate
    $fFloat = StringFormat('%.' & $iDigits & 'e', $fFloat) ; rounds to the specified number of decimal places

    Local $aFloat = StringSplit($fFloat, "e", 2) ; zero-based array
    If $iSign < 0 Then $aFloat[0] = StringTrimLeft($aFloat[0], 1) ; remove the minus sign

    ; remove the decimal point and trailing zeros
    $aFloat[0] = StringLeft($aFloat[0], 1) & StringRegExpReplace(StringRight($aFloat[0], $iDigits), '(0+\z)', '')
    $aFloat[1] += 1 - StringLen($aFloat[0]) ; adjust the exponent to accommodate changes

    Return SetExtended($aFloat[1], Int($aFloat[0]) * $iSign) ; add back the minus sign
EndFunc ;==> __FloatToDigits


; #INTERNAL_USE_ONLY# ==========================================================================================================
; Name...........: __GCD
; Description ...: Calculates the greatest common divisor of two integers. Original function name ==> _Greatest_Common_Factor()
; Syntax.........: __GCD($iValue1, $iValue2)
; Parameters.....; $iValue1 - First Integer.
;                  $iValue2 - Second Integer.
; Return values .: Success - Returns the greatest common divisor of $iValue1 and $iValue2.
; Author.........: Pheonix XL
; Modified.......; czardas
; Comments ......; IMPORTANT - Error checks have been removed. You must run the checks if you use this function yourself.
; ==============================================================================================================================

Func __GCD($iValue1, $iValue2) ; Only accepts positive integers greater than zero.
    ; If Not (IsInt($iValue1) And IsInt($iValue2)) Or $iValue1 < 1 Or $iValue2 < 1 Then Return SetError(1)

    Local $iToggle
    If  $iValue1 < $iValue2 Then ; Switch values.
        $iToggle = $iValue1
        $iValue1 = $iValue2
        $iValue2 = $iToggle
    EndIf

    Local $iModulus
    While 1 ; Method of Euclid.
        $iModulus = Mod($iValue1, $iValue2)
        If $iModulus = 0 Then ExitLoop
        $iValue1 = $iValue2
        $iValue2 = $iModulus
    WEnd

    Return $iValue2
EndFunc ;==> __GCD


; #INTERNAL_USE_ONLY# ==========================================================================================================
; Name...........: __Quotient
; Description ...: Returns the quotient after division ~(the whole number part of a fraction).
; Syntax.........: __Quotient($nDividend, $nDivisor)
; Parameters.....; $iDividend - The integer to divide
;                  $iDivisor - The integer to divide by
; Return values .: Returns the quotient.
; Author ........: czardas
; Comments ......; Uses the same correction method as __WholeNumberDivision() in operator64.au3.
; ==============================================================================================================================

Func __Quotient($nDividend, $nDivisor)
    Local $iQuotient = Floor($nDividend / $nDivisor), $iDifference, $iIntegral

    While $iQuotient * $nDivisor > $nDividend ; division is overstated
        $iDifference = ($nDivisor * $iQuotient) - $nDividend
        $iIntegral = Floor($iDifference / $nDivisor) ; avoid shooting beyond the target
        If $iIntegral = 0 Then $iIntegral = 1 ; prevents hanging in an infinite loop
        $iQuotient -= $iIntegral
    WEnd

    While $iQuotient * $nDivisor < $nDividend ; division is understated
        $iDifference = $nDividend - ($nDivisor * $iQuotient)
        $iIntegral = Floor($iDifference / $nDivisor) ; as above
        If $iIntegral = 0 Then ExitLoop ; we have found the floor already
        $iQuotient += $iIntegral
    WEnd

    Return $iQuotient
EndFunc ;==> __Quotient


; #INTERNAL_USE_ONLY# ==========================================================================================================
; Name...........: __Simplify
; Description ...: Simplification by division.
; Syntax.........: __Simplify($iDividend, $iDivisor)
; Parameters.....; $iDividend - Top fractional part.
;                  $iDivisor - Lower fractional part.
; Author ........: czardas
; ==============================================================================================================================

Func __Simplify(ByRef $iDividend, ByRef $iDivisor)
    Local $iGCD = __GCD($iDividend, $iDivisor)
    If $iGCD > 1 Then
        $iDividend = __WholeNumberDivision($iDividend, $iGCD)
        $iDivisor = __WholeNumberDivision($iDivisor, $iGCD)
    EndIf
EndFunc ;==> __Simplify

Examples - currently testing for accuracy and possible bugs.

#include 'Fraction.au3'

Local $aFraction = _Fraction(3.1416)
If @error Then Exit ; ==> Error handling.
ConsoleWrite("3.1416 = " & $aFraction[0] & " / " & $aFraction[1] & @LF)

$aFraction = _Fraction(0.125 , 2)
ConsoleWrite("0.125 / 2 = " & $aFraction[0] & " / " & $aFraction[1] & @LF)

$aFraction = _Fraction(0.00125, -0.32)
ConsoleWrite("0.00125 / -0.32 = " & $aFraction[0] & " / " & $aFraction[1] & @LF)

$aFraction = _Fraction(86418753, 2977963408767)
ConsoleWrite("86418753 / 2977963408767 = " & $aFraction[0] & " / " & $aFraction[1] & @LF)

; Multiply two fractions (27 / 28 x 374 / 555) using whole number arithmetic:
Local $aProduct = _FractionMultiply(_Fraction(27, 28), _Fraction(374, 555))
ConsoleWrite("27 / 28 x 374 / 555 = " & $aProduct[0] & " / " & $aProduct[1] & @LF)

; The modulus of two fractions:
Local $aMod = _FractionMod(_Fraction(-1, 2), _Fraction(1, 3))
ConsoleWrite("Mod(-1/2, 1/3) = " & $aMod[0] & "/" & $aMod[1] & @LF)

; Represent pi (as accurately as possible) using a fraction with denominator of no more than thirteen digits.
Local $aPi = _FractionApproximate(_Fraction(3.14159265358979), 1e+013 -1)
ConsoleWrite($aPi[0] & " / " & $aPi[1] & " = " & $aPi[0] / $aPi[1] & " ~ Pi" & @LF)

Local $aR2 = _FractionApproximate(_Fraction(2^.5), 1.0e+13 -1)
ConsoleWrite($aR2[0] & " / " & $aR2[1] & " = " & $aR2[0] / $aR2[1] & " ~ 2^(1/2)" & @LF)

Local $aLarge = _Fraction(1.23456789e+017,100000000000000100)
If @error Then MsgBox(0, "", @error)
ConsoleWrite(@extended & @LF)
ConsoleWrite($aLarge[0] & " / " & $aLarge[1] & " = " & $aLarge[0] / $aLarge[1]  & " = " & 1.23456789e+017 / 100000000000001000 & @LF)

Local $aSmall = _Fraction(1.23456789e-200,8.64197523e-192)
If @error Then MsgBox(0, "", @error)
ConsoleWrite(@extended & @LF)
ConsoleWrite($aSmall[0] & " / " & $aSmall[1] & " = " & $aSmall[0] / $aSmall[1]  & " = " & 1.23456789e-200 / 8.64197523e-192 & @LF)

Local $aTooSmall = _Fraction(1.23456789e-200,100000000000000100)
If @error Then MsgBox(0, "", @error)
ConsoleWrite("@extended = " & @extended & @LF)
ConsoleWrite($aTooSmall[0] & " / " & $aTooSmall[1] & " = " & $aTooSmall[0] / $aTooSmall[1]  & " = " & 1.23456789e-200 / 100000000000001000 & @LF)

Local $aTooLarge = _Fraction(100000000000000100, 1.23456789e-200)
ConsoleWrite("@error = " & @error & @LF)

Local $aAddApprox = _FractionAdd(_Fraction(134567890000, 999999999999), _Fraction(987654321000, 777777777777777))
ConsoleWrite("@extended = " & @extended & @LF)
ConsoleWrite($aAddApprox[0] & " / " & $aAddApprox[1] & " = " & $aAddApprox[0] / $aAddApprox[1]  & " = " & (134567890000/999999999999 + 987654321000/777777777777777)

;

See post 33 for information on the latest update.

Edited by czardas
4 people like this

Share this post


Link to post
Share on other sites



Nice! If I can find a way to use it then I will.

I really cannot contribute, as this is still  above me.


Spoiler

 

"If a vegetarian eats vegetables,What the heck does a humanitarian eat?"

"I hear voices in my head, but I ignore them and continue on killing."

"You have forced me to raise the indifference warning to beige, it's a beige alert people. As with all beige alerts please prepare to think about the possibility of caring."

An optimist says that giving someone power DOESN'T immediately turn them into a sadist. A pessimist says that giving someone power doesn't IMMEDIATELY turn them into a sadist.

 

 

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

Thanks Draygoes, the idea is to keep the original information intact and basically do maths with whole numbers. This way absolute accuracy is pretty much guaranteed, even when the whole numbers form part of a fraction. I think it's useful for small closed systems which use a lot of calculation. Only at the end of a number of precise calculations should the result be converted back to a float. This is the best way to maintain accuracy throughout a long winded calculation - where small inacuracies will have a knock on effect.

Edited by czardas

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

Update to first post. The internal function __Expand() was causing problems. Thanks to a suggestion by guinness, the modifications I made seem to be working correctly. I also added an example of multiplying two fractions together, so you can see how maths can be done using this (100% accurate) method. The method is what you might call 'Old School', but you shouldn't let that put you off: you might need to use something like this one day.

Edited by czardas

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

I would have done it using greatest common divisor to convert a float number to a fraction. Nice approach czardas!  :thumbsup:

Br,

UEZ

Edited by UEZ

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites

#6 ·  Posted (edited)

Thanks UEZ, and you're absolutely right! I was looking into this today and it would be much faster. There's a good method for GCD / HCF, used by PheonixXL, which I tested for speed earlier. I wasn't fully aware of the method until this afternoon - although something about it seems vaguely familiar. I think it's often a good exercise to try and solve a problem yourself, but finding neat little shortcuts is always good.

The prime sieve method was part of an earlier script I wrote: I thought I might save time using the same code again. After the speed tests I have revised that opinion. I will try implementing GCD. :thumbsup:

Edited by czardas

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

Code updated in the first post.

After a slight delay, I've changed the method to use GCD - the only serious approach really. Although the method I used earlier was sound in principle, further tests revealed hidden bugs which (I believe) had everything to do with implementation. Until I get to the bottom of this, I thought it best to remove the original code.

It seems that my assumption of 15 digit accuracy was incorrect, although I'm not entirely sure why at this moment in time. I have therefore limited the function to 14 digit input (for the time being), which seems to be working so far. I don't really see much need for such extreme fractions outside pure mathematics.

I'm convinced that I have seen this method of Euclid previously - maybe it's deja-vu. Anyway I needed further convincing that such a simple idea was even possible:

g = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1 :blink:

 

http://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity

Actually Euclid's proofs are very beautiful. :)


Incidentally: the forum's tagged content seems to disappear when logged in to the forum: guests can see it but members cannot. So here's the link to the UDF (by PheonixXL) where I found the GCD code. The UDF uses string representation of a fraction, as opposed to using an array containing two integers. >mathsEX UDF

Edited by czardas

Share this post


Link to post
Share on other sites

You might have fun trying the binary GCD variant and Knuth-Shönage. For those not too faint-hearted, I higly recommend the evaluation of the traditional euclidean algorithm discussed by Knuth in TAOCP vol 2.

Also the euclidean algorithm is important to music.

Disclaimer: I'm a big big big fan of the magic of the extended euclidean algorithm for too many reasons to expose here.

1 person likes this

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

The second link is a nice find and the article is well written. This area of music theory has fascinated me for years. I had an idea back in 1991 which involves a different solution to the tuning problem. Instead of using approximations (as is the case with equal temperament), it is possible to make small adjustments to pitch when needed (if the key changes). This is something that many musicians do already, but without necessarily knowing the maths or theory.

There are limitations to the musician's real-world approach, but nowadays computers should be able to circumvent some of these limitations (put simply) by designating pitch ranges to notes, and perhaps allowing a some drift in the frequency of the fundamental to accomodate the comma mentioned in the article. I call this idea 'Drifting Temperament', and there are several possible implementations that could be tested. Theoretically it should be possible to enhance music, making it sound richer and super vibrant. You might have to redesign speakers to cope with the extra sympathetic resonance though. ;)

Unfortunately AutoIt (alone) isn't capable of testing this. It would require fractional calculations converted to floating point pitch values. You can do the maths easily enough, but finding software that is capable of producing cents (100th of a semitone) seems to be an issue. I'm sure the hardware is up to the task. Anyway, one problem at a time hey!

Now back to the regular schedule - this was quite a digression.

BTW, this isn't the reason I created this function, but investigating the maths involved was indeed on the back of my mind. Coincidence perhaps! :)

Edited by czardas

Share this post


Link to post
Share on other sites

#10 ·  Posted (edited)

Total bugfix and library expansion in 1st post ==> _FractionAbs(), _FractionAdd(), _FractionCeiling(), _FractionDivide(), _FractionFloor(), _FractionMod(), _FractionMultiply(), _FractionSubtract(), _IsFraction(), _IsFractionNegative(), _Reciprocal(). I also introduced the value negative zero (0 / -1) ... all other values can be negative so why not? ;)

The fifteen digit limit has been restored, although it still cannot be 100% guaranteed that internal rounding adjustments won't cause small inacuracies in extreme cases. Obsticles encountered during development were caused by some perplexing anomalies idiosyncrasies:

;

; Nines anomaly
Local $iNines = 999999999999999
Nines($iNines)
MsgBox(0, "Hmm", $iNines) ; 1000000000000000 - What happened here?

Func Nines(ByRef $iNines)
    $iNines = Abs($iNines)
    $iNines = Int($iNines)
EndFunc

; Another Anomaly
Local $nFloat = 3.1416
While Not IsInt($nFloat)
    $nFloat *= 10
WEnd
MsgBox(0, "No worries!", $nFloat) ; 3.1416e+016 - I was expecting something a bit smaller.

;

Regardless of these (mostly circumvented) rare and sometimes insignificant anomalies idiosyncrasies, you can generally perform precision calculations with fractions which will be more accurate than if you were to use floats to do the same task.

Edit : function names missing underscore.

Edited by czardas

Share this post


Link to post
Share on other sites

Both examples are not anomalies: they are illustrations of our arithmetical mental world biaised towards decimal representation and its difficulty to fit actual maths.

For instance the first one (here called "nines") is a floating-point paraphrasing of:

1/3 = 0.33333333333333333333333...

1/3 = 0.33333333333333333333333...

1/3 = 0.33333333333333333333333...

----    --------------------------------------------

 1   = 0.99999999999999999999999...

In "pure" maths, the ellipsis are the crux matter (i.e. an infinite number of significant digits), but here we fold the "problem" into a non-infinite number of digits, somehow complexified by the binary representation used by IEEE754. The nature of the pseudo-issue is nonetheless similar.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

Both examples are not anomalies: they are illustrations of our arithmetical mental world biaised towards decimal representation and its difficulty to fit actual maths.

 

Perhaps not an anomaly to those who trust in the maxim that all things must have a cause. Actually I borrowed the phraseology. Dispite all of this, there has to be more going on beneath the surface because the same commands executed without passing the ByRef parameter to Nines() unexpectedly produces an expected result. :ermm:

:

Local $iNines = 999999999999999
$iNines = Abs($iNines)
$iNines = Int($iNines)
Msgbox(0, "As expected", $iNines) ; 999999999999999

;

Well it seems unusual to me at this moment in time - I wonder what's going on. Good comment about limitations of the decimal system BTW. :)

Edited by czardas

Share this post


Link to post
Share on other sites

Your last example produces 1000000000000000 for me running x86 or x64. Abs appears to return a Double for me on Windows 7.


If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

Thanks for testing it. I tested it on XP SP3 (x86) with the latest stable version of AutoIt and it behaves differently. Subtle differences are significant here because the function Fraction() should interpret 333333333333333 / 999999999999999 to be exactly equal to 1 / 3... and not equal to 333333333333333 / 1000000000000000. If accuracy fails, then the values may very quickly go out of range - or rather we end up back where we started.

Edited by czardas

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

I'm sure you all wanted to know that 127215011248504 / 40493795751381 is a very good approximation of Pi. <_<

My head was spinning trying to figure this one out. The fraction was generated using a new function FractionApproximate() - now included in the first post along with two examples. The function allows you to limit the size of a fractions denominator: approximating the fraction as closely as possible to the original value within the imposed limitation. This is similar to rounding down a float, only sometimes more accurate.

Due to the tendancy for certain types of internal calculation to go out of range with the functions in this library, you have to monitor the upper bounds of the input. Adding or multiplying fractions with large numerators and denominators will generally return an error. These functions were designed to be used with simple fractions. There are frequently going to be cases where extreme accuracy is less critical. So if you want to combine floats with using fractions, and avoid out of range errors; instead of rounding you can use fraction approximation.

continued-fractions9.png

It appears that the method of 'Continued Fractions' is rarely seen nowadays, but it's very interesting nontheless. Here are some links which might make it easier to understand:

http://www.millersville.edu/~bikenaga/number-theory/continued-fractions/continued-fractions.html

http://www.millersville.edu/~bikenaga/number-theory/approximation-by-rationals/approximation-by-rationals.html

http://www.math.uiuc.edu/~hildebr/453.spring11/pi-cf.pdf


I should also mention that these function names will be prefixed with the customary underscore in due course, to comply with standard UDF practices.

Edited by czardas

Share this post


Link to post
Share on other sites

I don't know who's still at school or university here, but if you are chances are you are familiar with the current casio calculators, which give you answers in terms of fractions, square roots, and pi when it is reasonable to do so. For example, sin(pi/3) = sqrt(3)/2. With those limits, you could define a new kind of "fraction" that had 4 components: A/B * sqrt© * pi^D, Of course in that vein you can keep adding variables and layers of complexity ad nauseam.

1 person likes this

Share this post


Link to post
Share on other sites

#17 ·  Posted (edited)

These casio calculators sound quite good. :)

Actually I wasn't planning on incorporating any trigonometry, and pi was used here as a test case for the approximation method above. Irrational roots are something that I would like to incorporate, but I haven't thought very deeply about it.

Edited by czardas

Share this post


Link to post
Share on other sites

#18 ·  Posted (edited)

I have removed input size limitations for _Fraction(). Input size is now unlimited within the confines of AutoIt. The return values still remain within double precision (or maybe I should say quadruple precision since a fraction is made up of two doubles). With several functions, the extended flag is set to 1 when: either rounding or an approximation has occurred, or if one of the input parameters to _Fraction() is a float. The output is limited to regions detailed below.

;

Input Size Limits for _Fraction()
Unlimited within the confines of AutoIt (approximately) between -1e+308 and +1e+308
Smallest value (approximately) 1e-323

Negative Output Size Limits for _Fraction()
1e+015 /-1 Out of range
999999999999999 /-1 To -1/ 999999999999999 negative default range
-1/ 999999999999999 To -1/ 1999999999999998 rounded down to -1/ 999999999999999
-1/ 1999999999999998 To 0/-1 rounded up to 0/-1

Positive Output Size Limits for _Fraction()
0/1 To 1/ 1999999999999998 rounded down to 0/1
1/ 1999999999999998 To 1/ 999999999999999 rounded up to 1/ 999999999999999
1/ 999999999999999 To 999999999999999 /1 positive default range
1e+015 /1 Out of range

;

See first post. Documentation still needs updating. I also replaced the troublesome function __Expand() with __RawFraction(); it's a bit of a misnomer because the returned data is actually half-cooked. Some more changes will be added soon, but functionality will not likely be affected. What remains to be done are mainly optimization procedures and a bit more tidying. ;)

Edit

Forum code syntax highlighting still has issues. >_<

Edited by czardas

Share this post


Link to post
Share on other sites

#19 ·  Posted (edited)

Accuracy of Double Precision Compared with that of a Fraction

While there are still some considerations and small modifications to be made, it's time to start illustrating the use of this library with some easy examples. There are quite a few tests need doing. Here's the first - testing the precision of _FractionApproximate(). It turns out that 16 different approximations for Pi are viewed as exactly equal when converted back to a double. Of course they cannot be equal, but double precision is not accurate enough to differentiate between them. I consider that an excellent result. :D

;

#include 'Fraction.au3'

Global Const $fPi = 3.14159265358979

Local $aPi = _Fraction($fPi)
Local $aFr = $aPi, $iMaxDivisor

Do
    ConsoleWrite($aFr[0] / $aFr[1] & " = " & $aFr[0] & "/" & $aFr[1] & @LF)
    $iMaxDivisor = $aFr[1] -1
    $aFr = _FractionApproximate($aPi, $iMaxDivisor) ; Approximate Pi
Until @error

;

Output:

3.14159265358979 = 314159265358979/100000000000000
3.14159265358979 = 127215011248504/40493795751381
3.14159265358979 = 59729242861971/19012408497238
3.14159265358979 = 7756525524562/2468978756905
3.14159265358979 = 5433564190037/1729557198903
3.14159265358979 = 2322961334525/739421558002
3.14159265358979 = 787641520987/250714082899
3.14159265358979 = 747678292551/237993392204
3.14159265358979 = 39963228436/12720690695
3.14159265358979 = 28340180703/9020959694
3.14159265358979 = 11623047733/3699731001
3.14159265358979 = 5094085237/1621497692
3.14159265358979 = 1434877259/456735617
3.14159265358979 = 789453460/251290841
3.14159265358979 = 645423799/205444776
3.14159265358979 = 144029661/45846065
3.14159265358979 = 69305155/22060516
3.14159265358982 = 5419351/1725033
3.14159265358939 = 4272943/1360120
3.1415926535914 = 1146408/364913
3.14159265358108 = 833719/265381
3.14159265361894 = 312689/99532
3.14159265346744 = 208341/66317
3.14159265392142 = 104348/33215
3.1415926530119 = 103993/33102
3.14159292035398 = 355/113
3.14150943396226 = 333/106
3.14285714285714 = 22/7
3 = 3/1

;

09/02/2015 : A bug was discovered in _FractionApproximate(), fixed in the first post.

10/02/2015 : _FractionMod() now also allows approximations.

Edited by czardas

Share this post


Link to post
Share on other sites

#20 ·  Posted (edited)

When Not to Use Fractions

Using _Fraction() produces accurate results when the numbers involved are easy to factorize, and inaccuracies tend to multiply after a number of approximations.

On 29 iterations, the following example exposes the weakness of double precision, but if you change the number of iterations to 30, _Fraction() does not do quite so well. The reason for this is partially stated above. There is also the fact that double precision is not limited to exactly 15 decimal digits and I don't exactly know how numbers are stored internally by AutoIt. Numbers are rounded  to 15 digits by the interpreter before returning a result, and fraction cannot be any more accurate than the numbers provided. This reasoning is given greater credence by the results in the previous test. It also becomes apparent that the test below is not entirely a fair one.

;

#include 'Fraction.au3'

Global $g_iAPPROXIMATIONS = 0

Local $iVal = 1/3, $aFr = _Fraction(1, 3), $iIterations = 29 ; Change this value to 30

; Do
For $i = 1 to $iIterations
    $iVal *= 2/3
    $iVal += 1/3

    $aFr = _FractionMultiply($aFr, _Fraction(2, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1

    $aFr = _FractionAdd($aFr, _Fraction(1, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1
Next

; Undo
For $i = 1 to $iIterations
    $iVal -= 1/3
    $iVal /= 2/3

    $aFr = _FractionSubtract($aFr, _Fraction(1, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1

    $aFr = _FractionDivide($aFr, _Fraction(2, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1
Next

ConsoleWrite($iVal & @LF _
        & $aFr[0] / $aFr[1] &@LF _
        & $g_iAPPROXIMATIONS & " Approximations" & @LF)

;

Earlier I mentioned closed systems. A typical closed system might be (a selected set of) rhythmic values used in music, where every duration is expressed as being proportional to another. The numbers are generally quite small, and no matter how many notes you add together the result will probably remain within range. Using floats to model such a simple system is not particularly useful because note duration is always expressed as being proportional to a power of two: not to powers of ten. There is a certain degree of incompatibility.

So there is both an up side and a down side to using this library. Whle the continued fraction approximation method is extremely accurate, it only exists in the library to enable wider compatibility with various numeric datatypes. It is essential to check the extended return value in situations where an exact result is needed. This may seem a bit of a pain, but having the option offers new advantage - otherwise unavailable. These functions may only offer any real advantage in specific cases like the one I just mentioned: to simplify certain tasks.

Edited by czardas

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Similar Content

    • czardas
      By czardas
      I have hardly any time to write any code recently. Even so, one of the most frustrating problems I, and others like myself, encounter is corruption from floating point innacuracies and integer overflow. I haven't had much time to test this, but the given example works. The method to fix division with whole numbers does not appear to be as complicated as I first anticipated. Divisible integers only!
      Func _WholeNumberDivision($iDividend, $iDivisor) ; Input ranges -9223372036854775807 To 9223372036854775807 If Not (IsInt($iDividend) And IsInt($iDivisor)) Then Return SetError(1, 0, $iDividend / $iDivisor) ; integers only If $iDivisor = 0 Then Return SetError(2, 0, $iDividend / $iDivisor) ; division by zero Local $aDiv = [$iDividend, $iDivisor], _ $iSign = 1 For $i = 0 To 1 If $aDiv[$i] > 0x7FFFFFFFFFFFFFFF Or $aDiv[$i] < 0x8000000000000001 Then Return SetError(3, 0, $iDividend / $iDivisor) ; input range exceeded If VarGetType($aDiv[$i]) = "Double" Then $aDiv[$i] = Number($aDiv[$i], 2) ; convert to Int-64 If $aDiv[$i] < 0 Then ; force positive integers $aDiv[$i] *= -1 $iSign *= -1 ; to add back later EndIf Next If Mod($aDiv[0], $aDiv[1]) Then Return SetError(4, 0, $iDividend / $iDivisor) ; not divisible If $aDiv[0] = 0 Then Return 0 If $aDiv[1] = 1 Then Return $aDiv[0] * $iSign Local $iDivision = Floor($aDiv[0] / $aDiv[1]), $iDifference, $iIntegral While $iDivision * $aDiv[1] > $aDiv[0] ; division is overstated $iDifference = ($aDiv[1] * $iDivision) - $aDiv[0] $iIntegral = Floor($iDifference / $aDiv[1]) ; avoid shooting beyond the target If $iIntegral = 0 Then $iIntegral = 1 ; prevents hanging in an infinite loop $iDivision -= $iIntegral WEnd While $iDivision * $aDiv[1] < $aDiv[0] ; division is understated $iDifference = $aDiv[0] - ($aDiv[1] * $iDivision) $iIntegral = Floor($iDifference / $aDiv[1]) If $iIntegral = 0 Then $iIntegral = 1 ; prevents hanging $iDivision += $iIntegral WEnd Return $iDivision * $iSign EndFunc This function currently works with all int-64 values with one exception - the lowest value 0x8000000000000000, and that's only divisible by powers of 2 anyway.
    • PhoenixXL
      By PhoenixXL
      I use Fractions Always In My Script
      But I never Found a UDF for That
      I made a UDF for Using
      So here I want to Share it
      I Named it MathsEx UDF but I Guess Fraction UDF would be Better

      It Requires Three Funtions Of Array.au3

      Currently Supported Functions

      ; #INDEX# ======================================================================================================================= ; Title .........: MathsEx ; AutoIt Version : 3.2.10++ ; Language ......: English ; Description ...: Functions for Carrying Out More Advanced Mathematical Calculations. ; Author(s) .....: Phoenix XL ; Included.......: Three Functions of Array.au3 i.e. _ArraySort and _ArrayReverse and __ArrayQuickSort1D Requires Array.au3 ; =============================================================================================================================== ; 0xDead=57005...............I just Like The Number :) ; #CURRENT# ===================================================================================================================== ; _Find_GCF ; _Find_LCM ; _Subtract_Fraction ; _Add_Fraction ; _Multiply_Fraction ; _Divide_Fraction ; _Reciprocal ; _Compare_Fraction ; _Quotient ; _Simplify ; _IntegerisNegative ; _IntegerisPositive ; _Get_Denominator ; _Get_Numerator ; _To_Fraction ; _To_Mixed_Fraction ; _Is_Fraction_Improper ; _Is_Fraction_Proper ; _Is_Fraction ; =============================================================================================================================== ; #INTERNAL_USE_ONLY# =========================================================================================================== ; _CheckArray ; _Greatest_Common_Factor ; _Operate_Fraction ; _Set_Sequence ; ===============================================================================================================================
      I havent Included Any Examples Yet
      The Documentation is Enough and Is Very Easy To Implement the Funtions
      Though If any Bug or Problem With The UDF Please Share It

      The UDF is Attached in the Post
      V1.1 = Fixed A Bug

      Regards
      Phoenix XL
      MathsEx V1.1.au3