Suppose you have an infinite supply of coins that are worth respectively 6, 9, and 20 yuan. Then it is possible to hand out e.g. 12 yuan, while it is impossible to hand out 11 yuan. In fact 43 is the largest number that cannot be handed out in this case. In general, let a_1, ..., a_N be N relatively prime positive integers, and consider the largest integer that cannot be written as a positive integral combination of these numbers. This number is known as the Frobenius number, and in this talk we present an exponential but practical algorithm that can compute Frobenius numbers even when the input numbers a_i have a thousand digits. Thus the algorithm can solve some Frobenius problems of a size that has not been solved before. It is in effect an enhancement of the algorithm by Einstein, Lichtblau, Strzebonksi and Wagon.