On Sun, 30 Jun 2024 at 11:22, Joel Jacobson wrote:
>
> On Sat, Jun 29, 2024, at 14:22, Dean Rasheed wrote:
>
> > But why just split it into two pieces? That will just lead
> > to a lot of unnecessary recursion for very unbalanced inputs. Instead,
> > why not split the longer input into N roughly e
On Sun, 30 Jun 2024 at 11:22, Joel Jacobson wrote:
>
> The surprising realization here is that there are actually (var1ndigits,
> var2ndigits)
> combinations where *only* doing mul_var_karatsuba_half() recursively
> all the way down to schoolbook *is* a performance win,
> even though we don't do
On Sun, Jun 30, 2024, at 17:44, Tom Lane wrote:
> "Joel Jacobson" writes:
>> On Sat, Jun 29, 2024, at 17:25, Tom Lane wrote:
>>> (In general I find this patch seriously undercommented.)
>
>> However, I think the comments above split_var_at(),
>> mul_var_karatsuba_full() and mul_var_karatsuba_half(
"Joel Jacobson" writes:
> On Sat, Jun 29, 2024, at 17:25, Tom Lane wrote:
>> (In general I find this patch seriously undercommented.)
> However, I think the comments above split_var_at(),
> mul_var_karatsuba_full() and mul_var_karatsuba_half()
> are quite good already, what do you think?
Not rem
On Sat, Jun 29, 2024, at 14:22, Dean Rasheed wrote:
> However, I really don't like having these magic constants at all,
> because in practice the threshold above which the Karatsuba algorithm
> is a win can vary depending on a number of factors, such as whether
> it's running on 32-bit or 64-bit, w
On Sat, Jun 29, 2024, at 17:25, Tom Lane wrote:
> Dean Rasheed writes:
>> There's another complication though (if the threshold is made
>> configurable): the various numeric functions that use mul_var() are
>> immutable, which means that the results from the Karatsuba algorithm
>> must match those
On 2024-Jun-30, Joel Jacobson wrote:
> However, I can imagine other crypto algorithms might require larger factors,
> as well as other scientific research use cases, such as astronomy and physics,
> that could desire storage of numeric values of very high precision.
FWIW I was talking to some peo
On Sat, Jun 29, 2024, at 14:22, Dean Rasheed wrote:
> On Sun, Jun 23, 2024 at 09:00:29AM +0200, Joel Jacobson wrote:
>> Attached, rebased version of the patch that implements the Karatsuba
>> algorithm in numeric.c's mul_var().
>>
>
> Something to watch out for is that not all callers of mul_var()
On Sat, 29 Jun 2024 at 16:25, Tom Lane wrote:
>
> Dean Rasheed writes:
> > There's another complication though (if the threshold is made
> > configurable): the various numeric functions that use mul_var() are
> > immutable, which means that the results from the Karatsuba algorithm
> > must match
Dean Rasheed writes:
> There's another complication though (if the threshold is made
> configurable): the various numeric functions that use mul_var() are
> immutable, which means that the results from the Karatsuba algorithm
> must match those from the schoolbook algorithm exactly, for all
> inpu
On Sun, Jun 23, 2024 at 09:00:29AM +0200, Joel Jacobson wrote:
> Attached, rebased version of the patch that implements the Karatsuba
> algorithm in numeric.c's mul_var().
>
Something to watch out for is that not all callers of mul_var() want
an exact result. Several internal callers request an a
On Sun, Jun 23, 2024 at 09:00:29AM +0200, Joel Jacobson wrote:
> Attached, rebased version of the patch that implements the Karatsuba
> algorithm in numeric.c's mul_var().
It's one of these areas where Dean Rasheed would be a good match for a
review, so adding him in CC. He has been doing a lot
On Fri, Jun 14, 2024, at 03:07, Aaron Altman wrote:
> Thanks for the detailed background and comments, Joel!
>
> The new status of this patch is: Ready for Committer
Thanks for reviewing.
Attached, rebased version of the patch that implements the Karatsuba algorithm
in numeric.c's mul_var().
/J
The following review has been posted through the commitfest application:
make installcheck-world: not tested
Implements feature: not tested
Spec compliant: not tested
Documentation:not tested
This applies cleanly to master, builds and passes regression tests in my
Win
On Tue, Jun 11, 2024, at 19:16, Aaron Altman wrote:
> Hi Joel, thanks for posting this. Although I have only a cursory
> familiarity with fast multiplication algorithms, I'd like to try and
> give it a review. To start with, can you help me understand the choice
> of this algorithm versus othe
Hi Joel, thanks for posting this. Although I have only a cursory
familiarity with fast multiplication algorithms, I'd like to try and
give it a review. To start with, can you help me understand the choice
of this algorithm versus others like Toom? If this looks correct on a
closer view I'll
Hi,
This patch introduces the Karatsuba algorithm to speed up multiplication
operations in numeric.c, where the operands have many digits.
It is implemented via a new conditional in mul_var() that determines whether
the sizes of the factors are sufficiently large to justify its use. This
decisio
17 matches
Mail list logo
