-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
OK, I'm quite happy with this (thanks David for suggesting it
and Carl for telling me how to do it!)
I've put this in and played around with it. It is definitely
*much* faster for the huge examples that I tried, and it's
also fast enough on smaller numbers.
I'll post a new patch for #1014 shortly. David, is it ok if I
replace the current exact_log() function with
return self.ndigits(m) - 1
(after checking self is positive, etc.)?
Alex
Carl Witty wrote:
>> BTW I think the following might be relevant:
>>
>> sage: I = RealInterval(10.0, 10.0)
>> sage: I
>> [10.000000000000000 .. 10.000000000000000]
>> sage: I**10000
>> [9.9999999999993908e9999 .. 1.0000000000000429e10000]
>>
>> I don't know exactly what this means, since I don't understand enough
>> about the semantics of the constructor, but surely someone like Carl
>> Witty would know.
>
> The above computation proves (barring bugs) that 10^10000 is between
> 9.9999999999993908e9999 and 1.0000000000000429e10000 (or, more
> precisely, between 5471845328006193*2^33167 and
> 5471845328006761*2^33167, inclusive).
>
> sage: ZZ((RIF(10)^10000).lower().exact_rational()).val_unit(2)
> (33167, 5471845328006193)
> sage: ZZ((RIF(10)^10000).upper().exact_rational()).val_unit(2)
> (33167, 5471845328006761)
>
> This does seem likely to lead to a faster version of ndigits (at
> least, faster for sufficiently large numbers).
>
> Before the source line above:
> compare = Integer(base)**(guess - one)
> you could first try:
> approx_compare = RIF(base)**(guess - one)
> Then check (self < approx_compare) and (self > approx_compare). If
> either of these returns True, then that tells you the answer. If both
> return False, then you'll either need to try again with higher
> precision, or go straight to the exact
> compare = Integer(base)**(guess - one)
> (I would recommend going straight to the exact computation. For
> randomly distributed integers, the chance of the above interval-based
> comparison failing are absurdly low; so if it fails, probably the
> original integer was not random, and quite possibly it is an exact
> power of base or very close to one.)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHnmmodZTaNFFPILgRAmqiAKCGIlQuZ3TaFQUkZ+JQd/UL8YVAnQCfeMCA
8KEWOkKL/EHVCjQxAAFhGpI=
=MS91
-----END PGP SIGNATURE-----
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
