[GSoC] Fraction, MixedFraction, ContinuedFraction, and Percentage

Hi Everyone,

I'm really excited to write my first post in the Swift forums :slightly_smiling_face:

I'm very interested in participating in this year's GSoC, I've been contemplating to contribute to Swift for a long time and I feel the safe environment this programme offers is the right opportunity to get started.

I've been in contact with Konrad Malawski, I'm fully aware I'm very late for proposing a project idea and securing a mentor. Nonetheless, there's still a bit of time left and I'd still rather try than regretting it later—writing this proposal is already a personal achievement and I'm learning so much just doing it :+1:t2:

The following is my draft that I plan to submit tomorrow if I'm able to secure a mentor. I'm looking for feedback on the proposal itself and examples of use cases where developers could benefit from this project. The timeline is still a work in progress.

Thank you @ktoso for encouraging me :slightly_smiling_face:

Definitions


  • Fraction: The quotient of two numbers without loss of precision.
  • MixedFraction: The quotient and remainder of a fraction.
  • ContinuedFraction: A fraction of infinite length whose denominator is a quantity plus a fraction.
  • Percentage: A fraction with a denominator of one hundred.

Abstract


Swift doesn't provide rational types in its standard library. A fraction type is useful when a developer wishes to simplify symbolic expressions without needing to worry about floating point errors. I'm proposing to implement types representing a fraction, mixed fraction, continued fraction and a percentage to the Swift Numerics package.

Proposal Details


Project size

Large (350 hours)

Recommended skills

  • Proficiency with Swift
  • Interest in numerical computing.

Expected difficulty

Medium

Description

Add Fraction, MixedFraction, ContinuedFraction and Percentage to the Swift Numerics package.

Some programming languages provide a built-in rational data type to represent rational numbers like 1/3 and -11/7 without rounding and to do arithmetic on them.

  • C++ has included support for compile-time rational arithmetic in the form of the contents of its standard library's ratio header.
  • Go provides rational numbers in the standard library, in the math/big package.
  • Python's standard library includes a fraction type in the fractions module.
  • The Apache Commons math library provides rational numbers for Java.

See also:

  • This is my first try at tackling fractions in Swift.
  • This issue and this gist are other examples of rational types in Swift.

Expected deliverables

The project would fit nicely as a new module in Swift Numerics with its own branch. The deliverables would include source code with tests and documentation.

Potential mentor(s)

I'm still looking for a mentor.

Proposed Design


I plan to follow the standard library contributor guidelines and conventions, and use Swift's numeric protocols as much as possible.

Rational

A new Rational protocol will be needed to implement the four fraction types detailed below. The main difference with my first try, is this version is generic so that developers can declare their fraction's terms to be any BinaryInteger as well as BigInt when it's merged. BigInt gives a new meaning to this project and re-evaluates whether implementing a fraction type is beneficial.

public protocol Rational {
  associatedtype Term
  where Term: BinaryInteger

  var numerator: Term { get }
  var denominator: Term { get }

  var quotient: Double { get }
}

extension Rational {
  public var isProper: Bool { get }
  public var isImproper: Bool { get }
  public var isWhole: Bool { get }
  internal var isNormalized: Bool { get }
  internal func normalized() -> Self
  internal mutating func normalize()
}

I believe Rational types shouldn't conform to FloatingPoint, however, NaN and Infinity must be represented. I could create new protocols RepresentableByNaN and RepresentableByInfinity for this purpose that would copy some of the properties from FloatingPoint. If that design gets accepted, I wish to pitch these two protocols for the standard library and in turn have FloatingPoint conform to both.

extension Rational
where Self: RepresentableByNaN {
	public var isNaN: Bool { get }
	public static var nan: Self { get }
}

extension Rational
where Self: RepresentableByInfinity {
	public var isFinite: Bool { get }
	public var isInfinite: Bool { get }
	public static var infinity: Self { get }
}

RationalSimplifiable

To keep any Rational type to it's lowest terms, I propose to create a separate protocol as the Percentage type doesn't require this functionality. A fraction would always be reduced to its lowest terms so that developers won't have to simplify after every arithmetic operation.

