In this case, you know the input is one out of 16384 distinct values (originally 65536, but due to range-reduction and symmetries, you only need to consider one

In this case, you know the input is one out of 16384 distinct values (originally 65536, but due to range-reduction and symmetries, you only need to consider one of them). So you can simply test them all. But in the case of the minimax polynomial, I just got it out of Maple (it can tell you as part of computing it). That's not accounting for floating-point inaccuracies, though.