GCHap quickly finds maximum likelihood estimates (MLEs) of frequencies of haplotypes given genotype information on a random sample of individuals. It uses the gene counting method but by excluding haplotypes with zero MLE at an early stage, this implementation uses many orders of magnitude less space and time than naive implementations. A second program, ApproxGCHap, is provided to give alternate estimates for data sets with large numbers of loci or large amounts of missing genotypes.