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
* License as published by the Free Software Foundation; either
* 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;
next_prec += limb_mask - ((next_prec - 1) & limb_mask);
/* 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);
mpz_add(R, R, D);
}
/* 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_add_ui(Q, Q, 1);
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
More information about the gmp-discuss
mailing list