Skip to content

rkreutz/UIntX

Repository files navigation

UIntX

Swift 5.2 Swift Package Manager License: MIT GitHub tag Run Tests

UIntX is the unsigned integer to rule them all. It can be used to represent any number, with virtually no size constraints. So you can store unsigned integers of 64-bits (default on most modern computers), 128-bits, 256-bits, 512-bits, 1024-bits, 2048-bits, really whatever size you want may be stored in this one single container.

Usage

UIntX is basically a container for several words of a pre-defined base value, so it is a generic struct that expects a FixedWidthInteger & UnsignedInteger as it's specialised base value. Right now in Swift's standard library there are UInt8, UInt16, UInt32, UInt64 and UInt that conform to these protocols, though other structs may be used as well as long as they conform to the specified protocols. There are four type alias provided in the library which goes as follows:

typealias UIntX8 = UIntX<UInt8>
typealias UIntX16 = UIntX<UInt16>
typealias UIntX32 = UIntX<UInt32>
typealias UIntX64 = UIntX<UInt64>

These are there strictly for convenience so UIntX is already specialised, you may use them or use the complete declaration of UIntX specialising it's base value, e.g. UIntX<UInt>.

There are two prefered ways of initialising UIntX. The first one is the most straight forward, you just need to provide a UnsignedInteger as the initialiser sole argument, like:

let unsignedInteger: UInt = 123
let uintx = UIntX8(unsignedInteger)

UIntX8 also conforms to ExpressibleByIntegerLiteral so you may just initialise it like:

let uintx: UIntX8 = 123

The second preferred way of initialising it is through an array of values, where the first element of the array is the least significant number in the array and the last element in the array is the most significant number:

let array: [UInt8] = [0x89, 0x67, 0x45, 0x23, 0x01]
let uintx = UIntX8(littleEndianArray: array)
uintx == 0x0123456789 // true

Notice that on both initialisers values provided that are higher than the base value can handle will be decomposed into smaller values that the base value can handle, this is all done automatically so you can just throw in any value into UIntX. When using the init(littleEndianArray:) initialiser there is one caveat that you must be aware of, each element of the array will be decomposed into N words of the base element if the array provided uses an element with greater magnitude (where N == ArrayElement.bitWidth / BaseElement.bitWidth), or elements in the array provided will be packed into equivalent bitWidth words of the base element, here is an example using different base values:

let array: [UInt64] = [1, 2]
let uintx8 = UIntX8(littleEndianArray: array)
let uintx64 = UIntX64(littleEndianArray: array)

uintx8 == 0x020000000000000001 // since each element has 64 bits they will each be transformed into 8 words of 8 bits. The leading zeros are truncated
uintx64 == 0x00000000000000020000000000000001

// OR

let array: [UInt8] = [1, 2]
let uintx8 = UIntX8(littleEndianArray: array)
let uintx64 = UIntX64(littleEndianArray: array)

uintx8 == 0x0201
uintx64 == 0x0000000000000201 // since each element has 8 bits they can be packed into the same word of the base element.

Once you have your UIntX you may use it as any other unsigned binary integer value, which means most common operations are available:

let binary: UIntX8 = 0b0001_0010
binary << 1     // 0b0010_0100
binary >> 1     // 0b0000_1001
binary & 0b1111 // 0b0000_0010
binary | 0b1111 // 0b0001_1111
binary ^ 0b1111 // 0b0001_1101
~binary         // 0b1110_1101

let value: UIntX8 = 123
value / 4       // 30
value % 4       // 3
value * 4       // 492
value + 4       // 127
value - 4       // 119
value > 4       // true
value < 4       // false
value == 4      // false
value != 4      // true

Technical limit of UIntX

UIntX is basically a container for storing words of the base value. To do so we store those words in an array (internally referred as parts). Arrays in Swift default to using Int indexes which means you can only store as many elements in the array as Int itself can handle (which is Int.max), since Int is a SignedNumber one of it's bits (the most significant one) is used to store the sign info, which leaves us with Int.max as 263 (for a 64-bit OS). If we use a base value of UInt64 (64-bit) will mean that each word will be able to store 64 bits, so if we have 1 word we'll have a 64 bits number, if we have 2 words we'll have a 128 bits number, and so on:

let baseValueBitWidth = 64 // base value number of bits
let indexes = 2^63 // maximum number of words that can be stored
let totalNumberOfBits = baseValueBitWidth * indexes // 64 * 2^63 = 2^6 * 2^63 = 2^69

So in the end we'll end up with a number that has 269 bits which means that the maximum number we can reach is 2(269). That's a huge number, let's try converting it to a base 10 powered number so it's a little bit easier to conceive its value.

Every time you power 2 to a multiple of 10, the resulting number can be roughly converted to 10 to the power of 3:

210 = 1,024 ~ 103 = 1,000

220 = 1,048,576 ~ 106 = 1,000,000

230 = 1,073,741,824 ~ 109 = 1,000,000,000

So 269 could be decomposed as 270 * 2-1 (= 0.5), which in turn can be approximated to: 0.5 * 1021

That's the amount of bits we have in that number: roughly 500 billion billion bits.

Ok, that's a huge amount of bits, now let's convert that to an actual number:

2(5 * 1020) ~ 10(5 * 1019 * 3) = 10(1.5 * 1020) = 10(1020) * 10(5 * 1019) = 10(1020) * 10(1019) * 10(1019) * 10(1019) * 10(1019) * 10(1019)

1020 = 100 billion billions

1019 = 10 billion billions

100 billion billions + 10 billion billions + 10 billion billions + 10 billion billions + 10 billion billions + 10 billion billions

That's 150 billion billions.

That's only the power of the number by the way, so the actual number would be:

10150 billion billions

Hopefully I got the maths right, but anyway it is clear that we can represent a very massive number with this struct.

Having said that, I'm forcefully limiting the number of words that can be stored, that's being done through:

UIntXConfig.maximumNumberOfWords = 128

I'm doing so as a safety net, since I don't know how a program would behave having to hold such large numbers.

You may change this value at any time, but do it at your own risk, I haven't tested UIntX using numbers past 8,192 bits (which is already a very large number) so I'd recommend sticking to that limit unless you know what you are doing.

Installation

Using Swift Package Manager

Add UIntX as a dependency to your Package.swift file. For more information, see the Swift Package Manager documentation.

.package(url: "https://github.com/rkreutz/UIntX", from: "1.0.0")

Help & Feedback

  • Open an issue if you need help, if you found a bug, or if you want to discuss a feature request.
  • Open a PR if you want to make some change to UIntX.

Roadmap

  • Init from String
    • Decimal
    • Hex
    • Binary
    • Different Radix
    • Base64 string
  • Codable conformance
  • UInt1
  • Faster and more efficient operations
    • Multiplication
    • Division
  • Any UnsignedInteger & FixedWidthInteger element to be used