mpf_div with arguments of different size
Jim White
mathimagics at yahoo.co.uk
Mon Jan 16 19:26:58 CET 2006
Hello
I believe I have found a problem with mpf_div.
There's no run-time error involved, and no loss of
accuracy - the only symptom of this problem is a
performance degradation, which can vary from being
very slight to severe to catastrophic, depending on
the circumstances.
It's taken me a week of sleepness nights to track this
down - the initial symptom was a computation that
occasionally ran 10 times slower than normal, and this
involved a rather complicated (and recursive) function
involving several hundreds of thousands of
multiplications of various sizes, but just one
division!
Having finally got to the bottom of it, it is in fact
very simply described and reproduced (see report
below).
Please let me know if more information is required.
Regards
Jim White
ANU, Canberra, Australia
1. Description
==============
The time required for mpf_div(rop, op1, op2) varies
dramatically on my system when op2._mp_size <
op1._mp_size.
2. System Config
================
Windows XP Home, Pentium 4 (3.0GHz).
GMP 4.1.4, --build=pentium4, built with MinGW (gcc
version 3.3.1 win32).
3. Steps to Reproduce Problem
=============================
Divide any N-limb operand by an M-limb operand where M
< N. The cost of the operation increases sharply as N
mod M increases.
Put another way, let M = floor(N/k), k = 1, 2 etc.
Now slowly reduce M and the relative cost of the
division rises very rapidly, eventually peaking as M
-> N/(k+1).
Since max(N mod M) is N/2, the worst cases occur for M
in the range N/2 < M < 3N/4.
Some example times, on my system (N, M are 32-bit limb
counts, T is div time in seconds, R is time relative
to NxN division):
N M T R
------------------------------
100K 100K 1.1
50K 0.9 0.8
60K 10.2 9.2
200K 200K 3.0
100K 2.3 0.8
150K 52.2 17.5
400K 400K 7.3
200K 6.0 0.8
250K 289.2 40.0 (ouch!!)
More information about the gmp-bugs
mailing list