Miscellaneous functions (Cython)

This file contains support for products, running totals, balanced sums, and also a function to flush output from external library calls.

AUTHORS:

  • William Stein (2005)

  • Joel B. Mohler (2007-10-03): Reimplemented in Cython and optimized

  • Robert Bradshaw (2007-10-26): Balanced product tree, other optimizations, (lazy) generator support

  • Robert Bradshaw (2008-03-26): Balanced product tree for generators and iterators

  • Stefan van Zwam (2013-06-06): Added bitset tests, some docstring cleanup

class sage.misc.misc_c.NonAssociative(left, right=None)[source]

Bases: object

This class is to test the balance nature of prod.

EXAMPLES:

sage: from sage.misc.misc_c import NonAssociative
sage: L = [NonAssociative(label) for label in 'abcdef']
sage: prod(L)
(((a*b)*c)*((d*e)*f))
sage: L = [NonAssociative(label) for label in range(20)]
sage: prod(L, recursion_cutoff=5)
((((((0*1)*2)*3)*4)*((((5*6)*7)*8)*9))*(((((10*11)*12)*13)*14)*((((15*16)*17)*18)*19)))
sage: prod(L, recursion_cutoff=1)
(((((0*1)*2)*(3*4))*(((5*6)*7)*(8*9)))*((((10*11)*12)*(13*14))*(((15*16)*17)*(18*19))))
sage: L = [NonAssociative(label) for label in range(14)]
sage: prod(L, recursion_cutoff=1)
((((0*1)*(2*3))*((4*5)*6))*(((7*8)*(9*10))*((11*12)*13)))

>>> from sage.all import *
>>> from sage.misc.misc_c import NonAssociative
>>> L = [NonAssociative(label) for label in 'abcdef']
>>> prod(L)
(((a*b)*c)*((d*e)*f))
>>> L = [NonAssociative(label) for label in range(Integer(20))]
>>> prod(L, recursion_cutoff=Integer(5))
((((((0*1)*2)*3)*4)*((((5*6)*7)*8)*9))*(((((10*11)*12)*13)*14)*((((15*16)*17)*18)*19)))
>>> prod(L, recursion_cutoff=Integer(1))
(((((0*1)*2)*(3*4))*(((5*6)*7)*(8*9)))*((((10*11)*12)*(13*14))*(((15*16)*17)*(18*19))))
>>> L = [NonAssociative(label) for label in range(Integer(14))]
>>> prod(L, recursion_cutoff=Integer(1))
((((0*1)*(2*3))*((4*5)*6))*(((7*8)*(9*10))*((11*12)*13)))
sage.misc.misc_c.balanced_sum(x, z=None, recursion_cutoff=5)[source]

Return the sum of the elements in the list x. If optional argument z is not given, start the sum with the first element of the list, otherwise use z. The empty product is the int 0 if z is not specified, and is z if given. The sum is computed recursively, where the sum is split up if the list is greater than recursion_cutoff. recursion_cutoff must be at least 3.

This assumes that your addition is associative; we do not promise which end of the list we start at.

EXAMPLES:

sage: balanced_sum([1,2,34])
37
sage: balanced_sum([2,3], 5)
10
sage: balanced_sum((1,2,3), 5)
11

>>> from sage.all import *
>>> balanced_sum([Integer(1),Integer(2),Integer(34)])
37
>>> balanced_sum([Integer(2),Integer(3)], Integer(5))
10
>>> balanced_sum((Integer(1),Integer(2),Integer(3)), Integer(5))
11

Order should be preserved:

sage: balanced_sum([[i] for i in range(10)], [], recursion_cutoff=3)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> from sage.all import *
>>> balanced_sum([[i] for i in range(Integer(10))], [], recursion_cutoff=Integer(3))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

We make copies when appropriate so that we do not accidentally modify the arguments:

sage: list(range(10^5))==balanced_sum([[i] for i in range(10^5)], [])
True
sage: list(range(10^5))==balanced_sum([[i] for i in range(10^5)], [])
True

>>> from sage.all import *
>>> list(range(Integer(10)**Integer(5)))==balanced_sum([[i] for i in range(Integer(10)**Integer(5))], [])
True
>>> list(range(Integer(10)**Integer(5)))==balanced_sum([[i] for i in range(Integer(10)**Integer(5))], [])
True

AUTHORS:

  • Joel B. Mohler (2007-10-03): Reimplemented in Cython and optimized

  • Robert Bradshaw (2007-10-26): Balanced product tree, other optimizations, (lazy) generator support

