E-Business + Web Science Research Group Good Relations logo

The Product Types Ontology: Class Definition for "Euclidean algorithm"

This page is part of http://www.productontology.org/, a huge, precise dictionary of product types and brand names for marking up Web sites with schema.org or the GoodRelations e-commerce standard.

Breaking news: schema.org has just implemented our proposal to define an additionalType property with the use of this service in mind!

Share on  Mention on Twitter  Set Google Bookmark  Bookmark on Delicious  Share on Facebook 

http://www.productontology.org/

On this page: Usage(schema.org/Microdata, RDFa, Facebook) Contact Information Caching Policy License Acknowledgments References

pto:Euclidean_algorithm (rdf:type owl:Class)

URI http://www.productontology.org/id/Euclidean_algorithm
rdfs:subClassOf gr:ProductOrService, http://schema.org/Product
rdfs:label Euclidean algorithm (as a class or brand name of products of services)
Translation(s):  خوارزمية أقليدس@ar;  Algoritmu d'Euclides@ast;  Evklid alqoritmi@az;  Евклид алгоритмы@ba;  Алгарытм Эўкліда@be;  Алгоритъм на Евклид@bg;  ইউক্লিডীয় এলগরিদম@bn;  Algorisme d'Euclides@ca;  ئەلگۆریتمی ئیقلیدس@ckb;  Eukleidův algoritmus@cs; 

rdfs:comment

