{"payload":{"allShortcutsEnabled":false,"path":"src/algorithms/math/fast-powering","repo":{"id":458013065,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"ninefyi","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2022-02-11T02:02:31.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/276376?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1644544959.132894","canEdit":false,"refType":"branch","currentOid":"7a37a6b86e76ee22bf93ffd9d01d7acfd79d0714"},"tree":{"items":[{"name":"__test__","path":"src/algorithms/math/fast-powering/__test__","contentType":"directory"},{"name":"README.fr-FR.md","path":"src/algorithms/math/fast-powering/README.fr-FR.md","contentType":"file"},{"name":"README.md","path":"src/algorithms/math/fast-powering/README.md","contentType":"file"},{"name":"fastPowering.js","path":"src/algorithms/math/fast-powering/fastPowering.js","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eFast Powering Algorithm\u003c/h1\u003e\u003ca id=\"user-content-fast-powering-algorithm\" class=\"anchor\" aria-label=\"Permalink: Fast Powering Algorithm\" href=\"#fast-powering-algorithm\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eRead this in other languages:\u003c/em\u003e\n\u003ca href=\"/ninefyi/javascript-algorithms/blob/master/src/algorithms/math/fast-powering/README.fr-FR.md\"\u003efrançais\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eThe power of a number\u003c/strong\u003e says how many times to use the number in a\nmultiplication.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIt is written as a small number to the right and above the base number.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/af4ae9088fdc5bef1ada8e8c003b52b9ef3b41df35351285056f7eb43418a81d/68747470733a2f2f7777772e6d61746873697366756e2e636f6d2f616c67656272612f696d616765732f6578706f6e656e742d382d322e737667\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/af4ae9088fdc5bef1ada8e8c003b52b9ef3b41df35351285056f7eb43418a81d/68747470733a2f2f7777772e6d61746873697366756e2e636f6d2f616c67656272612f696d616765732f6578706f6e656e742d382d322e737667\" alt=\"Power\" data-canonical-src=\"https://www.mathsisfun.com/algebra/images/exponent-8-2.svg\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eNaive Algorithm Complexity\u003c/h2\u003e\u003ca id=\"user-content-naive-algorithm-complexity\" class=\"anchor\" aria-label=\"Permalink: Naive Algorithm Complexity\" href=\"#naive-algorithm-complexity\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eHow to find \u003ccode\u003ea\u003c/code\u003e raised to the power \u003ccode\u003eb\u003c/code\u003e?\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe multiply \u003ccode\u003ea\u003c/code\u003e to itself, \u003ccode\u003eb\u003c/code\u003e times. That\nis, \u003ccode\u003ea^b = a * a * a * ... * a\u003c/code\u003e (\u003ccode\u003eb\u003c/code\u003e occurrences of \u003ccode\u003ea\u003c/code\u003e).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis operation will take \u003ccode\u003eO(n)\u003c/code\u003e time since we need to do multiplication operation\nexactly \u003ccode\u003en\u003c/code\u003e times.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eFast Power Algorithm\u003c/h2\u003e\u003ca id=\"user-content-fast-power-algorithm\" class=\"anchor\" aria-label=\"Permalink: Fast Power Algorithm\" href=\"#fast-power-algorithm\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eCan we do better than naive algorithm does? Yes we may solve the task of\npowering in \u003ccode\u003eO(log(n))\u003c/code\u003e time.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe algorithm uses divide and conquer approach to compute power. Currently the\nalgorithm work for two positive integers \u003ccode\u003eX\u003c/code\u003e and \u003ccode\u003eY\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe idea behind the algorithm is based on the fact that:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor \u003cstrong\u003eeven\u003c/strong\u003e \u003ccode\u003eY\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"X^Y = X^(Y/2) * X^(Y/2)\"\u003e\u003cpre lang=\"text\" class=\"notranslate\"\u003e\u003ccode\u003eX^Y = X^(Y/2) * X^(Y/2)\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eFor \u003cstrong\u003eodd\u003c/strong\u003e \u003ccode\u003eY\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"X^Y = X^(Y//2) * X^(Y//2) * X\nwhere Y//2 is result of division of Y by 2 without reminder.\"\u003e\u003cpre lang=\"text\" class=\"notranslate\"\u003e\u003ccode\u003eX^Y = X^(Y//2) * X^(Y//2) * X\nwhere Y//2 is result of division of Y by 2 without reminder.\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eFor example\u003c/strong\u003e\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)\"\u003e\u003cpre lang=\"text\" class=\"notranslate\"\u003e\u003ccode\u003e2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)\"\u003e\u003cpre lang=\"text\" class=\"notranslate\"\u003e\u003ccode\u003e2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow, since on each step we need to compute the same \u003ccode\u003eX^(Y/2)\u003c/code\u003e power twice we may optimise\nit by saving it to some intermediate variable to avoid its duplicate calculation.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eTime Complexity\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSince each iteration we split the power by half then we will call function\nrecursively \u003ccode\u003elog(n)\u003c/code\u003e times. This the time complexity of the algorithm is reduced to:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"O(log(n))\"\u003e\u003cpre lang=\"text\" class=\"notranslate\"\u003e\u003ccode\u003eO(log(n))\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=LUWavfN9zEo\u0026amp;index=80\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\u0026amp;t=0s\" rel=\"nofollow\"\u003eYouTube\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Exponentiation_by_squaring\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Fast Powering Algorithm","anchor":"fast-powering-algorithm","htmlText":"Fast Powering Algorithm"},{"level":2,"text":"Naive Algorithm Complexity","anchor":"naive-algorithm-complexity","htmlText":"Naive Algorithm Complexity"},{"level":2,"text":"Fast Power Algorithm","anchor":"fast-power-algorithm","htmlText":"Fast Power Algorithm"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fninefyi%2Fjavascript-algorithms%2Ftree%2Fmaster%2Fsrc%2Falgorithms%2Fmath%2Ffast-powering"}},"totalCount":4,"showBranchInfobar":true},"fileTree":{"src/algorithms/math":{"items":[{"name":"binary-floating-point","path":"src/algorithms/math/binary-floating-point","contentType":"directory"},{"name":"bits","path":"src/algorithms/math/bits","contentType":"directory"},{"name":"complex-number","path":"src/algorithms/math/complex-number","contentType":"directory"},{"name":"euclidean-algorithm","path":"src/algorithms/math/euclidean-algorithm","contentType":"directory"},{"name":"euclidean-distance","path":"src/algorithms/math/euclidean-distance","contentType":"directory"},{"name":"factorial","path":"src/algorithms/math/factorial","contentType":"directory"},{"name":"fast-powering","path":"src/algorithms/math/fast-powering","contentType":"directory"},{"name":"fibonacci","path":"src/algorithms/math/fibonacci","contentType":"directory"},{"name":"fourier-transform","path":"src/algorithms/math/fourier-transform","contentType":"directory"},{"name":"horner-method","path":"src/algorithms/math/horner-method","contentType":"directory"},{"name":"integer-partition","path":"src/algorithms/math/integer-partition","contentType":"directory"},{"name":"is-power-of-two","path":"src/algorithms/math/is-power-of-two","contentType":"directory"},{"name":"least-common-multiple","path":"src/algorithms/math/least-common-multiple","contentType":"directory"},{"name":"liu-hui","path":"src/algorithms/math/liu-hui","contentType":"directory"},{"name":"matrix","path":"src/algorithms/math/matrix","contentType":"directory"},{"name":"pascal-triangle","path":"src/algorithms/math/pascal-triangle","contentType":"directory"},{"name":"primality-test","path":"src/algorithms/math/primality-test","contentType":"directory"},{"name":"prime-factors","path":"src/algorithms/math/prime-factors","contentType":"directory"},{"name":"radian","path":"src/algorithms/math/radian","contentType":"directory"},{"name":"sieve-of-eratosthenes","path":"src/algorithms/math/sieve-of-eratosthenes","contentType":"directory"},{"name":"square-root","path":"src/algorithms/math/square-root","contentType":"directory"}],"totalCount":21},"src/algorithms":{"items":[{"name":"cryptography","path":"src/algorithms/cryptography","contentType":"directory"},{"name":"graph","path":"src/algorithms/graph","contentType":"directory"},{"name":"image-processing","path":"src/algorithms/image-processing","contentType":"directory"},{"name":"linked-list","path":"src/algorithms/linked-list","contentType":"directory"},{"name":"math","path":"src/algorithms/math","contentType":"directory"},{"name":"ml","path":"src/algorithms/ml","contentType":"directory"},{"name":"search","path":"src/algorithms/search","contentType":"directory"},{"name":"sets","path":"src/algorithms/sets","contentType":"directory"},{"name":"sorting","path":"src/algorithms/sorting","contentType":"directory"},{"name":"statistics","path":"src/algorithms/statistics","contentType":"directory"},{"name":"string","path":"src/algorithms/string","contentType":"directory"},{"name":"tree","path":"src/algorithms/tree","contentType":"directory"},{"name":"uncategorized","path":"src/algorithms/uncategorized","contentType":"directory"}],"totalCount":13},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":".husky","path":".husky","contentType":"directory"},{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".npmrc","path":".npmrc","contentType":"file"},{"name":".nvmrc","path":".nvmrc","contentType":"file"},{"name":"BACKERS.md","path":"BACKERS.md","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.ar-AR.md","path":"README.ar-AR.md","contentType":"file"},{"name":"README.de-DE.md","path":"README.de-DE.md","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.id-ID.md","path":"README.id-ID.md","contentType":"file"},{"name":"README.it-IT.md","path":"README.it-IT.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.ru-RU.md","path":"README.ru-RU.md","contentType":"file"},{"name":"README.tr-TR.md","path":"README.tr-TR.md","contentType":"file"},{"name":"README.uk-UA.md","path":"README.uk-UA.md","contentType":"file"},{"name":"README.vi-VN.md","path":"README.vi-VN.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":34}},"fileTreeProcessingTime":10.166827,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/ninefyi/javascript-algorithms/branches":{"post":"TA4Ch30FNfvbS2BuhFlhJNv2Aa78iXv4UzwsaXEzQc-UKGQG5gEAq7i8sYysvRMrtaELfNhUCJ0YX9GxtR-I7w"},"/ninefyi/javascript-algorithms/branches/fetch_and_merge/master":{"post":"WhJzZ7ynsvAvIOtR__gcZ6gKYLO1Nj_WPma8DJnKBZ_UtGEjYbgDLWfbK8GKh8TiUntPM5CchcQNDWr4G5_rpg"},"/ninefyi/javascript-algorithms/branches/fetch_and_merge/master?discard_changes=true":{"post":"jGUwE-JDgb2ltYBLnkWyri-QW5Q937RDyHzgrZnAJDkCwyJXP1wwYO1OQNvrOmor1eF0FBh1DlH7FzZZG5XKAA"}}},"title":"javascript-algorithms/src/algorithms/math/fast-powering at master · ninefyi/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.