Class: KZG::Polynomial

Inherits:
Object
  • Object
show all
Defined in:
lib/kzg/polynomial.rb

Overview

Polynomial

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(coeffs) ⇒ Polynomial

Create new polynomial

Parameters:

  • (Array(Integer|BLS::Fr)) 


10
11
12
 
# File 'lib/kzg/polynomial.rb', line 10

def initialize(coeffs)
  @coeffs = coeffs.map { |c| c.is_a?(BLS::Fr) ? c : BLS::Fr.new(c) }
end

Instance Attribute Details

#coeffs ⇒ Object (readonly)

Returns the value of attribute coeffs.



6
7
8
 
# File 'lib/kzg/polynomial.rb', line 6

def coeffs
  @coeffs
end

Class Method Details

.lagrange_interpolate(x, y) ⇒ KZG::Polynomial

Create polynomial using lagrange interpolation using (x, y) list. twice: no polynomial passes through two different y at one x, and one that repeats an (x, y) pair is under-determined either way. length.

Parameters:

  • x (Array(Integer)) —

    The array of x coordinate. Must not contain the same value

  • y (Array(Integer)) —

    The array of y coordinate. Must be as long as x.

Returns:

Raises:

  • (KZG::Error) —

    Occur when x contains a duplicate value, or x and y differ in



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/kzg/polynomial.rb', line 22

def self.lagrange_interpolate(x, y)
  n = x.length
  unless n == y.length
    raise KZG::Error, "x and y must have the same length."
  end

  x = x.map { |i| i.is_a?(BLS::Fr) ? i : BLS::Fr.new(i) }
  y = y.map { |i| i.is_a?(BLS::Fr) ? i : BLS::Fr.new(i) }
  # The product below runs over the differences between x[i] and every other x, so a
  # repeat makes it zero and the division by it undefined. Caught here rather than left
  # to BLS::Fr#invert so that it reads as the input error it is.
  if x.map(&:value).uniq.length < n
    raise KZG::Error, "x contains duplicate value."
  end
  coeffs = Array.new(n, BLS::Fr::ZERO)
  n.times do |i|
    prod = BLS::Fr::ONE
    n.times { |j| prod *= (x[i] - x[j]) unless i == j }
    prod = y[i] / prod
    term = [prod] + Array.new(n - 1, BLS::Fr::ZERO)
    n.times do |j|
      next if i == j
      (n - 1).step(1, -1) do |k|
        term[k] += term[k - 1]
        term[k - 1] *= x[j].negate
      end
    end
    n.times { |j| coeffs[j] += term[j] }
  end
  Polynomial.new(coeffs)
end

.zero_poly(x) ⇒ KZG::Polynomial

Create polynomial from array of x coordinate like f(x) = (x - x0)(x - x1)...(x - xn)

Parameters:

  • x (Array(Integer)) —

    An array of x coordinate.

Returns:

Raises:

  • (KZG::Error) —

    Occur when x is empty, which names no roots to build from.



58
59
60
61
62
63
64
 
# File 'lib/kzg/polynomial.rb', line 58

def self.zero_poly(x)
  raise KZG::Error, "x must not be empty." if x.empty?

  poleis =
    x.map { |v| Polynomial.new([BLS::Fr.new(v).negate, BLS::Fr::ONE]) }
  poleis[1..].inject(poleis.first) { |result, poly| result * poly }
end

Instance Method Details

#==(other) ⇒ Object 



171
172
173
174
 
# File 'lib/kzg/polynomial.rb', line 171

def ==(other)
  return false unless other.is_a?(Polynomial)
  coeffs == other.coeffs
end

#add(other) ⇒ KZG::Polynomial Also known as: +

Returns a new polynomial that is the sum of the given polynomial and this polynomial.

Parameters:

Returns:

Raises:

  • ArgumentError



85
86
87
88
89
90
91
92
 
# File 'lib/kzg/polynomial.rb', line 85

def add(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "add target must be Polynomial"
  end

  sum = process(coeffs, other.coeffs) { |a, b| a + b }
  Polynomial.new(sum)
end

#div(other) ⇒ KZG::Polynomial Also known as: /

Return a new polynomial that divide self and the given polynomial, i.e. self / other.

Parameters:

Returns:

Raises:

  • (KZG::Error) —

    Occur when other has no non-zero leading coefficient to divide by.



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/kzg/polynomial.rb', line 137

def div(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "divide target must be Polynomial"
  end
  # The long division below divides by this coefficient once per step. Zero has no
  # inverse, and an empty divisor has no coefficient at all; neither denominator names a
  # polynomial of any degree, so refuse both here rather than reach BLS::Fr#invert.
  if other.coeffs.empty? || other.coeffs.last.value.zero?
    raise KZG::Error, "divisor must have a non-zero leading coefficient."
  end

  a = coeffs.dup
  a_pos = a.length - 1
  b_pos = other.coeffs.length - 1
  diff = a_pos - b_pos
  quotient_poly = []

  while diff >= 0
    quot = a[a_pos] / other.coeffs[b_pos]
    i = b_pos
    while i >= 0
      tmp = quot * other.coeffs[i]
      tmp2 = a[diff + i] - tmp
      a[diff + i] = tmp2
      i -= 1
    end
    quotient_poly[diff] = quot
    a_pos -= 1
    diff -= 1
  end
  Polynomial.new(quotient_poly)
end

#eval_at(x) ⇒ BLS::Fr

Evaluate polynomial for given x using Horner's method.

Parameters:

  • x (Integer | BLS::Fr)

Returns:

  • (BLS::Fr) —

    Evaluated value.



69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/kzg/polynomial.rb', line 69

def eval_at(x)
  x = x.is_a?(BLS::Fr) ? x : BLS::Fr.new(x)
  return BLS::Fr::ZERO if coeffs.empty?
  return coeffs.first if x.value.zero?
  last = coeffs.last
  (coeffs.length - 2).step(0, -1) do |i|
    tmp = last * x
    last = tmp + coeffs[i]
  end
  last
end

#multiply(other) ⇒ KZG::Polynomial Also known as: *

Return a new polynomial that multiply self and the given polynomial.

Parameters:

Returns:



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/kzg/polynomial.rb', line 112

def multiply(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "multiply target must be Polynomial"
  end
  # An empty coefficient list is the zero polynomial, and zero times anything is zero.
  # Left to the loop below, an empty operand sizes the result at -1 when both are empty,
  # and otherwise leaves it a row of nils, since the inner loop never runs to fill them.
  return Polynomial.new([]) if coeffs.empty? || other.coeffs.empty?

  new_coeffs = Array.new(coeffs.length + other.coeffs.length - 1)
  coeffs.each.with_index do |a, i|
    other.coeffs.each.with_index do |b, j|
      k = i + j
      new_coeffs[k] = a * b + (new_coeffs[k] || BLS::Fr::ZERO)
    end
  end
  Polynomial.new(new_coeffs)
end

#sub(other) ⇒ KZG::Polynomial Also known as: -

Returns a new polynomial subtracting the given polynomial from self.

Parameters:

Returns:

Raises:

  • ArgumentError



99
100
101
102
103
104
105
 
# File 'lib/kzg/polynomial.rb', line 99

def sub(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "subtract target must be Polynomial"
  end

  Polynomial.new(process(coeffs, other.coeffs) { |a, b| a - b })
end