mpz_sizeinbase
Minh Nguyen
md6nguyen@yahoo.com
Fri, 8 Nov 2002 11:37:58 -0800 (PST)
--0-1416131209-1036784278=:65788
Content-Type: text/plain; charset=us-ascii
Torbjorn Granlund <tege@swox.com> wrote:
> Now, suppose the return value of mpz_sizeinbase(op, base) is
> numdigs and I want to know the *exact* number of digits. The most
> straightforward way is to compare op with base^(numdigs-1) and
> then reduce numdigs by 1 if op is less than base^(numdigs-1). Is
> there a better way?
Not that I know of.
One could compute t=approx(base^n/2^m), where n is initially
chosen to a suitable value less than returned mpz_sizeinbase(op,
base). During the computation of base^n, low limbs should be
truncated gradually,
Then, we compute op/t and op/(t+1) and convert these small number
to to base. If they are the same number of digits, we're done.
Else, decrease m and try again...
On average, this should be very fast.
If it is fast, is there any reason not to put it in mpz_sizeinbase?
Minh
---------------------------------
Do You Yahoo!?
Yahoo! Autos - Get free new car price quotes
--0-1416131209-1036784278=:65788
Content-Type: text/html; charset=us-ascii
<P>
<P> <B><I>Torbjorn Granlund <tege@swox.com></I></B> wrote:
<BLOCKQUOTE style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #1010ff 2px solid">
<P>> Now, suppose the return value of mpz_sizeinbase(op, base) is<BR>> numdigs and I want to know the *exact* number of digits. The most<BR>> straightforward way is to compare op with base^(numdigs-1) and<BR>> then reduce numdigs by 1 if op is less than base^(numdigs-1). Is<BR>> there a better way?<BR><BR>Not that I know of.<BR><BR>One could compute t=approx(base^n/2^m), where n is initially<BR>chosen to a suitable value less than returned mpz_sizeinbase(op,<BR>base). During the computation of base^n, low limbs should be<BR>truncated gradually,<BR><BR>Then, we compute op/t and op/(t+1) and convert these small number<BR>to to base. If they are the same number of digits, we're done.<BR>Else, decrease m and try again...<BR><BR>On average, this should be very fast.<BR></P>
<P>If it is fast, is there any reason not to put it in mpz_sizeinbase?</P>
<P>Minh</P></BLOCKQUOTE><p><br><hr size=1><b>Do You Yahoo!?</b><br>
<a href="http://autos.yahoo.com/">Yahoo! Autos</a> - Get free new car price quotes
--0-1416131209-1036784278=:65788--