We demonstrate a novel algorithmic approach for the second-harmonic-generation (SHG) frequency-resolved optical gating (FROG) ultrashort-pulse-measurement technique that always converges and, for complex pulses, is also much faster. It takes advantage of the Paley-Wiener Theorem to retrieve the precise pulse spectrum-half the desired information-directly from the measured trace. It also uses a multi-grid approach, permitting the algorithm to operate on smaller arrays for early iterations and on the complete array for only the final few iterations. We tested this approach on more than 25,000 randomly generated complex pulses with time-bandwidth products up to 100, yielding SHG FROG traces to which noise was added, and have achieved convergence to the correct pulse in all cases. Moreover, convergence occurs in less than half the time for extremely large traces corresponding to extremely complex pulses.