Skip to content

Instantly share code, notes, and snippets.

@smoge

smoge/ratio.md

Last active September 23, 2023 23:28
Show Gist options
  • Save smoge/508f7b97162f787ec794556d86de72cb to your computer and use it in GitHub Desktop.
Save smoge/508f7b97162f787ec794556d86de72cb to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ratio.md

. Complexity Factors: Let $C(p)$ represent the Complexity Factors of a rational number $p$, defined by the tuple:

$$C(p) = (N(p), A(p), R(p))$$

where:

  • $N(p)$ is the number of terms.
  • $A(p)$ is the average coefficient size.
  • $R(p)$ is a Boolean value representing whether the rational number has a repeating pattern.

Continued Fraction:

Given a rational number $p$, its continued fraction representation is a sequence $[a_0; a_1, a_2, a_3, \ldots, a_n]$ of integers $a_i$, such that:

$$p = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ddots + \cfrac{1}{a_n}}}}$$

Given a rational number $p$ with continued fraction representation $[a_0, a_1, ..., a_n]$, its complexity factors, $C(p)$, are calculated as:

$$N(p) = n + 1$$ $$A(p) = \frac{\sum_{i=0}^{n} a_i}{n + 1}$$

$R(p)$ = True if $[a_0, a_1, ... , a_n]$ has a repeating pattern, otherwise $False$

  1. Sorting by Complexity: A list of rationals, $[p_1, p_2, \ldots, p_k]$, is sorted by complexity using their complexity factors, $C(p_1), C(p_2), ... , C(p_k)$, in ascending order. The sorting is primarily by the number of terms, secondarily by the average coefficient size, and finally by whether there is a repeating pattern or not.

Examples:

  1. Complexity Factors Calculation:
$$C\left(\frac{355}{113}\right) = \left(3, \frac{26}{3}, \text{False}\right)$$ $$C\left(\frac{35}{13}\right) = \left(4, \frac{9}{4}, \text{False}\right)$$
  1. Sorting by Complexity: Given a list of rationals, $[3/2, 13/17, 5/7, 23/29, 17/13]$, the sorted list by complexity is:
$$[3/2, 17/13, 5/7, 13/17, 23/29]$$ 
module Math.RatioComplexity (
    ComplexityFactors (..),
    calculateComplexityFactors,
    calculateComplexities,
    compareByComplexity,
    getIntegerPart,
    getFractionalPart,
    continuedFraction,
    reconstruct,
    calculateComplexity

) where

import Data.Ratio 
import Data.List 
import Data.Ord ( comparing ) 
import Data.Maybe 


type PitchVal = Rational

-- | Calculates the integer part of a rational number.
getIntegerPart :: PitchVal -> Integer
getIntegerPart = floor

-- | Calculates the fractional part of a rational number.
getFractionalPart :: PitchVal -> PitchVal
getFractionalPart = snd . properFraction

-- | Calculates the continued fraction representation of a rational number.
continuedFraction :: PitchVal -> Integer -> Maybe [Integer]
continuedFraction _ 0 = Nothing
continuedFraction x maxDepth = helper x maxDepth 0
  where
    helper _ 0 _ = Just []
    helper x' maxDepth' depth
      | depth >= maxDepth' = Just []
      | r == 0             = Just [n]
      | otherwise          = (n :) <$> helper (1 / r) maxDepth' (depth + 1)
      where
        n = getIntegerPart x'
        r = getFractionalPart x'

-- | Reconstructs a rational number from its continued fraction representation.
reconstruct :: [Integer] -> PitchVal
reconstruct [] = 0 % 1
reconstruct xs = foldl (flip (\current val -> val + 1 / current)) (1 % last xs) (map (% 1) (init xs))

-- | Calculates the complexity of a list of integers.
calculateComplexity :: [Integer] -> Float
calculateComplexity [] = 0
calculateComplexity xs = numTermsFactor + sizeFactor + maxTermFactor
  where
    numTerms = length xs
    sizes = map ((\n -> numerator n + denominator n) . (% 1)) xs
    totalSize = sum sizes
    maxTerm = maximum sizes
    numTermsFactor = fromIntegral numTerms
    sizeFactor = fromIntegral totalSize / fromIntegral numTerms
    maxTermFactor = fromIntegral maxTerm / fromIntegral numTerms

-- Define a type to represent the complexity factors
data ComplexityFactors = ComplexityFactors
    { numTerms :: Int
    , averageCoefficientSize :: Double
    , repeatingPattern :: Bool
    } deriving (Show, Eq)


-- | An instance of Ord for ComplexityFactors
instance Ord ComplexityFactors where
    compare = comparing numTerms <> comparing averageCoefficientSize <> comparing repeatingPattern


-- | Sorts a list of rationals by complexity.
compareByComplexity :: PitchVal -> PitchVal -> Ordering
compareByComplexity ratio1 ratio2 =
    compare (calculateComplexityFactors ratio1) (calculateComplexityFactors ratio2)



-- Function to calculate the complexity factors for a list of rationals
calculateComplexities :: [PitchVal] -> [ComplexityFactors]
calculateComplexities = map calculateComplexityFactors


-- -- | Sorts a list of rationals by complexity.
-- compareByComplexity' :: Rational -> Rational -> Ordering
-- compareByComplexity' ratio1 ratio2 =
--     compare (calculateComplexityFactors ratio1) (calculateComplexityFactors ratio2)



