GPS is among the most widely used satellite systems, incorporated in devices ranging from smartphones, navigation systems, sensors, digital cameras, and bio chips. A GPS receiver calculates its position by locking onto and synchronizing with nearby satellite signals. This synchronization process is quite costly and requires hundreds of millions of hardware multiplications, leading to high power consumption. Many GPS-enabled devices have strict power limitations and would significantly benefit from reducing the complexity of the process. The fastest known algorithm for this problem is based on the Fourier transform and has a complexity of O(n log n), where n is the number of signal samples. The Inventors have developed an even faster GPS synchronization algorithm that reduces the locking complexity to O(n√log n). Further, if the SNR is above a threshold, the algorithm becomes linear (i.e., O(n).