speed of mpq_cmp vs mpq_sub
Torbjörn Granlund
tg at gmplib.org
Mon May 23 05:53:48 UTC 2016
Marc Glisse <marc.glisse at inria.fr> writes:
Note that after the multiplications by 3 and 5 (or 101 and 103), the
highparts are different. Or even simpler if den2 = 2 * den1. So this
would only apply in a few cases.
Right. My proposal seems rather dense after some sleep.
Perhaps we could modify the code to:
1. Check for equal denominators.
To make the tests as tight as possible we could use some simple
interval arithmetic (as opposed to just applying a safety margin).
The expected runtime for this assuming random operands is O(1). The
worst-case runtime is O(n) where n is the total size of the
operands. (When the optimisation triggers, the runtime is O(m)
... O(n) where m is the total size of the denominators.)
2. Perform an initial cross-product just using the topmost bits of all
operands. Here we could either extract GMP_NUMB_BITS/2 bits and use
plain *, or extract GMP_NUMB_BITS and rely on umul_ppmm.
We can use the bit counting code already present to locate the bits
which we need to extract.
This is O(1) but will need perhaps 20 cycles.
To avoid adding overhead for small operands, we could suppress the
trickery for expected products of (say) less than 3 limbs.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-discuss
mailing list