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 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([])
[]