Another alternative is making a @Simplified property wrapper and give developers the freedom to keep their fractions simplified or not. I'll investigate more which approach developers would prefer during the initial part of the project.

public protocol RationalSimplifiable: Rational {}

extension RationalSimplifiable {
  internal var isSimplifiable: Bool { get }
  internal var isSimplified: Bool { get }

  internal func simplified() -> Self
  internal mutating func simplify()
}

Swift Numerics has the gcd method already implemented that I'll be needing :+1:t2:

Fraction

Take the fraction 13/3. The quotient is 4.333... It is somewhat difficult to perform arithmetic with numbers using this form. Fraction aims to make it more convenient for developers to handle rational numbers. It retains precision as it isn't converted to its quotient during these operations.

Fraction represents a fraction m / n where m and n are two integer numbers. The denominator n will be constrained to be non-zero, and the two numbers may be kept in reduced form. The type will conform to Equatable, Hashable and Comparable, as well as ExpressibleByFloatLiteral, ExpressibleByIntegerLiteral and LosslessStringConvertible. Basic arithmetic operations such as addition, subtraction, multiplication, division and negation will be available.

public struct Fraction<Term>: RationalSimplifiable
where Term: BinaryInteger {
  public let numerator: Term
  public let denominator: Term

  public init(_ numerator: Term, on denominator: Term)

  public init<Value>(
    approximately value: Value, 
    withPrecision precision: Value = 1e-6
  ) where Value: BinaryFloatingPoint

  public var quotient: Double { get }
}

MixedFraction

Mixed fractions are used around the world such as in the United States and the United Kingdom to represent measurements. They are easier to understand as final outputs, since addition is easier than division. I don't understand 13/3 gallons of water, but I do understand 4 1/3, this expression make it clear that I have a little over 4 gallons of water.

MixedFraction works similarly to a Fraction—abstracting all the complexity away, it is represented by combining a whole number and a fraction.

public struct MixedFraction<Term>: RationalSimplifiable
where Term: BinaryInteger {
  public let integral: Term { get }
  public let fractional: Fraction<Term> { get }

  public init(_ numerator: Term, on denominator: Term)
  public init(_ integral: Term, _ numerator: Term, on denominator: Term)
  public init(_ integral: Term, _ fractional: Fraction<Term>)

  public var numerator: Term { get }
  public var denominator: Term { get }
  public var quotient: Double { get }
}

extension MixedFraction {
  internal var isMixable: Bool { get }
  public var isMixed: Bool { get }

  internal func mixed() -> Self
  internal mutating func mix()
}

ContinuedFraction

I'm yet undecided how ContinuedFraction would look like but I expect it to behave similarly to Fraction and conform to RationalSimplifiable. I'll have time during the initial part of the project to investigate more deeply the most efficient way to implement it.

Percentage

As humans we use percentages on a daily basis without even noticing. It's used to describe variations in prices, it's used when representing data in pie charts and it even has its own button on calculators alongside the four basic operators. I believe this simple type should have its place in Swift because it's so common.

Percentage works the same way as Fraction except it can not be simplified and the denominator is fixed to 100.

public struct Percentage<Term>: Rational
where Term: BinaryInteger {
  public let numerator: Term { get }

  public init<Value>(_ numerator: Value)
  where Value: BinaryInteger

  public init<Value>(_ numerator: Value)
  where Value: BinaryFloatingPoint

  public let denominator: Term = 100
  public var quotient: Double { get }
}

Proposal Timeline


As per last year's contributors' experiences posted on the forums, I'd love to have a weekly 10 to 15 minute call with my mentor.