sage.misc.misc_c.cyflush()[source]

Flush any output left over from external library calls.

Starting with Python 3, some output from external libraries (like FLINT) is not flushed, and so if a doctest produces such output, the output may not appear until a later doctest. See Issue #28649.

Use this function after a doctest which produces potentially unflushed output to force it to be flushed.

EXAMPLES:

sage: R.<t> = QQ[]
sage: t^(sys.maxsize//2)                                                        # needs sage.libs.flint
Traceback (most recent call last):
...
RuntimeError: FLINT exception
sage: from sage.misc.misc_c import cyflush
sage: cyflush()
...

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> t**(sys.maxsize//Integer(2))                                                        # needs sage.libs.flint
Traceback (most recent call last):
...
RuntimeError: FLINT exception
>>> from sage.misc.misc_c import cyflush
>>> cyflush()
...
sage.misc.misc_c.iterator_prod(L, z=None)[source]

Attempt to do a balanced product of an arbitrary and unknown length sequence (such as a generator). Intermediate multiplications are always done with subproducts of the same size (measured by the number of original factors) up until the iterator terminates. This is optimal when and only when there are exactly a power of two number of terms.

A StopIteration is raised if the iterator is empty and z is not given.

EXAMPLES:

sage: from sage.misc.misc_c import iterator_prod
sage: iterator_prod(1..5)
120
sage: iterator_prod([], z='anything')
'anything'

sage: from sage.misc.misc_c import NonAssociative
sage: L = [NonAssociative(label) for label in 'abcdef']
sage: iterator_prod(L)
(((a*b)*(c*d))*(e*f))

>>> from sage.all import *
>>> from sage.misc.misc_c import iterator_prod
>>> iterator_prod(ellipsis_iter(Integer(1),Ellipsis,Integer(5)))
120
>>> iterator_prod([], z='anything')
'anything'

>>> from sage.misc.misc_c import NonAssociative
>>> L = [NonAssociative(label) for label in 'abcdef']
>>> iterator_prod(L)
(((a*b)*(c*d))*(e*f))
sage.misc.misc_c.normalize_index(key, size)[source]

Normalize an index key and return a valid index or list of indices within the range(0, size).

INPUT:

  • key – the index key, which can be either an integer, a tuple/list of integers, or a slice

  • size – the size of the collection

OUTPUT:

A tuple (SINGLE, VALUE), where SINGLE is True (i.e., 1) if VALUE is an integer and False (i.e., 0) if VALUE is a list.

EXAMPLES:

sage: from sage.misc.misc_c import normalize_index
sage: normalize_index(-6,5)
Traceback (most recent call last):
...
IndexError: index out of range
sage: normalize_index(-5,5)
[0]
sage: normalize_index(-4,5)
[1]
sage: normalize_index(-3,5)
[2]
sage: normalize_index(-2,5)
[3]
sage: normalize_index(-1,5)
[4]
sage: normalize_index(0,5)
[0]
sage: normalize_index(1,5)
[1]
sage: normalize_index(2,5)
[2]
sage: normalize_index(3,5)
[3]
sage: normalize_index(4,5)
[4]
sage: normalize_index(5,5)
Traceback (most recent call last):
...
IndexError: index out of range
sage: normalize_index(6,5)
Traceback (most recent call last):
...
IndexError: index out of range
sage: normalize_index((4,-6),5)
Traceback (most recent call last):
...
IndexError: index out of range
sage: normalize_index((-2,3),5)
[3, 3]
sage: normalize_index((5,0),5)
Traceback (most recent call last):
...
IndexError: index out of range
sage: normalize_index((-5,2),5)
[0, 2]
sage: normalize_index((0,-2),5)
[0, 3]
sage: normalize_index((2,-3),5)
[2, 2]
sage: normalize_index((3,3),5)
[3, 3]
sage: normalize_index((-2,-5),5)
[3, 0]
sage: normalize_index((-2,-4),5)
[3, 1]
sage: normalize_index([-2,-1,3],5)
[3, 4, 3]
sage: normalize_index([4,2,1],5)
[4, 2, 1]
sage: normalize_index([-2,-3,-4],5)
[3, 2, 1]
sage: normalize_index([3,-2,-3],5)
[3, 3, 2]
sage: normalize_index([-5,2,-3],5)
[0, 2, 2]
sage: normalize_index([4,4,-5],5)
[4, 4, 0]
sage: s=slice(None,None,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,None,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,None,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,-2,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,-2,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,-2,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,4,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,4,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(None,4,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,None,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,None,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,None,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,-2,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,-2,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,-2,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,4,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,4,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(-2,4,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,None,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,None,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,None,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,-2,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,-2,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,-2,4); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,4,None); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,4,-2); normalize_index(s,5)==list(range(5))[s]
True
sage: s=slice(4,4,4); normalize_index(s,5)==list(range(5))[s]
True

>>> from sage.all import *
>>> from sage.misc.misc_c import normalize_index
>>> normalize_index(-Integer(6),Integer(5))
Traceback (most recent call last):
...
IndexError: index out of range
>>> normalize_index(-Integer(5),Integer(5))
[0]
>>> normalize_index(-Integer(4),Integer(5))
[1]
>>> normalize_index(-Integer(3),Integer(5))
[2]
>>> normalize_index(-Integer(2),Integer(5))
[3]
>>> normalize_index(-Integer(1),Integer(5))
[4]
>>> normalize_index(Integer(0),Integer(5))
[0]
>>> normalize_index(Integer(1),Integer(5))
[1]
>>> normalize_index(Integer(2),Integer(5))
[2]
>>> normalize_index(Integer(3),Integer(5))
[3]
>>> normalize_index(Integer(4),Integer(5))
[4]
>>> normalize_index(Integer(5),Integer(5))
Traceback (most recent call last):
...
IndexError: index out of range
>>> normalize_index(Integer(6),Integer(5))
Traceback (most recent call last):
...
IndexError: index out of range
>>> normalize_index((Integer(4),-Integer(6)),Integer(5))
Traceback (most recent call last):
...
IndexError: index out of range
>>> normalize_index((-Integer(2),Integer(3)),Integer(5))
[3, 3]
>>> normalize_index((Integer(5),Integer(0)),Integer(5))
Traceback (most recent call last):
...
IndexError: index out of range
>>> normalize_index((-Integer(5),Integer(2)),Integer(5))
[0, 2]
>>> normalize_index((Integer(0),-Integer(2)),Integer(5))
[0, 3]
>>> normalize_index((Integer(2),-Integer(3)),Integer(5))
[2, 2]
>>> normalize_index((Integer(3),Integer(3)),Integer(5))
[3, 3]
>>> normalize_index((-Integer(2),-Integer(5)),Integer(5))
[3, 0]
>>> normalize_index((-Integer(2),-Integer(4)),Integer(5))
[3, 1]
>>> normalize_index([-Integer(2),-Integer(1),Integer(3)],Integer(5))
[3, 4, 3]
>>> normalize_index([Integer(4),Integer(2),Integer(1)],Integer(5))
[4, 2, 1]
>>> normalize_index([-Integer(2),-Integer(3),-Integer(4)],Integer(5))
[3, 2, 1]
>>> normalize_index([Integer(3),-Integer(2),-Integer(3)],Integer(5))
[3, 3, 2]
>>> normalize_index([-Integer(5),Integer(2),-Integer(3)],Integer(5))
[0, 2, 2]
>>> normalize_index([Integer(4),Integer(4),-Integer(5)],Integer(5))
[4, 4, 0]
>>> s=slice(None,None,None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,None,-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,None,Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,-Integer(2),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,-Integer(2),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,-Integer(2),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,Integer(4),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,Integer(4),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(None,Integer(4),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),None,None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),None,-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),None,Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),-Integer(2),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),-Integer(2),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),-Integer(2),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),Integer(4),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),Integer(4),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(-Integer(2),Integer(4),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),None,None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),None,-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),None,Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),-Integer(2),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),-Integer(2),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),-Integer(2),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),Integer(4),None); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),Integer(4),-Integer(2)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
>>> s=slice(Integer(4),Integer(4),Integer(4)); normalize_index(s,Integer(5))==list(range(Integer(5)))[s]
True
sage.misc.misc_c.prod(x, z=None, recursion_cutoff=5)[source]

