SE-0368: StaticBigInt

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 {

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.)

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

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

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.

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.

2 Likes

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