| dbo:abstract
|
- L'exponenciació binària és un algorisme que es fa servir per a calcular potències d'un nombre. També se'l coneix com a algorisme d'elevar al quadrat i multiplicar o exponenciació ràpida. Fa servir de forma implícita l'expressió binària de l'exponent. Es pot fer servir de forma força general, per exemple en aritmètica modular. (ca)
- Algoritmus binárního umocňování je algoritmus pro mocnění čísel pomocí převodu z desítkové do binární soustavy. Příklad:Máme spočítat 510. Desítka je v binární soustavě je 1010.
* Při každém kroku algoritmu se číslo umocní na druhou (základ dvojkové soustavy);
* začíná se s číslem x, které je rovno mocněnému číslu (0. krok);
* pokud je v mocnině 1, pak se číslo nejen mocní na základ, ale i násobí původním mocněným číslem. 1: 50: x2 = 251: x2 · 5 = 625 · 5 = 31250: x2 = 9 765 625510 = 9 765 625 (cs)
- Die binäre Exponentiation (auch Square-and-Multiply genannt) ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form mit einer natürlichen Zahl . Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk namens Chandah-sûtra niedergeschrieben. (de)
- La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar. Implícitamente utiliza la expansión binaria del exponente. Es de uso bastante regular en aritmética modular. Este algoritmo es similar al de la duplicación en la multiplicación. (es)
- In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. (en)
- En informatique, l'exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square-and-multiply (« mettre au carré et multiplier »). (fr)
- Machtsverheffing door kwadrateren is een efficiënte rekentechniek om de bewerking machtsverheffing uit te voeren. (nl)
- Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi gdzie oznacza wykładnik obliczanej potęgi. Szybkie podnoszenie do potęgi w praktyce stosuje się do obliczania reszty z dzielenia potęgi przez ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA. (pl)
- Binär exponentiering är en algoritm för att beräkna heltalspotenser, multiplikation av ett tal med sig självt ett antal gånger, på ett effektivt sätt. Idén är att utnyttja exponentens binära representation för att reducera förfarandet till en serie kvadreringar och multiplikationer. Algoritmen kan beskrivas på rekursiv form av Antalet multiplikationer som krävs är av storleksordningen O(log n), vilket då exponenten är stor gör metoden oerhört mycket mer effektiv än direkt upprepad multiplikation. Till exempel krävs endast 25 multiplikationer för att med denna metod beräkna 101000000, 10 gånger sig självt en miljon gånger. Algoritmen används med fördel för att beräkna modulära potenser, en tillämpning som har betydelse inom kryptografi. (sv)
- Повторюване піднесення до квадрата (англ. exponentiating by squaring, repeated squaring) — алгоритм, призначений для піднесення числа x до натурального степеня n за менше число множень, ніж цього вимагає визначення степені. Алгоритм не завжди найоптимальніший: наприклад, піднесення в степінь n = 15 повторюваним піднесенням до квадрата потребує 6 множень, хоча це можна досягти за 5. (uk)
- 在数学和程序设计中，平方求冪（英語：exponentiating by squaring）或快速冪是快速计算一个数（或更一般地说，一个半群的元素，如多項式或方阵）的大正整数乘幂的一般方法。这些算法可以非常通用，例如用在模算數或矩阵幂。对于通常使用加性表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为double-and-add。 (zh)
- Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени. Алгоритмы основаны на том, что для возведения числа в степень не обязательно перемножать число на само себя раз, а можно перемножать уже вычисленные степени. В частности, если степень двойки, то для возведения в степень достаточно число возвести в квадрат раз, затратив при этом умножений вместо . Например, чтобы возвести число в восьмую степень, вместо выполнения семи умножений можно возвести число в квадрат, потом результат возвести ещё раз в квадрат и получить четвёртую степень, и наконец результат ещё раз возвести в квадрат и получить ответ. Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются. Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши. Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 21735 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
|
- May 2020 (en)
- May 2022 (en)
|
| dbp:reason
|
- It should be specified if this logarithm is in base 2, base 2^k, or base e. (en)
|
| dbp:talk
|
- talk:Exponentiation by squaring#Least significant bit is first (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- L'exponenciació binària és un algorisme que es fa servir per a calcular potències d'un nombre. També se'l coneix com a algorisme d'elevar al quadrat i multiplicar o exponenciació ràpida. Fa servir de forma implícita l'expressió binària de l'exponent. Es pot fer servir de forma força general, per exemple en aritmètica modular. (ca)
- Algoritmus binárního umocňování je algoritmus pro mocnění čísel pomocí převodu z desítkové do binární soustavy. Příklad:Máme spočítat 510. Desítka je v binární soustavě je 1010.
* Při každém kroku algoritmu se číslo umocní na druhou (základ dvojkové soustavy);
* začíná se s číslem x, které je rovno mocněnému číslu (0. krok);
* pokud je v mocnině 1, pak se číslo nejen mocní na základ, ale i násobí původním mocněným číslem. 1: 50: x2 = 251: x2 · 5 = 625 · 5 = 31250: x2 = 9 765 625510 = 9 765 625 (cs)
- Die binäre Exponentiation (auch Square-and-Multiply genannt) ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form mit einer natürlichen Zahl . Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk namens Chandah-sûtra niedergeschrieben. (de)
- La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar. Implícitamente utiliza la expansión binaria del exponente. Es de uso bastante regular en aritmética modular. Este algoritmo es similar al de la duplicación en la multiplicación. (es)
- In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. (en)
- En informatique, l'exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square-and-multiply (« mettre au carré et multiplier »). (fr)
- Machtsverheffing door kwadrateren is een efficiënte rekentechniek om de bewerking machtsverheffing uit te voeren. (nl)
- Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi gdzie oznacza wykładnik obliczanej potęgi. Szybkie podnoszenie do potęgi w praktyce stosuje się do obliczania reszty z dzielenia potęgi przez ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA. (pl)
- Повторюване піднесення до квадрата (англ. exponentiating by squaring, repeated squaring) — алгоритм, призначений для піднесення числа x до натурального степеня n за менше число множень, ніж цього вимагає визначення степені. Алгоритм не завжди найоптимальніший: наприклад, піднесення в степінь n = 15 повторюваним піднесенням до квадрата потребує 6 множень, хоча це можна досягти за 5. (uk)
- 在数学和程序设计中，平方求冪（英語：exponentiating by squaring）或快速冪是快速计算一个数（或更一般地说，一个半群的元素，如多項式或方阵）的大正整数乘幂的一般方法。这些算法可以非常通用，例如用在模算數或矩阵幂。对于通常使用加性表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为double-and-add。 (zh)
- Binär exponentiering är en algoritm för att beräkna heltalspotenser, multiplikation av ett tal med sig självt ett antal gånger, på ett effektivt sätt. Idén är att utnyttja exponentens binära representation för att reducera förfarandet till en serie kvadreringar och multiplikationer. Algoritmen kan beskrivas på rekursiv form av Algoritmen används med fördel för att beräkna modulära potenser, en tillämpning som har betydelse inom kryptografi. (sv)
- Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени. Алгоритмы основаны на том, что для возведения числа в степень не обязательно перемножать число на само себя раз, а можно перемножать уже вычисленные степени. В частности, если степень двойки, то для возведения в степень достаточно число возвести в квадрат раз, затратив при этом умножений вместо . Например, чтобы возвести число в восьмую степень, вместо выполнения семи умножений можно возвести число в квадрат, потом результат возвести ещё раз в квадрат и получить четвёртую степень, и наконец результат ещё раз (ru)
|
| rdfs:label
|
- Exponenciació binària (ca)
- Algoritmus binárního umocňování (cs)
- Binäre Exponentiation (de)
- Exponenciación binaria (es)
- Exponentiation by squaring (en)
- Exponentiation rapide (fr)
- Machtsverheffing door kwadrateren (nl)
- Algorytm szybkiego potęgowania (pl)
- Алгоритмы быстрого возведения в степень (ru)
- Binär exponentiering (sv)
- Швидке піднесення до степеня (uk)
- 平方求幂 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
