fac_ui rewrote.
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Sat Dec 10 21:31:27 CET 2011
Ciao!
Il Gio, 8 Dicembre 2011 6:32 pm, Torbjorn Granlund ha scritto:
> Using "configure --enable-alloca=debug --enable-assert" I tracked down
> this problem. I pushed a fix that I feel confident to be correct.
> Please review it.
Correct, thank you!
> There ars still problems with kolga.bibsys.no, a POWER6 machine.
> It looks like a compiler bug, but I am not certain.
>
> mpz_fac_ui(21) wrong
> got 6442746444000
> want 51090942171709440000
>
> The failing function seem to be mpz_bc_fac_1.
Yes, 21 is the first computed (not on the table) factorial for 64 bits. On
the same machine, the same problem arises for 32 bits:
mpz_fac_ui(13) wrong
got 128662719097651200
want 6227020800
Here too, we have 12! < 2^32 < 13!, i.e. it is the first computed factorial.
> I took a look at micro-optimisation of the new code. There are several
> integer divisions by non-constant divisors. These are extremely
> expensive, typically 50 to 200 cycles in modern CPUs.
You are right.
The function log_n_max should probably substituted by a few comparisons
with precomputed values.
> In block_resieve, it seems 'step' is of the form x*2^t, with t
Uhm, no, IIRC 'step' is a prime. It's Eratosthenes' sieve.
> In various places, you divide by n in order to figure out the number of
> products to accumulate into a limb. One could instead use
Yes, but I do not compute the number of products. I compute a maximum,
above it I avoid any other product.
--
http://bodrato.it/
More information about the gmp-devel
mailing list