On Wed, Apr 8, 2015 at 1:28 AM, <jonas.thornv...@gmail.com> wrote: > Den onsdag 8 april 2015 kl. 09:16:24 UTC+2 skrev Ian: >> On Tue, Apr 7, 2015 at 4:35 PM, <jonas.thornv...@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? > > Ok the number of comparissons is linear for each digitplace not exponential.
In other words, the first part of your algorithm where you find the largest digit place takes O(log n) operations. But the second part where you do a search for each digit takes O(b * log n) operations, so the overall number of operations is O(b * log n). If you replace the linear search with a binary search, that's still O(log b * log n). Meanwhile, the division method that I and others have repeatedly suggested does only one comparison and one division per digit, which is just O(log n). Note that this analysis doesn't take into account the complexity of the individual arithmetic operations, but that should affect either algorithm equally. -- https://mail.python.org/mailman/listinfo/python-list