My university still hasn't given us the start date of the summer, all they've said is it will be between the 10th and the 24th of June. In consequence, I have to be flexible with the first two weeks in my timeline.

  • June 13th (Week 1)
    Coding officially begins :tada:

  • June 20th (Week 2)
    TODO: timeline

  • June 27th (Week 3)
    TODO: timeline

  • July 4th (Week 4)
    TODO: timeline

  • July 11th (Week 5)
    TODO: timeline

  • July 18th (Week 6)
    TODO: timeline

  • July 25th (Week 7)
    July 29th 18:00 UTC: Mentors and contributors submit phase 1 evaluations

  • August 1st (Week 8)
    TODO: timeline

  • August 8th (Week 9)
    TODO: timeline

  • August 22nd (Week 10)
    TODO: timeline

  • September 5th (Week 11)
    Submit final work product and final mentor evaluation

  • September 12th (Week 12)
    September 12th 18:00 UTC: Contributors submit their final work product and their final mentor evaluation
    September 19th 18:00 UTC: Mentors submit final GSoC contributor evaluations

  • September 20th
    Initial results of Google Summer of Code 2022 announced

About Me


:wave:t2: Hi, my name is Alex, I'm currently studying at the Apple Developer Academy in Naples and I've been coding with Swift for the past three years. That's since SwiftUI was revealed at WWDC19 which completely changed my professional career. I've never contributed to an open-source project before but I do have a few public repositories on GitHub that are listed below for your perusal. You can also find more details about my work experience on LinkdedIn.

6 Likes

There is also @xwu's nice work which deserves a mention.

My old gist comes out of a hobby-level utility I was making at the time for a very narrow and specific use case. Since I didn't find what I was looking for, I extracted that part and published it as a gist. I am not sure if it actually worked for anyone.

Correctly tackling rational numbers at the standard library level is not an easy task and I am not very happy with many of the examples you mentioned from the other languages. I think Swift deserves a really good solution that needs some serious upfront problem space analysis and design work.

3 Likes

Hi Alex, i've read your work and i like it !
good luck in securing a mentor and starts working on this project.

1 Like

Thats wonderful, thank you for sharing. I’ll link to the gist in my final proposal :slightly_smiling_face:

I agree with you about the other examples I mentioned. They’re included in my proposal to demonstrate that other major programming languages have Rational types. They’ve also helped me to better understand rational types and are good for comparison. I’ll rephrase my wording so it is better understood why I’ve included them.

Thank you, that’s very kind of you :slightly_smiling_face: And good luck to you too for your submission!

Hi @alexandrehsaad.

I have to confess that I'm a little bit torn about this. It's a very well-written proposal for a feature that I don't really want to have. To paraphrase Ben, rationals are the linked lists of numerics. There's a very narrow set of situations in which they're a good option, but that set of situations is vastly more limited than most people think it is. I've written about their drawbacks a few times, but to paraphrase:

  • If you round results, it is always strictly better to use floating-point, because it has scale invariance and fewer redundant representations, so for any fixed precision it has smaller error.
  • If you do not round results, the sizes of the numerator and denominator grow exponentially in general.
  • Because of this, any non-trivial fixed-size rational program overflows immediately.

All that said, this is generally a well-written proposal, and rational types do have some limited uses, so I'm willing to mentor this if we narrow the scope a little bit. Specific feedback:

  1. You don't need a protocol. You need a generic type Rational<Term> (or your Fraction<Term>). At some future point, there might be a reason to create a protocol, but you need to start with the concrete type and build from there.

  2. There's probably no reason to include a NaN representation for rationals. Infinity is likely also unnecessary.

  3. You should simply require canonicalization (simplification). I'm open to being convinced otherwise, but this is generally the correct approach, and eliminates the need for RationalSimplifiable.

  4. MixedFraction isn't a separate type, it's a presentation of Fraction.

  5. Continued fractions are a whole separate thing, with a very different set of uses. They're worth investigating, but are probably their own separate project.

  6. Percentage is probably a string presentation on Fraction and FloatingPoint, rather than its own type. In particular, limiting to whole-number percentages is undesirable for a wide variety of reasons; we would especially not want people to convert to a percentage, changing the value, and then use that value for further computations. This is why it makes the most sense to have this be a presentation instead of a numeric type. If I have 363/1000 and 633/1000 and 4/1000, converting those to whole-number percentages and then adding would yield 99%, instead of the correct 100%; we want to prevent that.

  7. One of the more interesting and useful features that you should include is the ability to produce a "close" approximation of a FloatingPoint value with a rational, using continued fractions.

