Torbjorn Granlund writes:
> I believe Niels Möller made some experiments with saving a "transform"
> from a recursive chain of Toom.
If I remember the benchmarking, I think I got a speedup of 5%-10% or so
for toom2 (aka Karatsuba). It's in the mail archives.
> When we merge the small primes (S
We envision invariance for multiplication for almost all operand sizes
and for division for all operand sizes.
We have made some experiments with the implicit multiplication
invariance of a very unbalanced a * b, i.e., where log a >> log b.
Alberto Zanoni might have published something in this are
Hi,
On Wed, Oct 17, 2012 at 10:22 AM, Niels Möller wrote:
> And we totally lack interfaces for invariance (and such interfaces don't
> have to be fft-specific).
Just a follow-up on this. I recall Torbjörn expressing the desire to
add such functionality. That was a few years back, and indeed this
Zimmermann Paul writes:
> However we also use mpn_mul_fft when the input number is a Fermat number, and
> in that case we can't use mpn_mulmod_bnm1 instead. Is it planned to add
> mpn_mulmod_bnp1 to the public interface too?
I would make sense, but there is no plan I'm aware of. I think such a
f
Hi,
> It definitely makes the wrap-around trick useful for fairly small sizes.
indeed. I've changed the development version of GMP-ECM to use mpn_mulmod_bnm1
instead of mpn_mul_fft for the wrap-around trick.
However we also use mpn_mul_fft when the input number is a Fermat number, and
in
Zimmermann Paul writes:
> In fact it seems I should compare with mpn_mulmod_bnm1_rounded, which seems to
> use the best fft size greater or equal to the wanted size (speed mpn_mul_fft
> does this automatically):
That seems right, I wasn't ware of how this is done in speed. For good
performance,
Torbjörn,
> As Niels said, mpn_mulmod_bnm1 might be put there. But mpn_mul_fft will
> never be put there, at least not under that name.
>
> (We prefer functions names that describes a function, rather than an
> algorithm.)
ok.
> Note also that mpn_mulmod_bnm1 is currently signi
> Internally in gmp, these days the function used for wraparound
> arithmetic is mpn_mulmod_bnm1 (and mulmod_bnm1_next_size). Which
> computes modulo B^n - 1, and is useful also below the fft threshold.
> Have you tried that?
no, since mpn_mulmod_bnm1 is not in the public interface eit
Niels,
thank you for your answer.
> From: ni...@lysator.liu.se (Niels Möller)
> Date: Wed, 17 Oct 2012 10:22:43 +0200
>
> Zimmermann Paul writes:
>
> > several applications using GMP (in particular GMP-ECM) use the internal fft
> > functions (mainly mpn_mul_fft and mpn_fft_best_k) for m
Zimmermann Paul writes:
> several applications using GMP (in particular GMP-ECM) use the internal fft
> functions (mainly mpn_mul_fft and mpn_fft_best_k) for multiplication modulo
> 2^N+1. This saves a factor of two with respect to mpn_mul_n if for example you
> know the lower part of a N-bit pro
Hi GMP developers,
several applications using GMP (in particular GMP-ECM) use the internal fft
functions (mainly mpn_mul_fft and mpn_fft_best_k) for multiplication modulo
2^N+1. This saves a factor of two with respect to mpn_mul_n if for example you
know the lower part of a N-bit product, a
11 matches
Mail list logo
