Finding powers of multiple array pairs

Question

I'm doing a challenge on TalentBuddy that requires you to find the powers of multiple array pairs. Since I got the solution right, but not fast enough, I decided I'd ask for help here.

def fast_power(a, b)
  pairs = a.zip(b)
  pairs.each {|p| puts (p[0] ** p[1]) % 4211}
end

a1 = [long array with 5000 elements]
b1 = [Long array with 5000 elements]

Each element is a number between 0 and 50000.

I have to calculate the value of every element in the first array to the power of every corresponding element in the second array and then modulo that by 4211.

I ran benchmark tests on the data set and here is what I got

14.907000    0.734000    15.641000  (16.818161)

It was supposed to finish in under 2 seconds, so perhaps my algorithm is the issue.

Problem

Searching for a string in a large data store by simply comparing characters would take ages or a huge amount of computing power. We need a way to do it fast!

The first step to building a fast search algorithm is to encode the data in a format that makes search efficient.

A critical operation in the encoding process which we’ll get familiar with a bit later is the exponentiation of integer numbers.

Given a list of pairs of integers (a,b)

Your task is to

Write a function that prints to the standard output (stdout) for each pair the result of (ab) modulo 4211 (one per line)

Note that your function will receive the following arguments:

a - which is an array of integers giving the first element (a) of each pair

b - which is an array of integers giving the second element (b) of each pair

The ith pair is defined by a[i] and b[i].

Data constraints

The length of a, b arrays will not exceed 10000 elements of a, b arrays are integer numbers in the [0, 50000]

Efficiency constraints

Your function is expected to print the requested result and return in less than 2 seconds make sure you don't use any methods that do significant work for you (e.g. pow() in Python)

Answer 1

General Design

The pattern foreach...puts... means that each iteration performs IO. Because IO is slow and blocks writing the results of each multiplication to an output array and then batching the IO by writing the output array all at once is likely to improve performance.

Algorithm

From a pure algorithmic standpoint, using modular powers may significantly reduce computation. This website provides this example:

Let us compute 11⁴³ (mod 13). As we saw before we start with squaring this number:
11² (mod 13) = 121 (mod 13) = 4 (mod 13)
11⁴ (mod 13) = (11²)² (mod 13) = 4² (mod 13) = 16 (mod 13) = 3 (mod 13)
11⁸ (mod 13) = (11⁴)² (mod 13) = 3² (mod 13) = 9 (mod 13)
11¹⁶ (mod 13) = (11⁸)² (mod 13) = 9² (mod 13) = 81 (mod 13) = 3 (mod 13)
11³² (mod 13) = (11¹⁶)² (mod 13) = 3² (mod 13) = 9 (mod 13)

Putting this together (remember that 43 = 32 + 8 + 2 +1), we get

11⁴³ (mod 13) = 11 * 4 * 9 * 9 (mod 13)

Now we do our usual modular multiplication:
11 * 4 * 9 * 9 (mod 13) = 44 * 81 (mod 13) = 5 * 3 (mod 13) = 2 (mod 13).

When tackling a numeric problem and throughput matters, a good place to start is with assuming that the fundamental problem has already been solved and attempting to reduce the specific problem to an existing numeric algorithm. It is hard to embody performant mathematics into code without first knowing what is performant.

Answer 2

I don't know Ruby, but your issue is that you are taking a^b and then taking the modulus. This may mean you are dealing with giant intermediary numbers. The solution is to use a proper modular exponentiation algorithm. This might be built into Ruby, or you might have to roll your own. Here's some pythonish psuedocode for modular exponentiation by squaring:

def exponent_mod(a, b, mod):
    r = a
    while b > 0:
        if b % 2 == 1:
            r = (r * r) % mod
        b = b / 2
        a = (a * a) % mod
    return r

If you're really looking for the highest speed possible, though, this is probably a CPU instruction, if you can find a way to reach that far down the stack.

Answer 3

Array#zip accepts block, so:

def fast_power a, b
    a.zip(b){ |i,j| puts (i**j) % 4211 }
end

or

def fast_power a, b
    puts a.zip(b).map{ |i,j| (i**j) % 4211 }
end

But I believe, that competition is really mathematical and is about to find such X for specified i, that:

(i ** (j % X)) % 4211    ==    (i ** j) % 4211

To reduce powering significantly.

Answer 4

Assuming you can use Ruby's standard library, there's no reason to reinvent the wheel. What you need is contained in the module OpenSSL::BN, namely, the methods OpenSSL::BN#to_bn and OpenSSL::BN#mod_exp. I can't find documentation for the latter method (or for other instance methods in that module). Note:

OpenSSL::BN.instance_methods(false).sort
  #=> [:%, :*, :**, :+, :-, :/, :<<, :<=>, :==, :===, :>>,
  #    :bit_set?, :clear_bit!, :cmp, :coerce, :copy, :eql?, 
  #    :gcd, :lshift!, :mask_bits!, :mod_add, :mod_exp, :mod_inverse,
  #    :mod_mul, :mod_sqr, :mod_sub, :num_bits, :num_bytes, :odd?,
  #    :one?, :prime?, :prime_fasttest?, :rshift!, :set_bit!, :sqr,
  #    :to_bn, :to_i, :to_int, :to_s, :ucmp, :zero?]

but only a fraction of these are shown in the documentation. Perhaps a reader could provide an explanation. In any event, the two methods I mentioned are used as follows (when applied to @Ben's example):

11.to_bn.mod_exp(43,13).to_i #=> 2

You therefore could write:

require 'openssl'

def fast_power(a, b, m)
  puts a.zip(b).map { |i,j| i.to_bn.mod_exp(j,m).to_i }
end

Let's try it:

a = [2,3,4]
b = [1,2,3]
m = 3

fast_power(a, b, m) 
  # 2
  # 0
  # 1

and the brute-force way:

def slow_power(a,b,m)
  puts a.zip(b).map { |i,j| (i**j) % m }
end

slow_power(a,b,m)
  # ...
  # ...
  # (I'm waiting)
  # ...
  # 2
  # 0
  # 1