Division by 2
DTAshley@aol.com
DTAshley@aol.com
Fri, 2 May 2003 17:11:48 EDT
--part1_18f.198a7df6.2be43914_boundary
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Hi Minh,
Did you notice the "2exp" family of division functions, such as
mpz_cdiv_q_2exp?
You posed the question "Is mpz_tdiv_q_ui smart enough to treat 2 as a special
case?".
Well, let's assume that mpz_tdiv_q_ui() used in some application is _never_
called with 2 or another power of 2 as the divisor. Then, testing for 2 or
any other power of 2 would not be very "smart"! In fact, it would be stupid!
So, "smart" is kind of relative.
For a math library whose design goal is brute speed, you need to push those
decisions up to the caller in a way where the caller can give the library
some information about what can and cannot happen in a given application.
The "2exp" family of division calls are one way to push this up to the
caller.
Also, let me point out that there are typically 32 bits in an unsigned
integer, so this is 32 powers of 2 that can occur in the divisor. But, there
are 4.2 billion other possible divisors that are NOT powers of 2. So, if
divisors are normally distributed, this means that the test for a power of 2
has to be on the order of less than one 134-millionth of the cost of the
division in order to pay off. In most applications, this won't be true.
This is also a function of the dividend size.
So, checking for powers of 2 may not be "smart" after all.
My feeling is that if there is something special about the distribution of
divisors in a given application, a user of the GMP might be better to "wrap"
the division function and test for the powers of 2 and perhaps call a 2exp
function.
There are other ways to do it besides wrapping. The "wrapping" is just a
mechanical point. The important point is that if the divisors in a given
application are not normally distributed, the caller has to have a way to use
the library effectively (i.e. to communicate that information to the library
or otherwise exploit it). The mechanism for exploitation is not particulary
important.
The GMP has ordinary division calls and 2exp division calls. This gives the
caller the ability to exploit unusual distributions of divisors. This is
all that is required.
Embarrassingly, I have not checked the source code.
But the important point is that checking for powers of 2 may not be smart!
If divisors are normally distributed and dividends are not too large, it may
actually be a performance disadvantage.
Best regards, Dave.
In a message dated 5/2/2003 4:52:32 PM Eastern Daylight Time,
md6nguyen@yahoo.com writes:
> Hi, if I want to divide a number n by 2, is it reasonable to call
>
> mpz_tdiv_q_ui( n, n, 2 );
>
> Is mpz_tdiv_q_ui smart enough to treat 2 as a special case?
>
> Thanks,
> Minh
>
--part1_18f.198a7df6.2be43914_boundary
Content-Type: text/html; charset="US-ASCII"
Content-Transfer-Encoding: quoted-printable
<HTML><FONT FACE=3Darial,helvetica><FONT SIZE=3D2 FAMILY=3D"SANSSERIF" FACE=
=3D"Arial" LANG=3D"0">Hi Minh,<BR>
<BR>
Did you notice the "2exp" family of division functions, such as mpz_cdiv_q_2=
exp?<BR>
<BR>
You posed the question "Is mpz_tdiv_q_ui smart enough to treat 2 as a specia=
l case?".<BR>
<BR>
Well, let's assume that mpz_tdiv_q_ui() used in some application is _never_=20=
called with 2 or another power of 2 as the divisor. Then, testing for=20=
2 or any other power of 2 would not be very "smart"! In fact, it would=
be stupid! So, "smart" is kind of relative.<BR>
<BR>
For a math library whose design goal is brute speed, you need to push those=20=
decisions up to the caller in a way where the caller can give the library so=
me information about what can and cannot happen in a given application. =
; The "2exp" family of division calls are one way to push this up to the cal=
ler.<BR>
<BR>
Also, let me point out that there are typically 32 bits in an unsigned integ=
er, so this is 32 powers of 2 that can occur in the divisor. But, ther=
e are 4.2 billion other possible divisors that are NOT powers of 2. So=
, if divisors are normally distributed, this means that the test for a power=
of 2 has to be on the order of less than one 134-millionth of the cost of t=
he division in order to pay off. In most applications, this won't be t=
rue. This is also a function of the dividend size.<BR>
<BR>
So, checking for powers of 2 may not be "smart" after all.<BR>
<BR>
My feeling is that if there is something special about the distribution of d=
ivisors in a given application, a user of the GMP might be better to "wrap"=20=
the division function and test for the powers of 2 and perhaps call a 2exp f=
unction.<BR>
<BR>
There are other ways to do it besides wrapping. The "wrapping" is just=
a mechanical point. The important point is that if the divisors in a=20=
given application are not normally distributed, the caller has to have a way=
to use the library effectively (i.e. to communicate that information to the=
library or otherwise exploit it). The mechanism for exploitation is n=
ot particulary important.<BR>
<BR>
The GMP has ordinary division calls and 2exp division calls. This give=
s the caller the ability to exploit unusual distributions of divisors.=
This is all that is required.<BR>
<BR>
Embarrassingly, I have not checked the source code.<BR>
<BR>
But the important point is that checking for powers of 2 may not be smart!&n=
bsp; If divisors are normally distributed and dividends are not too large, i=
t may actually be a performance disadvantage.<BR>
<BR>
Best regards, Dave.<BR>
<BR>
In a message dated 5/2/2003 4:52:32 PM Eastern Daylight Time, md6nguyen@yaho=
o.com writes:<BR>
<BR>
<BLOCKQUOTE TYPE=3DCITE style=3D"BORDER-LEFT: #0000ff 2px solid; MARGIN-LEFT=
: 5px; MARGIN-RIGHT: 0px; PADDING-LEFT: 5px">Hi, if I want to divide a numbe=
r n by 2, is it reasonable to call<BR>
<BR>
mpz_tdiv_q_ui( n, n, 2 );<BR>
<BR>
Is mpz_tdiv_q_ui smart enough to treat 2 as a special case?<BR>
<BR>
Thanks,<BR>
Minh<BR>
</BLOCKQUOTE><BR>
<BR>
</FONT></HTML>
--part1_18f.198a7df6.2be43914_boundary--