Number of FLOP (Floating Point Operations) for exponentiation












4












$begingroup$


What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this, and how does it work if $n$ isn't an integer?






algorithms complexity-theory arithmetic floating-point







share|cite|improve this question









New contributor




Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    4












    $begingroup$


    What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this, and how does it work if $n$ isn't an integer?






    algorithms complexity-theory arithmetic floating-point







    share|cite|improve this question









    New contributor




    Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      4












      4








      4


      1



      $begingroup$


      What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this, and how does it work if $n$ isn't an integer?






      algorithms complexity-theory arithmetic floating-point







      share|cite|improve this question









      New contributor




      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this, and how does it work if $n$ isn't an integer?






      algorithms complexity-theory arithmetic floating-point




      algorithms complexity-theory arithmetic floating-point






      share|cite|improve this question









      New contributor




      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question









      New contributor




      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question








      edited 10 hours ago









      xskxzr

      3,66511031




      3,66511031






      New contributor




      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 12 hours ago









      Mr. EivindMr. Eivind

      1235




      1235




      New contributor




      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Mr. Eivind is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          3 Answers
          3






          active

          oldest

          votes


















          3












          $begingroup$


          Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...




          There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.




          • Convert the non-negative integer power to base 2.

          • Count the number of ones in this representation.

          • Add the power of two corresponding to the most significant non-zero bit in this representation.

          • Subtract one.


          This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.




          ... and how does it work if $n$ isn't an integer?




          There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $exp(nln(x))$.)






          share|cite|improve this answer











          $endgroup$





















            4












            $begingroup$

            Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Thanks, don't know why that didn't come to my mind...
              $endgroup$
              – Mr. Eivind
              7 hours ago





















            3












            $begingroup$

            You can use the formula
            $$ x^y = exp (y ln x). $$



            If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.






            share|cite|improve this answer









            $endgroup$













              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "419"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: false,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });






              Mr. Eivind is a new contributor. Be nice, and check out our Code of Conduct.










              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105026%2fnumber-of-flop-floating-point-operations-for-exponentiation%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              3 Answers
              3






              active

              oldest

              votes








              3 Answers
              3






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              3












              $begingroup$


              Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...




              There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.




              • Convert the non-negative integer power to base 2.

              • Count the number of ones in this representation.

              • Add the power of two corresponding to the most significant non-zero bit in this representation.

              • Subtract one.


              This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.




              ... and how does it work if $n$ isn't an integer?




              There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $exp(nln(x))$.)






              share|cite|improve this answer











              $endgroup$


















                3












                $begingroup$


                Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...




                There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.




                • Convert the non-negative integer power to base 2.

                • Count the number of ones in this representation.

                • Add the power of two corresponding to the most significant non-zero bit in this representation.

                • Subtract one.


                This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.




                ... and how does it work if $n$ isn't an integer?




                There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $exp(nln(x))$.)






                share|cite|improve this answer











                $endgroup$
















                  3












                  3








                  3





                  $begingroup$


                  Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...




                  There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.




                  • Convert the non-negative integer power to base 2.

                  • Count the number of ones in this representation.

                  • Add the power of two corresponding to the most significant non-zero bit in this representation.

                  • Subtract one.


                  This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.




                  ... and how does it work if $n$ isn't an integer?




                  There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $exp(nln(x))$.)






                  share|cite|improve this answer











                  $endgroup$




                  Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...




                  There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.




                  • Convert the non-negative integer power to base 2.

                  • Count the number of ones in this representation.

                  • Add the power of two corresponding to the most significant non-zero bit in this representation.

                  • Subtract one.


                  This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.




                  ... and how does it work if $n$ isn't an integer?




                  There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $exp(nln(x))$.)







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited 3 hours ago

























                  answered 4 hours ago









                  David HammenDavid Hammen

                  1764




                  1764























                      4












                      $begingroup$

                      Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.






                      share|cite|improve this answer









                      $endgroup$













                      • $begingroup$
                        Thanks, don't know why that didn't come to my mind...
                        $endgroup$
                        – Mr. Eivind
                        7 hours ago


















                      4












                      $begingroup$

                      Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.






                      share|cite|improve this answer









                      $endgroup$













                      • $begingroup$
                        Thanks, don't know why that didn't come to my mind...
                        $endgroup$
                        – Mr. Eivind
                        7 hours ago
















                      4












                      4








                      4





                      $begingroup$

                      Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.






                      share|cite|improve this answer









                      $endgroup$



                      Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered 9 hours ago









                      gnasher729gnasher729

                      10.9k1217




                      10.9k1217












                      • $begingroup$
                        Thanks, don't know why that didn't come to my mind...
                        $endgroup$
                        – Mr. Eivind
                        7 hours ago




















                      • $begingroup$
                        Thanks, don't know why that didn't come to my mind...
                        $endgroup$
                        – Mr. Eivind
                        7 hours ago


















                      $begingroup$
                      Thanks, don't know why that didn't come to my mind...
                      $endgroup$
                      – Mr. Eivind
                      7 hours ago






                      $begingroup$
                      Thanks, don't know why that didn't come to my mind...
                      $endgroup$
                      – Mr. Eivind
                      7 hours ago













                      3












                      $begingroup$

                      You can use the formula
                      $$ x^y = exp (y ln x). $$



                      If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.






                      share|cite|improve this answer









                      $endgroup$


















                        3












                        $begingroup$

                        You can use the formula
                        $$ x^y = exp (y ln x). $$



                        If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.






                        share|cite|improve this answer









                        $endgroup$
















                          3












                          3








                          3





                          $begingroup$

                          You can use the formula
                          $$ x^y = exp (y ln x). $$



                          If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.






                          share|cite|improve this answer









                          $endgroup$



                          You can use the formula
                          $$ x^y = exp (y ln x). $$



                          If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered 11 hours ago









                          Yuval FilmusYuval Filmus

                          193k14181345




                          193k14181345






















                              Mr. Eivind is a new contributor. Be nice, and check out our Code of Conduct.










                              draft saved

                              draft discarded


















                              Mr. Eivind is a new contributor. Be nice, and check out our Code of Conduct.













                              Mr. Eivind is a new contributor. Be nice, and check out our Code of Conduct.












                              Mr. Eivind is a new contributor. Be nice, and check out our Code of Conduct.
















                              Thanks for contributing an answer to Computer Science Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid …



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105026%2fnumber-of-flop-floating-point-operations-for-exponentiation%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              -

                              Popular posts from this blog

                              Aikido

                              Image
                              Ĉi tiu artikolo citas neniun fonton . Vi povas plibonigi ĝin, aldonante fidindajn fontojn. Senfontaj asertoj povas esti forigitaj.  (Novembro 2012) Aikido Japana Nomo: Kanji 合気道 Hiragana あいきどう Spiradaj ekzercoj Aikido , aŭ Ajkido , estas moderna japana luktarto (Shin Budo) kompilita de Ueshiba Morihei dum la periodo inter la 1930-aj jaroj ĝis 1960-aj jaroj. Ĝi estas senperforta kaj multaj el ĝiaj teĥnikoj evoluis el Daito-Rjuo (speco de ĵuĵicuo) kaj el glava batalado. La filozofio de aikido devenis ĉefe de la religio Oomoto pro la kontaktoj inter O´Sensei ("granda majstro", esprimo uzata de la aikidistoj por nomi Ueshiba Morihei) kaj Deguchi Onisaburo Sensei el Oomoto. Oni konsideras, ke aikidisto havu iom da spiriteco, interalie pri la uzo de la Ĉi, KI, ĝi postulas nenuran teknikan trejnon. La nepo de la kreinto, Ueshiba Moriteru, nun estas "Doshu", tiu kiu montras la vojon. Enhavo 1 Aikido - Oomoto - Esperanto...
                              Read more

                              Tivadar Csontváry Kosztka

                              Image
                              Ponto de Mostar Tivadar Csontváry Kosztka [tivadar ĉontvAri kostka], hungare Csontváry Kosztka Tivadar estis indivudueca hungara pentristo kaj apotekisto. En la hungara medio sufiĉas Csontváry. Memportreto de Csontváry Ruinoj de greka teatro en Taormina Pilgrimado al cedroj Soleca cedro Skulptaĵo pri Csontváry Enhavo 1 Vivo 2 Verkaro 3 Postvivo 4 Figuro de Csontváry en artoj 4.1 Filmoj 4.2 Romano 4.3 Dramo 4.4 Esperanto Vivo | Csontváry naskiĝis en Kisszeben en la 5-an de julio 1853 (kiel Kosztka Mihály Tivadar ), li mortis en Budapeŝto, en la 20-a de junio 1919. Lia patro Kosztka László estis apotekisto, tiun profesion praktikadis ankaŭ Tivadar. En 1880 antaŭ la apoteko li desegnis sur apoteka papereto ĉaron kun bovoj. Tiun ekvidis la ĉefapotekisto kaj ekkriis: „Ja vi naskiĝis pentristo!”. Tiam Csontváry aŭdis ankaŭ dian voĉon: „Vi estos la plej granda sunovoja pentristo de la mondo, pli granda, ol Raf...
                              Read more

                              Metroo de Marsejlo

                              Image
                              Metroo de Marsejlo Logoo Ĝeneralaj informoj Loko Marsejlo  Francio Transportsistema speco Metroo Komenco de trafiko 26-a de novembro 1977 Teknikaj informoj Longeco de sistemo 21,6 km Nombro de linioj 2 Nombro de veturiloj 36 Nombro de stacioj 28 (+ 2 interkonektoj) Aliaj informoj Traklarĝo 1 435 mm Transportisto RTM v   •   d   •   r La Metroo de Marsejlo (Francio) (france  Métro de Marseille ) estas metrosistemo funkcianta per pneŭoj derivita de la teknologio disvolvigita de la RATP por la metroo de Parizo. Ĝi malfermiĝis unuafoje al la publiko en la jaro 1977. Ĝi konsistas el du linioj, parte subteraj, kun longeco de entute 21,6 km , situantaj nur en la municipo Marsejlo. Nuntempe konstruiĝas du plilongigaĵoj. Enhavo 1 Mapo 2 Metrolinioj 2.1 Linio 1 2.2 Linio 2 3 Vidu ankaŭ 4 Eksteraj ligiloj Mapo | Mapo de la metroo de Marsejlo Metrolinioj | ...
                              Read more