fac_ui rewrote.

[bodrato at mail.dm.unipi.it]

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/