Module: HenselCode::ModularArithmetic

Included in:
Polynomial
Defined in:
lib/hensel_code/modular_arithmetic.rb

Overview

modular arithmetic class

Instance Method Summary collapse

Instance Method Details

#cauchy_product(prime, coefficients1, coefficients2) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
 
# File 'lib/hensel_code/modular_arithmetic.rb', line 6

def cauchy_product(prime, coefficients1, coefficients2)
  product = []
  carry = 0
  (0..coefficients1.size - 1).each do |i|
    sum = 0
    (0..i).each { |j| sum += (coefficients1[j] * coefficients2[i - j]) }
    product << ((carry + sum) % prime)
    carry = (carry + sum) / prime
  end
  product
end

#multiplication(prime, coefficients1, coefficients2) ⇒ Object 



18
19
20
21
22
23
24
25
26
 
# File 'lib/hensel_code/modular_arithmetic.rb', line 18

def multiplication(prime, coefficients1, coefficients2)
  partial_multiplications = []
  coefficients2.each_with_index do |c1, i|
    rows = multiplication_inner_loop(prime, coefficients1, coefficients2, c1, i)
    partial_multiplications << rows
    rows.append(*([0] * i))
  end
  sum_of_partial_multiplications(partial_multiplications)
end