Best search algorithm to find condition within a range

jonas.thornvall at gmail.com jonas.thornvall at gmail.com
Wed Apr 8 09:35:46 CEST 2015


Den onsdag 8 april 2015 kl. 09:16:24 UTC+2 skrev Ian:
> On Tue, Apr 7, 2015 at 4:35 PM,  <jonas.thornvall at gmail.com> wrote:
> > I am not sure you guys realised, that althoug the size of the factors to muliply expands according to base^(exp+1) for each digitplace the number of comparissons needed to reach the digit place (multiple of base^exp+1) is constant with my approach/method.
> 
> No it isn't. You do one comparison on every iteration of your while
> loop, and you do one iteration for every digit. How is that constant?

The for loop should be replaced with a version of binary search making comparisson instead of adding to digit. It will be alot faster with a base using 32-bits.

But the point is the number of operations is linear for each digitplace with my approach/method, you will multiply bigger numbers. But the numbers of comparissons and multiplications is linear over the digitspace.



More information about the Python-list mailing list