Ask Your Question
1

ContinuedFractions fail on large integers?

asked 2017-07-18 09:31:37 -0500

cappallo gravatar image

updated 2017-07-18 17:16:02 -0500

tmonteil gravatar image

I've been doing some work with continued fractions, and when I get to a large enough number, I start hitting an error. For example, with the ContinuedFraction from [(18806263158919164762262694978536817267490601162205305175017345804331141023863425152608922362862834892943764814900901973487239748665085369033027389281788183,), [1, 1, 1, 1, 37612526317838329524525389957073634534981202324410610350034691608662282047726850305217844725725669785887529629801803946974479497330170738066054778563576366]]), I get the error below.

Specifically, I get it after I've created a ContinuedFraction with the arguments above, and then call .value() on it. I've tried to make sure all of those are sage Integer types, but it doesn't seem to help, and it looks like internally the CF code is overflowing somewhere. Is there any way around this, or is this a limitation I'll have to live with?

Thanks for any help!

    Traceback (most recent call last):
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/multiprocessing/process.py", line 258, in _bootstrap
    self.run()
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/multiprocessing/process.py", line 114, in run
    self._target(*self._args, **self._kwargs)
  File "/home/tc/code/cfp/pi/piX/ones.py", line 16, in leeloo
    v = ocf.value()
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/site-packages/sage/rings/continued_fraction.py", line 1423, in value
    Q = QuadraticField(DD, 'sqrt%d' % DD)
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 922, in QuadraticField
    return NumberField(f, name, check=False, embedding=embedding, latex_name=latex_name, **args)
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 524, in NumberField
    return NumberField_version2(polynomial=polynomial, name=name, check=check, embedding=embedding, latex_name=latex_name, assume_disc_small=assume_disc_small, maximize_at_primes=maximize_at_primes, structure=structure)
  File "sage/structure/factory.pyx", line 362, in sage.structure.factory.UniqueFactory.__call__ (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/structure/factory.c:1856)
  File "/home/tc/Downloads/sagetemp/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 612, in create_key_and_extra_args
    x = number_field_morphisms.root_from_approx(polynomial, embedding)
  File "sage/rings/number_field/number_field_morphisms.pyx", line 490, in sage.rings.number_field.number_field_morphisms.root_from_approx (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/number_field/number_field_morphisms.c:7640)
  File "sage/rings/real_lazy.pyx", line 1584, in sage.rings.real_lazy.LazyAlgebraic.__init__ (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/real_lazy.c:17914)
  File "sage/rings/polynomial/polynomial_element.pyx", line 7247, in sage.rings.polynomial.polynomial_element.Polynomial.roots (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:68115)
  File "sage/rings/polynomial/polynomial_element.pyx", line 7143, in sage.rings.polynomial.polynomial_element.Polynomial.roots (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:64632)
  File "sage/rings/polynomial/polynomial_element.pyx", line 5786, in sage.rings.polynomial.polynomial_element.Polynomial._pari_ (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:55229)
  File "sage/rings/polynomial/polynomial_element.pyx", line 5839, in sage.rings.polynomial.polynomial_element.Polynomial._pari_with_name (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:55757)
  File "sage/rings/real_mpfr.pyx", line 3103, in sage.rings.real_mpfr.RealNumber._pari_ (/home/tc/Downloads/sagetemp/SageMath/src/build/cythonized/sage/rings/real_mpfr.c:22771)
ValueError: Cannot convert NaN or infinity to Pari float
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2017-07-18 14:01:07 -0500

updated 2017-07-18 14:07:40 -0500

Thanks for your report. The problem comes from the fact that you can not create quadratic field with very large D

sage: QuadraticField(4**1000+1)
Traceback (most recent call last):
...
ValueError: Cannot convert NaN or infinity to Pari float

I opened the ticket #23459 to track the issue.

EDIT: in the mean time you can use the following modification of value that I adapted from the .value() method of the continued fraction

def periodic_cf_value(cf):
    from sage.rings.continued_fraction import last_two_convergents

    if cf._x1 and cf._x1[0] < 0:
        return -(-cf).value()

    if cf._x2[0] is Infinity:
        return cf._rational_()

    # determine the equation for the purely periodic cont. frac. determined
    # by self._x2
    p0,q0,p1,q1 = last_two_convergents(cf._x2)

    # now x is one of the root of the equation
    #   q1 x^2 + (q0 - p1) x - p0 = 0
    D = (q0-p1)**2 + 4*q1*p0
    x = ((p1 - q0) + sqrt(D)) / (2*q1)

    # we add the preperiod
    p0,q0,p1,q1 = last_two_convergents(cf._x1)
    return (p1*x + p0) / (q1*x + q0)

With the above function you can do with your list l

sage: x = continued_fraction(l)
sage: v = periodic_cf_value(x)

However, the number obtained is a symbolic number not that easy to work with

sage: parent(v)
Symbolic Ring
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-07-18 09:31:37 -0500

Seen: 39 times

Last updated: Jul 18