Content deleted Content added
Jason Quinn (talk | contribs) m →Basic method: removed un-needed/wanted spaces in example code |
Cup o' Java (talk | contribs) m →Computational complexity: wording: “number of 1 in…” → “number of ones present in…” |
||
Line 56:
==Computational complexity==
A brief analysis shows that such an algorithm uses <math>\lfloor \log_2n\rfloor</math> squarings and at most <math>\lfloor \log_2n\rfloor</math> multiplications, where <math>\lfloor\;\rfloor</math> denotes the [[floor function]]. More precisely, the number of multiplications is one less than the number of
Each squaring results in approximately double the number of digits of the previous, and so, if multiplication of two ''d'' digit numbers is implemented in O(''d''<sup>''k''</sup>) operations for some fixed ''k'' then the complexity of computing ''x''<sup>''n''</sup> is given by:
| |||