Fixing the problem with large powers
Equipped with all the toolboxes of asymptotic analysis, we will start optimizing our algorithm. However, since we have already seen that our program does not work properly for even moderately large values of power, let's first fix that. There are two ways of fixing this; one is to actually give the amount of space it requires to store all the intermediate products, and the other is to do a trick to limit all the intermediate steps to be within the range of values that the long datatype can support. We will use binomial theorem to do this part.
As a reminder, binomial theorem says (x+y)n = xn + n C1 xn-1 y + n C2 xn-2 y2 + n C3 xn-3 y3 + n C4 xn-4 y4 + … n Cn-1 x1 yn-1 + yn for positive integral values ...
Get Java 9 Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
