This HTML5 document contains 157 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
wikipedia-enhttp://en.wikipedia.org/wiki/
dbrhttp://dbpedia.org/resource/
n6http://ml.dbpedia.org/resource/
n13http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n20http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
dbpedia-eohttp://eo.dbpedia.org/resource/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n8http://cr.yp.to/papers/
n39https://global.dbpedia.org/id/
yago-reshttp://yago-knowledge.org/resource/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
n26http://www.cs.pitt.edu/~kirk/cs1501/animations/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Binary_logarithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Arbitrary-precision_arithmetic
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:List_of_numerical_analysis_topics
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Multiplication
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Computational_complexity_of_mathematical_operations
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Strassen_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Toom–Cook_multiplication
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Divide-and-conquer_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Division_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Anatoly_Karatsuba
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Karatsuba_algorithm
rdf:type
yago:WikicatComputerArithmeticAlgorithms yago:YagoPermanentlyLocatedEntity yago:Procedure101023820 yago:Rule105846932 yago:WikicatAlgorithms yago:Algorithm105847438 yago:Event100029378 yago:Activity100407535 yago:Act100030358 yago:PsychologicalFeature100023100 yago:Abstraction100002137
rdfs:label
Algoritmo de Karacuba Алгоритм Карацубы Karacubovo násobení Algoritmo de Karatsuba Algorithme de Karatsuba Algorisme de Karatsuba Algorytm Karacuby Karatsuba algorithm Karazuba-Algorithmus Algoritmo di Karatsuba カラツバ法 Algoritmo de Karatsuba 카라추바 알고리즘 卡拉楚巴算法 Множення Карацуби
rdfs:comment
Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью: . Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности. 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. 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. カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者のAnatolii Alexeevitch Karatsuba（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。 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. Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。 值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。 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. 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ší. 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. 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. Множення Карацуби — метод швидкого множення, який дозволяє перемножувати два n-значних числа зі складністю обчислення: Цей підхід відкрив новий напрямок в обчислювальній математиці. 카라추바 알고리즘은 소련의 수학자 가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다.이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다. 은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다. 카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다. 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 . 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. 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).
foaf:depiction
n13:Karatsuba_multiplication.svg
dcterms:subject
dbc:Computer_arithmetic_algorithms dbc:Divide-and-conquer_algorithms dbc:Articles_with_example_pseudocode dbc:Multiplication
dbo:wikiPageID
6395589
dbo:wikiPageRevisionID
1113431971
dbo:wikiPageWikiLink
dbr:Proceedings_of_the_USSR_Academy_of_Sciences dbr:Multiplication_algorithm dbr:Asymptotically_optimal dbr:Recurrence_relation n20:Karatsuba_multiplication.svg dbr:Time_complexity dbr:Big_O_notation dbr:Radix dbc:Divide-and-conquer_algorithms dbc:Computer_arithmetic_algorithms dbr:Long_multiplication dbr:Toom–Cook_multiplication dbr:Computational_complexity_theory dbr:Yuri_Petrovich_Ofman dbr:Charles_Babbage dbr:Cybernetics dbr:Carry-save_adder dbr:Divide-and-conquer_algorithm dbr:Binary_multiplier dbr:Imaginary_unit dbr:Big-O_notation dbr:Schönhage–Strassen_algorithm dbr:Asymptotic_complexity dbc:Articles_with_example_pseudocode dbc:Multiplication dbr:Anatoly_Karatsuba dbr:Andrey_Kolmogorov dbr:Recursion dbr:Computer_platform dbr:Master_theorem_(analysis_of_algorithms) dbr:Moscow_State_University
dbo:wikiPageExternalLink
n8:m3.pdf n26:Karatsuba.html
owl:sameAs
n6:കരത്സൂബാ_അൽഗൊരിതം dbpedia-ko:카라추바_알고리즘 dbpedia-ca:Algorisme_de_Karatsuba dbpedia-uk:Множення_Карацуби dbpedia-fr:Algorithme_de_Karatsuba dbpedia-ru:Алгоритм_Карацубы dbpedia-fa:الگوریتم_کاراتسوبا dbpedia-pl:Algorytm_Karacuby dbpedia-pt:Algoritmo_de_Karatsuba dbpedia-it:Algoritmo_di_Karatsuba freebase:m.0g3ts6 dbpedia-cs:Karacubovo_násobení dbpedia-eo:Algoritmo_de_Karacuba dbpedia-es:Algoritmo_de_Karatsuba dbpedia-sr:Карацубин_алгоритам dbpedia-de:Karazuba-Algorithmus dbpedia-th:ขั้นตอนวิธีของคาราซูบา dbpedia-zh:卡拉楚巴算法 yago-res:Karatsuba_algorithm dbpedia-ja:カラツバ法 wikidata:Q629940 n39:4oyxr
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Mvar dbt:Number-theoretic_algorithms dbt:Reflist dbt:MathWorld
dbo:thumbnail
n13:Karatsuba_multiplication.svg?width=300
dbp:title
Karatsuba Multiplication
dbp:urlname
KaratsubaMultiplication
dbo:abstract
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. カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。発見者のAnatolii Alexeevitch Karatsuba（Карацуба Анатолий Алексеевич）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、（≒1.585）まで計算コストが抑えられる。 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. 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 . 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. Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью: . Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности. 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. Множення Карацуби — метод швидкого множення, який дозволяє перемножувати два n-значних числа зі складністю обчислення: Цей підхід відкрив новий напрямок в обчислювальній математиці. 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). 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. 카라추바 알고리즘은 소련의 수학자 가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다.이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다. 은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다. 카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다. 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ší. 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. Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），卡拉楚巴算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的，Schönhage-Strassen演算法甚至更快，算法的时间复杂度为。 值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。 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.
prov:wasDerivedFrom
wikipedia-en:Karatsuba_algorithm?oldid=1113431971&ns=0
dbo:wikiPageLength
13620
foaf:isPrimaryTopicOf
wikipedia-en:Karatsuba_algorithm
Subject Item
dbr:List_of_Russian_IT_developers
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:List_of_Russian_mathematicians
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:List_of_Russian_scientists
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Pi
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Multiplication_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:List_of_Russian_people
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
Subject Item
dbr:Karatsuba's_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
dbo:wikiPageRedirects
dbr:Karatsuba_algorithm
Subject Item
dbr:Karatsuba-Ofman_algorithm
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
dbo:wikiPageRedirects
dbr:Karatsuba_algorithm
Subject Item
dbr:Karatsuba_Multiplication
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
dbo:wikiPageRedirects
dbr:Karatsuba_algorithm
Subject Item
dbr:Karatsuba_multiplication
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
dbo:wikiPageRedirects
dbr:Karatsuba_algorithm
Subject Item
dbr:The_Karatsuba_multiplication
dbo:wikiPageWikiLink
dbr:Karatsuba_algorithm
dbo:wikiPageRedirects
dbr:Karatsuba_algorithm
Subject Item
wikipedia-en:Karatsuba_algorithm
foaf:primaryTopic
dbr:Karatsuba_algorithm