SE-0368: StaticBigInt

Evolution Proposal Reviews
21

The intention is for StaticBigInt to support the implementation of BigInt in a package. The comparison with StaticString exists because BigInt could then be moved into the standard library.

No, StaticBigInt uses the following ABI-neutral abstraction, to avoid the requirement of contiguously stored words on every platform.

Builtin.wordAtIndex_IntLiteral(
  _ value: Builtin.IntLiteral,
  _ index: Builtin.Word
) -> Builtin.Word

No, a simple implementation could store both a StaticBigInt and an array of words (which may be empty if unused).

public struct BigInt: SignedInteger {
  internal let _constant: StaticBigInt
  internal var _variable: [UInt]
}

It's a trade-off between branching on every storage access, and heap allocation on every construction.

Alternatively, apple/swift-numerics#84 stores a cache of digits for better performance.

private static let _digits: [BigInt] = (0 ... 36).map {
22

Yes, this is very tempting, as long as we don't give up on the infinite sign extension.

I can rewrite the examples and tests for 64-bit architectures only.

(32-bit testing isn't available on CI bots now, and on my computer the watchsimulator-i386 target displays an empty alert for every executable test.)

23

I don’t get it. What’s the downside to not including it in the first place?

24

Swift supports explicitly writing out a positive sign in front of an integer literal. This support is provided in the form of prefix + defined in the standard library for all types expressible by an integer literal. Excluding the function in question for StaticBigInt would drop that support, but only for integer literals that are used to express large integers. This would be a mystifying inconsistency that's bad for the end user experience.

7 Likes
25

I've created a pull request that uses only a "non-generic" subscript, in case the Language Workgroup decides to amend the proposal.

/// Returns a 32-bit or 64-bit word of this value's binary representation.
///
/// The words are ordered from least significant to most significant, with
/// an infinite sign extension. Negative values are in two's complement.
///
///     let negative: StaticBigInt = -0x0011223344556677_8899AABBCCDDEEFF
///     negative.signum()  //-> -1
///     negative.bitWidth  //-> 118
///     negative[0]        //-> 0x7766554433221101
///     negative[1]        //-> 0xFFEEDDCCBBAA9988
///     negative[2]        //-> 0xFFFFFFFFFFFFFFFF
///
///     let positive: StaticBigInt = +0x0011223344556677_8899AABBCCDDEEFF
///     positive.signum()  //-> +1
///     positive.bitWidth  //-> 118
///     positive[0]        //-> 0x8899AABBCCDDEEFF
///     positive[1]        //-> 0x0011223344556677
///     positive[2]        //-> 0x0000000000000000
///
/// - Parameter wordIndex: A nonnegative zero-based offset.
public subscript(_ wordIndex: Int) -> UInt { get }

For expressions like StaticBigInt(+42) and UInt64(+0xFFFF_FFFF_FFFF_FFFF), another alternative to waiting for a "plus sign" in the language is:

extension ExpressibleByIntegerLiteral {

  /// Creates a new instance from the given integer.
  ///
  /// If the value passed as `source` is not representable in this type, a
  /// runtime error may occur.
  ///
  /// - Parameter source: An immutable arbitrary-precision signed integer.
  public init(_ source: StaticBigInt) {
    let target = IntegerLiteralType(_builtinIntegerLiteral: source._value)
    self.init(integerLiteral: target)
  }
}

It was originally suggested as init(dynamicIntegerLiteral:) by @John_McCall. However, it's blocked by an issue where overflow can result in a zero-initialized value (without a compile-time or run-time error). I don't know how to fix that issue, and I didn't want to delay this proposal. I'm also unsure of the effect on source compatibility, if it's implemented without an argument label.

26

As I understand it, there is a general bug where we don't emit runtime diagnostics during generic initialization of integer literals. That is something we need to fix, but I don't think it's reasonable to block this on that.

3 Likes
27

This is a very useful addition which will add great flexibility. I like the idea of unblocking literals for external big int implementations without otherwise committing the language.

The latest version with a non-generic subscript is a good improvement. Simplicity wins.

1 Like
28

Hello Everyone,

The discussion of the generic subscript in this thread led to a proposed change to make that subscript non-generic. The author has amended the proposal with that change. The Language Workgroup is extending the review until next Tuesday to provide more time to discuss the amended proposal.

Thanks everyone,
Doug

6 Likes
29

Why are we proposing a StaticBigInt if we think an eventual BigInt will just "deprecate" it much like StaticString & String, if we could instead just jump to the BigInt addition?

1 Like
30

BigInt would not deprecate StaticBigInt. StaticBigInt is a tool for expressing arbitrary-precision integer literals, which can be useful for negotiating the boundary between the language syntax and the static/dynamic semantics of a specific type, which needn't be arbitrary-precision to benefit from the existence of StaticBigInt.

6 Likes
31

In addition, an eventual BigInt might not be in the standard library, but StaticBigInt has to be in order to provide this function for literals.

7 Likes
32

I almost forgot to review this. This has a +1 for me. Arbitrary length integer literals is a definite improvement over the status quo.

I realize it's not really up for discussion yet, but I absolutely support the future direction of moving the prefix + for positive numbers to the grammar instead of having it be an operator. I have never once used the prefix + operator on anything other than a literal.

3 Likes
33

This proposal has been accepted, thank you everyone!

Doug

2 Likes