Purpose: A fast and accurate intraoperative registration method is important for Computer-Aided Orthopedic Surgery (CAOS). A-mode ultrasound (US) is able to acquire bone surface data in a non-invasive manner. To utilize A-mode US in CAOS, a suitable registration algorithm is necessary with a small number of registration points and the presence of measurement errors. Therefore, we investigated the effects of (1) the number of registration points and (2) the Ultrasound Point Localization Error (UPLE) on the overall registration accuracy. Methods: We proposed a new registration method (ICP-PS), including the Iterative Closest Points (ICP) algorithm and a Perturbation Search algorithm. This method enables to avoid getting stuck in the local minimum of ICP iterations and to find the adjacent global minimum. This registration method was subsequently validated in a numerical simulation and a cadaveric experiment using a 3D-tracked A-mode US system. Results: The results showed that ICP-PS outperformed the standard ICP algorithm. The registration accuracy improved with the addition of ultrasound registration points. In the numerical simulation, for 25 sample points with zero UPLE, the averaged registration error of ICP-PS reached 0.25 mm, while 1.71 mm for ICP, decreasing by 85.38%. In the cadaver experiment, using 25 registration points, ICP-PS achieved an RMSE of 2.81 mm relative to 5.84 mm for the ICP, decreasing by 51.88%. Conclusions: The simulation approach provided a well-defined framework for estimating the necessary number of ultrasound registration points and acceptable level of UPLE for a given required level of accuracy for intraoperative registration in CAOS. ICP-PS method is suitable for Amode US based intraoperative registration. This study would facilitate the application of Amode US probe in registering the point cloud to a known shape model, which also has the potential for accurately estimating bone position and orientation for skeletal motion tracking and surgical navigation.