Return the product of the elements in the list x.

If optional argument z is not given, start the product with the first element of the list, otherwise use z. The empty product is the int 1 if z is not specified, and is z if given.

This assumes that your multiplication is associative; we do not promise which end of the list we start at.

See also

For the symbolic product function, see sage.calculus.calculus.symbolic_product().

EXAMPLES:

sage: prod([1,2,34])
68
sage: prod([2,3], 5)
30
sage: prod((1,2,3), 5)
30
sage: F = factor(-2006); F
-1 * 2 * 17 * 59
sage: prod(F)
-2006

>>> from sage.all import *
>>> prod([Integer(1),Integer(2),Integer(34)])
68
>>> prod([Integer(2),Integer(3)], Integer(5))
30
>>> prod((Integer(1),Integer(2),Integer(3)), Integer(5))
30
>>> F = factor(-Integer(2006)); F
-1 * 2 * 17 * 59
>>> prod(F)
-2006

AUTHORS:

  • Joel B. Mohler (2007-10-03): Reimplemented in Cython and optimized

  • Robert Bradshaw (2007-10-26): Balanced product tree, other optimizations, (lazy) generator support

  • Robert Bradshaw (2008-03-26): Balanced product tree for generators and iterators

sage.misc.misc_c.running_total(L, start=None)[source]