If you still want to move forward with this, feel free to reach out to me with an updated draft (I know that time is short, so you don't have to incorporate all of my feedback--what I'm mainly interested in is knowing that you're OK with this slight redirection.)

9 Likes

Thank you so much for your feedback :slightly_smiling_face: I was not expecting this, I'm truly grateful. I'm very interested in moving forward with the redirection. Time is short but I wish to give it a go nonetheless! I'll keep you updated, thanks again

1 Like

A quick update, I'm not too far from done, still working on points 1, 2, and 7, and the timeline.

Please find my revised proposal below.

You've made me rethink whether NaN and Infinity are necessary. I need to make more research so I've kept them for the time being.

Could you please let me know if Point 7 has been properly covered in the "Continued Fraction" part of the proposal?

I'm doing the timeline now, if you have any suggestions, I'm all ears.

Thank you again for all your help :slight_smile:

Fraction type for Swift


April 19th, 2022
GSoC 2022

Definitions


  • Fraction: The quotient of two numbers without loss of precision.
  • Mixed Fraction: The quotient and remainder of a fraction.
  • Continued Fraction: A fraction of infinite length whose denominator is a quantity plus a fraction.
  • Percentage: A fraction with a denominator of one hundred.

Abstract


The Swift programming language doesn't provide a rational type in its standard library. Such a type is useful when a developer wishes to simplify symbolic expressions without needing to worry about floating point errors. My proposal consists of contributing to the Swift Numerics package by implementing a rational type Fraction.

Proposal Details


Project size

Large (350 hours)

Recommended skills

  • Proficiency with Swift
  • Interest in numerical computing.

Expected difficulty

Medium

Description

Add Fraction to the Swift Numerics package, to represent rational numbers like 1/3 and -11/7 without rounding and to do arithmetic on them.

Some attempts have been made previously in Swift:

Other programming languages provide a built-in rational type:

  • C++ has included support for compile-time rational arithmetic in the form of the contents of its standard library's ratio header.
  • Go provides rational numbers in the standard library, in the math/big package.
  • Python's standard library includes a fraction type in the fractions module.
  • The Apache Commons math library provides rational numbers for Java.

Expected deliverables

The project would fit nicely as a new module in Swift Numerics with its own branch. The deliverables would include source code with tests and documentation.

Potential mentor(s)

Steve Canon

Proposed Design


I plan to follow the standard library contributor guidelines and conventions, and use Swift's numeric protocols as much as possible.

Fraction

Take the fraction 13/3. The quotient is 4.333... It is somewhat difficult to perform arithmetic with numbers using this form. Fraction aims to make it more convenient for developers to handle rational numbers. It retains precision as it isn't converted to its quotient during these operations.

Fraction represents a fraction m / n where m and n are two integer numbers. The denominator n will be constrained to be non-zero, and the two numbers will be kept in reduced form. The type will conform to Equatable, Hashable and Comparable, as well as ExpressibleByFloatLiteral, ExpressibleByIntegerLiteral and LosslessStringConvertible. Basic arithmetic operations such as addition, subtraction, multiplication, division and negation will be available.

The main difference with my first try, is this version is generic so that developers can declare their fraction's terms to be any BinaryInteger as well as BigInt when it's merged.

public struct Fraction<Term>
where Term: BinaryInteger {
  public let numerator: Term
  public let denominator: Term

  public init(_ numerator: Term, on denominator: Term)
  public init(_ integral: Term, _ numerator: Term, on denominator: Term)
  public init(_ integral: Term, _ fractional: Fraction<Term>)

  public var quotient: Double { get }
}

A fraction will always be reduced to its lowest terms so that developers won't have to simplify after every arithmetic operation. Swift Numerics has the gcd method already implemented that I'll be needing :+1:t2:

extension Fraction {
  internal func simplified() -> Self
  internal mutating func simplify()
}

For the same reason as above, it is preferred that fractions are always normalised.

extension Fraction {
  internal func normalized() -> Self
  internal mutating func normalize()
}

NaN and Infinity

I believe rational types shouldn't conform to FloatingPoint, however, I plan to allocate some time to researching whether NaN and Infinity are necessary. I could create new protocols RepresentableByNaN and RepresentableByInfinity for this purpose that would copy some of the properties from FloatingPoint. If that design gets accepted, I wish to pitch these two protocols for the standard library and in turn have FloatingPoint conform to both.

extension Fraction: RepresentableByNaN {
  public var isNaN: Bool { get }
  public static var nan: Self { get }
}

extension Fraction: RepresentableByInfinity {
  public var isFinite: Bool { get }
  public var isInfinite: Bool { get }
  public static var infinity: Self { get }
}

Mixed Fraction

Mixed fractions are used around the world such as in the United States and the United Kingdom to represent measurements. They are easier to understand as final outputs, since addition is easier than division. I don't understand 13/3 gallons of water, but I do understand 4 1/3, this expression makes it clear that I have a little over 4 gallons of water. Mixed fractions will be represented by combining a whole number and a fraction.

extension Fraction {
  public var isProper: Bool { get }
  public var isImproper: Bool { get }
  public var isWhole: Bool { get }
  public var mixed: (integral: Term, fractional: Self<Term>) { get }
}

Percentage

As humans we use percentages on a daily basis without even noticing. It's used to describe variations in prices, it's used when representing data in pie charts and it even has its own button on calculators alongside the four basic operators. I believe percentages should have its place in Swift because it's so common. It could also be added to the FloatingPoint protocol.

extension Fraction {
  public var percentage: String { get }
}

Continued Fraction

One of the most interesting and useful features is the ability to produce a close approximation of a FloatingPoint value with a rational, using continued fractions.

extension Fraction {
  public init<Value>(
    approximately value: Value,
    withPrecision precision: Value = 1e-6
  ) where Value: BinaryFloatingPoint
}

Following the feedback from my potential mentor, I understand continued fractions are a whole different thing and could potentially be a separate project. However, it's worth investigating more deeply, so I plan to allocate some time in my schedule for research.

Rational Protocol

A new Rational protocol could be needed in the future, but it's not necessary right now.

Proposal Timeline


As per last year's contributors' experiences posted on the forums, I'd love to have a weekly 10 to 15 minute call with my mentor.

My university still hasn't given us the start date of the summer, all they've said is it will be between the 10th and the 24th of June. In consequence, I have to be flexible with the first two weeks in my timeline.

June 13th (Week 1)

  • Coding officially begins :tada:

June 20th (Week 2)

  • TODO: timeline

June 27th (Week 3)

  • TODO: timeline

July 4th (Week 4)

  • TODO: timeline

July 11th (Week 5)

  • TODO: timeline

July 18th (Week 6)

  • TODO: timeline

July 25th (Week 7)

  • July 29th 18:00 UTC: Mentors and contributors submit phase 1 evaluations

August 1st (Week 8)

  • TODO: timeline

August 8th (Week 9)

  • TODO: timeline

August 22nd (Week 10)

  • TODO: timeline

September 5th (Week 11)

  • Submit final work product and final mentor evaluation.

September 12th (Week 12)

  • September 12th 18:00 UTC: Contributors submit their final work product and their final mentor evaluation.
  • September 19th 18:00 UTC: Mentors submit final GSoC contributor evaluations.

September 20th

  • Initial results of Google Summer of Code 2022 announced.

About Me


:wave:t2: Hi, my name is Alex, I'm currently studying at the Apple Developer Academy in Naples and I've been coding with Swift since SwiftUI was revealed at WWDC19 —almost three years ago. I've never contributed to an open-source project before but I do have a few public repositories on GitHub that are listed below for your perusal. You can also find more details about my work experience on LinkdedIn.

1 Like

That seems reasonable to me!

1 Like

I implemented rational numbers as a generic Rational<IntegerType struct, so perhaps I could help.
This is the source code if you’re interested: GitHub - abdel-17/exact-math: A Swift package for exact computation.
Let me offer you some advice.

  1. You don’t really need a protocol. Rational numbers are just a pair of integers, so the customizability lies entirely within the type of the integers.
  2. Simplifying rational values to their canonical form automatically seems to be the right way to go. It makes implementing == easier, and helps avoid overflow, which is common with rational types.