How do you do it? Well, one way to do it is to make sure you cover all the possible use cases and test for those. But that can go into the thousands. There's no hope you can test all of those cases in a short period of time (let's say 3 months or so...). Well, now we just made it even more difficult: we have to release every 4 weeks. Oh, and did we tell you that we are changing the architecture as we go? Incrementally of course, but nevertheless.
How would you cope with a situation like this? Yes, the answer is you would not (just setting up my answer... wait for it). The answer is that you must make sure you are never in the this position!
How to avoid being in a position to have to test a large piece of code with large code changes ongoing and still release every 4 weeks? Test automation. All tests that can be automated should be so, and at all levels: unit, integration, system, performance, reliability, you name it.
The point is this, testers brain power is wasted if all they can/are allowed to do is to test against a static specification with a few tests added every 4 weeks. That's not the best way to get the most out of the smart people you have in your company. If you are not a tester, just imagine yourself having to go over the same 40-50 pages of tests every single iteration, month-in, month-out. How long would it take you to quit? I suspect not too much...
Additionally, if you consider the effect of familiarity (reading the same test cases 2-3 times a month for several months) on the quality of the testing you quickly realize that manual testing against a script over and over again is the best way to get problems to escape even the most dedicated tester's eyes.
So, what next? Well, test automation is one solution. The next step is to train your testers to be expert "breakers", their goal should be to find more and more ways in which to break your software. Specifically ways you have not thought about!
The message is: testers are way too valuable and way to smart to have them spend their work-hours going over a brainless set of tests-to-spec, you will get a lot more from your test team if you automate the repetitive tasks and let the loose on your code.
This is, BTW, what Richard Feynman advocated when he reviewed the Challenger disaster in the 80's:
"(...) take an adversary attitude to the software development group, and tests and verifies the software as if it were a customer of the delivered product."