It took me three months to come up with a solution—which came to me, incidentally, lying in my bed at six in the morning. The sun was rising, the birds were singing, and I finally had an idea. The reasoning was as follows:
Applying half of the changes has a small chance of getting a consistent build; the risk of skipping a dependent change is simply too high. On the other hand, if we get a consistent build (or a "resolved" outcome), we can very quickly narrow down the set of changes.
On the other hand, applying individual changes has a far greater chance of getting something meaningful—in particular, if the version being changed was already consistent. As an example, think of changing a single function; unless its interface changes, we will most likely get a running program. On the other hand, trying out one change after the other would still take ages.
Therefore, I'd call for a compromise: I would start with two halves. If neither half of the changes would result in a testable build, I would split the set of changes into four subsets instead, and then apply each subset individually to the gdb 4.16 source. In addition, I would also unapply the subset from the gdb 4.17 source (which would be realized by applying the complement of the subset to the gdb 4.16 source).
Splitting in four (rather than two) would mean that smaller change sets would be applied, which means that the changed versions would be closer to the (working) original versions—and ...