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.

Parameters:

  • x (Array(Integer)) —

    The array of x coordinate.

  • y (Array(Integer)) —

    The array of y coordinate.

Returns:



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/kzg/polynomial.rb', line 18

def self.lagrange_interpolate(x, y)
  n = x.length
  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) }
  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:



43
44
45
46
47
 
# File 'lib/kzg/polynomial.rb', line 43

def self.zero_poly(x)
  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 



141
142
143
144
 
# File 'lib/kzg/polynomial.rb', line 141

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



68
69
70
71
72
73
74
75
 
# File 'lib/kzg/polynomial.rb', line 68

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:



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/kzg/polynomial.rb', line 114

def div(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "divide target must be Polynomial"
  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.



52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/kzg/polynomial.rb', line 52

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[coeffs.length - 1]
  (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:



95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/kzg/polynomial.rb', line 95

def multiply(other)
  unless other.is_a?(Polynomial)
    raise ArgumentError, "multiply target must be Polynomial"
  end
  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



82
83
84
85
86
87
88
 
# File 'lib/kzg/polynomial.rb', line 82

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