Date: Fri, 8 Aug 2025 18:35:45 +0000
One application where I've seen this was in the modular computation in elliptic curves.
We are not talking _BitInt(128) but something more like _BitInt(1040).
Where you would start with two 520bit numbers and multiply them together to get a 1040bit number.
But in order to do that with _BitInt you would need to convert it a _BitInt(520) to a _BitInt(1040) before doing the multiplication.
But that's not the number you want, you want the modulus of a large prime that is close to a power of 2 with 520 bits.
Now you don't want to divide that number because that would have been extremely inefficient, you use the fact that the prime is close to a power of 2 and fold the high bits multiplied by a constant in order to do the reduction. Now this method is not guaranteed to complete the modulus every single time, but we know that it is at most a couple of bits of so you fold it again to complete the job.
You don't need to the calculation with all 1040 bits, but there's no way for the compiler to figure that you wouldn't need all of those because your constants are special and guarantees a certain outcome in the result.
Because the compiler can't predict the result, if you use _BitInt(1040) you have no choice but to roll out every single operation for all bits as if they were used, but you would need a lot less if you roll them out manually.
With _BitInt you always have to use all bits, with multi-precision you get to choose depending on the circumstance.
________________________________
From: Thiago Macieira <thiago_at_[hidden]>
Sent: Friday, August 8, 2025 8:06:43 PM
To: std-proposals_at_[hidden] <std-proposals_at_[hidden]>; Tiago Freire <tmiguelf_at_[hidden]>
Subject: Re: [std-proposals] Multiprecision division
On Friday, 8 August 2025 10:02:30 Pacific Daylight Time Tiago Freire wrote:
> No, _BitInt is a different philosophy of dealing with numbers. _BitInt is
> not multi-precision, it's fix precision but with support for widths larger
> than the CPU word size.
>
> And the compiler would not be able to optimize code the way multi-precision
> does because of limitations on what the compiler can reason about.
Why not? How would the division of two _BitInt(128) be different from what Hans
is proposing?
We are not talking _BitInt(128) but something more like _BitInt(1040).
Where you would start with two 520bit numbers and multiply them together to get a 1040bit number.
But in order to do that with _BitInt you would need to convert it a _BitInt(520) to a _BitInt(1040) before doing the multiplication.
But that's not the number you want, you want the modulus of a large prime that is close to a power of 2 with 520 bits.
Now you don't want to divide that number because that would have been extremely inefficient, you use the fact that the prime is close to a power of 2 and fold the high bits multiplied by a constant in order to do the reduction. Now this method is not guaranteed to complete the modulus every single time, but we know that it is at most a couple of bits of so you fold it again to complete the job.
You don't need to the calculation with all 1040 bits, but there's no way for the compiler to figure that you wouldn't need all of those because your constants are special and guarantees a certain outcome in the result.
Because the compiler can't predict the result, if you use _BitInt(1040) you have no choice but to roll out every single operation for all bits as if they were used, but you would need a lot less if you roll them out manually.
With _BitInt you always have to use all bits, with multi-precision you get to choose depending on the circumstance.
________________________________
From: Thiago Macieira <thiago_at_[hidden]>
Sent: Friday, August 8, 2025 8:06:43 PM
To: std-proposals_at_[hidden] <std-proposals_at_[hidden]>; Tiago Freire <tmiguelf_at_[hidden]>
Subject: Re: [std-proposals] Multiprecision division
On Friday, 8 August 2025 10:02:30 Pacific Daylight Time Tiago Freire wrote:
> No, _BitInt is a different philosophy of dealing with numbers. _BitInt is
> not multi-precision, it's fix precision but with support for widths larger
> than the CPU word size.
>
> And the compiler would not be able to optimize code the way multi-precision
> does because of limitations on what the compiler can reason about.
Why not? How would the division of two _BitInt(128) be different from what Hans
is proposing?
-- Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org Principal Engineer - Intel Platform & System Engineering
Received on 2025-08-08 18:35:50