perfect power / nth root improvements
tg at swox.com
Wed May 14 09:29:16 CEST 2008
From: Torbjorn Granlund <tg at swox.com>
Date: Wed, 14 May 2008 09:25:01 +0200
Howdy. I'm using GMP to generate and test a variety of numbers to see
if they are prefect powers. 98% of the run time of my program is spent
inside mpz_perfect_power_p, so it seems wise to spend time investigating
the efficiency of this portion of the code.
I read, regarding "Nth root"
Improve mpn_rootrem. The current code is really naive, using full
precision from the first iteration. Also, calling mpn_pow_1 isn't very
clever, as only 1/n of the result bits will be used; truncation after
each multiplication would be better. Avoiding division might also be
The current code is O(M(n)(log n)^2), it is possible to do O(M(n)) in
the worst case, or O(M(n/k)) on average, for computing the kth root of
an n-bit number.
And then an exciting tidbit:
Work mostly done, see http://swox.com/gmp/development.html.
Unfortunately, this is wrong.
We had a contribution, but we cannot use it for legal reasons.
But on that page, I don't see anything related to Nth root.
I see root.c and rootrem.c here:
But nothing related here:
Are there any code updates or news regarding Nth root or perfect power
More information about the gmp-discuss