Finding powers of multiple array pairs 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)
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 1143 (mod 13). As we saw before we start with squaring this number:

112 (mod 13) = 121 (mod 13) = 4 (mod 13)

114 (mod 13) = (112)2 (mod 13) = 42 (mod 13) = 16 (mod 13) = 3 (mod 13)

118 (mod 13) = (114)2 (mod 13) = 32 (mod 13) = 9 (mod 13)

1116 (mod 13) = (118)2 (mod 13) = 92 (mod 13) = 81 (mod 13) = 3 (mod 13)

1132 (mod 13) = (1116)2 (mod 13) = 32 (mod 13) =  9 (mod 13)


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

 1143 (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.