Miscellaneous functions (Cython)¶
This file contains support for products, running totals and balanced sums.
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)¶ 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)))
-
sage.misc.misc_c.
balanced_sum
(x, z=None, recursion_cutoff=5)¶ 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 don’t 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
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]
We make copies when appropriate so that we don’t accidentally modify the arguments:
sage: range(10e4)==balanced_sum([[i] for i in range(10e4)], []) True sage: range(10e4)==balanced_sum([[i] for i in range(10e4)], []) True
TESTS:
sage: balanced_sum((1..3)) # nonempty, z=None 6 sage: balanced_sum((1..-1)) # empty, z=None 0 sage: balanced_sum((1..3), 5) # nonempty, z is not None 11 sage: balanced_sum((1..-1), 5) # empty, z is not None 5
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.
iterator_prod
(L, z=None)¶ 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))
-
sage.misc.misc_c.
normalize_index
(key, size)¶ 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)==range(5)[s] True sage: s=slice(None,None,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,None,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,-2,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,-2,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,-2,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,4,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,4,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(None,4,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,None,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,None,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,None,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,-2,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,-2,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,-2,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,4,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,4,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(-2,4,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,None,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,None,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,None,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,-2,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,-2,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,-2,4); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,4,None); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,4,-2); normalize_index(s,5)==range(5)[s] True sage: s=slice(4,4,4); normalize_index(s,5)==range(5)[s] True
-
sage.misc.misc_c.
prod
(x, z=None, recursion_cutoff=5)¶ 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 don’t promise which end of the list we start at.
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
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)¶ Return a list where the i-th entry is the sum of all entries up to (and including) i.
INPUT:
L
– the liststart
– (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([]) []