ReallyBigInt

Evolution Discussion
1

I recently learned about a limitation of Swift - and as the thread already has a name that's not super descriptive ;-) (Literal initialization via coercion - #28 by nuclearace), I'm following a suggestion by opening this thread.
So, for those who have been as naive as I: Swift's integer literals are always transformed to one of the well known integer types, so their limits apply.

It's rather easy to implement a type that allows calculations like 89089452489057249582345 * 2523423423424234234, but it's not possible to initialize such a type with an integer literal that doesn't fit into Int64 (or whatever the biggest type is ;-) - like most of us, I don't encounter such problems everyday).

For "normal" numeric applications, you often want to stick with types that have hardware support; nonetheless, I think it would be really nice if Swift could not only calculate fib(100), but also allow you to copy & paste the result into a playground.

So... would it make sense for Swift to support numbers of arbitrary size? (that question does not only apply for ints - posits would imho be cool as well ;-)

1 Like
2

I would love to see a BigNum type in the default toolchain that ships with Swift. I think some of the issues that are going to come up from this discussion are related to what the scope of the stdlib should be. Personally, I could go with shipping it in the stdlib, or as part of some new "extended" library.

But into the meat of this. Like I said in the thread that spawned from this. I believe some work has been done with DoubleWidth that allows for up to 2048-bit literals. I could be wrong on the specifics. @xwu probably knows.

To drive this discussion more. If we did ship with a BigNum type. What kind of backing algorithm would we decide on? And would that be a pure Swift implementation or a hybrid.

3

I recently did a fun proof-of-concept library for Big Integers. To get around the "2^64" limit problem, I made this initializer:

public extension BigInt {
    public init(_ base: Int16, _ others: UInt16...) { ... }
}

This let me do things like:

let r = BigInt(-237,852,473,059,884,421,722,857,673,528,501,169,661,482,804,087,269,125,170,759,104,621,765,636,717,323,318,579,440,796,987,823,926,801,315,856,105,052,997,259,652,698,492,658,301,636,190,251,577,533,000,978,051,836,271,871,929,698,451,335,720,957,848,579,092,116,517,591,530,783,518,836,635,575,382,149,313,301,260,856,609,115,997,039,803,188,139,801,441,302,218,983,470,764,861,164,131,428,587,390,743,143,808,670,336,115,010,201,682,935,485,692,632,534,535,142,841,178,144,429,142,489,233,855,041,026,161,142,426,559,252,528,645,411,949,124,998,043,430,379,779,061,759,203,154,413,926,597,456,368,096,601,648,345,990,592,999,817,876,775,548,971,446,267,479,816,716,141,558,907,784,689,691,286,396,211,818,834,706,820,076,979,441,803,796,883,968,548,857,181,007,796,548,073,180,902,299,523,903,448,165,738,281,259,101,110,292,865,411,825,881,853,036,603,727,593,186,880,090,553,735,399,464,821,418,262,787,599,748,907,030,609,804,498,690,879,748,899,967,080,267,407,249,938,194,052,930,299,697,232,682,707,886,904,906,977,279,436,211,236,657,723,844,643,368,769,319,592,807,819,805,787,119,047,978,915,155,280,363,661,696,385,940,925,726,298,007,489,714,212,663,077,986,619,513,004,294,822,808,797,448,923,057,716,775,642,900,478,064,158,728,180,184,126,194,954,398,642,205,638,746,730,007,451,325,443,387,551,766,402,070,376,400,524,149,166,821,008,194,010,520,006,623,519,210,223,741,352,928,401,974,944,912,460,965,766,149,738,398,448,363,825,402,240,786,325,798,683,750,636,362,520,639,823,342,582,169,510,600,917,146,412,544,648,574,870,547,830,521,686,604,799,354,288,513,907,393,994,833,070,196,489,112,643,286,121,200,321,767,830,896,523,528,452,930,294,178,601,563,296,769,761,158,487,786,762,694,643,141,917,688,556,093,041,955,982,862,428,826,376,366,348,136,261,083,989,307,750,397,679,281,334,021,058,950,625,894,306,106,135,948,143,640,195,276,452,728,311,189,740,222,957,639,732,063,778,592,477,171,196,689,325,948,653,340,890,532,578,489,064,303,821,611,562,573,509,185,193,074,183,311,295,386,490,820,418,172,534,129,248,371,572,311,212,259,425,110,754,306,681,967,391,617,481,982,260,866,994,693,913,044,942,282,227,392,723,511,720,581,898,823,053,356,889,420,221,019,195,298,268,889,186,418,226,082,189,062,584,682,206,263,339,015,425,266,333,497,520,017,292,876,883,288,841,446,080,776,133,805,085,601,984,598,720,623,180,367,751,316,135,357,141,322,828,699,039,114,095,949,514,350,271,739,325,712,486,761,935,016,805,119,352,271,332,209,250,426,385,294,241,272,091,826,367,014,038,901,844,729,493,301,530,465,199,530,613,668,826,137,611,376,383,065,839,092,791,992,841,746,966,867,972,976,717,997,895,190,429,515,455,372,130,481,692,651,083,962,241,060,854,303,720,516,538,578,961,712,305,413,329,197,480,996,982,922,695,310,414,037,279,483,048,656,291,774,275,392,577,238,027,373,468,957,451,820,079,105,875,870,514,019,689,706,112,973,631,450,543,703,552,057,408,480,913,775,258,946,411,370,984,897,964,883,955,002,862,846,947,529,856,144,891,214,213,624,943,034,179,175,123,838,930,359,669,517,446,857,964,846,357,723,537,957,730,190,707,834,340,125,412,913,734,594,187,070,743,784,300,307,019,292,844,053,403,503,276,515,937,572,491,547,316,634,664,765,971,645,739,547,499,750,104,011,064,429,429,829,617,219,068,537,839,350,922,113,447,640,463,034,781,906,746,559,111,529,559,009,678,683,030,429,860,224,935,434,174,095,041,204,769,221,872,182,063,139,882,397,602,186,311,531,389,128,222,148,796,474,795,092,270,169,386,445,268,973,589,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000)

It's a hack, but it's a pretty good one IMO. :smiling_imp:

7 Likes
4

That reminds me on a program I wrote as a child:
I wanted to do calculations with text input from the user - so I just did what I learned to do on paper (e.g. sum("77", "33") // -> "110" [actually, I did this with AppleScript] ;-)
I guess you proof of concept is more space efficient, though...

5

I'm not actually defending this, but FYI, Swift supports integer literals up to 2048 bits. I agree that arbitrary is better.

Policy.swift:public typealias _MaxBuiltinIntegerType = Builtin.Int2048

-Chris

4 Likes
6

That hack is beautiful.

1 Like