mpf_div with arguments of different size

[Jim White]

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!!)