{- 
>>> calculateComplexityFactors (355 % 113)
ComplexityFactors {numTerms = 3, averageCoefficientSize = 8.666666666666666, repeatingPattern = False}

>>> calculateComplexityFactors (35 % 13) 
ComplexityFactors {numTerms = 4, averageCoefficientSize = 2.25, repeatingPattern = False}

-}

-- -- Function to sort a list of rationals by complexity
-- sortRationalsByComplexity' :: [Rational] -> [Rational]
-- sortRationalsByComplexity'  = sortedRatios 

-- | Sorts a list of rationals by complexity
sortRationalsByComplexity :: [PitchVal] -> [PitchVal]
sortRationalsByComplexity  = sortBy compareByComplexity 

{-
>>> example3 =  [ num %  den | den <- [2..11], num <- [1..11], gcd num den == 1]   :: [Rational]

>>>  sortRationalsByComplexity example3
[1 % 2,3 % 2,1 % 3,4 % 3,1 % 4,5 % 2,7 % 2,7 % 3,5 % 4,1 % 5,9 % 2,9 % 4,6 % 5,1 % 6,10 % 3,11 % 2,11 % 5,7 % 6,1 % 7,8 % 7,1 % 8,9 % 8,1 % 9,10 % 9,1 % 10,11 % 10,1 % 11,2 % 3,3 % 4,5 % 3,2 % 5,8 % 3,4 % 5,2 % 7,3 % 7,7 % 4,7 % 5,11 % 3,11 % 4,5 % 6,9 % 7,10 % 7,2 % 9,4 % 9,9 % 5,3 % 10,6 % 7,11 % 9,2 % 11,5 % 11,11 % 6,7 % 8,8 % 9,9 % 10,10 % 11,3 % 5,3 % 8,8 % 5,4 % 7,5 % 7,11 % 8,7 % 9,7 % 10,3 % 11,4 % 11,11 % 7,5 % 9,9 % 11,6 % 11,5 % 8,8 % 11,7 % 11]

-- Calculate complexities for the example rationals
>>> exampleComplexities = calculateComplexities example3  :: [ComplexityFactors]
 -}



{- 
>>> calculateComplexityFactors (355 % 113)
ComplexityFactors {numTerms = 3, averageCoefficientSize = 8.666666666666666, repeatingPattern = False}

>>> calculateComplexityFactors (35 % 13)
ComplexityFactors {numTerms = 4, averageCoefficientSize = 2.25, repeatingPattern = False}
 -}

 -- | Calculates the complexity factors for a rational number
calculateComplexityFactors :: PitchVal -> ComplexityFactors
calculateComplexityFactors ratio =
    case continuedFraction ratio 10 of
        Just cf -> let numTerms = length cf
                       totalSize = sum cf
                   in ComplexityFactors
                        { numTerms = numTerms
                        , averageCoefficientSize = fromIntegral totalSize / fromIntegral numTerms
                        , repeatingPattern = hasRepeatingPattern cf
                        }
        Nothing -> ComplexityFactors
            { numTerms = 0
            , averageCoefficientSize = 0
            , repeatingPattern = False
            }




-- hasRepeatingPattern :: [Integer] -> Bool
-- hasRepeatingPattern cf = any (\(_, groupSize) -> groupSize > 1) consecutiveGroups
--   where
--     consecutiveGroups = map (\group -> (head group, length group)) (group cf)

-- Check if a continued fraction has a repeating pattern
hasRepeatingPattern :: [Integer] -> Bool
hasRepeatingPattern cf = any (\(_, groupSize) -> groupSize > 1) consecutiveGroups
  where
    consecutiveGroups = map (\group -> (head group, length group)) (group cf)



-- | Sorts a list of rationals by complexity
sortedRatios :: [PitchVal] -> [PitchVal]
sortedRatios = sortBy compareByComplexity 


{- 
>>> sortedRatios [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17%13]
[3 % 2,17 % 13,5 % 7,13 % 17,23 % 29]


 -}

{- 
>>> rationals = [3%2, 13 % 17, 5 % 7, 21 % 29, 17%13]
>>> complexities = map (calculateComplexity . fromJust . (`continuedFraction` 20)) rationals
>>> complexities
[6.0,8.25,7.0,9.571428,8.333334]
-}


-- -- | Example demonstrating the calculation of complexity factors.
-- example1 :: ComplexityFactors
-- example1 = calculateComplexityFactors (355 % 113)

-- -- | Example demonstrating sorting rationals by complexity.
-- example2 :: [Rational]
-- example2 = sortRationalsByComplexity [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17 % 13]

-- -- | Example demonstrating the calculation of complexities for a list of rationals.
-- example3 :: [ComplexityFactors]
-- example3 = calculateComplexities [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17 % 13]



-- -- | Example demonstrating the calculation of complexities for a list of rationals.
-- example4 :: [ComplexityFactors]
-- example4 = calculateComplexities [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17 % 13]

-- -- | Example demonstrating the calculation of complexities for a list of rationals.
-- example5 :: [ComplexityFactors]
-- example5 = calculateComplexities [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17 % 13]

-- -- | Example demonstrating the calculation of complexities for a list of rationals.
-- example6 :: [ComplexityFactors]
-- example6 = calculateComplexities [3 % 2, 13 % 17, 5 % 7, 23 % 29, 17 % 13]

-- -- | Example demonstrating the calculation of complexities for a list of rationals.
-- -- example7 :: [ComplexityFactors]
-- -- example7 = calculateComplexities [3 % 2, 13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment