Russian peasant string repeat in Jass

[oephun]

The title of this post is a clickbait, a Russian peasant doesn't need to do string repeat, obviously. The algorithm also has other names.

What do we mean by string repeat anyway? We want a function that given a string s and an integer n to return: s . s . s ... n times. For example:

stringRepeat("*", 10) // returns '**********'
stringRepeat("Hi", 4) // returns 'HiHiHiHi'

Sounds easy enough, lets give it a try:

function stringRepeat_naive takes string s, integer n returns string
  local string res = ""
  local integer a = -1
  loop
    set a = a + 1
    exitwhen a == n
    set res = res + s
  endloop
  return res
endfunction

Well, it works, but the problem with it, is that in Jass, strings are interned/immutable. In order to construct the result string, the above function also constructs n - 2 other strings, which we didn't ask for. We can print Jass' string table and see for ourselves:

function print takes string s returns nothing
  call DisplayTimedTextToPlayer(GetLocalPlayer(), 0.0, 0.0, 10.0, s)
endfunction

// this function only works in patches < 1.24, not in reforged, for sure
//# +nosemanticerror
function jassStringTableGetEntryAtIdx takes integer idx returns string
  return idx
  return null
endfunction

function printJassStringTable takes nothing returns nothing
  local real sentinelValue = GetRandomReal(-123456.0, 123456.0) // some value that has not been converted to a string, yet
  local string sentinel = R2SW(sentinelValue, 1, 6) // adds a new entry at the end of the string table
  local string s
  local integer a = -1
  loop
    set a = a + 1
    set s = jassStringTableGetEntryAtIdx(a)
    exitwhen sentinel == s
    call print(s)
  endloop
endfunction

Trivia: another programming language with interned strings is Lua, but it has a native implementation for string repeat in its standard library, although it doesn't seem to special case input strings of length 1, anyway...

Here's our improved string repeat function based on Russian peasant multiplication:

function stringRepeat_rpm takes string s, integer n returns string
  local string x
  local string res
  if 0 == n then
    return "" // identity element for string concatenation
  endif

  set x = s
  loop
   exitwhen 0 != (n - ((n / 2) * 2)) // while 'n' is even
    set n = n / 2
    set x = x + x
  endloop

  set res = x
  set n = n / 2
  loop
    exitwhen 0 == n
    set x = x + x
    if 0 != (n - ((n / 2) * 2)) then // if 'n' is odd
      set res = res + x
    endif
    set n = n / 2
  endloop

  return res
endfunction

It works, somehow, don't ask me how, and most importantly, it does way fewer string concatenations, which results in fewer intermediate other string values (which we didn't ask for). How many string concatenations does it do, you might ask? Somewhere in the order of: log2(n) + popcount(n), or something (I'm not sure), which is a lot less than n, for most values of n.

The above algorithm, believe it or not, can also do multiplication (you could have guessed it from the name: Russian peasant multiplication, remember?). Lets leave Jass for now, and use a programming language that is beyond contempt, but will never the less, save us some typing. You've guessed it, it's C++, dun dun duuun.

template <class T, class Integer, class MonoidOperation>
T rpm(T x, Integer n, T identityElementForOp, MonoidOperation op) {
  if (0 == n) { return identityElementForOp; }

  while (0 == (n & 1)) {
    n >>= 1;
    x = op(x, x);
  }

  T res = x;
  n >>= 1;
  while (0 != n) {
    x = op(x, x);
    if (0 != (n & 1)) {
      res = op(res, x);
    }
    n >>= 1;
  }
  return res;
}

The above is a generalized version of our stringRepeat_rpm function. Let's try and use it:

  int64_t x1 = rpm((int64_t)1234, (int64_t)5678, (int64_t)0, std::plus<int64_t>()); // 0 is the identity element for addition, std::plus<int64_t>() is some C++ nonsense
  std::cout << x1 << std::endl; // 1234 * 5678 = 7006652

  int64_t x2 = rpm((int64_t)2, 32, (int64_t)1, std::multiplies<int64_t>()); // 1 is the identity element for multiplication
  std::cout << x2 << std::endl; // 2^32 = 4294967296

  std::string x3 = rpm(std::string("*"), 10, std::string(""), std::plus<std::string>()); // "" is the identity element for string concatenation
  std::cout << x3 << std::endl; // **********
  std::cout << rpm(std::string("Hi"), 4, std::string(""), std::plus<std::string>()) << std::endl; // HiHiHiHi

Cool cool, you might say, but what in the world is a MonoidOperation, you might ask? Is it like that monad is just a monoid in the category of endofunctors nonsense thing or something? No. Well, maybe, I don't know. It's just a special sort of a binary function: (T, T) -> T, that has an identity element (0, 1, "", etc.), and must also be associative.

I am sure, you are not bored at all from reading this post right now, and you are thinking what else can be raised to a power? If you are thinking of matrices, then maybe you've studied linear algebra, or watched that 90s movie. Here's some homework, what does the function homework print?

struct Mat2 {
  int64_t m11, m12;
  int64_t m21, m22;
  Mat2() { }
  Mat2(int64_t a, int64_t b, int64_t c, int64_t d) : m11(a), m12(b), m21(c), m22(d) { }
};

static Mat2 operator*(Mat2 A, Mat2 B) {
  Mat2 R;
  R.m11 = A.m11 * B.m11 + A.m12 * B.m21;
  R.m12 = A.m11 * B.m12 + A.m12 * B.m22;
  R.m21 = A.m21 * B.m11 + A.m22 * B.m21;
  R.m22 = A.m21 * B.m12 + A.m22 * B.m22;
  return R;
}

static void homework(void) {
  Mat2 identity(1, 0, 0, 1);
  for (int64_t a = 0; a < 20; ++a) {
    Mat2 M = rpm(Mat2(1, 1, 1, 0), a, identity, std::multiplies<Mat2>());
    std::cout << a + 1 << ": " << M.m11 << std::endl;
  }
}

Good luck, and remember, if you see a naive loop like in the stringRepeat_naive function, maybe you can speed it up using Russian peasant multiplication.