1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
//===--- AlgebraicField.swift ---------------------------------*- swift -*-===//
//
// This source file is part of the Swift Numerics open source project
//
// Copyright (c) 2019 Apple Inc. and the Swift Numerics project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
/// A type modeling an algebraic [field]. Refines the `SignedNumeric` protocol,
/// adding division.
///
/// A field is a set on which addition, subtraction, multiplication, and
/// division are defined, and behave basically like those operations on
/// the real numbers. More precisely, a field is a commutative group under
/// its addition, the non-zero elements of the field form a commutative
/// group under its multiplication, and the distributitve law holds.
///
/// Some common examples of fields include:
///
/// - the rational numbers
/// - the real numbers
/// - the complex numbers
/// - the integers modulo a prime
///
/// The most familiar example of a thing that is *not* a field is the integers.
/// This may be surprising, since integers seem to have addition, subtraction,
/// multiplication and division. Why don't they form a field?
///
/// Because integer multiplication does not form a group; it's commutative and
/// associative, but integers do not have multiplicative inverses.
/// I.e. if a is any integer other than 1 or -1, there is no integer b such
/// that a*b = 1. The existence of inverses is requried to form a field.
///
/// If a type `T` conforms to the `Real` protocol, then `T` and `Complex<T>`
/// both conform to `AlgebraicField`.
///
/// See Also:
/// -
/// - Real
/// - SignedNumeric
/// - Numeric
/// - AdditiveArithmetic
///
/// [field]: https://en.wikipedia.org/wiki/Field_(mathematics)
public protocol AlgebraicField: SignedNumeric {
/// Replaces a with the (approximate) quotient `a/b`.
static func /=(a: inout Self, b: Self)
/// The (approximate) quotient `a/b`.
static func /(a: Self, b: Self) -> Self
/// The (approximate) reciprocal (multiplicative inverse) of this number,
/// if it is representable.
///
/// If self is zero and the type has no representation for infinity (as
/// in a typical finite field implementation), or if a reciprocal would
/// overflow or underflow such that it cannot be accurately represented,
/// the result is nil.
///
/// Note that `.zero.reciprocal`, somewhat surprisingly, is *not* nil
/// for `Real` or `Complex` types, because these types have an
/// `.infinity` value that acts as the reciprocal of `.zero`.
///
/// If `x.reciprocal` is non-nil, you may be able to replace division by `x`
/// with multiplication by this value. It is not advantageous to do this
/// for an isolated division unless it is a compile-time constant visible
/// to the compiler, but if you are dividing many values by a single
/// denominator, this will often be a significant performance win.
///
/// Note that this will slightly perturb results for some fields with
/// approximate arithmetic, such as real types--using a normal division
/// is generally more accurate--but no catastrophic loss of accuracy will
/// result. For fields with exact arithmetic, or for the Complex types,
/// the results are identical.
///
/// A typical use case looks something like this:
/// ```
/// func divide<T: AlgebraicField>(data: [T], by divisor: T) -> [T] {
/// // If divisor is well-scaled, multiply by reciprocal.
/// if let recip = divisor.reciprocal {
/// return data.map { $0 * recip }
/// }
/// // Fallback on using division.
/// return data.map { $0 / divisor }
/// }
/// ```
var reciprocal: Self? { get }
}
extension AlgebraicField {
@_transparent
public static func /(a: Self, b: Self) -> Self {
var result = a
result /= b
return result
}
/// Implementations should be *conservative* with the reciprocal property;
/// it is OK to return `nil` even in cases where a reciprocal could be
/// represented. For this reason, a default implementation that simply
/// always returns `nil` is correct, but conforming types should provide
/// a better implementation if possible.
public var reciprocal: Self? {
return nil
}
}
|
