#987

Build # #987

Build Type

push

travis-ci

Committed by GitHub

Commit Message

build(deps): bump decode-uri-component in /waves/javascript_demo

Run Details

910 of 910 relevant lines covered (100.0%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/secret_sharing/interpolate.py

from polynomial import Polynomial
from polynomial import ZERO


def single_term(points, i):
    """Return one term of an interpolated polynomial.

    This method computes one term of the sum from the proof of Theorem 2.2.
    In particular, it computes:

      y_i \\product_{j=0}^n (x - x_i) / (x_i - x_j)

    The encapsulating `interpolate` function sums these terms to construct
    the final interpolated polynomial.

    Arguments:
      - points: a list of (float, float)
      - i: an integer indexing a specific point

    Returns:
      A Polynomial instance containing the desired product.
    """
    the_term = Polynomial([1.])
    xi, yi = points[i]

    for j, p in enumerate(points):
        if j == i:
            continue

        xj = p[0]

        """
        The inlined Polynomial instance below is how we represent

          (x - x_j) / (x_i - x_j)

        using our Polynomial data type (where t replaces x as the variable, and
        x_i, x_j are two x-values of data points):

          (x - x_j) / (x_i - x_j) = (-x_j / (x_i - x_j)) * t^0
                                  +    (1 / (x_i - x_j)) * t^1
        """
        the_term = the_term * Polynomial([-xj / (xi - xj), 1.0 / (xi - xj)])

    # Polynomial([yi]) is a constant polynomial, i.e., we're scaling the_term
    # by a constant.
    return the_term * Polynomial([yi])


def interpolate(points):
    """Return the unique polynomial of degree at most n passing through the given n+1 points."""
    if len(points) == 0:
        raise ValueError('Must provide at least one point.')

    x_values = [p[0] for p in points]
    if len(set(x_values)) < len(x_values):
        raise ValueError('Not all x values are distinct.')

    terms = [single_term(points, i) for i in range(0, len(points))]
    return sum(terms, ZERO)

1	from polynomial import Polynomial	1✔
2	from polynomial import ZERO	1✔
3
4
5	def single_term(points, i):	1✔
6	"""Return one term of an interpolated polynomial.
7
8	This method computes one term of the sum from the proof of Theorem 2.2.
9	In particular, it computes:
10
11	y_i \\product_{j=0}^n (x - x_i) / (x_i - x_j)
12
13	The encapsulating `interpolate` function sums these terms to construct
14	the final interpolated polynomial.
15
16	Arguments:
17	- points: a list of (float, float)
18	- i: an integer indexing a specific point
19
20	Returns:
21	A Polynomial instance containing the desired product.
22	"""
23	the_term = Polynomial([1.])	1✔
24	xi, yi = points[i]	1✔
25
26	for j, p in enumerate(points):	1✔
27	if j == i:	1✔
28	continue	1✔
29
30	xj = p[0]	1✔
31
32	"""
33	The inlined Polynomial instance below is how we represent
34
35	(x - x_j) / (x_i - x_j)
36
37	using our Polynomial data type (where t replaces x as the variable, and
38	x_i, x_j are two x-values of data points):
39
40	(x - x_j) / (x_i - x_j) = (-x_j / (x_i - x_j)) * t^0
41	+ (1 / (x_i - x_j)) * t^1
42	"""
43	the_term = the_term * Polynomial([-xj / (xi - xj), 1.0 / (xi - xj)])	1✔
44
45	# Polynomial([yi]) is a constant polynomial, i.e., we're scaling the_term
46	# by a constant.
47	return the_term * Polynomial([yi])	1✔
48
49
50	def interpolate(points):	1✔
51	"""Return the unique polynomial of degree at most n passing through the given n+1 points."""
52	if len(points) == 0:	1✔
53	raise ValueError('Must provide at least one point.')	1✔
54
55	x_values = [p[0] for p in points]	1✔
56	if len(set(x_values)) < len(x_values):	1✔
57	raise ValueError('Not all x values are distinct.')	1✔
58
59	terms = [single_term(points, i) for i in range(0, len(points))]	1✔
60	return sum(terms, ZERO)	1✔

pim-book / programmers-introduction-to-mathematics / #987

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous