Multiplication of Long Integers - Faster than Long Multiplication View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Arno Eigenwillig , Kurt Mehlhorn

ABSTRACT

In this chapter the authors present an algorithm for fast multiplication that is much more efficient than the standard grade-school method, especially if one wants to multiply large numbers consisting of many digits. The authors present and analyze the efficiency of Karatsuba’s method – named after its inventor, he came up with the idea in the 1960s. The method exploits recursion, a fundamental technique in computer science, and it also involves the trick of dividing the problem into three subproblems of half the size. More... »

PAGES

101-109

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-15328-0_11

DOI

http://dx.doi.org/10.1007/978-3-642-15328-0_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1001387898


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Eigenwillig", 
        "givenName": "Arno", 
        "id": "sg:person.016055347343.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016055347343.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "In this chapter the authors present an algorithm for fast multiplication that is much more efficient than the standard grade-school method, especially if one wants to multiply large numbers consisting of many digits. The authors present and analyze the efficiency of Karatsuba\u2019s method \u2013 named after its inventor, he came up with the idea in the 1960s. The method exploits recursion, a fundamental technique in computer science, and it also involves the trick of dividing the problem into three subproblems of half the size.", 
    "editor": [
      {
        "familyName": "V\u00f6cking", 
        "givenName": "Berthold", 
        "type": "Person"
      }, 
      {
        "familyName": "Alt", 
        "givenName": "Helmut", 
        "type": "Person"
      }, 
      {
        "familyName": "Dietzfelbinger", 
        "givenName": "Martin", 
        "type": "Person"
      }, 
      {
        "familyName": "Reischuk", 
        "givenName": "R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Scheideler", 
        "givenName": "Christian", 
        "type": "Person"
      }, 
      {
        "familyName": "Vollmer", 
        "givenName": "Heribert", 
        "type": "Person"
      }, 
      {
        "familyName": "Wagner", 
        "givenName": "Dorothea", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-15328-0_11", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-15327-3", 
        "978-3-642-15328-0"
      ], 
      "name": "Algorithms Unplugged", 
      "type": "Book"
    }, 
    "keywords": [
      "fast multiplication", 
      "computer science", 
      "long integers", 
      "fundamental technique", 
      "subproblems", 
      "multiplication", 
      "large number", 
      "recursion", 
      "long multiplication", 
      "integers", 
      "algorithm", 
      "Karatsuba", 
      "problem", 
      "tricks", 
      "idea", 
      "technique", 
      "number", 
      "efficiency", 
      "authors", 
      "science", 
      "size", 
      "chapter", 
      "digits", 
      "inventors", 
      "method"
    ], 
    "name": "Multiplication of Long Integers - Faster than Long Multiplication", 
    "pagination": "101-109", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001387898"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-15328-0_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-15328-0_11", 
      "https://app.dimensions.ai/details/publication/pub.1001387898"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_291.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-15328-0_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15328-0_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15328-0_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15328-0_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15328-0_11'


 

This table displays all metadata directly associated to this object as RDF triples.

121 TRIPLES      22 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-15328-0_11 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N82354d59451d4f628f9bdf1d71eef380
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description In this chapter the authors present an algorithm for fast multiplication that is much more efficient than the standard grade-school method, especially if one wants to multiply large numbers consisting of many digits. The authors present and analyze the efficiency of Karatsuba’s method – named after its inventor, he came up with the idea in the 1960s. The method exploits recursion, a fundamental technique in computer science, and it also involves the trick of dividing the problem into three subproblems of half the size.
7 schema:editor N88eb5f0f2bd84d38893869c6de3e9ac5
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf02be4fe80a547ba8fc08aedea60b6af
11 schema:keywords Karatsuba
12 algorithm
13 authors
14 chapter
15 computer science
16 digits
17 efficiency
18 fast multiplication
19 fundamental technique
20 idea
21 integers
22 inventors
23 large number
24 long integers
25 long multiplication
26 method
27 multiplication
28 number
29 problem
30 recursion
31 science
32 size
33 subproblems
34 technique
35 tricks
36 schema:name Multiplication of Long Integers - Faster than Long Multiplication
37 schema:pagination 101-109
38 schema:productId N142d02ce58884d378d8d20c6994dca90
39 Nf27a94dbe223497f824df43b3b37e676
40 schema:publisher N97b96b45556b4cff92cd509f2fd4a682
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001387898
42 https://doi.org/10.1007/978-3-642-15328-0_11
43 schema:sdDatePublished 2022-09-02T16:13
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N06266a32412646ea807996cf4443fd35
46 schema:url https://doi.org/10.1007/978-3-642-15328-0_11
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N06266a32412646ea807996cf4443fd35 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N142d02ce58884d378d8d20c6994dca90 schema:name doi
53 schema:value 10.1007/978-3-642-15328-0_11
54 rdf:type schema:PropertyValue
55 N1cc3276f35af4a049daaa2aaad2bb6c4 schema:familyName Wagner
56 schema:givenName Dorothea
57 rdf:type schema:Person
58 N227dd05a51b54442908c5cee82ce596f rdf:first Nb0c355643f09436bbe2caef110503616
59 rdf:rest Nf9f0a472cdc94ad8bea42a6b07f6475d
60 N36175564ce844f2a8eef4c2d85c50272 schema:familyName Dietzfelbinger
61 schema:givenName Martin
62 rdf:type schema:Person
63 N38e7a26f47ca4eeb9c00244f65a8fd25 schema:familyName Vöcking
64 schema:givenName Berthold
65 rdf:type schema:Person
66 N5cbe9789c78c43dfb3f12a95643579ac rdf:first N8647b70a859a40edb523816e5b7c09f2
67 rdf:rest Nf24283bf96b641b4a040ef2505dd1312
68 N6395ea4058024b749c945721be93b22c rdf:first sg:person.011757371347.43
69 rdf:rest rdf:nil
70 N666c45c905d248009e3b026d5b7601c5 schema:familyName Reischuk
71 schema:givenName Rüdiger
72 rdf:type schema:Person
73 N82354d59451d4f628f9bdf1d71eef380 rdf:first sg:person.016055347343.52
74 rdf:rest N6395ea4058024b749c945721be93b22c
75 N8647b70a859a40edb523816e5b7c09f2 schema:familyName Vollmer
76 schema:givenName Heribert
77 rdf:type schema:Person
78 N88eb5f0f2bd84d38893869c6de3e9ac5 rdf:first N38e7a26f47ca4eeb9c00244f65a8fd25
79 rdf:rest N227dd05a51b54442908c5cee82ce596f
80 N8daca0a8c4b346178b4c08fd2f3be3ec rdf:first Nba8a45434579448d906902eb8e59c9af
81 rdf:rest N5cbe9789c78c43dfb3f12a95643579ac
82 N97b96b45556b4cff92cd509f2fd4a682 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Nb0c355643f09436bbe2caef110503616 schema:familyName Alt
85 schema:givenName Helmut
86 rdf:type schema:Person
87 Nba8a45434579448d906902eb8e59c9af schema:familyName Scheideler
88 schema:givenName Christian
89 rdf:type schema:Person
90 Nc10f691d2772400bb419d3f3ad38d5d2 rdf:first N666c45c905d248009e3b026d5b7601c5
91 rdf:rest N8daca0a8c4b346178b4c08fd2f3be3ec
92 Nf02be4fe80a547ba8fc08aedea60b6af schema:isbn 978-3-642-15327-3
93 978-3-642-15328-0
94 schema:name Algorithms Unplugged
95 rdf:type schema:Book
96 Nf24283bf96b641b4a040ef2505dd1312 rdf:first N1cc3276f35af4a049daaa2aaad2bb6c4
97 rdf:rest rdf:nil
98 Nf27a94dbe223497f824df43b3b37e676 schema:name dimensions_id
99 schema:value pub.1001387898
100 rdf:type schema:PropertyValue
101 Nf9f0a472cdc94ad8bea42a6b07f6475d rdf:first N36175564ce844f2a8eef4c2d85c50272
102 rdf:rest Nc10f691d2772400bb419d3f3ad38d5d2
103 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
104 schema:name Mathematical Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
107 schema:name Pure Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
110 schema:familyName Mehlhorn
111 schema:givenName Kurt
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
113 rdf:type schema:Person
114 sg:person.016055347343.52 schema:affiliation grid-institutes:grid.419528.3
115 schema:familyName Eigenwillig
116 schema:givenName Arno
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016055347343.52
118 rdf:type schema:Person
119 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
120 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
121 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...