mpz_sizeinbase

[Minh Nguyen]

--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>&nbsp;
<P>&nbsp;<B><I>Torbjorn Granlund &lt;tege@swox.com&gt;</I></B> wrote:
<BLOCKQUOTE style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #1010ff 2px solid">
<P>&gt; Now, suppose the return value of mpz_sizeinbase(op, base) is<BR>&gt; numdigs and I want to know the *exact* number of digits. The most<BR>&gt; straightforward way is to compare op with base^(numdigs-1) and<BR>&gt; then reduce numdigs by 1 if op is less than base^(numdigs-1). Is<BR>&gt; 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--