nisse at lysator.liu.se
Thu Aug 4 22:17:45 CEST 2011
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
> Could be done essentially with the same algorithm, but tabulating the
> roots two; there's no need to recompute them for each base. Right?
> Not sure what you mean here. Surely, one could compute the 2nd, 4th,
> 8th, ..., 2^255th roots of the prime factors of all bases, and combine
> them. That would be complex, and not worth the debugging effort.
I missed a couple of words, I think.
The idea is, to compute log(b)/log(2), first compute sqrt(2),
sqrt(sqrt(2)), .... Then compute the logrithm starting from the most
significant bit by multiplying selected roots to get a value just below
(And then the integer part of the logarithm must be done upfront, or,
equivalently, you need to include repeated squares as well).
It's the same algorithm as for log(2)/log(b), just swapping exchanging
the roles of two and b: use roots of two rather than roots of b, and in
each iteration, compare the product to b rather than to two.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel