| dbo:abstract
|
- L'algorisme de Karatsuba és un algorisme de multiplicació ràpid. Va ser descobert per Anatoli Karatsuba el 1960, i publicat dos anys més tard. Redueix la multiplicació de dos nombres de n dígits a com a molt multiplicacions d'un dígit en general (i exactament quan n és una potència de 2).És per tant asimptomàticament més ràpid que l'algorisme tradicional, que requereix multiplicacions d'un dígit. Per exemple, l'algorisme de Karatsuba requereix 3¹⁰ = 59049 multiplicacions d'un dígit per multiplicar dos nombres de 1024 dígits (n = 1024 = 2¹⁰), mentre que l'algorisme tradicional requereix (2¹⁰) ² = 1048576 (17.75 vegades més ràpid). L'algorisme de Karatsuba va ser el primer algorisme de multiplicació asimptòticament més ràpid que l'algorisme quadràtic tradicional. L' (1963) és una generalització més ràpida del mètode de Karatsuba, i l' (1971) és encara més ràpid per n suficientment grans. L'algorisme de Karatsuba és un clar exemple del paradigma divideix i venceràs, concretament de l'algorisme de partició binària. (ca)
- Karacubovo násobení je asymptoticky rychlý , který v roce 1960 vymyslel sovětský matematik Anatolij Alexejevič Karacuba jako tehdy asymptoticky nejrychlejší algoritmus násobení . Jeho složitost je pro dvě n-ciferná čísla nanejvýš jednociferných násobení. Tradiční přitom vyžaduje násobení. Od doby Karacubova objevu byly vymyšleny algoritmy asymptoticky ještě rychlejší, a . Karacubův algoritmus je přesto stále používán, protože je pro určitou délku vstupních čísel v praxi nejrychlejší. (cs)
- La algoritmo de Karacuba estas algoritmo por multipliko de grandaj nombroj. Ĝi ebligas fari la multiplikon de du n-ciferaj nombroj per maksimume unu-ciferaj multiplikoj ĝenerale. La kvanto de la unu-ciferaj multiplikoj estas akurate se n estas entjera potenco de 2. Ĝi estas pro tio pli rapida ol la klasika longa multiplika algoritmo, kiu postulas n2 unu-ciferaj multiplikojn. Se ekzemple n = 210 = 1024, la kvanto de la unu-ciferaj multiplikoj ĉe algoritmo de Karacuba estas 310 = 59049; kaj la kvanto de la unu-ciferaj multiplikoj ĉe klasika longa multipliko estas (210)2 = 1048576. (eo)
- Der Karazuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier großer ganzer Zahlen. Er wurde 1960 von dem 23-jährigen Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анатолий Алексеевич Карацуба) entwickelt und 1962 veröffentlicht. Bezeichnet die Bit-Anzahl der beiden Zahlen und ein Landau-Symbol, so ist der Algorithmus mit einer Laufzeitkomplexität von deutlich schneller als die Schulmethode. Diese (und auch deren implizite Übertragung auf das Binärsystem in Form der russischen Bauernmultiplikation) besitzt eine Laufzeitkomplexität von . Die Methode von Karazuba wurde zum Vorbild für das Teile-und-herrsche-Prinzip in der Informatik. Für hinreichend große Zahlen ist der Karazuba-Algorithmus langsamer als seine Verallgemeinerungen, wie der Toom-Cook-Algorithmus (1965) und der Schönhage-Strassen-Algorithmus (1971), dessen Laufzeitkomplexität beträgt und der aus Sicht der Komplexitätstheorie als schnellster Algorithmus zur Multiplikation großer ganzer Zahlen galt, bis 2007 eine Weiterentwicklung mit einer (bisher nur theoretisch) geringeren Laufzeitkomplexität vorstellte. (de)
- The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. For example, the traditional algorithm requires (210)2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the Karatsuba algorithm requires 310 = 59,049 thus being ~17.758 times faster. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n. (en)
- El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962. El algoritmo consigue reducir la múltiplicación de dos números de n dígitos a como máximo multiplicaciones de un dígito. Es, por lo tanto, más rápido que el algoritmo clásico, que requiere n2 productos de un dígito. Si n = 210 = 1024, en particular, el cómputo final exacto es 310 = 59.049 y (210)2 = 1.048.576, respectivamente. El algoritmo de Toom-Cook es una generalización más rápida del de Karatsuba. Para un n suficientemente grande, el algoritmo de Schönhage-Strassen es mejor que el algoritmo de Karatsuba. El algoritmo de Karatsuba es un claro ejemplo del paradigma divide y vencerás, concretamente del algoritmo de partición binaria. (es)
- En informatique, l'algorithme de Karatsuba est un algorithme pour multiplier rapidement deux nombres de n chiffres avec une complexité temporelle en O(nlog2(3)) ≈ O(n1,585) au lieu de O(n2) pour la méthode naïve. Il a été développé par Anatolii Alexevich Karatsuba en 1960 et publié en 1962 . (fr)
- カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者のAnatolii Alexeevitch Karatsuba（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。 (ja)
- 카라추바 알고리즘은 소련의 수학자 가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다.이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다. 은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다. 카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다. (ko)
- L'algoritmo di Karatsuba (1960) è un algoritmo di moltiplicazione rapida (subquadratica) per moltiplicare grandi numeri interi o polinomi. È stata proposta da Anatolii Alexeevich Karatsuba in un articolo scritto insieme a nel 1962. La sua complessità è Θ, questo la rende più rapida della moltiplicazione ingenua che ha complessità Θ(n2). (it)
- Assenálio ou Método de Multiplicação de Karatsuba é um método utilizado para multiplicar números grandes eficientemente, descoberto por Anatolii Alexeievitch Karatsuba em 1960; e publicado em 1962. Este algoritmo reduz a multiplicação de dois números de dígitos a no máximo: multiplicações de dígitos simples e a exatamente quando é uma potência de 2. É mais rápido que o método usual de multiplicação longa, que necessita de multiplicações de um dígito simples. Por exemplo, seja . O cálculo final exato será e , respectivamente. O algoritmo de Toom-Cook é uma generalização mais rápida do algoritmo de Karatsuba. Para suficientemente grande, o algoritmo de Schönhage-Strassen é melhor que o algoritmo de Karatsuba. O algoritmo de Karatsuba é um exemplo de algoritmo do tipo divisão e conquista, e do modelo de algoritmo de partição binária. A classificação de algoritmos do tipo divisão e conquista foi usada pela primeira vez para este método. (pt)
- Algorytm Karacuby – algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962 roku. Jego złożoność obliczeniowa wynosi Θ w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego dla odpowiednio dużych wartości n. Mnożenie niewielkich liczb jest szybsze przy pomocy mniej skomplikowanego algorytmu klasycznego. (pl)
- Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью: . Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности. (ru)
- Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。 值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。 (zh)
- Множення Карацуби — метод швидкого множення, який дозволяє перемножувати два n-значних числа зі складністю обчислення: Цей підхід відкрив новий напрямок в обчислювальній математиці. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13620 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
|
- Karatsuba Multiplication (en)
|
| dbp:urlname
|
- KaratsubaMultiplication (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Karacubovo násobení je asymptoticky rychlý , který v roce 1960 vymyslel sovětský matematik Anatolij Alexejevič Karacuba jako tehdy asymptoticky nejrychlejší algoritmus násobení . Jeho složitost je pro dvě n-ciferná čísla nanejvýš jednociferných násobení. Tradiční přitom vyžaduje násobení. Od doby Karacubova objevu byly vymyšleny algoritmy asymptoticky ještě rychlejší, a . Karacubův algoritmus je přesto stále používán, protože je pro určitou délku vstupních čísel v praxi nejrychlejší. (cs)
- La algoritmo de Karacuba estas algoritmo por multipliko de grandaj nombroj. Ĝi ebligas fari la multiplikon de du n-ciferaj nombroj per maksimume unu-ciferaj multiplikoj ĝenerale. La kvanto de la unu-ciferaj multiplikoj estas akurate se n estas entjera potenco de 2. Ĝi estas pro tio pli rapida ol la klasika longa multiplika algoritmo, kiu postulas n2 unu-ciferaj multiplikojn. Se ekzemple n = 210 = 1024, la kvanto de la unu-ciferaj multiplikoj ĉe algoritmo de Karacuba estas 310 = 59049; kaj la kvanto de la unu-ciferaj multiplikoj ĉe klasika longa multipliko estas (210)2 = 1048576. (eo)
- En informatique, l'algorithme de Karatsuba est un algorithme pour multiplier rapidement deux nombres de n chiffres avec une complexité temporelle en O(nlog2(3)) ≈ O(n1,585) au lieu de O(n2) pour la méthode naïve. Il a été développé par Anatolii Alexevich Karatsuba en 1960 et publié en 1962 . (fr)
- カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者のAnatolii Alexeevitch Karatsuba（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。 (ja)
- 카라추바 알고리즘은 소련의 수학자 가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다.이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다. 은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다. 카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다. (ko)
- L'algoritmo di Karatsuba (1960) è un algoritmo di moltiplicazione rapida (subquadratica) per moltiplicare grandi numeri interi o polinomi. È stata proposta da Anatolii Alexeevich Karatsuba in un articolo scritto insieme a nel 1962. La sua complessità è Θ, questo la rende più rapida della moltiplicazione ingenua che ha complessità Θ(n2). (it)
- Algorytm Karacuby – algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962 roku. Jego złożoność obliczeniowa wynosi Θ w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego dla odpowiednio dużych wartości n. Mnożenie niewielkich liczb jest szybsze przy pomocy mniej skomplikowanego algorytmu klasycznego. (pl)
- Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью: . Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности. (ru)
- Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。 值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。 (zh)
- Множення Карацуби — метод швидкого множення, який дозволяє перемножувати два n-значних числа зі складністю обчислення: Цей підхід відкрив новий напрямок в обчислювальній математиці. (uk)
- L'algorisme de Karatsuba és un algorisme de multiplicació ràpid. Va ser descobert per Anatoli Karatsuba el 1960, i publicat dos anys més tard. Redueix la multiplicació de dos nombres de n dígits a com a molt multiplicacions d'un dígit en general (i exactament quan n és una potència de 2).És per tant asimptomàticament més ràpid que l'algorisme tradicional, que requereix multiplicacions d'un dígit. L'algorisme de Karatsuba és un clar exemple del paradigma divideix i venceràs, concretament de l'algorisme de partició binària. (ca)
- Der Karazuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier großer ganzer Zahlen. Er wurde 1960 von dem 23-jährigen Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анатолий Алексеевич Карацуба) entwickelt und 1962 veröffentlicht. (de)
- The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. For example, the traditional algorithm requires (210)2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the Karatsuba algorithm requires 310 = 59,049 thus being ~17.758 times faster. (en)
- El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962. El algoritmo consigue reducir la múltiplicación de dos números de n dígitos a como máximo multiplicaciones de un dígito. Es, por lo tanto, más rápido que el algoritmo clásico, que requiere n2 productos de un dígito. Si n = 210 = 1024, en particular, el cómputo final exacto es 310 = 59.049 y (210)2 = 1.048.576, respectivamente. (es)
- Assenálio ou Método de Multiplicação de Karatsuba é um método utilizado para multiplicar números grandes eficientemente, descoberto por Anatolii Alexeievitch Karatsuba em 1960; e publicado em 1962. Este algoritmo reduz a multiplicação de dois números de dígitos a no máximo: multiplicações de dígitos simples e a exatamente quando é uma potência de 2. É mais rápido que o método usual de multiplicação longa, que necessita de multiplicações de um dígito simples. Por exemplo, seja . O cálculo final exato será e , respectivamente. (pt)
|
| rdfs:label
|
- Algorisme de Karatsuba (ca)
- Karacubovo násobení (cs)
- Karazuba-Algorithmus (de)
- Algoritmo de Karacuba (eo)
- Algoritmo de Karatsuba (es)
- Algorithme de Karatsuba (fr)
- Algoritmo di Karatsuba (it)
- Karatsuba algorithm (en)
- 카라추바 알고리즘 (ko)
- カラツバ法 (ja)
- Algorytm Karacuby (pl)
- Algoritmo de Karatsuba (pt)
- Алгоритм Карацубы (ru)
- Множення Карацуби (uk)
- 卡拉楚巴算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
