Discrete Mathematics

DiscreteMathematics is a set of algorithm implementations from Discrete Mathematics.

Examples

Operators

Congruence Modulo n ==%:

The equivalence relation a ≡ b(mod m) ↔ m | (b - a).

-8 ==% (7, 5) // true
2 ==% (8, 5) // false

Divides |%:

Returns whether or not a|b ↔ ∃ q ∈ N, b = q · a.

3 |% 9 // true
2 |% 7 // false

Functions

Long Division

Performs division on two integers and returns the quotient and remainder.


a = q · b + r

longDivision(a: 8, b: 3) // (q: 2, r: 2)

Greatest Common Divisor

gcd() returns the greatest common divisor using the Euclidean Algorithm.

gcd(5005, 4410) // 35
gcd(175, 155) // 5

egcd() returns the GCD of two integers as an integer combination using the Extended Euclidean Algorithm.


a · x + b · y = d

egcd(5005, 4410) // (d: 35, x: -37, y: 42)
egcd(175, 155) // (d: 5, x: 8, y: -9)

Coprime

Two elements, a, b, are coprime if gcd(a, b) = 1.

coprime(17, -60) // true

Linear Diophantine Equation

lde() returns a solution to the given Linear Diophantine Equation or nil if it has no solutions.

lde(a: 175, b: 155, c: 50) // (x: 80, y: -90)
lde(a: 234, b: 182, c: 10) // nil

ldeSolutions() returns a function that will compute all possible solutions to an LDE.

let solutions = ldeSolutions(a: 175, b: 155, c: 50)
solutions!(3) // (173, -195)

Installation

Requirements

• iOS 8.0+
• macOS 10.9+
• tvOS 9.0+
• watchOS 2.0+
• Linux
• Swift 4

CocoaPods

DiscreteMathematics is available through CocoaPods. To install
it, simply add the following line to your Podfile:

pod 'DiscreteMathematics', '~> 1.2'

Swift Package Manager

DiscreteMathematics is available through the Swift Package Manager
To install it, add the following to your Package.swift.

import PackageDescription

let package = Package(
    name: "MyProject",
    dependencies: [
        .package(url: "https://github.com/cszatma/DiscreteMathematics.git", from: "1.2.0")
    ]
)

Contributing

Open an issue or submit a pull request.