Systematic Method for Determining the Number of Multiplications Required to Compute x^m Where m is a Positive Integer

• Item type: JInfP(1)
• 公開日: 1983-03-20
• タイトル: Systematic Method for Determining the Number of Multiplications Required to Compute x^m Where m is a Positive Integer
• タイトル / 言語: en
• タイトル: Systematic Method for Determining the Number of Multiplications Required to Compute x^m, Where m is a Positive Integer
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Pure and Applied Sciences College of General Education University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Pure and Applied Sciences, College of General Education, University of Tokyo
• 著者名: Ichiro, Semba
• 著者名(英): Ichiro, Semba
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We consider the problem of determining the number of multiplications required to compute x^m where m is a positive integer. We propose a new systematic method (Euclid method) based on Euclid's algorithm. For a given positive integer n the Euclid method determines the number of multiplications required to compute x^m for every integer m 4≤m≤n successively. The Euclid method gives the minimum number of multiplications for m such that the number of 1's in the binary representation of m is equal to or less than 4. The time required to determine the number of multiplications for every integer m 4≤m≤n is shown to be bounded by cn^2 log_2 n where c is some constant. Computer tests have been done for n=1000 and they have shown that the Euclid method gives the minimum number of multiplications for m such that 4≤m≤622 and 624≤m≤1000.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the problem of determining the number of multiplications required to compute x^m, where m is a positive integer. We propose a new systematic method (Euclid method) based on Euclid's algorithm. For a given positive integer n, the Euclid method determines the number of multiplications required to compute x^m for every integer m, 4≤m≤n, successively. The Euclid method gives the minimum number of multiplications for m such that the number of 1's in the binary representation of m is equal to or less than 4. The time required to determine the number of multiplications for every integer m, 4≤m≤n, is shown to be bounded by cn^2 log_2 n, where c is some constant. Computer tests have been done for n=1000 and they have shown that the Euclid method gives the minimum number of multiplications for m such that 4≤m≤622 and 624≤m≤1000.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of Information Processing; 巻 6, 号 1, p. 31-33, 発行日 1983-03-20
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会