ni...@lysator.liu.se (Niels Möller) writes:
0. Support in speed, for benchmarking.
Not checked in yet, but here are some benchmark numbers, comparing to
binvert:
$ ./speed -s 1-50 -r mpn_binvert mpn_broot.3 mpn_broot.5 mpn_broot.0x
overhead 0.8 secs, precision 1 units of
ni...@lysator.liu.se (Niels Möller) writes:
ni...@lysator.liu.se (Niels Möller) writes:
0. Support in speed, for benchmarking.
Not checked in yet, but here are some benchmark numbers, comparing to
binvert:
Do you have any interpretation of these numbers?
I am hacking out the
Torbjorn Granlund t...@gmplib.org writes:
Do you have any interpretation of these numbers?
Nothing deep. It make sense that for small k (k'th root), it's a
constant factor slower than binvert. And for large k, time should grow
in the same way as powlo time grows with the bitsize of the
Torbjorn Granlund t...@gmplib.org writes:
For a prospective mpn_rootexact, I assume the time will decrease with k,
given an n-bit input argument. Right?
I think so. Not sure if it's going to be completely monotone, though.
if we consider the problem of identifying perfect powers, I'd expect
ni...@lysator.liu.se (Niels Möller) writes:
Perhaps you could add some of your remarks as a comment to the file?
Makes sense. Not tonight, though.
I saw your edits. And I edited them sligtly, adding some more FIXMEs
and clarifying the operation of binv_root. Please read and tell me
Torbjorn Granlund t...@gmplib.org writes:
I realise that Use a small table to get starting value might not be
easy to implement for root since one might need k tables. Other
possibilities would be:
I think we discussed some months ago. IIRC, to get a starting value for
a^{1/k}, it should
ni...@lysator.liu.se (Niels Möller) writes:
broot.c:mpn_broot and your mpn_xxx that computes a^{1/n-1},
perhaps call the latter mpn_brootinvm1
I'll start with this one, then.
Here's an initial patch, integrating my code from a few months ago. Some
TODO items:
0. Support in
ni...@lysator.liu.se (Niels Möller) writes:
Sounds right. Such convolution type sum-of-products might want a
separate function, returning 3 limbs.
But I'm not talking about a convolution, but about the complete
powering. If x is a candidate nth root, and x^n is of size s bits, I
Torbjorn Granlund t...@gmplib.org writes:
I would like to avoid fp hardware in the portable parts of GMP.
I guess this means: Avoid using functions from libm, and avoid using
floating point in critical loops. Right? There's a (non-critical)
floating point operation in mpn_perfect_power_p
ni...@lysator.liu.se (Niels Möller) writes:
I guess this means: Avoid using functions from libm, and avoid using
floating point in critical loops. Right? There's a (non-critical)
floating point operation in mpn_perfect_power_p involving some logarithm
table.
Right. I would actually
Torbjorn Granlund t...@gmplib.org writes:
I just got a crazy idea. Compute the logarithm of the number (to a few
bits of precision, perhaps using table lookup). Multiply this logarithm
by k. Exponentiate using the logbase (again using a small table).
Conservatively compare to number being
ni...@lysator.liu.se (Niels Möller) writes:
Ah, and if we're brain storming, yet another variant would be to compute
an extra limb (or maybe only half a limb) of precision when we compute
the 2-adic k'th root. If the extra limb is non-zero, then the input can't
be a k'th power. That's
Torbjorn Granlund t...@gmplib.org writes:
ni...@lysator.liu.se (Niels Möller) writes:
My bsqrt uses an iteration converging to a^{-1/2}, and broot uses an
iteration converging to a^{1/n - 1}. Both division free.
So binv_sqroot (from mpn/generic/perfpow.c and your bsqrt seem to
ni...@lysator.liu.se (Niels Möller) writes:
Do you think we should have an advertised binv_sqrt function returning
a^{-1/2}? (And if so, should we have something analogous also for
euclidean square root? And for nth roots?)
Perhaps. A start would be to advertise it internally.
My
Torbjorn Granlund t...@gmplib.org writes:
With all respect for your functions, I don't think we should replace the
tested ones in perfpow. I think those should in he first place be
improved (and put in their own file).
I see. Do you want the functions in the separate files to compute
Torbjorn Granlund t...@gmplib.org writes:
OK. One might also want to consider which is the most useful function.
Computing x^{1/2} and x^{1/n} looks nice, at least in the manual ;-). And
we get there with a single mullo if we compute x^{-1/2} and x^{1/n-1}.
Which variants really are most
Torbjorn Granlund t...@gmplib.org writes:
2. What to return for inputs 0, and 1 and -1? They're perfect powers
(according to the docs), but which exponent should be returned?
(Here, the largest one is an impractical answer).
Perhaps 1 is the least silly answer.
Agree this makes
ni...@lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund t...@gmplib.org writes:
How should we solve this? It is tempting to let mpz_perfect_power_p
return p, but unfortunately it has type 'int' which might be too small.
Which type would be right? mp_bitcnt_t?
Yes, or
18 matches
Mail list logo
