Should a Unit-test replicate functionality or Test output?

Testing the functionality by using the same implementation, doesn't test anything. If one has a bug in it, the other will as well.

But testing by comparing with an alternative implementation is a valid approach. For example, you might test a iterative (fast) method of calculating fibonacci numbers by comparing it with a trivial recursive, yet slow implementation of the same method.

A variation of this is using an implementation, that only works for special cases. Of course in that case you can use it only for such special cases.

When choosing input values, using random values most of the time isn't very effective. I'd prefer carefully chosen values anytime. In the example you gave, null values and extremely long values which won't fit into a String when concatenated come to mind.

If you use random values, make sure, you have a way to recreate the exact run, with the same random values, for example by logging the seed value, and having a way to set that value at start time.

It's a controversial stance, but I believe that unit testing using Derived Values is far superior to using arbitrary hard-coded input and output.

The issue is that as an algorithm becomes even slightly complex, the relationship between input and output becomes obscure if represented by hard-coded values. The unit test ends up being a postulate. It may work technically, but hurts test maintenability because it leads to Obscure Tests.

Using Derived Values to test against the result establishes a much clearer relationship between test input and expected output.

The argument that this doesn't test anything is simply not true, because any test case will exercise only a part of a path through the SUT, so no single test case will reproduce the entire algorithm being tested, but the combination of tests will do so.

An additional benefit is that you can use fewer unit tests to cover the desired functionality, and even make them more communicative at the same time. The end result is terser and more maintainable unit tests.

In unit testing you should definitely manually come up with test cases (so input, output and what side-effects you are expecting - these will be expectations on your mock objects). You come up with these test cases in a way so that they cover all functionality of your class (e.g. all methods are covered, all branches of all if statements, etc.). Think about it more along the lines of creating documentation of your class by showing all possible usages.

Reimplementing the class is not a good idea, because not only you get obvious code/functionality duplication, but also it is likely that you will introduce the same bugs in this new implementation.