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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 一般社団法人情報処理学会の論文
• 1983-03-20

著者

• Semba Ichiro

  Department Of Computer Science Ibaraki University

関連論文

• Immunohistochemical Analysis of Cell Proliferation and Suppression of Ameloblastoma with Special Reference to Plexiform and Follicular Ameloblastoma
• Genetic Controls of Susceptibility and Resistance to 4-Nitroquinoline 1-Oxide-induced Tongue Carcinomas in Rats
• Specificities of the Early Body Formation in the Lancelet Embryo
• Expressions of junB and c-fos are enhanced in 4-nitroquinoline 1-oxide-induced rat tongue cancers
• Generation of Permutations by Using an Input Restricted-deque or an Output Restricted-deque
• Generation of Stack Sequences in Lexicographical Order
• 10. BMP4 induce ectopic cartilage formation in the mouse embryonal mandibular process : BMP4 mediates Msx2 and Sox9 expression during chondrogenesis.
• Generation of Permutations by Using a Stack or a Queue
• An Efficient Algorithm for Generating all Partitions of the Set{1, 2, ..., n}
• A Note on Enumerating Combinations in Lexicographical Order
• Systematic Method for Determining the Number of Multiplications Required to Compute x^m, Where m is a Positive Integer
• On Generating and Counting All the Longest Increasing Subsequences
• An O(1) Time Algorithm for Generating Fibonacci Strings(Special Issue on Selected Papers from LA Symposium)
• Generation of Binary Trees from Stack Permutations

もっと見る 閉じる

スポンサーリンク