Multidimensional Continued Fraction Algorithms¶

Multidimensional Continued Fraction Algorithms (Python code)

EXAMPLES:

sage: from slabbe.mult_cont_frac import Brun
sage: algo = Brun()

Drawing the natural extension:

sage: fig = algo.natural_extension_plot(3000, norm_xyz=1, axis_off=True)
sage: fig
<Figure size 1200x200 with 4 Axes>
sage: fig.savefig('a.png')  # not tested

Drawing the invariant measure:

sage: fig = algo.invariant_measure_wireframe_plot(10^6, 50)
sage: fig
<Figure size 640x480 with 1 Axes>
sage: fig.savefig('a.png')  # not tested

Word with given frequencies:

sage: algo.s_adic_word((1,e,pi))
word: 1232323123233231232332312323123232312323...

Construction of the same s-adic word from the substitutions and the coding iterator:

sage: from itertools import repeat
sage: D = algo.substitutions()
sage: it = algo.coding_iterator((1,e,pi))
sage: words.s_adic(it, repeat(1), D)
word: 1232323123233231232332312323123232312323...

AUTHORS:

Sébastien Labbé, Externalize Python only functions (pip install takes now 33s instead of 51s), August 2016

slabbe.mult_cont_frac.ARP(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import ARP
sage: ARP()
Arnoux-Rauzy-Poincar\'e 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.ArnouxRauzy(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import ArnouxRauzy
sage: ArnouxRauzy()
ArnouxRauzy 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Brun(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Brun
sage: Brun()
Brun 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Cassaigne(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Cassaigne
sage: Cassaigne()
Cassaigne 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.FullySubtractive(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import FullySubtractive
sage: FullySubtractive()
Fully Subtractive 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.JacobiPerron()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import JacobiPerron
sage: JacobiPerron()
JacobiPerron 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.JacobiPerronAdditif()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import JacobiPerronAdditif
sage: JacobiPerronAdditif()
JacobiPerronAdditif 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.JacobiPerronAdditifv2()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import JacobiPerronAdditifv2
sage: JacobiPerronAdditifv2()
JacobiPerronAdditifv2 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Poincare(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Poincare
sage: Poincare()
Poincar\'e 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Reverse(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Reverse
sage: Reverse()
Reverse 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Selmer(dim=3)¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Selmer
sage: Selmer()
Selmer 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ARMonteil()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ARMonteil
sage: Sorted_ARMonteil()
Sorted_ARMonteil 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ARP()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ARP
sage: Sorted_ARP()
Sorted_ARP 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ARPMulti()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ARPMulti
sage: Sorted_ARPMulti()
Sorted_ARPMulti 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ARrevert()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ARrevert
sage: Sorted_ARrevert()
Sorted_ARrevert 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ARrevertMulti()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ARrevertMulti
sage: Sorted_ARrevertMulti()
Sorted_ARrevertMulti 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ArnouxRauzy()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ArnouxRauzy
sage: Sorted_ArnouxRauzy()
Sorted_ArnouxRauzy 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_ArnouxRauzyMulti()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_ArnouxRauzyMulti
sage: Sorted_ArnouxRauzyMulti()
Sorted_ArnouxRauzyMulti 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_Brun()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_Brun
sage: Sorted_Brun()
Sorted_Brun 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_BrunMulti()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_BrunMulti
sage: Sorted_BrunMulti()
Sorted_BrunMulti 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_Delaunay()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_Delaunay
sage: Sorted_Delaunay()
Sorted_Delaunay 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_FullySubtractive()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_FullySubtractive
sage: Sorted_FullySubtractive()
Sorted_FullySubtractive 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_Poincare()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_Poincare
sage: Sorted_Poincare()
Sorted_Poincare 3-dimensional continued fraction algorithm

slabbe.mult_cont_frac.Sorted_Selmer()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac import Sorted_Selmer
sage: Sorted_Selmer()
Sorted_Selmer 3-dimensional continued fraction algorithm

Multidimensional Continued Fraction Algorithms (Cython code)

See also the Python code which provides more methods.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: algo = Brun()

Orbit in the cone (with dual coordinates):

sage: algo.cone_orbit_list((10,23,15), 6)
[(((10.0, 8.0, 15.0), (1.0, 1.0, 2.0)), 132),
 (((10.0, 8.0, 5.0), (3.0, 1.0, 2.0)), 213),
 (((2.0, 8.0, 5.0), (3.0, 4.0, 2.0)), 321),
 (((2.0, 3.0, 5.0), (3.0, 4.0, 6.0)), 132),
 (((2.0, 3.0, 2.0), (3.0, 10.0, 6.0)), 123),
 (((2.0, 1.0, 2.0), (3.0, 10.0, 16.0)), 132)]

Orbit in the simplex:

sage: algo.simplex_orbit_list((10,23,15), 3)
[(0.30303030303030304,
  0.24242424242424246,
  0.45454545454545453,
  0.25,
  0.25,
  0.5,
  132),
 (0.43478260869565216,
  0.3478260869565218,
  0.21739130434782603,
  0.5,
  0.16666666666666666,
  0.3333333333333333,
  213),
 (0.13333333333333328,
  0.5333333333333334,
  0.3333333333333333,
  0.33333333333333337,
  0.4444444444444445,
  0.22222222222222224,
  321)]

BENCHMARKS:

With slabbe-0.2 or earlier, 68.6 ms on my machine. With slabbe-0.3.b1, 62.2 ms on my machine. With slabbe-0.3.b2, 28.6 ms on my machine. With slabbe-0.3.b2, 13.3 ms on priminfo in Liège:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: %time Brun().lyapunov_exponents(n_iterations=10^6)  # not tested
(0.3049429393152174, -0.1120652699014143, 1.367495867105725)

With slabbe-0.3.b1, 74ms on my machine. With slabbe-0.3.b2, 35ms on my machine. With slabbe-0.3.b2, 17ms on priminfo in Liège:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: %time ARP().lyapunov_exponents(n_iterations=10^6)  # not tested
(0.443493194984839, -0.17269097306340797, 1.3893881011394358)

With slabbe-0.2 or earlier, 3.71s at liafa, 4.58s on my machine. With slabbe-0.3.b1, 3.93s on my machine. With slabbe-0.3.b2, 1.93s on my machine. With slabbe-0.3.b2, 1.22s on priminfo in Liège:

sage: %time Brun().lyapunov_exponents(n_iterations=67000000) # not tested
(0.30456433843239084, -0.1121770192467067, 1.36831961293987303)

With slabbe-0.3.b1, 4.83 s on my machine: With slabbe-0.3.b2, 2.33 s on my machine: With slabbe-0.3.b2, 1.56 s on priminfo in Liège:

sage: %time ARP().lyapunov_exponents(n_iterations=67*10^6)   # not tested
(0.44296596371477626, -0.17222952278277034, 1.3888098339168744)

With slabbe-0.2 or earlier, 660 ms on my machine. With slabbe-0.3.b1, 640 ms on my machine (maybe this test could be made much faster without using list…). With slabbe-0.3.b2, 215 ms on priminfo in Liège:

sage: %time L = Brun().simplex_orbit_list(n_iterations=10^6)   # not tested

Question:

Comment factoriser le code sans utiliser les yield?

Comment faire un appel de fonction rapide (pour factoriser le code)

AUTHORS:

Sébastien Labbé, Invariant measures, Lyapounov exponents and natural extensions for a dozen of algorithms, October 2013.

Sébastien Labbé, Cleaning the code, Fall 2015

Sébastien Labbé, Making use of PairPoint to prepare for higher dimension, Fall 2016

class slabbe.mult_cont_frac_pyx.ARP¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: algo = ARP()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: ARP().dual_substitutions()
{1: WordMorphism: 1->123, 2->2, 3->3,
WordMorphism: 1->1, 2->231, 3->3,
WordMorphism: 1->1, 2->2, 3->312,
WordMorphism: 1->1, 2->21, 3->321,
WordMorphism: 1->1, 2->231, 3->31,
WordMorphism: 1->12, 2->2, 3->312,
WordMorphism: 1->132, 2->2, 3->32,
WordMorphism: 1->13, 2->213, 3->3,
WordMorphism: 1->123, 2->23, 3->3}

name()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: ARP().name()
"Arnoux-Rauzy-Poincar\\'e"

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: ARP().substitutions()
{1: WordMorphism: 1->1, 2->21, 3->31,
WordMorphism: 1->12, 2->2, 3->32,
WordMorphism: 1->13, 2->23, 3->3,
WordMorphism: 1->123, 2->23, 3->3,
WordMorphism: 1->132, 2->2, 3->32,
WordMorphism: 1->13, 2->213, 3->3,
WordMorphism: 1->1, 2->231, 3->31,
WordMorphism: 1->12, 2->2, 3->312,
WordMorphism: 1->1, 2->21, 3->321}

class slabbe.mult_cont_frac_pyx.ArnouxRauzy¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ArnouxRauzy
sage: algo = ArnouxRauzy()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ArnouxRauzy
sage: ArnouxRauzy().dual_substitutions()
{1: WordMorphism: 1->123, 2->2, 3->3,
 2: WordMorphism: 1->1, 2->231, 3->3,
 3: WordMorphism: 1->1, 2->2, 3->312}

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ArnouxRauzy
sage: ArnouxRauzy().substitutions()
{1: WordMorphism: 1->1, 2->21, 3->31,
 2: WordMorphism: 1->12, 2->2, 3->32,
 3: WordMorphism: 1->13, 2->23, 3->3}

class slabbe.mult_cont_frac_pyx.Brun¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: algo = Brun()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().dual_substitutions()
{123: WordMorphism: 1->1, 2->2, 3->32,
 132: WordMorphism: 1->1, 2->23, 3->3,
 213: WordMorphism: 1->1, 2->2, 3->31,
 231: WordMorphism: 1->13, 2->2, 3->3,
 312: WordMorphism: 1->1, 2->21, 3->3,
 321: WordMorphism: 1->12, 2->2, 3->3}

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().substitutions()
{123: WordMorphism: 1->1, 2->23, 3->3,
 132: WordMorphism: 1->1, 2->2, 3->32,
 213: WordMorphism: 1->13, 2->2, 3->3,
 231: WordMorphism: 1->1, 2->2, 3->31,
 312: WordMorphism: 1->12, 2->2, 3->3,
 321: WordMorphism: 1->1, 2->21, 3->3}

class slabbe.mult_cont_frac_pyx.Cassaigne¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Cassaigne
sage: algo = Cassaigne()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Cassaigne
sage: Cassaigne().dual_substitutions()
{1: WordMorphism: 1->12, 2->3, 3->2, 
 2: WordMorphism: 1->2, 2->1, 3->23}

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Cassaigne
sage: Cassaigne().substitutions()
{1: WordMorphism: 1->1, 2->13, 3->2, 
 2: WordMorphism: 1->2, 2->13, 3->3}

class slabbe.mult_cont_frac_pyx.FullySubtractive¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import FullySubtractive
sage: algo = FullySubtractive()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import FullySubtractive
sage: FullySubtractive().dual_substitutions()
{1: WordMorphism: 1->1, 2->21, 3->31,
 2: WordMorphism: 1->12, 2->2, 3->32,
 3: WordMorphism: 1->13, 2->23, 3->3}

name()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import FullySubtractive
sage: FullySubtractive().name()
'Fully Subtractive'

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import FullySubtractive
sage: FullySubtractive().substitutions()
{1: WordMorphism: 1->123, 2->2, 3->3,
 2: WordMorphism: 1->1, 2->231, 3->3,
 3: WordMorphism: 1->1, 2->2, 3->312}

class slabbe.mult_cont_frac_pyx.JacobiPerron¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.JacobiPerronAdditif¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.JacobiPerronAdditifv2¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.MCFAlgorithm¶

Bases: object

branches()¶

Returns the branches labels of the algorithm.

This method is an heuristic and should be implemented in the inherited classes.

EXAMPLES:

sage: import slabbe.mult_cont_frac_pyx as mcf
sage: mcf.Brun().branches()
{123, 132, 213, 231, 312, 321}
sage: mcf.ARP().branches()
{1, 2, 3, 123, 132, 213, 231, 312, 321}

class_name()¶

The name of the class.

Note

This might not be the same as the name of the algorithm.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Reverse, Brun, ARP
sage: Reverse().class_name()
'Reverse'
sage: Brun().class_name()
'Brun'
sage: ARP().class_name()
'ARP'

coding_iterator()¶

INPUT:

start – iterable of three real numbers

OUTPUT:

iterator

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import ARP
sage: it = ARP().coding_iterator((1,e,pi))
sage: [next(it) for _ in range(20)]
[123, 2, 1, 123, 1, 231, 3, 3, 3, 3, 123, 1, 1, 1, 231, 2, 321, 2, 3, 312]

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: algo = Poincare(4)
sage: it = algo.coding_iterator((1,e,pi,sqrt(2)))
sage: [next(it) for _ in range(10)]
[1423, 4312, 3241, 3412, 3142, 3214, 4312, 1342, 3412, 1342]

cone_orbit_iterator()¶

INPUT:

start - initial vector (default: None), if None, then initial point is random

NOTE:

This iterator is 10x slower because of the yield statement. So avoid using this when writing fast code. Just copy paste the loop or use simplex_orbit_list or simplex_orbit_filtered_list method.

OUTPUT:

iterator of tuples (PairPoint, integer)

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: it = Brun().cone_orbit_iterator((13,17,29))
sage: for _ in range(10): next(it)
(((13.0, 17.0, 12.0), (1.0, 2.0, 1.0)), 123)
(((13.0, 4.0, 12.0), (3.0, 2.0, 1.0)), 312)
(((1.0, 4.0, 12.0), (3.0, 2.0, 4.0)), 231)
(((1.0, 4.0, 8.0), (3.0, 6.0, 4.0)), 123)
(((1.0, 4.0, 4.0), (3.0, 10.0, 4.0)), 123)
(((1.0, 4.0, 0.0), (3.0, 14.0, 4.0)), 123)
(((1.0, 3.0, 0.0), (17.0, 14.0, 4.0)), 312)
(((1.0, 2.0, 0.0), (31.0, 14.0, 4.0)), 312)
(((1.0, 1.0, 0.0), (45.0, 14.0, 4.0)), 312)
(((1.0, 0.0, 0.0), (59.0, 14.0, 4.0)), 312)

cone_orbit_list()¶

INPUT:

start - initial vector (default: None), if None, then initial point is random
n_iterations - integer, number of iterations

OUTPUT:

list of tuples (PairPoint, integer)

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: L = Brun().cone_orbit_list((10, 21, 37), 20)
sage: L[-1]
(((1.0, 0.0, 0.0), (68.0, 55.0, 658.0)), 231)

dimension()¶

Return the dimension of the linear space for this algorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().dimension()
3
sage: Brun(3).dimension()
3
sage: Brun(4).dimension()
4
sage: Brun(25).dimension()
25

dual_substitutions()¶

This method must be implemented in the inherited classes.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().dual_substitutions()
{123: WordMorphism: 1->1, 2->2, 3->32,
 132: WordMorphism: 1->1, 2->23, 3->3,
 213: WordMorphism: 1->1, 2->2, 3->31,
 231: WordMorphism: 1->13, 2->2, 3->3,
 312: WordMorphism: 1->1, 2->21, 3->3,
 321: WordMorphism: 1->12, 2->2, 3->3}

image()¶

Return the image of a vector in R^3 after n iterations.

INPUT:

start - initial vector
n_iterations - integer, number of iterations (default: 1)

OUTPUT:

tuple of three floats

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().image((10, 21, 37))
(10.0, 21.0, 16.0)
sage: Brun().image((10, 21, 37), 2)
(10.0, 5.0, 16.0)
sage: Brun().image((10, 21, 37), 3)
(10.0, 5.0, 6.0)
sage: Brun().image((10, 21, 37), 10)
(1.0, 1.0, 0.0)

lyapunov_exponents()¶

Return the lyapunov exponents (theta1, theta2, 1-theta2/theta1)

See also the module slabbe.lyapunov for parallel computations.

INPUT:

start - initial vector (default: None), if None, then initial point is random
n_iterations – integer
verbose – bool (default: False)

OUTPUT:

tuple of the first two liapounov exponents and the uniform approximation exponent:

(theta1, theta2, 1-theta2/theta1)

Note

the code of this method was translated from C to cython. The C version is from Vincent Delecroix.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().lyapunov_exponents(n_iterations=1000000)  # tol 0.02
(0.3049429393152174, -0.1120652699014143, 1.367495867105725)

sage: start = (0.2134134, 0.31618415, 0.414514985)
sage: Brun().lyapunov_exponents(start=start, n_iterations=10^6)  # tol 0.01
(0.3046809303742965, -0.1121152799778245, 1.3679760326322108)

name()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Reverse, Brun, ARP
sage: Reverse().name()
'Reverse'
sage: Brun().name()
'Brun'
sage: ARP().name()
"Arnoux-Rauzy-Poincar\\'e"

nsmall_entries_list()¶

INPUT:

ratio - real number, 0 < ratio < 1
start - initial vector (default: None), if None, then initial point is random
n_iterations – integer
p – integer, p-norm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: algo = Poincare(4)
sage: algo.nsmall_entries_list(.1, (1,e,pi,sqrt(2)), n_iterations=20)
[0, 1, 1, 1, 1, 0, 0, 1, 0, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3]

sage: from slabbe.finite_word import run_length_encoding
sage: L = algo.nsmall_entries_list(.01, (1,e,pi,sqrt(2)), n_iterations=1000)
sage: run_length_encoding(L)
[(0, 1), (1, 1), (0, 7), (1, 1), (0, 3), (1, 2), (2, 1), (3, 984)]

return_time_to_nsmall_entries()¶

INPUT:

ratio - real number, 0 < ratio < 1
n - integer, number of small entries
start - initial vector (default: None), if None, then initial point is random
p – integer, p-norm

OUTPUT:

a tuple (integer, PairPoint)

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: algo = Poincare(4)
sage: algo.return_time_to_nsmall_entries(.05, 0, (1,e,pi,sqrt(2))) # known bug
(3,
 ((0.31830988618379064, 0.41509782135371204, 
   0.13474402056773493, 0.1318482718947624), 
  (0.0, 0.0, 0.0, 0.0)))

sage: algo = Poincare(6)
sage: start = (1,e,pi,sqrt(2),sqrt(3),sqrt(5))
sage: algo.return_time_to_nsmall_entries(.05, 0, start) # known bug
(5,
 ((0.3183098861837907, 0.153493436015088, 0.134744020567735,
 0.1318482718947624, 0.1011707373432389, 0.16043364799538504),
 (0.0, 0.0, 0.0, 0.0, 0.0, 0.0)))

simplex_orbit_filtered_list()¶

Return a list of the orbit filtered to fit into a rectangle.

INPUT:

start - initial vector (default: None), if None, then initial point is random
n_iterations - integer, number of iterations
norm_xyz – integer (default: 1), either 0 or 1, the norm used for the orbit of points \((x,y,z)\) of the algo
norm_uvw – integer (default: 1), either 0 or 1 or 'hypersurfac', the norm used for the orbit of dual coordinates \((u,v,w)\).
xmin - double
ymin - double
umin - double
vmin - double
xmax - double
ymax - double
umax - double
vmax - double
ndvis - integer, number of divisions

OUTPUT:

list

BENCHMARK:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: %time D = Brun().simplex_orbit_filtered_list(10^6) # not tested
CPU times: user 366 ms, sys: 203 ms, total: 568 ms
Wall time: 570 ms

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: start=(.414578,.571324,.65513)
sage: D = Brun().simplex_orbit_filtered_list(start, 3)
sage: D      # random
[(0.3049590483124023,
  -0.36889249928767137,
  -0.21650635094610976,
  -0.125,
  312,
  312),
 (0.08651831333735083,
  -0.31784823591841554,
  -0.34641016151377557,
  -0.2,
  312,
  312),
 (-0.41045591033143647,
  -0.20171750067080554,
  -0.4330127018922195,
  -0.25000000000000006,
  312,
  231)]

sage: Brun().simplex_orbit_filtered_list(n_iterations=3, norm_xyz=1,ndivs=1000)
Traceback (most recent call last):
...
ValueError: when ndivs is specified, you must provide a value
for xmin, xmax, ymin, ymax, umin, umax, vmin and vmax

sage: Brun().simplex_orbit_filtered_list(n_iterations=7,  # random
....:       norm_xyz=1, ndivs=100,
....:       xmin=-.866, xmax=.866, ymin=-.5, ymax=1.,
....:       umin=-.866, umax=.866, vmin=-.5, vmax=1.)
[(30, 47, 50, 50, 132, 213),
 (15, 83, 33, 66, 213, 231),
 (18, 80, 38, 44, 231, 231),
 (22, 75, 41, 33, 231, 231),
 (30, 68, 43, 26, 231, 231),
 (44, 53, 44, 22, 231, 213),
 (41, 78, 24, 56, 213, 321)]

simplex_orbit_iterator()¶

INPUT:

start - initial vector (default: None), if None, then initial point is random
norm_xyz – integer (default: 0), either 0 or 1, the norm used for the orbit of points \((x,y,z)\) of the algo
norm_uvw – integer (default: 1), either 0 or 1 or 'hypersurfac', the norm used for the orbit of dual coordinates \((u,v,w)\).

NOTE:

This iterator is 10x slower because of the yield statement. So avoid using this when writing fast code. Just copy paste the loop or use simplex_orbit_list or simplex_orbit_filtered_list method.

OUTPUT:

iterator

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: it = Brun().simplex_orbit_iterator((.414578,.571324,.65513))
sage: for _ in range(4): next(it)
((0.7256442929056017, 1.0, 0.14668734378391243), 
 (0.25, 0.5, 0.25), 
 123)
((1.0, 0.37808566783572695, 0.20214772612150184),
 (0.5, 0.3333333333333333, 0.16666666666666666),
 312)
((1.0, 0.6079385025908344, 0.32504111204194974),
 (0.3333333333333333, 0.5555555555555555, 0.1111111111111111),
 321)
((0.6449032192209051, 1.0, 0.534661171576946),
 (0.25, 0.6666666666666666, 0.08333333333333333),
 321)

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: it = Brun().simplex_orbit_iterator((.414578,.571324,.65513), norm_xyz=1)
sage: for _ in range(4): next(it)
((0.3875618393056797, 0.5340934161472103, 0.07834474454711005),
 (0.25, 0.5, 0.25),
 123)
 ((0.6328179140018012, 0.23925938363378257, 0.12792270236441622),
 (0.5, 0.3333333333333333, 0.16666666666666666),
 312)
((0.5173360300491189, 0.3145084914443481, 0.16815547850653312),
 (0.3333333333333333, 0.5555555555555555, 0.1111111111111111),
 321)
((0.2958862889959549, 0.45880727553726447, 0.24530643546678058),
 (0.25, 0.6666666666666666, 0.08333333333333333),
 321)

simplex_orbit_list()¶

INPUT:

start - initial vector (default: None), if None, then initial point is random
n_iterations - integer, number of iterations
norm_xyz – integer (default: 1), either 0 or 1, the norm used for the orbit of points \((x,y,z)\) of the algo
norm_uvw – integer (default: 1), either 0 or 1 or 'hypersurfac', the norm used for the orbit of dual coordinates \((u,v,w)\).

OUTPUT:

list

Note

It could be 10 times faster because 10^6 iterations can be done in about 60ms on this machine. But for drawing images, it does not matter to be 10 times slower:

sage: %time L = Brun().simplex_orbit_list(10^6)   # not tested
CPU times: user 376 ms, sys: 267 ms, total: 643 ms
Wall time: 660 ms

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: L = Brun().simplex_orbit_list(n_iterations=10^5)
sage: L[-1]    # random
(0.7307002153148079,
 1.0,
 0.31588474491578816,
 0.29055326655584235,
 0.4690741038784866,
 0.24037262956567113,
 321)

substitutions()¶

This method must be implemented in the inherited classes.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Brun
sage: Brun().substitutions()
{123: WordMorphism: 1->1, 2->23, 3->3,
 132: WordMorphism: 1->1, 2->2, 3->32,
 213: WordMorphism: 1->13, 2->2, 3->3,
 231: WordMorphism: 1->1, 2->2, 3->31,
 312: WordMorphism: 1->12, 2->2, 3->3,
 321: WordMorphism: 1->1, 2->21, 3->3}

class slabbe.mult_cont_frac_pyx.PairPoint¶

Bases: object

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: PairPoint(3, (.2,.3,.4))
((0.2, 0.3, 0.4), (..., ..., ...))
sage: PairPoint(3, a=(.2,.3,.4))
((..., ..., ...), (0.2, 0.3, 0.4))

number_small_entries()¶: Returns the number of indices i such that x[i]/||x|| < ratio.

permutation()¶

http://stackoverflow.com/questions/17554242/how-to-obtain-the-index-permutation-after-the-sorting

OUTPUT:

int (the permutation, works well if self.dim < 10)

Permutation gets written to self.perm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: P = PairPoint(4, [.4, .2, .3, .1], [4,3,2,1])
sage: P.permutation()
4231

sort()¶

Sort array x and sort array a with the same permutation.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: P = PairPoint(4, [.4, .2, .3, .1], [4,3,2,1])
sage: P.sort()
sage: P
((0.1, 0.2, 0.3, 0.4), (1.0, 3.0, 2.0, 4.0))

sage: P = PairPoint(3, [.3,.6,.2], [.2,.6,.3])
sage: P.sort()
sage: P
((0.2, 0.3, 0.6), (0.3, 0.2, 0.6))

sort_a()¶

Sort array a according to values in array x.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: P = PairPoint(4, [.4, .2, .3, .1], [4,3,2,1])
sage: P.sort_a()
sage: P
((0.4, 0.2, 0.3, 0.1), (1.0, 3.0, 2.0, 4.0))

sage: P = PairPoint(3, [.3,.6,.2], [.2,.6,.3])
sage: P.sort_a()
sage: P
((0.3, 0.6, 0.2), (0.3, 0.2, 0.6))

sort_x()¶

Sort array x independently of array a.

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: P = PairPoint(4, [.4, .2, .3, .1], [4,3,2,1])
sage: P.sort_x()
sage: P
((0.1, 0.2, 0.3, 0.4), (4.0, 3.0, 2.0, 1.0))

to_dict()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: PairPoint(3, [1,2,3], [4,5,6]).to_dict()
{'a': [4.0, 5.0, 6.0], 'x': [1.0, 2.0, 3.0]}

to_tuple()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import PairPoint
sage: PairPoint(3, [1,2,3], [4,5,6]).to_tuple()
((1.0, 2.0, 3.0), (4.0, 5.0, 6.0))

class slabbe.mult_cont_frac_pyx.Poincare¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: algo = Poincare()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: Poincare().dual_substitutions()
{123: WordMorphism: 1->1, 2->21, 3->321,
 132: WordMorphism: 1->1, 2->231, 3->31,
 213: WordMorphism: 1->12, 2->2, 3->312,
 231: WordMorphism: 1->132, 2->2, 3->32,
 312: WordMorphism: 1->13, 2->213, 3->3,
 321: WordMorphism: 1->123, 2->23, 3->3}

name()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: Poincare().name()
"Poincar\\'e"

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Poincare
sage: Poincare().substitutions()
{123: WordMorphism: 1->123, 2->23, 3->3,
 132: WordMorphism: 1->132, 2->2, 3->32,
 213: WordMorphism: 1->13, 2->213, 3->3,
 231: WordMorphism: 1->1, 2->231, 3->31,
 312: WordMorphism: 1->12, 2->2, 3->312,
 321: WordMorphism: 1->1, 2->21, 3->321}

class slabbe.mult_cont_frac_pyx.Reverse¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Reverse
sage: algo = Reverse()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Reverse
sage: Reverse().dual_substitutions()
{1: WordMorphism: 1->123, 2->2, 3->3,
 2: WordMorphism: 1->1, 2->231, 3->3,
 3: WordMorphism: 1->1, 2->2, 3->312,
 4: WordMorphism: 1->23, 2->13, 3->12}

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Reverse
sage: Reverse().substitutions()
{1: WordMorphism: 1->1, 2->21, 3->31,
 2: WordMorphism: 1->12, 2->2, 3->32,
 3: WordMorphism: 1->13, 2->23, 3->3,
 4: WordMorphism: 1->23, 2->31, 3->12}

class slabbe.mult_cont_frac_pyx.Selmer¶

Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Selmer
sage: algo = Selmer()
sage: TestSuite(algo).run()
sage: algo._test_dual_substitution_definition()
sage: algo._test_coherence()
sage: algo._test_definition()

dual_substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Selmer
sage: Selmer().dual_substitutions()
{123: WordMorphism: 1->1, 2->2, 3->31,
 132: WordMorphism: 1->1, 2->21, 3->3,
 213: WordMorphism: 1->1, 2->2, 3->32,
 231: WordMorphism: 1->12, 2->2, 3->3,
 312: WordMorphism: 1->1, 2->23, 3->3,
 321: WordMorphism: 1->13, 2->2, 3->3}

substitutions()¶

EXAMPLES:

sage: from slabbe.mult_cont_frac_pyx import Selmer
sage: Selmer().substitutions()
{123: WordMorphism: 1->13, 2->2, 3->3,
 132: WordMorphism: 1->12, 2->2, 3->3,
 213: WordMorphism: 1->1, 2->23, 3->3,
 231: WordMorphism: 1->1, 2->21, 3->3,
 312: WordMorphism: 1->1, 2->2, 3->32,
 321: WordMorphism: 1->1, 2->2, 3->31}

class slabbe.mult_cont_frac_pyx.Sorted_ARMonteil¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ARP¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ARPMulti¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ARrevert¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ARrevertMulti¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ArnouxRauzy¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_ArnouxRauzyMulti¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_Brun¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_BrunMulti¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_Delaunay¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_FullySubtractive¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_Poincare¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

class slabbe.mult_cont_frac_pyx.Sorted_Selmer¶: Bases: slabbe.mult_cont_frac_pyx.MCFAlgorithm

Multidimensional Continued Fraction Algorithms¶

Previous topic

Next topic

This Page