Stream: ideas

Topic: ✔ Arbitrary-Precision support

Jacob (Jul 16 2023 at 19:29):

What were the thoughts of doing what Lean 4 does and natively supporting arbitrary-precision.

• "the internal representation of Nat is optimized. Small natural numbers (i.e., < 2^63 in a 64-bit machine) are represented by a single machine word. Big numbers are implemented using GMP numbers."

This is a nice built-in feature, while also having access to USize if I want to be the size of a memory address.

Richard Feldman (Jul 16 2023 at 19:33):

we've talked about it before - basically my thinking is:

• I128 lets you represent numbers in the undecillions
• usually when people talk about something being "multiple orders of magnitude faster" it's hyperbole for emphasis, but in this case, I128 is literally multiple orders of magnitude faster than arbitrary-sized integers, because they can live entirely in CPU registers instead of requiring heap allocations or chasing pointers
• what are the specific use cases where undecillions are insufficient, and we need something bigger, and are those specific use cases common enough to justify inclusion in the standard library?

Richard Feldman (Jul 16 2023 at 19:33):

I'm very skeptical, but always open to the possibility I'm missing something! :big_smile:

Brendan Hansknecht (Jul 16 2023 at 19:47):

Side question to add in:

How important is native support vs having a library implementation? I get the rare need for big buns, but given they are rare, I tend to think they fit best in a library.

Jacob (Jul 16 2023 at 19:47):

Honestly, there isn't a rock solid reason that would improve the language for most people, just a bunch of niche ones (i.e usually scientific/math computing related). But it is nice to know that I can't overflow and not have to look to some library. However, having people constantly write USize instead of Nat might make it not worth it for other use cases beyond math/scientific computing.

Ajai Nelson (Jul 16 2023 at 19:59):

It’s somewhat common for me to want larger numbers than that, but that’s when I’m doing problems for fun (e.g. Project Euler problems). I don’t know of any common situations where you would actually need them

Brendan Hansknecht (Jul 16 2023 at 20:05):

As a note, currently the plan is for nat to go away. Just use u64 instead.

Richard Feldman (Jul 16 2023 at 20:35):

fwiw overflow is still possible with arbitrary ints (memory is finite!) just less likely. Which again comes back to how much overflow is worth worrying about with 128-bit integers! :big_smile:

Jacob (Jul 16 2023 at 20:41):

Yes you can technically still overflow, but for the use cases where it's commonly used usually result in a question of whether your computer can actually compute such a large result before you reach memory limits.

Brendan Hansknecht (Jul 16 2023 at 20:42):

So death by lock up do to gigantic compute instead of death by overflow. Still represents a broken/unusable program

Jacob (Jul 16 2023 at 21:04):

Well only death by gigantic compute because you're intentionally trying to annihilate your RAM haha. But the use cases are limited, I personally was interested for cryptography where U128 wouldn't be close to enough. But other than math/scientific computing related, not sure if there are any solid use cases where it just makes things way nicer to deal with.

Richard Feldman (Jul 16 2023 at 21:29):

huh, interesting! I haven't heard of cryptography uses that need more than U128 - can you say more about the use case?

Jacob (Jul 16 2023 at 21:33):

A lot of algorithms have intermediate computations that are 100's to 1000's of bits large. RSA-4096 for example but also ECC. Although for some specific cases there are tricks to reduce it, but generally you need at a minimum 100's of bits

Richard Feldman (Jul 16 2023 at 21:44):

interesting! I've never looked at the implementations of one of those...is it common to implement things like RSA-4096 using arbitrary-sized integers?

Richard Feldman (Jul 16 2023 at 21:44):

for performance, I'd have guessed there'd be some preferred other way to do it without heap allocations

Jacob (Jul 16 2023 at 22:06):

I am not super familiar with the implementation optimizations done today, but you definitely need arbitrary-sized integers just for the key itself. But looking at the crypto-bigint crate for rust, they determine the size and do the computations at compile time (const fn).

Jacob (Jul 16 2023 at 22:20):

Another thing, this wouldn't be to support rigorous implementations (usually done in C++/Rust and with more security considerations), but there are other math algorithms/applications where it's typical to have arbitrary-precision. However, I think that maybe it's best in a library. It does make those use cases where you are building something that needs it easier (e.g like a CAS, or anything below world class security RSA) and I think it does make sense because its the closest thing to the concept of a natural number. But beyond those niches it doesn't really do much and roc isn't necessarily targeting to be a math/science oriented language. Which makes sense why Julia/Lean natively have it.

Richard Feldman (Jul 16 2023 at 22:23):

gotcha, very good to know!

Notification Bot (Jul 17 2023 at 04:14):

Jacob has marked this topic as resolved.

Last updated: Jun 16 2026 at 16:19 UTC