<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see ), THIS ARTICLE AVOIDS MATH MODE, UNLESS IT'S NECESSARY. PLEASE DO NOT ADD MATH-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. --> In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, 21 = 5 × 105 + (−2) × 252).The fact that the GCD can always be expressed in this way is known as Bézout's identity. The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century. The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains. (Source: Wikipedia, the free encyclopedia, see http://en.wikipedia.org/wiki/Euclidean_algorithm)

Note: The extraction of the abstract from the Wikipedia page may sometimes yield imperfect results. We are improving the algorithm regularly.

is rdfs:domain of gr:category gr:color gr:condition gr:depth gr:hasEAN_UCC-13 gr:hasGTIN-14 gr:hasMPN gr:hasManufacturer gr:hasStockKeepingUnit gr:height gr:isAccessoryOrSparePartFor gr:isConsumableFor gr:isSimilarTo gr:weight gr:width
is rdfs:range of gr:includes gr:isAccessoryOrSparePartFor gr:isConsumableFor gr:isSimilarTo

Note: This is a generic list. Some of the properties may not be applicable to this particular type of object.

Trademark Disclaimer:  Since this service returns class descriptions for potentiall any series of characters, it cannot indicate automatically whether a name is a registered trademark or otherwise protected. We assume no liability for the absence of trademark rights and other damages. See the section "License" below for details.

[back to top]

Usage

The following shows how to model that you offer to sell [a/an/some] Euclidean algorithm for $ 19.99.

[back to top]

Microdata / Use with http://schema.org/Product

One of the most powerful usages of the class definitions from this site is to describe the type of your page and product for the schema.org product markup in Microdata syntax much more precisely.

Simply add the full URI of a class from this site, e.g. http://www.productontology.org/id/Euclidean_algorithm as an additional type as follows:

<div itemscope itemtype="http://schema.org/Product">
    <link itemprop="additionalType" href="http://www.productontology.org/id/Euclidean_algorithm" />
    <!-- other schema.org properties go in here -->
</div>		

Note: In HTML5, it is valid to use the <link> element in the body of a HTML document.

Here is a complete example:

<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
    <title>An offer to sell a / some Euclidean_algorithm</title>
</head>
<body>
<div itemscope itemtype="http://schema.org/Product" itemid="#product">
    <link itemprop="additionalType" href="http://www.productontology.org/id/Euclidean_algorithm" />
    <span itemprop="name">.. a short name for the object ...</span>
    Product description: 
    <span itemprop="description">... a longer description ...</span>
    <div itemprop="offers" itemscope itemtype="http://schema.org/Offer" itemid="#offer">
        <span itemprop="price">$19.99</span> 
        <link itemprop="availability" href="http://schema.org/InStock" />In stock
    </div>
</div>
</body>
</html>

Turtle Syntax

@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
@prefix pto: <http://www.productontology.org/id/> .
@prefix gr: <http://purl.org/goodrelations/v1#> .
@prefix foo: <http://example.com/> .

# The object
foo:myObject a <http://www.productontology.org/id/Euclidean_algorithm> ;
	a gr:SomeItems ;
	gr:name "... a short name for the object ..."@en ;
	gr:description "... a longer description ..."@en .

# The agent (person or company) who is offering it
foo:ACMECorp a gr:BusinessEntity ;
	gr:legalName "ACME Corp" ;
	gr:offers foo:Offer .
		
# The offer to sell it
foo:Offer a gr:Offering ;
	gr:includes foo:myObject;
	foaf:page <http://URI_of_the_page_containing_the_offer.com>;
	gr:hasBusinessFunction gr:Sell ;
	gr:validFrom "2011-01-24T00:00:00+01:00"^^xsd:dateTime ;
	gr:validThrough "2011-12-24T00:00:00+01:00"^^xsd:dateTime ;
	gr:hasPriceSpecification
         [ a gr:UnitPriceSpecification ;
           gr:hasCurrency "USD"^^xsd:string ;
           gr:hasCurrencyValue "19.99"^^xsd:float ;
           gr:validThrough "2011-12-24T00:00:00+01:00"^^xsd:dateTime ] .

Note: Replace gr:SomeItems (http://purl.org/goodrelations/v1#SomeItems) by gr:Individual if you are describing a unique object of that kind (e.g. antique furniture).

[back to top]

RDFa

<!DOCTYPE html>
<html version="HTML+RDFa 1.1" xmlns="http://www.w3.org/1999/xhtml">
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
    <title>An offer to sell a / some Euclidean_algorithm</title>
</head>
<body>
<div xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
     xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
     xmlns:foaf="http://xmlns.com/foaf/0.1/"
     xmlns:gr="http://purl.org/goodrelations/v1#"
     xmlns:pto="http://www.productontology.org/id/"
     xmlns:foo="http://example.com/"
     xmlns:xsd="http://www.w3.org/2001/XMLSchema#">

<!-- The agent (person or company) who is offering it -->
   <div about="#ACMECorp" typeof="gr:BusinessEntity">
      <div property="gr:legalName">ACME Corp</div>
      <div rel="gr:offers">
<!-- The offer to sell it -->	
         <div about="#offer" typeof="gr:Offering">
            <div rel="gr:hasBusinessFunction" resource="http://purl.org/goodrelations/v1#Sell"></div>
            <div rel="gr:includes">
<!-- The object -->	
               <div about="#myObject" typeof="http://www.productontology.org/id/Euclidean_algorithm">
                  <div rel="rdf:type" resource="http://purl.org/goodrelations/v1#SomeItems"></div>
                  <div property="gr:description" xml:lang="en">... a longer description ...</div>
                  <div property="gr:name" xml:lang="en">.. a short name for the object ...</div>
               </div>
            </div>
            <div rel="foaf:page" resource="http://URI_of_the_page_containing_the_offer"></div>
            <div rel="gr:hasPriceSpecification">
               <div typeof="gr:UnitPriceSpecification">
                  <div property="gr:hasCurrency" content="USD" datatype="xsd:string">$ </div>
                  <div property="gr:hasCurrencyValue" datatype="xsd:float">19.99</div>
                  <div property="gr:validThrough" content="2011-12-24T00:00:00+01:00" 
					   datatype="xsd:dateTime"></div>
               </div>
            </div>
            <div property="gr:validFrom" content="2011-01-24T00:00:00+01:00"
                 datatype="xsd:dateTime"></div>
            <div property="gr:validThrough" content="2011-12-24T00:00:00+01:00"
                 datatype="xsd:dateTime"></div>
         </div>
      </div>
   </div>
</div>
</body>
</html>

Note: Replace gr:SomeItems (http://purl.org/goodrelations/v1#SomeItems) by gr:Individual if you are describing a unique object of that kind (e.g. antique furniture).

[back to top]

RDF/XML

<?xml version="1.0" encoding="UTF-8" ?>
<rdf:RDF xmlns:gr="http://purl.org/goodrelations/v1#" 
  xmlns:pto="http://www.productontology.org/id/" 
  xmlns:xsd="http://www.w3.org/2001/XMLSchema#" 
  xmlns:foaf="http://xmlns.com/foaf/0.1/" 
  xmlns:foo="http://example.com/" 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
<!-- The object -->
  <rdf:Description rdf:about="http://example.com/myObject">
    <rdf:type rdf:resource="http://www.productontology.org/id/Euclidean_algorithm"/>    
    <rdf:type rdf:resource="http://purl.org/goodrelations/v1#SomeItems"/>
    <gr:name xml:lang="en">... a short name for the object ...</gr:name>
    <gr:description xml:lang="en">... a longer description ...</gr:description>
  </rdf:Description>
<!-- The agent (person or company) who is offering it -->
  <gr:BusinessEntity rdf:about="http://example.com/ACMECorp">
    <gr:legalName>ACME Corp</gr:legalName>
    <gr:offers rdf:resource="http://example.com/Offer" />
  </gr:BusinessEntity>
<!-- The offer to sell it -->   
  <gr:Offering rdf:about="http://example.com/Offer">
    <gr:includes rdf:resource="http://example.com/myObject" />
    <foaf:page rdf:resource="http://URI_of_the_page_containing_the_offer"/>
    <gr:hasBusinessFunction rdf:resource="http://purl.org/goodrelations/v1#Sell"/>
    <gr:validFrom rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">
      2011-01-24T00:00:00+01:00</gr:validFrom>
    <gr:validThrough rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">
      2011-12-24T00:00:00+01:00</gr:validThrough>
    <gr:hasPriceSpecification>
      <gr:UnitPriceSpecification>
        <gr:hasCurrency rdf:datatype="http://www.w3.org/2001/XMLSchema#string">USD</gr:hasCurrency>
        <gr:hasCurrencyValue rdf:datatype="http://www.w3.org/2001/XMLSchema#float">19.99</gr:hasCurrencyValue>
        <gr:validThrough rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">
          2011-12-24T00:00:00+01:00</gr:validThrough>
      </gr:UnitPriceSpecification>
    </gr:hasPriceSpecification>
  </gr:Offering>

</rdf:RDF>

Note: Replace gr:SomeItems (http://purl.org/goodrelations/v1#SomeItems) by gr:Individual if you are describing a unique object of that kind (e.g. antique furniture).

[back to top]

SPARQL Query

prefix foaf: <http://xmlns.com/foaf/0.1/> 
prefix xsd: <http://www.w3.org/2001/XMLSchema#> 
prefix pto: <http://www.productontology.org/id/> 
prefix gr: <http://purl.org/goodrelations/v1#> 
prefix foo: <http://example.com/> 

# Find the cheapest offer for a Euclidean_algorithm

SELECT * WHERE{
?company gr:offers ?offer .
?offer a gr:Offering .
?offer gr:hasBusinessFunction gr:Sell .
OPTIONAL {?offer rdfs:label ?label } .
OPTIONAL {?offer gr:name ?label } .
OPTIONAL {?offer rdfs:comment ?label } .
OPTIONAL {?offer gr:description ?label } .
?offer gr:hasPriceSpecification ?p .
?p a gr:UnitPriceSpecification .
?p gr:hasCurrency ?currency .
?p gr:hasCurrencyValue ?price .
?offer gr:includes ?product .
?product a <http://www.productontology.org/id/Euclidean_algorithm> .
}
ORDER BY (?price)
LIMIT 10

[back to top]

Facebook Open Graph Protocol

You can also use the class definitions from this site for better describing the type of your page or product for the Facebook Open Graph Protocol.

Simply define the namespace prefix pto: in the <html> element of your page

<html version="HTML+RDFa 1.1" 
	xmlns="http://www.w3.org/1999/xhtml" 
	xmlns:pto="http://www.productontology.org/id/" 
	>

and use the compact URI (CURIE) pto:Euclidean_algorithm in combination with og:type as follows:

	<meta property="og:type" content="pto:Euclidean_algorithm"/>

A complete example is here.

[back to top]

Contact Information

Univ.-Prof. Dr. Martin Hepp

E-Business and Web Science Research Group
Chair of General Management and E-Business
Universität der Bundeswehr München
Werner-Heisenberg-Weg 39
D-85579 Neubiberg, Germany

Phone: +49 89 6004-4217
eMail: mhepp(at)computer.org (preferred mode of communication)
Web: http://www.heppnetz.de/
Web: http://www.unibw.de/ebusiness/

[back to top]

Caching Policy

In order to minimize the load on the Wikipedia API, all requests are cached internally for 72 hours. This means that changes to the English Wikipedia will be available in this service within 72 hours or less if the same entry has been requested before. Classes not requested within the last six hours are always guaranteed to be in sync with the latest version in Wikipedia.

The RDF/XML dump file is updated every 12 hours only.

[back to top]

License

The class definition text is taken from Wikipedia, the free encyclopedia under a Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license. Accordingly, the ontology class definitions are available under the very same license.

Trademark Disclaimer:  Since this service returns class descriptions for potentially any series of characters, it cannot indicate automatically whether a name is a registered trademark or otherwise protected. If you want us to block a certain name, please send your request including proof of your rights on the name to our contact address listed below.. Any of the trademarks, service marks, collective marks, design rights or similar rights that are mentioned, used, or cited in this service are the property of their respective owners. Their use here does not imply that you may use them for any purpose other than for the same or a similar informational use as contemplated by the original authors of the underlying Wikipedia articles under the CC-BY-SA and GFDL licensing schemes. Productontology.org is neither endorsed by nor affiliated with any of the holders of any such rights and as such cannot grant any rights to use any otherwise protected materials. Your use of any such or similar incorporeal property is at your own risk.

[back to top]

Acknowledgements

Thanks to Stefano Bertolo, Julien Chaumond, Bob Ferris, Kingsley Idehen, Axel Polleres, Andreas Radinger, Alex Stolz, and Giovanni Tummarello for very valuable feedback, and to Katharina Siorpaes and Daniel Bachlechner, who contributed to the initial analysis of the stability of Wikipedia URIs back in 2007.

The work on The Product Types Ontology has been supported by the German Federal Ministry of Research (BMBF) by a grant under the KMU Innovativ program as part of the Intelligent Match project (FKZ 01IS10022B).

BMBF logo

[back to top]

References

Wikipedia: Euclidean algorithm, available at http://en.wikipedia.org/wiki/Euclidean_algorithm.

Hepp, Martin: GoodRelations: An Ontology for Describing Products and Services Offers on the Web, Proceedings of the 16th International Conference on Knowledge Engineering and Knowledge Management (EKAW2008), Acitrezza, Italy, September 29 - October 3, 2008, Springer LNCS, Vol 5268, pp. 332-347.

Hepp, Martin; Siorpaes, Katharina; Bachlechner, Daniel: Harvesting Wiki Consensus: Using Wikipedia Entries as Vocabulary for Knowledge Management, IEEE Internet Computing, Vol. 11, No. 5, pp. 54-65, Sept-Oct 2007.

Valid XHTML 1.0 Strict