Incomplete GMP documentation...

Torbjorn Granlund tg at swox.com
Tue Sep 19 12:18:10 CEST 2006


Looking through the GMP mailing list archives, I found an odd
reply from myself:

Torbjorn Granlund <tege at swox.com> writes:

    I believe mpz_root can be speeded up; I might look into it if I get
    some spare time.
  
  Yes, http://swox.com/gmp/projects.html suggests a division-free
  iteration:
  
                      2
                     x   = x  (3  A x )/2
                      i+1   i        i
  
  This should be faster than the current code, since division is hard to
  make fast (and since current GMP division is a log(n) factor worse
  than multiplication).
  
I replied as if you talked about mpz_sqrt/mpn_sqrt, not mpz_root.

I try again: Please look at http://swox.com/gmp/devel/ for vastly
improved nth root code.  Compared to the code in GMP 4.2, there
is a 20x to 30x speedup.

-- 
Torbjörn


More information about the gmp-bugs mailing list