Worst-Case Analysis of an Algorithm for Computing the Greatest Common Divisor of n Inputs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Charles Lam , Jeffrey Shallit , Scott Vanstone

ABSTRACT

We give an exact worst-case analysis of an algorithm for computing the greatest common divisor of n inputs. The algorithm is extracted from a 1995 algorithm of de Rooij for fixed-base exponentiation.

PAGES

156-166

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-57189-3_14

DOI

http://dx.doi.org/10.1007/978-3-642-57189-3_14

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lam", 
        "givenName": "Charles", 
        "id": "sg:person.012436040744.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012436040744.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo Waterloo, N2L 3G1, Waterloo, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shallit", 
        "givenName": "Jeffrey", 
        "id": "sg:person.0776416736.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776416736.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vanstone", 
        "givenName": "Scott", 
        "id": "sg:person.010344544767.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010344544767.07"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "We give an exact worst-case analysis of an algorithm for computing the greatest common divisor of n inputs. The algorithm is extracted from a 1995 algorithm of de Rooij for fixed-base exponentiation.", 
    "editor": [
      {
        "familyName": "Buchmann", 
        "givenName": "Johannes", 
        "type": "Person"
      }, 
      {
        "familyName": "H\u00f8holdt", 
        "givenName": "Tom", 
        "type": "Person"
      }, 
      {
        "familyName": "Stichtenoth", 
        "givenName": "Henning", 
        "type": "Person"
      }, 
      {
        "familyName": "Tapia-Recillas", 
        "givenName": "Horacio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-57189-3_14", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66248-8", 
        "978-3-642-57189-3"
      ], 
      "name": "Coding Theory, Cryptography and Related Areas", 
      "type": "Book"
    }, 
    "keywords": [
      "worst-case analysis", 
      "algorithm", 
      "greatest common divisor", 
      "common divisor", 
      "input", 
      "exponentiation", 
      "analysis", 
      "divisors", 
      "N input", 
      "de Rooij"
    ], 
    "name": "Worst-Case Analysis of an Algorithm for Computing the Greatest Common Divisor of n Inputs", 
    "pagination": "156-166", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009062270"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-57189-3_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-57189-3_14", 
      "https://app.dimensions.ai/details/publication/pub.1009062270"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:10", 
    "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_15.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-57189-3_14"
  }
]
 

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-57189-3_14'

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-57189-3_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-57189-3_14'

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-57189-3_14'


 

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

92 TRIPLES      21 PREDICATES      33 URIs      28 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-57189-3_14 schema:author Nd2f19625dce048bab0f50ab170953274
2 schema:datePublished 2000
3 schema:datePublishedReg 2000-01-01
4 schema:description We give an exact worst-case analysis of an algorithm for computing the greatest common divisor of n inputs. The algorithm is extracted from a 1995 algorithm of de Rooij for fixed-base exponentiation.
5 schema:editor N4f0848c840fd4e6896114e6c9bebc852
6 schema:genre chapter
7 schema:isAccessibleForFree false
8 schema:isPartOf Nb51641dbe6c4413bb5decad2a75fea05
9 schema:keywords N input
10 algorithm
11 analysis
12 common divisor
13 de Rooij
14 divisors
15 exponentiation
16 greatest common divisor
17 input
18 worst-case analysis
19 schema:name Worst-Case Analysis of an Algorithm for Computing the Greatest Common Divisor of n Inputs
20 schema:pagination 156-166
21 schema:productId N423274814211492ca436acbf7ae1ecd9
22 N4587a6305a8e46ab94b5efc40c849f5e
23 schema:publisher Ne914d989e4994426a803308934e54825
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009062270
25 https://doi.org/10.1007/978-3-642-57189-3_14
26 schema:sdDatePublished 2022-09-02T16:10
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Nfabba31325c54ce48a3c31e8556290d2
29 schema:url https://doi.org/10.1007/978-3-642-57189-3_14
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N0c0b5484d46242a694d7087ac8cffa69 schema:familyName Tapia-Recillas
34 schema:givenName Horacio
35 rdf:type schema:Person
36 N423274814211492ca436acbf7ae1ecd9 schema:name dimensions_id
37 schema:value pub.1009062270
38 rdf:type schema:PropertyValue
39 N4587a6305a8e46ab94b5efc40c849f5e schema:name doi
40 schema:value 10.1007/978-3-642-57189-3_14
41 rdf:type schema:PropertyValue
42 N4f0848c840fd4e6896114e6c9bebc852 rdf:first Ne1fb8e3b67f9474ebaef6793e25e48cb
43 rdf:rest Na1f4d4113c4d46c88b9b35cffbc2dfcb
44 Na06bf79baf6c49998ff5a4790b8d26fb rdf:first N0c0b5484d46242a694d7087ac8cffa69
45 rdf:rest rdf:nil
46 Na1f4d4113c4d46c88b9b35cffbc2dfcb rdf:first Nd24a840a5d2a42b99f3b5a6fb3c6b3da
47 rdf:rest Ndf311dd9c982438f928f3cdfc7918a72
48 Na34e7a5f7a1b472d82860e8337afac3f rdf:first sg:person.0776416736.27
49 rdf:rest Ncd111fcccc5e48bc8463ed995ba370be
50 Nb51641dbe6c4413bb5decad2a75fea05 schema:isbn 978-3-540-66248-8
51 978-3-642-57189-3
52 schema:name Coding Theory, Cryptography and Related Areas
53 rdf:type schema:Book
54 Ncd111fcccc5e48bc8463ed995ba370be rdf:first sg:person.010344544767.07
55 rdf:rest rdf:nil
56 Nd24a840a5d2a42b99f3b5a6fb3c6b3da schema:familyName Høholdt
57 schema:givenName Tom
58 rdf:type schema:Person
59 Nd2f19625dce048bab0f50ab170953274 rdf:first sg:person.012436040744.03
60 rdf:rest Na34e7a5f7a1b472d82860e8337afac3f
61 Nd3748ecbe9654d9b8cd324004056f279 schema:familyName Stichtenoth
62 schema:givenName Henning
63 rdf:type schema:Person
64 Ndf311dd9c982438f928f3cdfc7918a72 rdf:first Nd3748ecbe9654d9b8cd324004056f279
65 rdf:rest Na06bf79baf6c49998ff5a4790b8d26fb
66 Ne1fb8e3b67f9474ebaef6793e25e48cb schema:familyName Buchmann
67 schema:givenName Johannes
68 rdf:type schema:Person
69 Ne914d989e4994426a803308934e54825 schema:name Springer Nature
70 rdf:type schema:Organisation
71 Nfabba31325c54ce48a3c31e8556290d2 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 sg:person.010344544767.07 schema:affiliation grid-institutes:grid.46078.3d
74 schema:familyName Vanstone
75 schema:givenName Scott
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010344544767.07
77 rdf:type schema:Person
78 sg:person.012436040744.03 schema:affiliation grid-institutes:grid.46078.3d
79 schema:familyName Lam
80 schema:givenName Charles
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012436040744.03
82 rdf:type schema:Person
83 sg:person.0776416736.27 schema:affiliation grid-institutes:grid.46078.3d
84 schema:familyName Shallit
85 schema:givenName Jeffrey
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776416736.27
87 rdf:type schema:Person
88 grid-institutes:grid.46078.3d schema:alternateName Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
89 Department of Computer Science, University of Waterloo Waterloo, N2L 3G1, Waterloo, Ontario, Canada
90 schema:name Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
91 Department of Computer Science, University of Waterloo Waterloo, N2L 3G1, Waterloo, Ontario, Canada
92 rdf:type schema:Organization
 




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


...