# 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))
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


EXAMPLES:

sage: from slabbe.mult_cont_frac import JacobiPerronAdditif


EXAMPLES:

sage: from slabbe.mult_cont_frac import JacobiPerronAdditifv2

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)

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

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,
2: WordMorphism: 1->1, 2->231, 3->3,
3: WordMorphism: 1->1, 2->2, 3->312,
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 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,
2: WordMorphism: 1->12, 2->2, 3->32,
3: WordMorphism: 1->13, 2->23, 3->3,
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.ArnouxRauzy

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

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

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

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
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.04
(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

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

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

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
class slabbe.mult_cont_frac_pyx.Sorted_ARP
class slabbe.mult_cont_frac_pyx.Sorted_ARPMulti
class slabbe.mult_cont_frac_pyx.Sorted_ARrevert
class slabbe.mult_cont_frac_pyx.Sorted_ARrevertMulti
class slabbe.mult_cont_frac_pyx.Sorted_ArnouxRauzy
class slabbe.mult_cont_frac_pyx.Sorted_ArnouxRauzyMulti
class slabbe.mult_cont_frac_pyx.Sorted_Brun
class slabbe.mult_cont_frac_pyx.Sorted_BrunMulti
class slabbe.mult_cont_frac_pyx.Sorted_Delaunay
class slabbe.mult_cont_frac_pyx.Sorted_FullySubtractive
class slabbe.mult_cont_frac_pyx.Sorted_Poincare
class slabbe.mult_cont_frac_pyx.Sorted_Selmer