On Sun, 11 Feb 2007 00:22:23 -0800, Carl Witty <[EMAIL PROTECTED]> wrote:
> That's one of the uses of interval arithmetic. My own use for
> interval arithmetic is dealing with algebraic numbers. It is possible
> to do exact computations with algebraic numbers, but if the question
> you are asking is not too difficult then it is often far more
> efficient to compute with interval approximations of the numbers in
> question. Here "difficult" means "requires computing the sign of an
> algebraic number which is very close to 0"; so checking that
> (sqrt(2)+sqrt(3))^5 >= 300 is easy, since the true value of the left
> hand side is about 308.302, but checking that phi^150 <
> 22291846172619859445381409012498 is hard, since the two sides differ
> by less than 10^{-31}. (You need intervals with at least 217-bit
> mantissas to prove the latter fact; for proving the former, 8-bit
> mantissas suffice.)
Here's some code doing this sort of thing:
sage: R = RealIntervalField(200)
sage: exp(R(pi)*sqrt(R(163)))
[262537412640768743.99999999999925007259719818568887935385633377 ...
262537412640768743.99999999999925007259719818568887935385635477]
So exp(pi*sqrt(163)) is definitely not an integer, since the upper endpoint of
the interval is less than an integer. It's not just roundoff error.
sage: phi = R(golden_ratio)
sage: phi^150
[22291846172619859445381409012497.999999999999999999999999997904 ...
22291846172619859445381409012498.000000000000000000000000003812]
Not enough precision so say anything definite, so try again:
sage: phi = RealIntervalField(300)(golden_ratio)
sage: phi^150
[22291846172619859445381409012497.999999999999999999999999999999955140548151267161675399951322
...
22291846172619859445381409012497.999999999999999999999999999999955140548151267161675399954669]
Good.
---
The way I've personally used interval arithmetic so far is for compution with
the Birch and Swinnerton-Dyer conjecture. If you compute each of the quantities
in the Gross-Zagier formula for the index [E(K): Zy_K]^2 of the Heegner point,
you compute an interval that this index squared definitely lies in. It is
difficult
to compute some of the quantities in this formula to high precision (e.g., the
L-function),
so you compute the low precision but with proven error bounds. Then you plug in
everything and if the interval you get contains exactly one square integer, you
know for certain it has to be [E(K): Zy_K]^2. This can save a lot of time
computationally. Here's a good example:
sage: E = EllipticCurve([1, 1, 0, -1154, -15345])
sage: E.heegner_index(-20)
[8.9999389 ... 9.0000458]
It could have been faster to do this computation, instead:
sage: E = EllipticCurve([1, 1, 0, -1154, -15345])
sage: E.heegner_index(-20, prec=1)
[8.5029907 ... 9.4971772]
If I had just got "8.5029907", say, which I might have got if I
didn't use intervals, I wouldn't have much trust in it -- I'd have
no clue if my precision was so bad that the true answer might really
be 4 or even 25! But with intervals I know the true index squared
must be 9 in this case. This sort of thing was crucially important
in being able to efficiently compute Heegner indexes (and hence apply
work of Kolyvagin toward BSD) in some cases.
William
--~--~---------~--~----~------------~-------~--~----~
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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
