Would you be interested in BigInt support?
I did some programming exercises in Mojo and noticed that BigInt support is missing, and Mojo should probably support BigInt at some point, seeing as Python uses arbitrary precision integers by default.
Are there any other users missing this?
Would it make sense for me to start working on this as a Mojo stdlib PR or is this the sort of thing Mojo would rather have as a 3rd party library for now?
42 Replies
Can you elaborate on what you mean by BigInt? The Int type in Mojo is arbitary precision if I am interpreting your question correctly, are you refering to a BigInt DType?
Int is currently not arbitrary precision. It's a pointer width integer (32 or 64 bits). IntLiteral is arbitrary precision, but cannot be used at runtime.One of the cool things about Mojo is you can literally just write a struct with some inline MLIR and make your own BigInt that works exactly the way an official one would. Not saying there should never be a stdlib version but I doubt it's going to be a major blocker to anyone for this reason
Of course it's not going to be a blocker. You can probably write an efficient one without inline MLIR as well, but any implementation will take a bit of time.
If there was a way to make a package easily usable by the ecosystem I would just do that instead, but as things are I'm significantly less motivated to build a third party library for something like this than make a PR to the stdlib. Either way I'd like to know which approach makes more sense for Modular.
I would like it because rust interop is hard without 128 bit ints, and small width ints are the easiest way to support binding to C bitfields.
Ideally, this can ride on top of the _BitInt(N) and unsigned _BitInt(N) support already in LLVM due to C23.
what would be really cool is Int[Width] / Float[Width] / UInt[Width]
Is there any reason to do bigint as fixed length types instead of using const generics? Truly arbitrary bit widths would give a bit more freedom for transformations later that don't respect high bits
Float should ideally be separate sign/exponent/mantissa parts.
nice idea actually, might try and implement later
That's something different from what I'm talking about. You only need a family of types with increasing precision. I'm talking about a single type that can store values of arbitrary precision (perhaps "unbounded dynamic precision" would be a better term). Python doesn't require you to select the precision before running the code.
Runtime dynamic precision ints are messy. They start to get very slow because they’re very difficult to make fast, if you allow choosing a “large enough” fixed-width integer, you can get better code gen. IIRC, java’s BitInt spends most of its time branching rather than actually doing number crunching.
It's sounding (to me) more like you want a library for symbolic math, maybe with some automatic simplification
Sure, you can lose a lot of time to cache misses, and selecting algorithms based on precision also costs a bit. It seems like the slowness in Java specifically is not inherent though: https://codeforces.com/blog/entry/17235
Still, because python uses runtime dynamic precision ints by default Mojo should probably do so as well for compatibility and flexibility. Deciding on an appropriate precision is an optimization that can be done when desired.
Outside of scientific code, how many people are actually dealing with numbers over 2^63-1? Defaulting int to 64 bit is probably enough for most people and brings massive perf gains.
Not at all. I want an integer type that matches the semantics of the python integer type. I think in python it makes sense mostly for flexibility reasons.