We present some of our findings on the use of genetic algorithms in evolving arithmetic circuits on gate arrays. We have developed two models of gate arrays and encoded the representation of circuits with two types of chromosomes. In the first we define a rectangular array of gates with functionalities similar to those available on the Xilinx 6200 FPGAs. The representation allows a high level of connectivity between gates and is mediated by a parameter level-back which determines the level of interconnectivity of the circuit. The second representation is based very closely on the Xilinx chip in which cells may only connect to their immediate neighbours, and each cell may carry out a function of its inputs or merely route its inputs to its outputs. We contrast these two representations and show some evolved circuits for both. We demonstrate the great importance of adequate routing resources and its effect on the evolvability of circuits. Some of the evolved circuits (2-bit multiplier) are very unconventional but also very efficient. It is argued that by studying a series of evolved examples it may be possible to discover new and efficient ways of building larger systems.