title: Using omp parallel for in multiplication algorithm (BigInt multiplication)
body: <p>For educational purpose I'm developing c++ library for operating with large numbers represented as vectors of chars (<code>vector&lt;char&gt;</code>).</p>
  <p>Here is algorithm that I am using for multiplication:</p>
  <pre><code>string multiplicationInner(CharVector a, CharVector b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
  
    IntVector stack(a.size() + b.size() + 1);
  
    int i, j;
    for (i = 0; i &lt; a.size(); i++)
      for (j = 0; j &lt; b.size(); j++)
        stack[i + j] += charToInt(a[i]) * charToInt(b[j]);
   
  
    for (int i = 0; i &lt; stack.size(); i++) {
      int num = stack[i] % 10;
      int move = stack[i] / 10;
      stack[i] = num;
  
      if (stack[i + 1])
        stack[i + 1] += move;
      else if (move)
        stack[i + 1] = move;
    }
  
    CharVector stackChar = intVectorToCharVector(&amp;stack);
    deleteZerosAtEnd(&amp;stackChar);
    reverse(stackChar.begin(), stackChar.end());
  
    return charVectorToString(&amp;stackChar);
  };
  </code></pre>
  <p>This function is called billion times in my program, so I would like to implement #pragma omp parallel for in it.</p>
  <p>My question is: How can i parallelize first cycle?</p>
  <p>This is what I have tried:</p>
  <pre><code>int i, j;
    #pragma omp parallel for
    for (i = 0; i &lt; a.size(); i++) {
      for (j = 0; j &lt; b.size(); j++)
        stack[i + j] += charToInt(a[i]) * charToInt(b[j]);
    }
  </code></pre>
  <p>Algorithm stops working properly.
  Advice needed.</p>
  <p>Edit:
  This variant works, but (with omp parallel for) benchmark shows it is 15x-20x slower than without it. (CPU: M1 Pro, 8 cores)</p>
  <pre><code>#pragma omp parallel for schedule(dynamic)
    for (int k = 0; k &lt; a.size() + b.size(); k++) { 
      for (int i = 0; i &lt; a.size(); i++) {
        int j = k - i;
        if (j &gt;= 0 &amp;&amp; j &lt; b.size()) {
          stack[k] += charToInt(a[i]) * charToInt(b[j]);
        }
      }
    }
  </code></pre>
  <p>This is part of my program, where multiplication is called most often. (Miller-Rabin test)</p>
  <pre><code>BigInt modularExponentiation(BigInt base, BigInt exponent, BigInt mod) {
    BigInt x = B_ONE; // 1
    BigInt y = base;
  
    while (exponent &gt; B_ZERO) { // while exponent &gt; 0
      if (isOdd(exponent))
        x = (x * y) % mod;
      y = (y * y) % mod;
      exponent /= B_TWO; // exponent /= 2
    }
  
    return (x % mod);
  };
  
  bool isMillerRabinTestOk(BigInt candidate) {
    if (candidate &lt; B_TWO)
      return false;
  
    if (candidate != B_TWO &amp;&amp; isEven(candidate))
      return false;
  
    BigInt canditateMinusOne = candidate - B_ONE;
    BigInt s = canditateMinusOne;
    while (isEven(s))
      s /= B_TWO;
  
    for (int i = 0; i &lt; MILLER_RABIN_TEST_ITERATIONS; i++) {
      BigInt a = BigInt(rand()) % canditateMinusOne + B_ONE;
      BigInt temp = s;
      BigInt mod = modularExponentiation(a, temp, candidate);
  
      while (temp != canditateMinusOne &amp;&amp; mod != B_ONE &amp;&amp; mod != canditateMinusOne) {
        mod = (mod * mod) % candidate;
        temp *= B_TWO;
      }
  
      if (mod != canditateMinusOne &amp;&amp; isEven(temp))
        return false;
    }
  
    return true;
  };
  </code></pre>