# Newton's method for integer division

Craig Schroeder schroeder at santel.net
Mon Nov 27 03:30:28 CET 2006

```Below is an implementation of Newton's method for division.  I am new to
the list, so I do not know what the general policy is for sending code.
I have opted to include it directly in the email text.  I hope this is
not unreasonable.  I apologize for the lengthiness of this email.

Prototype:

void my_tdiv_qr(mpz_t Q, mpz_t R, mpz_t N, mpz_t D, int want_rem, int
order);

Usage is like mpz_tdiv_qr(Q, R, N, D) except:

* Remainder is computed when want_rem is nonzero, but otherwise is only
computed in the unlikely event that it is needed for correct rounding.
Thus, R should be initialized and may be used, even if want_rem is 0.

* Order should be one of 2, 3, 4, or 5.  These indicate that the
quadratic, cubic, quartic, or quintic convergent iterations should be
used.  Currently, the cubic version is fastest on my machine.

* Both N and D must be greater than zero.

Benchmark data is after the code below.  It is a comparison of GMP's
division (without remainder) against this version at a variety of
numerator and denominator sizes.

For 2n / n division, Newton's method became faster (on this machine)
with n = 98,304 bits.

The method does worse for smaller denominators, and much better for
larger denominators:

For 1.6n / n division, Newton's method became faster (on this machien)
with n = 5,120 bits.  (Unless I am mistaken, this is even below the FFT
multiplication cutoff.)  Below is the complete set of cutoffs, by size
ratio:

8/1: 1,048,576 bits / 131,072 bits
8/2: 786,432 bits / 196,608 bits
8/3: 393,216 bits / 147,456 bits
8/4: 196,608 bits / 98,304 bits
8/5: 8,192 bits / 5,120 bits
8/6: 4,096 bits / 3,072 bits
8/7: 3,072 bits / 2688 bits

Please consider inclusion of Newton's method for division in the GMP
library.  The code below is completely of my own writing, and I am
releasing it under the terms of the LGPL.

Thanks,
Craig Schroeder

---------------------------------------------------------------

/* Efficient integer division using Newton's method.
* Copyright (C) 2006  Craig Schroeder
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301  USA
*/

#include <gmp.h>
#include <assert.h>

/* This is the minimum number of bits on which to recurse.  Below
* this, use division with GMP's built-in floating division.  This
* would be more meaningful as an actual multiple of the limb size,
* but it doesn't matter.  What is interesting is that it doesn't seem
* to pay to switch to the next fastest division algorithm below a
* certain size.  It seems to be faster to go all the way down to very
* tiny numbers and build the estimate up recursively all the way.
*/
int min_prec = 100;

/* Number of bits in each limb (used for conversions between precision
* and limb sizes), and one less than this number (used for rounding
* to even limbs).
*/
int bits_per_limb = sizeof(mp_limb_t) * 8;
int limb_mask = sizeof(mp_limb_t) * 8 - 1;

/* Many of the computation below will be much less than one, but are
* effectively added to one in their use.  These values only need to
* be computed and used with enough precision that they could be added
* to one without loss of precision.  The _mp_exp field gives a good
* lower bound for how much precision would be lost if the value were
* added to one (and thus how much need not be computed).  This
* routine reduces the precision of x by the amount of precision that
* would no longer be needed by multiplying by y.  This is done in
* advance of multiplication to compute at a lower precision.
*/
int my_lower_prec(mpf_t x, mpf_t y)
{
/* This function only makes sense if 0 < y < 1.  However, if y = 0,
* then we treat it as having an infinite number of leading zeros,
* which would make the precision negative, and thus we should
* handle this case by saying we need negative precision.
*/
if(((__mpf_struct*)y)->_mp_size == 0)
return 0;

assert(((__mpf_struct*)y)->_mp_exp <= 0);

/* Actually adjust the precision */
((__mpf_struct*)x)->_mp_prec += ((__mpf_struct*)y)->_mp_exp;

/* It can happen that we now need negative precision.  Return a value
* indicating whether this has happened.  If so, the computations
* using this value should pretend it is identically zero.
*/
return ((__mpf_struct*)x)->_mp_prec >= 0;
}

/* This is the recursive part of the division routine.  It does the
* actual iteration.  It currently supports orders 2, 3, 4, and 5.
* Initially, D holds the integer to be divided, but represented as a
* floating point number and with the precision that the quotient will
* need.  prec is the number of limbs of precision to which x is to be
* computed.  order is the order of iteration to use.  On entry, x is
* initialized.  The remaining arguments, h, x0, and v, are
* initialized auxiliary space.  On exit, x = 1/D, accurate to prec
* full limbs.  Currently, D is required to be positive.
*/
void my_tdiv_rec(mpf_t x, mpf_t D, mpf_t h, mpf_t x0, mpf_t v, int prec,
int order)
{
/* Precision with which its seed should be computed.  For an
* "order"-convergent iteration, the amount of accuracy is
* multiplied by the order, so the size of seed required to get the
* necessary precision is about prec/order.  This effectively forces
* the precision to be rounded up, even if prec is an even multiple
* of the order.  This ensures that there is a steady "shedding" of
* bits at each iteration.  This effectively prevents roundoff from
* accumulating, since the roundoff is shed at each iteration.  The
* extra few limbs this computes is negligible compared to the
* number of limbs needed for this method to be competetive.
*/
int next_prec = prec / order + 2;

/* Compute x0, the seed estimate for 1/D, accurately to next_prec
* bits of precision.
*/
if(next_prec < min_prec)
{
/* Below the threshold, use GMP's built-in division to compute
* it to precision.
*/
mpf_set_prec_raw(x0, next_prec);
mpf_ui_div(x0, 1, D);
}
else
{
/* Otherwise, compute the seed recursively.  Note that x is
* passed in as working area.
*/
my_tdiv_rec(x0, D, h, x, v, next_prec, order);
}

/* Set the precisions of all of the working variables.  At this
* point, x0 holds the seed estimate for 1/D, at reduced precision
* next_prec.  Make sure it has this precision to avoid wasting time
* using it at higher precision.  The others are started off at full
* precision and reduced as needed.
*/
mpf_set_prec_raw(x0, next_prec);
mpf_set_prec_raw(h, prec);
mpf_set_prec_raw(x, prec);
mpf_set_prec_raw(v, prec);

/* All of the orders are computed by first computing an error
* estimate: h = 1 - D * x0.  Because x0 is approximately equal to
* 1/D, D * x0 will be approximately 1, and h will be very close to
* zero.  If x0 is accurate to next_prec, then h can be computed
* with accuracy reduced by next_prec.  GMP seems to figure this out
* on its own, so it is unnecessary to explicitely lower the
* precision.
*/
mpf_mul(h, x0, D);
mpf_ui_sub(h, 1, h);

/* All of the versions except order 2 will compute v = h^2, which
* can be done with reduced precision.  v will have about twice as
* many "leading zeros" as h does, and leading zeros equate into
* reduced precision.  Each call reduces v's precision by the number
* of "leading zeros" in h.  If we get "lucky" and we had an
* especially good approximation, then h^2 can be sufficiently small
* that it is effectively zero.  In this case, all higher order
* algorithms decay to the order two formula.  We still get the
* accuracy we need, but we get it with a lot less work.  If h^2 is
* needed, compute it.
*/
if(order > 2)
{
if(my_lower_prec(v, h) && my_lower_prec(v, h))
mpf_mul(v, h, h);       /* [2:1,1] h^2 */
else
order = 2;
}

/* At this point, the orders part ways.  They will all compute x to
* be the "correction delta" that should be multiplied by and then
* added to the seed.  Each computation has a comment indicating the
* quantity that was computed.  Before each quantity are three
* numbers in square brackets indicating its precision.  0 indicates
* full precision computation.  1 indicates full precision minus the
* number of "leading zeros" in h.  2 indicates full precision
* minutes twice the number of "leading zeros" in h, etc.  Bigger
* numbers mean faster operations.  [2:1,1] indicates that the
* result has precision 2 and the the arguments have precision 1.
* [0:1,0] indicates that a full-precision number was obtained from
* a full precision number and a reduced precision number.
*/
if(order == 2)
{
/* Iterative formula: x = x0 + x0 * h
* Thus, we should compute h <- h here (nothing to do).
*/
}
else if(order == 3)
{
/* Iterative formula: x = x0 + x0 * (h + h^2)
* Thus, we should compute h <- h + h^2 here.
*/
mpf_add(h, h, v);         /* [1:1,2] h + h^2 */
}
else if(order == 4)
{
/* Iterative formula: x = x0 + x0 * (h + h^2 + h^3)
* Thus, we should compute h <- h + h^2 + h^3 here.
*/
if(my_lower_prec(x, h) && my_lower_prec(x, v))
{
mpf_mul(x, v, h);     /* [3:2,1] h^3 */
mpf_add(v, v, x);     /* [2:2,3] h^2 + h^3 */
}
mpf_add(h, h, v);         /* [1:1,2] h + h^2 + h^3 */
mpf_set_prec_raw(x, prec);
}
else if(order == 5)
{
/* Iterative formula: x = x0 + x0 * (h + h^2 + h^3 + h^4)
* Thus, we should compute h <- h + h^2 + h^3 + h^4 here.
*/
mpf_add(h, h, v);         /* [1:1,2] h + h^2 */
if(my_lower_prec(x, h) && my_lower_prec(x, v))
{
mpf_mul(x, v, h);     /* [3:2,1] h^3 + h^4 */
mpf_add(h, h, x);     /* [1:3,1] h + h^2 + h^3 + h^4 */
}
mpf_set_prec_raw(x, prec);
}
assert(my_lower_prec(x, h));
mpf_mul(x, h, x0);            /* [1:1,0] x0 * h */
mpf_set_prec_raw(x, prec);
mpf_add(x, x, x0);            /* [0:1:0] x0 + x0 * h */
}

/* This is the wrapper part of the division routine.  It sets up a
* recursive call to my_tdiv_rec to do the inversion.  Then, it uses
* the computed 1/D to compute N/D, handle rounding, and compute the
* remainder if needed.
*
* On entry:
*   Q:        initialized
*   R:        initialized
*   N:        numerator (dividend)
*   D:        denominator (divisor)
*   want_rem: 1 (compute remainder) or 0 (do not compute remainder)
*   order:    2, 3, 4, or 5.  Which order of iteration should be used.
*
* On return:
*   Q:        quotient, truncated
*   R:        remainder, 0 <= R < D (if computed)
*   N:        not changed
*   D:        not changed
*   want_rem: not changed
*   order:    not changed
*
* Limitations:
*   * N and D must be positive (that is, neither negative nor zero)
*   * order must be one of 2, 3, 4, or 5
*   * no automatic choice of order
*   * does not attempt to handle small demonimators efficiently
*
* Remainder is computed if any of these is met:
*   * want_rem is nonzero
*   * the remainder is needed to decide how to round the quotient
*
* If the remainder is computed, R will hold the remainder on return,
* even if want_rem is zero.  If the remainder is not computed, R is
* not changed.  This routine does attempt to decide how to round by
* computing slightly more precisely than necessary and looking to see
* what the extra values are.  This works as long as the remainder is
* not very near 0 or very near D, when the precision necessary to
* resolve the rounding is highest.
*/
void my_tdiv_qr(mpz_t Q, mpz_t R, mpz_t N, mpz_t D, int want_rem, int order)
{
/* precision of numerator and denominator, in limbs */
int num_size = mpz_size(N);
int den_size = mpz_size(D);

/* precision to which quotient must be computed, in bits.  We need
* (numerator precision - denominator precision) for this.  We also
* want one extra limb for the indicator.  We want one more limb to
* get full precision in the high limb.  The extra bits added at
* each iteration and GMP's internal extra precision should be
* sufficient to make sure roundoff does not creep into the
* indicator limb.
*/
int quot_prec = (num_size - den_size + 2) * bits_per_limb;

/* DF and NF are floating point versions of D and N, the quantities
* being divided.  Note that DF is used throughout the recursion,
* but NF is only needed for one multiplication afterwards; it must
* be a float, however, since no mpz_t times mpf_t routine exists.
* one_over_D is used for computing 1/D.  Variables t, u, and v are
* auxiliary space used by the recursive routines.  They are
* allocated here to avoid the need to reallocate at each iteration.
*/
mpf_t DF, NF, one_over_D, t, u, v;

/* Not pretty, and not my fault. :-) */
__mpf_struct* xs;

/* This is an "indicator" limb, which is to say it is the limb
* directly beyond the portion of the quotient that I care about.
* Its value is rather unimportant, except that it is a good
* indicator of whether the rounding might have been done
* incorrectly.  If ind is 0x00000000 or 0xFFFFFFFF, then the number
* was very close to being an integer, and it is possible that it
* might not have been rounded properly.  Otherwise, the number is
* bounded away from an integer, and we can be sure the rounding is
* right.  Note that this requires an extra limb of precision.
*/
mp_limb_t ind = 0;

/* Limitation of this implementation. */
assert(mpz_sgn(N) > 0);
assert(mpz_sgn(D) > 0);
assert(order >= 2 && order <= 5);

/* Allocate all the variables to full precision.  Full precision
* here is the precision to which quotient must be computed.  Note
* that order two does not use v.  As such, there is not actually
* any need to initialize it if order is 2.  Note that v is still
* referenced because the precision changes are still applied to it,
* even though they aren't used in this case.  Both of these should
* probably be changed to reduce memory use.
*/
mpf_init2(DF, quot_prec);
mpf_init2(one_over_D, quot_prec);
mpf_init2(t, quot_prec);
mpf_init2(u, quot_prec);
mpf_init2(v, quot_prec);

/* DF is the same as D, but a floating point value.  The recursive
* computation needs it to be floating point.  This also is
* convenient, since it is easy to use it in lower precision
* computations. */
mpf_set_z(DF, D);

/* This does most of the work.  This is the recursive routine that
* computes one_over_D to be 1/DF (i.e., 1/D) accurately to
* quot_prec bits.
*/
my_tdiv_rec(one_over_D, DF, t, u, v, quot_prec, order);

/* Make sure t, u, and v are restored to their original precisions,
* so that they can be savely cleared.  The precision of DF is never
* modified, so it can be safely cleared.  Clear each of them.
*/
mpf_set_prec_raw(t, quot_prec);
mpf_set_prec_raw(u, quot_prec);
mpf_set_prec_raw(v, quot_prec);
mpf_clear(t);
mpf_clear(u);
mpf_clear(v);
mpf_clear(DF);

/* We do not need NF (the floating point copy of the numerator)
* until now, so do not create it until we absolutely need it, to
* reduce memory use. */
mpf_init2(NF, num_size * bits_per_limb);
mpf_set_z(NF, N);

/* Make sure are are computing with a full precision 1/D. */
mpf_set_prec_raw(one_over_D, quot_prec);

/* Compute N/D as NF * (1/D) */
mpf_mul(one_over_D, one_over_D, NF);

/* That is all we needed NF for.  What a waste. */
mpf_clear(NF);

/* Set the quotient Q to be the floor of one_over_D (which is
* actually holding N/D at this point.)  Use the floor version to
* round down.  Since N>0 and D>0, it follows that Q>=0, so that
* floor and truncation are the same.
*/
mpz_set_f(Q, one_over_D);

/* This parts gets a little messy.  The structure fields will be
* used a few times, so make life a little easier by doing the cast
* once and for all.
*/
xs = (__mpf_struct*)one_over_D;

/* If the indicator limb is not represented (the size is small
* enough that it does not include the limb just below the decimal
* point), then the indicator limb is zero (by GMP convention).
* Otherwise, pick out that limb.
*/
if(xs->_mp_size > xs->_mp_exp + 1)
ind = xs->_mp_d[xs->_mp_size - xs->_mp_exp - 1];

/* Do we need to compute the remainder?  It will cost one
* full-precision multiplication, so it is definitely worth avoiding
* if possible.  Only compute it if (a) the indicator limb cannot
* determine if rounding was done properly or (b) the caller
* actually wants the remainder.
*/
if(ind == 0x00000000 || ind == 0xFFFFFFFF || want_rem)
{
/* Computing the remainder is straightforward: R = N - Q * D. */
mpz_mul(R, Q, D);
mpz_sub(R, N, R);

/* If the indicator limb did not resolve the rounding question,
* we need to examine the remainder here.  There are two
* possibilities.  The first case is that the quotient was
* computed slightly high, resulting in it being rounded to the
* integer above where it should.  I do not not think this can
* happen, particularly for even order versions.  I have also
* never seen it occur.  Nevertheless, it is best to be safe and
* check anyway.  Either way, the quotient was one too high,
* resulting in a remainder that is negative.
*/
if(ind == 0x00000000 && mpz_sgn(R) < 0)
{
/* Fix by decrementing the quotient and adding back the
* divisor to the remainder.
*/
mpz_sub_ui(Q, Q, 1);
}

/* The other possibility can and does occur.  The quotient is
* rounded down and is one less than what it should be.  This
* results in a remainder that is equal to or greater than the
* divisor.
*/
if(ind == 0xFFFFFFFF && mpz_cmp(R, D) > 0)
{
/* Fix by incrementing the quotient and subtracting the
* divisor from the remainder.
*/
mpz_sub(R, R, D);
}
}

/* No longer needed, and already set to its original full precision
* above; it is safe to delete it now.
*/
mpf_clear(one_over_D);
}

-----------------------------------------------------------

First, a quick explanation of what these lines mean:
size:      256/      64  runs:   262144  time: gmp 0.18 o2 1.1 o3 1.01
o4 1.04 o5 1.07  rem: 0
This means that a randomly generated 256-bit dividend was divided by a
randomly generated 64-bit divisor 262,144 times (different random
numbers each time).  The times listed include random number generation.

GMP's division took 0.18 seconds total.  The above code took 1.10
seconds, 1.01 seconds, 1.04 seconds, and 1.07 seconds when run with
order=2, 3, 4, and 5 respectively.

In general, the dividends are powers of two and 3/2 times powers of two,
starting at 2^8 and ending at 3/2 * 2^27.  The divisors have 1/8, 2/8,
3/8, 4/8, 5/8, 6/8, and 7/8 as many bits as the divisor.

All tests were performed on a one-processor 2.4GHz Pentium 4 with 1 GB
of memory running Gentoo Linux.

The code was compiled with gcc (GCC) 4.1.1 (Gentoo 4.1.1-r1) with
optimization flags -O3 -mmmx -msse -msse2.

Cross over points (by dividend/divisor ratio, where Newton's method is
first faster than GMP, or where they are indistinguishably close and
Newton's method is faster after that) in bits:
8/1: 1,048,576 bits / 131,072 bits
8/2: 786,432 bits / 196,608 bits
8/3: 393,216 bits / 147,456 bits
8/4: 196,608 bits / 98,304 bits
8/5: 8,192 bits / 5,120 bits
8/6: 4,096 bits / 3,072 bits
8/7: 3,072 bits / 2688 bits

In 32-bit limbs:
8/1: 32,768 / 4,096
8/2: 24,576 / 6,144
8/3: 12,288 / 4,608
8/4: 6,144 / 3,072
8/5: 256 / 160
8/6: 128 / 96
8/7: 96 / 84

size:      256/      32  runs:   262144  time: gmp 0.11 o2 1 o3 1.27 o4
1.01 o5 1.01  rem: 0
size:      256/      64  runs:   262144  time: gmp 0.18 o2 1.1 o3 1.01
o4 1.04 o5 1.07  rem: 0
size:      256/      96  runs:   262144  time: gmp 0.2 o2 1.11 o3 0.98
o4 1.05 o5 1.05  rem: 0
size:      256/     128  runs:   262144  time: gmp 0.21 o2 1.07 o3 0.95
o4 1.03 o5 1.04  rem: 0
size:      256/     160  runs:   262144  time: gmp 0.23 o2 0.88 o3 0.95
o4 0.97 o5 0.96  rem: 0
size:      256/     192  runs:   262144  time: gmp 0.22 o2 0.85 o3 0.94
o4 0.92 o5 0.93  rem: 0
size:      256/     224  runs:   262144  time: gmp 0.2 o2 0.79 o3 0.8 o4
0.8 o5 0.8  rem: 0
size:      384/      48  runs:   262144  time: gmp 0.27 o2 1.51 o3 1.57
o4 1.56 o5 1.35  rem: 0
size:      384/      96  runs:   262144  time: gmp 0.29 o2 1.6 o3 1.55
o4 1.36 o5 1.36  rem: 0
size:      384/     144  runs:   262144  time: gmp 0.33 o2 1.39 o3 1.53
o4 1.23 o5 1.36  rem: 0
size:      384/     192  runs:   262144  time: gmp 0.32 o2 1.35 o3 1.18
o4 1.18 o5 1.29  rem: 0
size:      384/     240  runs:   262144  time: gmp 0.38 o2 1.24 o3 1.11
o4 1.08 o5 1.09  rem: 0
size:      384/     288  runs:   262144  time: gmp 0.32 o2 0.95 o3 0.99
o4 1 o5 0.99  rem: 0
size:      384/     336  runs:   262144  time: gmp 0.28 o2 0.85 o3 0.85
o4 0.85 o5 0.85  rem: 0
size:      512/      64  runs:   262144  time: gmp 0.31 o2 1.97 o3 2.06
o4 2.14 o5 2.14  rem: 0
size:      512/     128  runs:   262144  time: gmp 0.39 o2 2.01 o3 1.95
o4 2.04 o5 1.77  rem: 0
size:      512/     192  runs:   262144  time: gmp 0.44 o2 1.99 o3 1.86
o4 1.96 o5 1.69  rem: 0
size:      512/     256  runs:   262144  time: gmp 0.44 o2 1.9 o3 1.73
o4 1.53 o5 1.55  rem: 0
size:      512/     320  runs:   262144  time: gmp 0.49 o2 1.48 o3 1.35
o4 1.35 o5 1.41  rem: 0
size:      512/     384  runs:   262144  time: gmp 0.42 o2 1.28 o3 1.17
o4 1.22 o5 1.21  rem: 0
size:      512/     448  runs:   262144  time: gmp 0.34 o2 0.92 o3 1.01
o4 1.02 o5 1.02  rem: 0
size:      768/      96  runs:   262144  time: gmp 0.54 o2 3.21 o3 3.01
o4 3.15 o5 3.09  rem: 0
size:      768/     192  runs:   262144  time: gmp 0.67 o2 3.39 o3 3 o4
3.13 o5 3.09  rem: 0
size:      768/     288  runs:   262144  time: gmp 0.72 o2 2.93 o3 2.74
o4 2.84 o5 2.93  rem: 0
size:      768/     384  runs:   262144  time: gmp 0.73 o2 2.63 o3 2.37
o4 2.54 o5 2.38  rem: 0
size:      768/     480  runs:   262144  time: gmp 0.76 o2 2.28 o3 2.13
o4 1.94 o5 1.91  rem: 0
size:      768/     576  runs:   262144  time: gmp 0.67 o2 1.62 o3 1.49
o4 1.5 o5 1.53  rem: 0
size:      768/     672  runs:   262144  time: gmp 0.5 o2 1.12 o3 1.16
o4 1.19 o5 1.18  rem: 0
size:     1024/     128  runs:   262144  time: gmp 0.76 o2 4.33 o3 4.69
o4 4.27 o5 4.51  rem: 0
size:     1024/     256  runs:   262144  time: gmp 1 o2 4.45 o3 4.53 o4
4.33 o5 4.3  rem: 0
size:     1024/     384  runs:   262144  time: gmp 1.07 o2 4.24 o3 3.7
o4 4 o5 3.94  rem: 0
size:     1024/     512  runs:   262144  time: gmp 1.08 o2 3.76 o3 3.21
o4 3.34 o5 3.48  rem: 0
size:     1024/     640  runs:   262144  time: gmp 1.1 o2 2.86 o3 2.51
o4 2.71 o5 2.65  rem: 0
size:     1024/     768  runs:   262144  time: gmp 0.96 o2 2.23 o3 2.02
o4 1.82 o5 1.84  rem: 0
size:     1024/     896  runs:   262144  time: gmp 0.72 o2 1.47 o3 1.37
o4 1.37 o5 1.38  rem: 0
size:     1536/     192  runs:   262144  time: gmp 1.36 o2 7.47 o3 7.71
o4 7.86 o5 7.54  rem: 0
size:     1536/     384  runs:   262144  time: gmp 1.77 o2 7.58 o3 7.28
o4 7.02 o5 7.07  rem: 0
size:     1536/     576  runs:   262144  time: gmp 1.97 o2 6.7 o3 6.24
o4 6.23 o5 6.36  rem: 0
size:     1536/     768  runs:   262144  time: gmp 2.04 o2 5.69 o3 5.35
o4 5.2 o5 5.26  rem: 0
size:     1536/     960  runs:   262144  time: gmp 2.01 o2 4.46 o3 3.79
o4 3.96 o5 3.94  rem: 0
size:     1536/    1152  runs:   262144  time: gmp 1.7 o2 2.95 o3 2.62
o4 2.82 o5 2.86  rem: 0
size:     1536/    1344  runs:   262144  time: gmp 1.2 o2 1.8 o3 1.65 o4
1.62 o5 1.7  rem: 0
size:     2048/     256  runs:   262144  time: gmp 2.07 o2 10.59 o3
11.11 o4 11.39 o5 10.88  rem: 0
size:     2048/     512  runs:   262144  time: gmp 2.77 o2 10.73 o3
10.32 o4 10.39 o5 10.09  rem: 0
size:     2048/     768  runs:   262144  time: gmp 3.21 o2 10.03 o3 9.15
o4 9.1 o5 9.33  rem: 0
size:     2048/    1024  runs:   262144  time: gmp 3.3 o2 8.44 o3 7.43
o4 7.32 o5 7.52  rem: 0
size:     2048/    1280  runs:   262144  time: gmp 3.2 o2 5.97 o3 5.57
o4 5.35 o5 5.42  rem: 0
size:     2048/    1536  runs:   262144  time: gmp 2.66 o2 4.1 o3 3.57
o4 3.68 o5 3.76  rem: 0
size:     2048/    1792  runs:   262144  time: gmp 1.83 o2 2.4 o3 2.22
o4 2.02 o5 2.11  rem: 0
size:     3072/     384  runs:   262144  time: gmp 3.84 o2 19.73 o3
20.65 o4 20.84 o5 21.27  rem: 0
size:     3072/     768  runs:   131072  time: gmp 2.78 o2 9.88 o3 9.49
o4 9.22 o5 9.41  rem: 0
size:     3072/    1152  runs:   131072  time: gmp 3.37 o2 8.68 o3 7.98
o4 8.02 o5 8.11  rem: 0
size:     3072/    1536  runs:   131072  time: gmp 3.47 o2 7.05 o3 6.22
o4 6.13 o5 6.31  rem: 0
size:     3072/    1920  runs:   131072  time: gmp 3.33 o2 5.18 o3 4.46
o4 4.38 o5 4.49  rem: 0
size:     3072/    2304  runs:   131072  time: gmp 2.61 o2 3.08 o3 2.92
o4 2.88 o5 2.88  rem: 0
size:     3072/    2688  runs:   262144  time: gmp 3.44 o2 3.23 o3 2.94
o4 3.12 o5 3.09  rem: 0
size:     4096/     512  runs:   131072  time: gmp 3.03 o2 14.65 o3
15.81 o4 15.43 o5 15.72  rem: 0
size:     4096/    1024  runs:    65536  time: gmp 2.49 o2 7.39 o3 7.08
o4 6.72 o5 7.13  rem: 0
size:     4096/    1536  runs:    65536  time: gmp 2.73 o2 6.7 o3 6.05
o4 6.17 o5 6.44  rem: 0
size:     4096/    2048  runs:    65536  time: gmp 2.87 o2 5.41 o3 4.74
o4 4.72 o5 4.79  rem: 0
size:     4096/    2560  runs:    65536  time: gmp 2.68 o2 3.65 o3 3.22
o4 3.22 o5 3.24  rem: 0
size:     4096/    3072  runs:    65536  time: gmp 2.12 o2 2.26 o3 2.01
o4 2.02 o5 2.04  rem: 0
size:     4096/    3584  runs:   262144  time: gmp 5.58 o2 4.52 o3 3.94
o4 4.09 o5 4.12  rem: 0
size:     6144/     768  runs:    65536  time: gmp 3.09 o2 13.64 o3
13.94 o4 14.02 o5 14.65  rem: 0
size:     6144/    1536  runs:    32768  time: gmp 2.45 o2 7.04 o3 6.47
o4 6.46 o5 6.54  rem: 0
size:     6144/    2304  runs:    32768  time: gmp 2.95 o2 6.04 o3 5.54
o4 5.58 o5 5.82  rem: 0
size:     6144/    3072  runs:    32768  time: gmp 3.1 o2 4.86 o3 4.37
o4 4.34 o5 4.48  rem: 0
size:     6144/    3840  runs:    32768  time: gmp 2.78 o2 3.37 o3 2.98
o4 2.63 o5 3.05  rem: 0
size:     6144/    4608  runs:    65536  time: gmp 3.7 o2 3.86 o3 3.3 o4
3.33 o5 3.38  rem: 0
size:     6144/    5376  runs:   131072  time: gmp 5.57 o2 3.39 o3 3.29
o4 3.15 o5 3.18  rem: 0
size:     8192/    1024  runs:    32768  time: gmp 2.63 o2 10.86 o3 11.3
o4 11.34 o5 11.56  rem: 0
size:     8192/    2048  runs:    16384  time: gmp 2.1 o2 5.36 o3 5 o4
4.99 o5 5.14  rem: 0
size:     8192/    3072  runs:    16384  time: gmp 2.55 o2 4.71 o3 4.15
o4 4.29 o5 4.5  rem: 0
size:     8192/    4096  runs:    16384  time: gmp 2.31 o2 3.77 o3 3.38
o4 3.43 o5 3.48  rem: 0
size:     8192/    5120  runs:    16384  time: gmp 2.31 o2 2.46 o3 2.24
o4 2.23 o5 2.29  rem: 0
size:     8192/    6144  runs:    32768  time: gmp 3.37 o2 2.93 o3 2.53
o4 2.54 o5 2.55  rem: 0
size:     8192/    7168  runs:    65536  time: gmp 4.54 o2 2.49 o3 2.23
o4 2.2 o5 2.24  rem: 0
size:    12288/    1536  runs:    16384  time: gmp 2.85 o2 10.22 o3
10.43 o4 10.32 o5 10.56  rem: 0
size:    12288/    3072  runs:     8192  time: gmp 2.26 o2 4.95 o3 4.58
o4 4.62 o5 4.64  rem: 0
size:    12288/    4608  runs:     8192  time: gmp 2.43 o2 4.32 o3 4.1
o4 3.99 o5 4.17  rem: 0
size:    12288/    6144  runs:     8192  time: gmp 2.33 o2 3.38 o3 3.04
o4 3.05 o5 3.2  rem: 0
size:    12288/    7680  runs:     8192  time: gmp 2.14 o2 2.28 o3 2 o4
2.02 o5 2.05  rem: 0
size:    12288/    9216  runs:    16384  time: gmp 3.25 o2 2.52 o3 2.27
o4 2.3 o5 2.31  rem: 0
size:    12288/   10752  runs:    65536  time: gmp 8.71 o2 4.13 o3 3.61
o4 3.62 o5 3.62  rem: 0
size:    16384/    2048  runs:     8192  time: gmp 2.37 o2 7.55 o3 7.7
o4 7.69 o5 8.03  rem: 0
size:    16384/    4096  runs:     8192  time: gmp 3.32 o2 7.69 o3 7.1
o4 7.08 o5 7.27  rem: 0
size:    16384/    6144  runs:     8192  time: gmp 3.85 o2 6.56 o3 5.88
o4 6.03 o5 6.26  rem: 0
size:    16384/    8192  runs:     8192  time: gmp 3.55 o2 4.74 o3 4.8
o4 4.84 o5 5.06  rem: 0
size:    16384/   10240  runs:     8192  time: gmp 3.5 o2 3.38 o3 3.05
o4 3.08 o5 3.27  rem: 0
size:    16384/   12288  runs:    16384  time: gmp 5.06 o2 3.93 o3 3.42
o4 3.44 o5 3.54  rem: 0
size:    16384/   14336  runs:    32768  time: gmp 6.88 o2 3.05 o3 2.7
o4 2.68 o5 2.72  rem: 0
size:    24576/    3072  runs:     4096  time: gmp 2.58 o2 7.27 o3 7.33
o4 7.32 o5 7.71  rem: 0
size:    24576/    6144  runs:     4096  time: gmp 3.41 o2 7.05 o3 6.44
o4 6.53 o5 6.49  rem: 0
size:    24576/    9216  runs:     4096  time: gmp 3.75 o2 6.1 o3 5.44
o4 5.64 o5 5.92  rem: 0
size:    24576/   12288  runs:     4096  time: gmp 3.55 o2 4.8 o3 4.46
o4 4.36 o5 4.64  rem: 0
size:    24576/   15360  runs:     4096  time: gmp 3.22 o2 3.13 o3 2.8
o4 2.84 o5 2.93  rem: 0
size:    24576/   18432  runs:     8192  time: gmp 4.88 o2 3.41 o3 3.11
o4 3.16 o5 3.3  rem: 0
size:    24576/   21504  runs:    16384  time: gmp 6.61 o2 2.63 o3 2.41
o4 2.45 o5 2.46  rem: 0
size:    32768/    4096  runs:     4096  time: gmp 3.83 o2 10.96 o3 11.2
o4 11.24 o5 11.69  rem: 0
size:    32768/    8192  runs:     2048  time: gmp 2.65 o2 5.61 o3 5.35
o4 5.21 o5 5.31  rem: 0
size:    32768/   12288  runs:     2048  time: gmp 2.98 o2 4.77 o3 4.26
o4 4.3 o5 4.57  rem: 0
size:    32768/   16384  runs:     2048  time: gmp 2.76 o2 3.73 o3 3.27
o4 3.42 o5 3.44  rem: 0
size:    32768/   20480  runs:     2048  time: gmp 2.6 o2 2.42 o3 2.23
o4 2.19 o5 2.29  rem: 0
size:    32768/   24576  runs:     4096  time: gmp 3.83 o2 2.7 o3 2.46
o4 2.45 o5 2.52  rem: 0
size:    32768/   28672  runs:    16384  time: gmp 10.39 o2 4.04 o3 3.66
o4 3.76 o5 3.83  rem: 0
size:    49152/    6144  runs:     2048  time: gmp 3.95 o2 10.26 o3
10.23 o4 10.3 o5 10.85  rem: 0
size:    49152/   12288  runs:     1024  time: gmp 2.61 o2 5.07 o3 4.68
o4 4.64 o5 4.79  rem: 0
size:    49152/   18432  runs:     1024  time: gmp 2.8 o2 4.29 o3 3.85
o4 4.07 o5 4.22  rem: 0
size:    49152/   24576  runs:     1024  time: gmp 2.64 o2 3.44 o3 3.2
o4 3.21 o5 3.29  rem: 0
size:    49152/   30720  runs:     2048  time: gmp 4.78 o2 4.38 o3 3.94
o4 4.08 o5 4.19  rem: 0
size:    49152/   36864  runs:     2048  time: gmp 3.59 o2 2.42 o3 2.27
o4 2.25 o5 2.34  rem: 0
size:    49152/   43008  runs:     8192  time: gmp 9.88 o2 3.6 o3 3.26
o4 3.3 o5 3.42  rem: 0
size:    65536/    8192  runs:     1024  time: gmp 3.03 o2 8.02 o3 8 o4
7.95 o5 8.35  rem: 0
size:    65536/   16384  runs:      512  time: gmp 2.06 o2 3.9 o3 3.52
o4 3.59 o5 3.66  rem: 0
size:    65536/   24576  runs:      512  time: gmp 2.24 o2 3.32 o3 2.94
o4 3.09 o5 3.23  rem: 0
size:    65536/   32768  runs:      512  time: gmp 2.04 o2 2.63 o3 2.33
o4 2.48 o5 2.51  rem: 0
size:    65536/   40960  runs:     1024  time: gmp 3.83 o2 3.49 o3 3.16
o4 3.16 o5 3.29  rem: 0
size:    65536/   49152  runs:     2048  time: gmp 5.55 o2 3.81 o3 3.33
o4 3.44 o5 3.51  rem: 0
size:    65536/   57344  runs:     4096  time: gmp 7.86 o2 2.83 o3 2.57
o4 2.55 o5 2.63  rem: 0
size:    98304/   12288  runs:      512  time: gmp 3.06 o2 7.26 o3 7.31
o4 7.3 o5 7.61  rem: 0
size:    98304/   24576  runs:      512  time: gmp 3.92 o2 7.31 o3 6.76
o4 6.74 o5 6.8  rem: 0
size:    98304/   36864  runs:      256  time: gmp 2.11 o2 3.06 o3 2.76
o4 2.85 o5 2.98  rem: 0
size:    98304/   49152  runs:      256  time: gmp 2 o2 2.48 o3 2.13 o4
2.21 o5 2.24  rem: 0
size:    98304/   61440  runs:      512  time: gmp 3.53 o2 3.11 o3 2.64
o4 2.86 o5 3.02  rem: 0
size:    98304/   73728  runs:     1024  time: gmp 5.35 o2 3.56 o3 3.26
o4 3.29 o5 3.37  rem: 0
size:    98304/   86016  runs:     2048  time: gmp 7.21 o2 2.51 o3 2.3
o4 2.32 o5 2.41  rem: 0
size:   131072/   16384  runs:      256  time: gmp 2.4 o2 5.28 o3 5.35
o4 5.27 o5 5.47  rem: 0
size:   131072/   32768  runs:      256  time: gmp 3.05 o2 5.18 o3 4.63
o4 4.8 o5 5.03  rem: 0
size:   131072/   49152  runs:      256  time: gmp 3.37 o2 4.72 o3 4.17
o4 4.36 o5 4.52  rem: 0
size:   131072/   65536  runs:      256  time: gmp 3.01 o2 3.73 o3 3.54
o4 3.53 o5 3.1  rem: 0
size:   131072/   81920  runs:      256  time: gmp 2.8 o2 2.42 o3 2.17
o4 2.2 o5 2.28  rem: 0
size:   131072/   98304  runs:      512  time: gmp 4.03 o2 2.64 o3 2.36
o4 2.48 o5 2.54  rem: 0
size:   131072/  114688  runs:     2048  time: gmp 10.98 o2 3.92 o3 3.44
o4 3.57 o5 3.62  rem: 0
size:   196608/   24576  runs:      128  time: gmp 2.31 o2 4.37 o3 4.36
o4 4.3 o5 4.55  rem: 0
size:   196608/   49152  runs:      128  time: gmp 2.94 o2 4.75 o3 4.28
o4 4.38 o5 4.47  rem: 0
size:   196608/   73728  runs:      128  time: gmp 3.13 o2 4.01 o3 3.56
o4 3.72 o5 3.92  rem: 0
size:   196608/   98304  runs:      128  time: gmp 2.85 o2 3.19 o3 2.8
o4 2.99 o5 3.04  rem: 0
size:   196608/  122880  runs:      128  time: gmp 2.58 o2 2.23 o3 2.04
o4 2.07 o5 2.11  rem: 0
size:   196608/  147456  runs:      256  time: gmp 3.74 o2 2.45 o3 2.17
o4 2.22 o5 2.29  rem: 0
size:   196608/  172032  runs:     1024  time: gmp 10.7 o2 3.58 o3 3.27
o4 3.28 o5 3.41  rem: 0
size:   262144/   32768  runs:      128  time: gmp 3.56 o2 6.73 o3 6.78
o4 6.71 o5 7.07  rem: 0
size:   262144/   65536  runs:       64  time: gmp 2.26 o2 3.3 o3 2.95
o4 2.97 o5 3.09  rem: 0
size:   262144/   98304  runs:       64  time: gmp 2.41 o2 2.92 o3 2.59
o4 2.7 o5 2.79  rem: 0
size:   262144/  131072  runs:       64  time: gmp 2.21 o2 2.37 o3 2.07
o4 2.17 o5 2.26  rem: 0
size:   262144/  163840  runs:      128  time: gmp 4.03 o2 3.18 o3 2.84
o4 2.98 o5 3.06  rem: 0
size:   262144/  196608  runs:      256  time: gmp 5.86 o2 3.75 o3 3.4
o4 3.43 o5 3.62  rem: 0
size:   262144/  229376  runs:      512  time: gmp 7.94 o2 2.71 o3 2.43
o4 2.54 o5 2.59  rem: 0
size:   393216/   49152  runs:       64  time: gmp 3.42 o2 5.5 o3 4.85
o4 5.51 o5 5.55  rem: 0
size:   393216/   98304  runs:       32  time: gmp 2.12 o2 2.55 o3 2.32
o4 2.62 o5 2.58  rem: 0
size:   393216/  147456  runs:       32  time: gmp 2.25 o2 2.31 o3 2.26
o4 2.33 o5 2.35  rem: 0
size:   393216/  196608  runs:       64  time: gmp 3.91 o2 3.76 o3 3.69
o4 3.69 o5 3.88  rem: 0
size:   393216/  245760  runs:       64  time: gmp 3.34 o2 2.96 o3 2.62
o4 2.71 o5 2.79  rem: 0
size:   393216/  294912  runs:      128  time: gmp 4.82 o2 3.22 o3 2.85
o4 3 o5 3.1  rem: 0
size:   393216/  344064  runs:      256  time: gmp 7.29 o2 2.52 o3 2.2
o4 2.28 o5 2.35  rem: 0
size:   524288/   65536  runs:       32  time: gmp 2.64 o2 4.34 o3 3.7
o4 3.87 o5 3.88  rem: 0
size:   524288/  131072  runs:       32  time: gmp 3.29 o2 3.57 o3 3.33
o4 3.4 o5 3.89  rem: 0
size:   524288/  196608  runs:       32  time: gmp 3.4 o2 3.21 o3 2.83
o4 3.41 o5 3.43  rem: 0
size:   524288/  262144  runs:       32  time: gmp 2.91 o2 2.55 o3 2.65
o4 2.73 o5 2.79  rem: 0
size:   524288/  327680  runs:       64  time: gmp 4.91 o2 3.74 o3 3.69
o4 3.68 o5 3.91  rem: 0
size:   524288/  393216  runs:       64  time: gmp 3.36 o2 2.39 o3 2.11
o4 2.18 o5 2.27  rem: 0
size:   524288/  458752  runs:      256  time: gmp 11.45 o2 3.82 o3 3.49
o4 3.49 o5 3.7  rem: 0
size:   786432/   98304  runs:       16  time: gmp 2.46 o2 2.91 o3 2.85
o4 2.84 o5 2.91  rem: 0
size:   786432/  196608  runs:       16  time: gmp 2.92 o2 2.76 o3 2.6
o4 2.59 o5 2.65  rem: 0
size:   786432/  294912  runs:       16  time: gmp 3.03 o2 2.55 o3 2.33
o4 2.39 o5 2.45  rem: 0
size:   786432/  393216  runs:       32  time: gmp 5.02 o2 4.23 o3 3.78
o4 4.02 o5 4.89  rem: 0
size:   786432/  491520  runs:       32  time: gmp 4.41 o2 3.07 o3 2.66
o4 3.28 o5 3.28  rem: 0
size:   786432/  589824  runs:       64  time: gmp 5.8 o2 3.78 o3 3.7 o4
3.7 o5 3.91  rem: 0
size:   786432/  688128  runs:      128  time: gmp 7.35 o2 3.27 o3 2.95
o4 3.08 o5 3.14  rem: 0
size:  1048576/  131072  runs:       16  time: gmp 3.84 o2 3.85 o3 3.75
o4 3.94 o5 4.13  rem: 0
size:  1048576/  262144  runs:       16  time: gmp 4.39 o2 3.96 o3 3.88
o4 3.87 o5 3.92  rem: 0
size:  1048576/  393216  runs:       16  time: gmp 4.28 o2 3.65 o3 3.33
o4 3.47 o5 3.57  rem: 0
size:  1048576/  524288  runs:       16  time: gmp 3.72 o2 2.9 o3 2.63
o4 2.68 o5 2.87  rem: 0
size:  1048576/  655360  runs:       32  time: gmp 6.15 o2 4.27 o3 3.77
o4 4.04 o5 4.94  rem: 0
size:  1048576/  786432  runs:       32  time: gmp 4.41 o2 2.58 o3 2.69
o4 2.75 o5 2.79  rem: 0
size:  1048576/  917504  runs:       64  time: gmp 5.76 o2 2.44 o3 2.13
o4 2.22 o5 2.31  rem: 0
size:  1572864/  196608  runs:        8  time: gmp 3.4 o2 3.32 o3 3.18
o4 3.37 o5 3.39  rem: 0
size:  1572864/  393216  runs:        8  time: gmp 3.77 o2 3.12 o3 2.9
o4 3.04 o5 3.06  rem: 0
size:  1572864/  589824  runs:        8  time: gmp 3.77 o2 2.93 o3 2.61
o4 2.85 o5 2.91  rem: 0
size:  1572864/  786432  runs:        8  time: gmp 3.25 o2 2.33 o3 2.2
o4 2.31 o5 2.44  rem: 0
size:  1572864/  983040  runs:       16  time: gmp 5.48 o2 3.32 o3 3.1
o4 3.31 o5 3.35  rem: 0
size:  1572864/ 1179648  runs:       32  time: gmp 7.06 o2 4.28 o3 3.8
o4 4.05 o5 4.93  rem: 0
size:  1572864/ 1376256  runs:       64  time: gmp 9.17 o2 3.86 o3 3.78
o4 3.77 o5 3.97  rem: 0
size:  2097152/  262144  runs:        4  time: gmp 2.57 o2 2.2 o3 2.14
o4 2.18 o5 2.35  rem: 0
size:  2097152/  524288  runs:        4  time: gmp 2.79 o2 2.31 o3 2.13
o4 2.18 o5 2.32  rem: 0
size:  2097152/  786432  runs:        8  time: gmp 5.5 o2 4.14 o3 3.64
o4 4.07 o5 4.15  rem: 0
size:  2097152/ 1048576  runs:        8  time: gmp 4.6 o2 3.26 o3 2.92
o4 3.21 o5 3.38  rem: 0
size:  2097152/ 1310720  runs:        8  time: gmp 3.92 o2 2.34 o3 2.21
o4 2.31 o5 2.45  rem: 0
size:  2097152/ 1572864  runs:       16  time: gmp 5.29 o2 2.93 o3 2.66
o4 2.7 o5 2.87  rem: 0
size:  2097152/ 1835008  runs:       32  time: gmp 6.46 o2 2.63 o3 2.72
o4 2.79 o5 2.83  rem: 0
size:  3145728/  393216  runs:        4  time: gmp 4.4 o2 3.73 o3 3.65
o4 3.68 o5 3.83  rem: 0
size:  3145728/  786432  runs:        4  time: gmp 4.84 o2 3.54 o3 3.31
o4 3.35 o5 3.5  rem: 0
size:  3145728/ 1179648  runs:        4  time: gmp 4.64 o2 3.3 o3 2.94
o4 3.11 o5 3.34  rem: 0
size:  3145728/ 1572864  runs:        4  time: gmp 4.03 o2 2.68 o3 2.46
o4 2.63 o5 2.86  rem: 0
size:  3145728/ 1966080  runs:        8  time: gmp 6.58 o2 3.75 o3 3.34
o4 3.62 o5 3.74  rem: 0
size:  3145728/ 2359296  runs:        8  time: gmp 4.48 o2 2.36 o3 2.23
o4 2.31 o5 2.48  rem: 0
size:  3145728/ 2752512  runs:       32  time: gmp 11.17 o2 4.33 o3 3.85
o4 4.08 o5 4.98  rem: 0
size:  4194304/  524288  runs:        2  time: gmp 3.25 o2 2.53 o3 2.44
o4 2.54 o5 2.59  rem: 0
size:  4194304/ 1048576  runs:        2  time: gmp 3.46 o2 2.54 o3 2.37
o4 2.44 o5 2.47  rem: 0
size:  4194304/ 1572864  runs:        2  time: gmp 3.37 o2 2.44 o3 2.13
o4 2.32 o5 2.36  rem: 0
size:  4194304/ 2097152  runs:        4  time: gmp 5.64 o2 3.7 o3 3.38
o4 3.51 o5 3.66  rem: 0
size:  4194304/ 2621440  runs:        4  time: gmp 4.78 o2 2.69 o3 2.46
o4 2.64 o5 2.86  rem: 0
size:  4194304/ 3145728  runs:        8  time: gmp 6.46 o2 3.3 o3 2.94
o4 3.23 o5 3.41  rem: 0
size:  4194304/ 3670016  runs:       16  time: gmp 7.79 o2 2.95 o3 2.71
o4 2.74 o5 2.91  rem: 0
size:  6291456/  786432  runs:        1  time: gmp 2.85 o2 2.07 o3 2.03
o4 2.06 o5 2.14  rem: 0
size:  6291456/ 1572864  runs:        2  time: gmp 6.2 o2 4.12 o3 3.89
o4 3.96 o5 4.07  rem: 0
size:  6291456/ 2359296  runs:        2  time: gmp 5.67 o2 3.86 o3 3.41
o4 3.63 o5 3.84  rem: 0
size:  6291456/ 3145728  runs:        2  time: gmp 4.94 o2 3.02 o3 2.7
o4 2.95 o5 3.09  rem: 0
size:  6291456/ 3932160  runs:        4  time: gmp 7.9 o2 4.24 o3 3.88
o4 4.05 o5 4.32  rem: 0
size:  6291456/ 4718592  runs:        4  time: gmp 5.4 o2 2.73 o3 2.47
o4 2.65 o5 2.94  rem: 0
size:  6291456/ 5505024  runs:        8  time: gmp 6.93 o2 2.44 o3 2.29
o4 2.39 o5 2.54  rem: 0
size:  8388608/ 1048576  runs:        1  time: gmp 4.13 o2 2.99 o3 2.86
o4 2.95 o5 2.96  rem: 0
size:  8388608/ 2097152  runs:        1  time: gmp 4.34 o2 2.95 o3 2.71
o4 2.77 o5 2.76  rem: 0
size:  8388608/ 3145728  runs:        1  time: gmp 4.21 o2 2.76 o3 2.43
o4 2.67 o5 2.72  rem: 0
size:  8388608/ 4194304  runs:        2  time: gmp 7.01 o2 4.35 o3 3.98
o4 4.23 o5 4.11  rem: 0
size:  8388608/ 5242880  runs:        2  time: gmp 5.97 o2 3.1 o3 2.76
o4 3.04 o5 3.19  rem: 0
size:  8388608/ 6291456  runs:        4  time: gmp 7.82 o2 3.84 o3 3.51
o4 3.62 o5 3.76  rem: 0
size:  8388608/ 7340032  runs:        8  time: gmp 9.48 o2 3.4 o3 3.05
o4 3.34 o5 3.52  rem: 0
size: 12582912/ 1572864  runs:        1  time: gmp 7.22 o2 4.96 o3 4.74
o4 4.85 o5 4.98  rem: 0
size: 12582912/ 3145728  runs:        1  time: gmp 7.62 o2 4.82 o3 4.42
o4 4.51 o5 4.58  rem: 0
size: 12582912/ 4718592  runs:        1  time: gmp 7.06 o2 4.4 o3 4 o4
4.27 o5 4.51  rem: 0
size: 12582912/ 6291456  runs:        1  time: gmp 6.08 o2 3.5 o3 3.14
o4 3.39 o5 3.4  rem: 0
size: 12582912/ 7864320  runs:        1  time: gmp 4.9 o2 2.54 o3 2.28
o4 2.39 o5 2.55  rem: 0
size: 12582912/ 9437184  runs:        2  time: gmp 6.77 o2 3.11 o3 2.82
o4 3.03 o5 3.19  rem: 0
size: 12582912/11010048  runs:        4  time: gmp 8.09 o2 2.84 o3 2.56
o4 2.75 o5 2.98  rem: 0
size: 16777216/ 2097152  runs:        1  time: gmp 9.94 o2 6.33 o3 6 o4
6.11 o5 6.31  rem: 0
size: 16777216/ 4194304  runs:        1  time: gmp 10.17 o2 6.27 o3 5.81
o4 5.96 o5 6.05  rem: 0
size: 16777216/ 6291456  runs:        1  time: gmp 9.79 o2 6.18 o3 5.42
o4 5.9 o5 6.05  rem: 0
size: 16777216/ 8388608  runs:        1  time: gmp 8.19 o2 4.78 o3 4.34
o4 4.62 o5 4.82  rem: 0
size: 16777216/10485760  runs:        1  time: gmp 6.86 o2 3.42 o3 3.07
o4 3.31 o5 3.32  rem: 0
size: 16777216/12582912  runs:        2  time: gmp 8.95 o2 4.27 o3 3.85
o4 4.11 o5 3.99  rem: 0
size: 16777216/14680064  runs:        4  time: gmp 10.97 o2 3.78 o3 3.44
o4 3.56 o5 3.71  rem: 0
size: 25165824/ 3145728  runs:        1  time: gmp 17.21 o2 9.99 o3 9.63
o4 9.81 o5 10.08  rem: 0
size: 25165824/ 6291456  runs:        1  time: gmp 17.81 o2 10.11 o3
9.14 o4 9.32 o5 9.43  rem: 0
size: 25165824/ 9437184  runs:        1  time: gmp 16.32 o2 9.41 o3 8.48
o4 8.98 o5 9.42  rem: 0
size: 25165824/12582912  runs:        1  time: gmp 14.08 o2 7.56 o3 6.83
o4 7.23 o5 7.35  rem: 0
size: 25165824/15728640  runs:        1  time: gmp 11.42 o2 5.63 o3 4.93
o4 5.37 o5 5.66  rem: 0
size: 25165824/18874368  runs:        1  time: gmp 7.65 o2 3.43 o3 3.08
o4 3.3 o5 3.31  rem: 0
size: 25165824/22020096  runs:        2  time: gmp 9.27 o2 3.05 o3 2.72
o4 2.99 o5 3.16  rem: 0
size: 33554432/ 4194304  runs:        1  time: gmp 24.23 o2 13.7 o3
12.72 o4 12.84 o5 13.21  rem: 0
size: 33554432/ 8388608  runs:        1  time: gmp 24.88 o2 13.71 o3
12.13 o4 12.33 o5 12.53  rem: 0
size: 33554432/12582912  runs:        1  time: gmp 23.38 o2 13.22 o3
11.9 o4 12.41 o5 12.65  rem: 0
size: 33554432/16777216  runs:        1  time: gmp 19.81 o2 10.24 o3
9.45 o4 10.4 o5 9.79  rem: 0
size: 33554432/20971520  runs:        1  time: gmp 16.06 o2 7.51 o3 6.7
o4 7.33 o5 7.52  rem: 0
size: 33554432/25165824  runs:        1  time: gmp 10.52 o2 4.85 o3 4.38
o4 4.64 o5 4.7  rem: 0
size: 33554432/29360128  runs:        2  time: gmp 12.21 o2 4.32 o3 3.89
o4 4.17 o5 4.08  rem: 0
size: 50331648/ 6291456  runs:        1  time: gmp 41.1 o2 20.95 o3
20.04 o4 20.36 o5 20.82  rem: 0
size: 50331648/12582912  runs:        1  time: gmp 41.91 o2 20.9 o3
18.67 o4 19.59 o5 19.48  rem: 0
size: 50331648/18874368  runs:        1  time: gmp 38.47 o2 19.31 o3
17.36 o4 18.56 o5 18.69  rem: 0
size: 50331648/25165824  runs:        1  time: gmp 32.42 o2 15.42 o3
13.87 o4 15.03 o5 15  rem: 0
size: 50331648/31457280  runs:        1  time: gmp 26.03 o2 11.74 o3
10.34 o4 11.04 o5 11.61  rem: 0
size: 50331648/37748736  runs:        1  time: gmp 17.42 o2 7.48 o3 6.72
o4 7.29 o5 7.33  rem: 0
size: 50331648/44040192  runs:        1  time: gmp 10.08 o2 3.46 o3 3.12
o4 3.35 o5 3.37  rem: 0
size: 67108864/ 8388608  runs:        1  time: gmp 57.06 o2 27.87 o3
26.25 o4 27.06 o5 27.49  rem: 0
size: 67108864/16777216  runs:        1  time: gmp 58.16 o2 28.11 o3
25.99 o4 26.56 o5 26.78  rem: 0
size: 67108864/25165824  runs:        1  time: gmp 54.07 o2 26.42 o3
22.97 o4 24.96 o5 25.43  rem: 0
size: 67108864/33554432  runs:        1  time: gmp 45.1 o2 21.05 o3
19.18 o4 20.78 o5 21.21  rem: 0
size: 67108864/41943040  runs:        1  time: gmp 36.59 o2 15.4 o3
13.86 o4 15 o5 14.91  rem: 0
size: 67108864/50331648  runs:        1  time: gmp 23.91 o2 10.29 o3
9.44 o4 10.19 o5 10.06  rem: 0
size: 67108864/58720256  runs:        1  time: gmp 13.63 o2 4.84 o3 4.39
o4 4.69 o5 4.87  rem: 0
size: 100663296/12582912  runs:        1  time: gmp 97.2 o2 43.47 o3
41.23 o4 42.51 o5 43.61  rem: 0
size: 100663296/25165824  runs:        1  time: gmp 97.52 o2 43.27 o3
39.74 o4 41.2 o5 41.58  rem: 0
size: 100663296/37748736  runs:        1  time: gmp 89.51 o2 40.36 o3
35.82 o4 38.29 o5 38.59  rem: 0
size: 100663296/50331648  runs:        1  time: gmp 74.75 o2 32.64 o3
29.62 o4 31.56 o5 32.71  rem: 0
size: 100663296/62914560  runs:        1  time: gmp 59.61 o2 24.57 o3
21.53 o4 23.26 o5 23.96  rem: 0
size: 100663296/75497472  runs:        1  time: gmp 39.64 o2 16.18 o3
13.75 o4 15.15 o5 15.3  rem: 0
size: 100663296/88080384  runs:        1  time: gmp 22.66 o2 7.68 o3
6.38 o4 7.2 o5 7.35  rem: 0
size: 134217728/16777216  runs:        1  time: gmp 135.39 o2 59.93 o3
56.67 o4 57.55 o5 61  rem: 0
size: 134217728/33554432  runs:        1  time: gmp 135.4 o2 57.48 o3
54.06 o4 55.16 o5 56.15  rem: 0
size: 134217728/50331648  runs:        1  time: gmp 123.48 o2 53.93 o3
46.82 o4 51.8 o5 52.01  rem: 0
size: 134217728/67108864  runs:        1  time: gmp 103.35 o2 44.81 o3
40.33 o4 43.29 o5 44.78  rem: 0
size: 134217728/83886080  runs:        1  time: gmp 81.66 o2 32.13 o3
29.32 o4 31.09 o5 32.37  rem: 0
size: 134217728/100663296  runs:        1  time: gmp 55.02 o2 21.24 o3
19.65 o4 20.87 o5 21.33  rem: 0
size: 134217728/117440512  runs:        1  time: gmp 30.47 o2 10.39 o3
9.51 o4 10.13 o5 10.16  rem: 0
size: 201326592/25165824  runs:        1  time: gmp 226.51 o2 92.58 o3
87.17 o4 91.59 o5 93.15  rem: 0
size: 201326592/50331648  runs:        1  time: gmp 221.55 o2 88.46 o3
81.61 o4 83.94 o5 85.27  rem: 0
size: 201326592/75497472  runs:        1  time: gmp 200.02 o2 82.66 o3
72.53 o4 78.71 o5 80.74  rem: 0
size: 201326592/100663296  runs:        1  time: gmp 168.77 o2 67.09 o3
60.52 o4 65.02 o5 68.26  rem: 0
size: 201326592/125829120  runs:        1  time: gmp 132.41 o2 50.96 o3
44.7 o4 47.74 o5 50.18  rem: 0
size: 201326592/150994944  runs:        1  time: gmp 88.64 o2 32.55 o3
29.7 o4 31.64 o5 32.53  rem: 0
size: 201326592/176160768  runs:        1  time: gmp 50.49 o2 15.76 o3
14.24 o4 15.48 o5 15.38  rem: 0

```