Return a list where the \(i\)-th entry is the sum of all entries up to (and including) \(i\).

INPUT:

  • L – the list

  • start – (optional) a default start value

EXAMPLES:

sage: running_total(range(5))
[0, 1, 3, 6, 10]
sage: running_total("abcdef")
['a', 'ab', 'abc', 'abcd', 'abcde', 'abcdef']
sage: running_total("abcdef", start="%")
['%a', '%ab', '%abc', '%abcd', '%abcde', '%abcdef']
sage: running_total([1..10], start=100)
[101, 103, 106, 110, 115, 121, 128, 136, 145, 155]
sage: running_total([])
[]

>>> from sage.all import *
>>> running_total(range(Integer(5)))
[0, 1, 3, 6, 10]
>>> running_total("abcdef")
['a', 'ab', 'abc', 'abcd', 'abcde', 'abcdef']
>>> running_total("abcdef", start="%")
['%a', '%ab', '%abc', '%abcd', '%abcde', '%abcdef']
>>> running_total((ellipsis_range(Integer(1),Ellipsis,Integer(10))), start=Integer(100))
[101, 103, 106, 110, 115, 121, 128, 136, 145, 155]
>>> running_total([])
[]
class sage.misc.misc_c.sized_iter[source]

Bases: object

Wrapper for an iterator to verify that it has a specified length.

INPUT:

  • iterable – object to be iterated over

  • length – (optional) the required length; if this is not given, then len(iterable) will be used

If the iterable does not have the given length, a ValueError is raised during iteration.

EXAMPLES:

sage: from sage.misc.misc_c import sized_iter
sage: list(sized_iter(range(4)))
[0, 1, 2, 3]
sage: list(sized_iter(range(4), 4))
[0, 1, 2, 3]
sage: list(sized_iter(range(5), 4))
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 4, got more)
sage: list(sized_iter(range(3), 4))
Traceback (most recent call last):
...
ValueError: sequence too short (expected length 4, got 3)

>>> from sage.all import *
>>> from sage.misc.misc_c import sized_iter
>>> list(sized_iter(range(Integer(4))))
[0, 1, 2, 3]
>>> list(sized_iter(range(Integer(4)), Integer(4)))
[0, 1, 2, 3]
>>> list(sized_iter(range(Integer(5)), Integer(4)))
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 4, got more)
>>> list(sized_iter(range(Integer(3)), Integer(4)))
Traceback (most recent call last):
...
ValueError: sequence too short (expected length 4, got 3)

If the iterable is too long, we get the error on the last entry:

sage: it = sized_iter(range(5), 2)
sage: next(it)
0
sage: next(it)
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 2, got more)

>>> from sage.all import *
>>> it = sized_iter(range(Integer(5)), Integer(2))
>>> next(it)
0
>>> next(it)
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 2, got more)

When the expected length is zero, the iterator is checked on construction:

sage: list(sized_iter([], 0))
[]
sage: sized_iter([1], 0)
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 0, got more)

>>> from sage.all import *
>>> list(sized_iter([], Integer(0)))
[]
>>> sized_iter([Integer(1)], Integer(0))
Traceback (most recent call last):
...
ValueError: sequence too long (expected length 0, got more)

If no length is given, the iterable must implement __len__:

sage: sized_iter(x for x in range(4))
Traceback (most recent call last):
...
TypeError: object of type 'generator' has no len()

>>> from sage.all import *
>>> sized_iter(x for x in range(Integer(4)))
Traceback (most recent call last):
...
TypeError: object of type 'generator' has no len()