[Paul Zimmermann <Paul.Zimmermann@loria.fr>] mpz_cbrtrem

[Jason Moxham]

On Monday 04 Nov 2002 9:39 am, Torbjorn Granlund wrote:
> This is of interest to gmp-devel I think.
>
> From: Paul Zimmermann <Paul.Zimmermann@loria.fr>
> Subject: mpz_cbrtrem
>
> here is a first implementation of mpz_cbrtrem which is asymptotically
> optimal, and even faster than mpz_sqrtrem:
>
> [zimmerma@ecrouves ~/gmp]$ ./cbrtrem 50000 1
> mpz_root took 29670ms
> mpz_sqrtrem took 2270ms
> mpz_cbrtrem took 1950ms
>

strange , On my athlon mpz_cbrtrem is 50% slower than mpz_sqrtrem ?


> while being reasonably fast for one-limb operands:
>
> [zimmerma@ecrouves ~/gmp]$ ./cbrtrem 1 100000
> mpz_root took 1830ms
> mpz_sqrtrem took 110ms
> mpz_cbrtrem took 2400ms
>
> The key function is mpz_add_bits: set the low bits of the destination
> to bits n0 to n1-1 from the operand.
>
> Paul
>

I assume this is the karatsuba cube root , does it generilize to k-th roo=
t ?

If this is the karatsuba cbrt-root then I was under the impression that i=
t was=20
not asymptotically optimal , although faster for pratical ranges .

So Paul , if it does generalize to k-th root , do you plan to implement i=
t for=20
GMP ? , or does anyone else ?


jason



=20