links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

The sieve of eratosthenes

XSL

<?xml version='1.0' encoding='iso-8859-1' ?>
<?xml-stylesheet href="sieve.xsl" type="text/xsl"?>
<!--
/******************************************************************
* Sieve of Eratosthenes
* =====================
* Purpose: print a list of primes between 2 and some input number
* Input: integer
* Output: string of primes separated by single whitespace
*
* How to run: use saxon (saxon 8 or greater) like this:
*
*             saxon -a sieve.xsl input=10000
*
*             the above example will run sieve.xsl without an
*             input XML file and it will print the primes between
*             2 and 1024 - obviously you can change the input
*             param to whatever you want
*
*             depending on where/how you have saxon installed,
*             you'll probably have to invoke it like this:
*
*             java -jar /path/to/saxon/saxon
*
*             your saxon version may affect performance;
*             at high enough inputs, java WILL overlfow the stack
*             you'll probably want to give java more heap memory
*             and stack size
*             using -Xmx512m -Xss64m or so:
*
*             java -Xmx512m -Xss64m -jar /path/to/saxon/saxon
*
*             example run:
*
*   java -Xmx512 -Xss64m -jar saxon9.jar -a sieve.xsl input=10000
*
*             under java 1.4 it can only reach input=6500
*             under java 1.5 it can reach well above input=10000
*             play with -Xmx and -Xss and you can reach very big
*             input sizes (I've hit 20000 with java 1.5 and
*             -Xmx1024m -Xss128m but I never really tried higher)
*
* Author: Nick "nutbar" Legg
* Date: 04/08/2008
******************************************************************/
-->
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xhtml="http://www.w3.org/1999/xhtml" xmlns:rg="http://ravenguard.dyndns.org"
exclude-result-prefixes="xhtml" version="2.0">


  <xsl:output omit-xml-declaration="yes" method="text" indent="yes" />

  <!--
    $input param can be defined on the command line if you use saxon
    $input = 10 by default
  -->
  <xsl:param name="input" select="number(10)" />

  <!-- build initial array, convert it to string, and start the sieve -->
  <xsl:template match="/">
    <xsl:variable name="arr" select="rg:arr_to_string(rg:new_array($input), $input)" />
    <xsl:value-of select="rg:sieve($arr, 2, $input)" />
  </xsl:template>

  <!-- Sieve of Eratosthenes main function -->
  <xsl:function name="rg:sieve">
    <xsl:param name="arr" />
    <xsl:param name="i" />
    <xsl:param name="len" />
    <xsl:if test="$i &lt; $len">
      <xsl:variable name="prime" select="substring($arr, $i, 1)" />
      <xsl:if test="$prime = '0'">
        <xsl:value-of select="$i" /><xsl:text> </xsl:text>
      </xsl:if>
      <xsl:variable name="arr2">
        <xsl:choose>
          <xsl:when test="$prime = '0' and $i * $i &lt;= $len">
            <xsl:value-of select="rg:multiples($arr, $i, $len)" />
          </xsl:when>
          <xsl:otherwise>
            <xsl:value-of select="$arr" />
          </xsl:otherwise>
        </xsl:choose>
      </xsl:variable>
      <xsl:value-of select="rg:sieve($arr2, $i + 1, $len)" />
    </xsl:if>
  </xsl:function>

  <!-- denote multiples of $i in $arr with 'x' -->
  <xsl:function name="rg:multiples">
    <xsl:param name="arr" />
    <xsl:param name="i" />
    <xsl:param name="len" />
    <xsl:choose>
      <xsl:when test="string-length($arr) &gt; $i">
        <xsl:value-of select="substring($arr, 1, $i - 1)" />
        <xsl:text>x</xsl:text>
        <xsl:value-of select="rg:multiples(substring($arr, $i + 1), $i, $len)" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$arr" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <!-- init new array of '0' characters of length $input -->
  <xsl:function name="rg:new_array">
    <xsl:param name="len" />
    <xsl:if test="$len &gt; 0">
      <xsl:text>0</xsl:text>
      <xsl:value-of select="rg:new_array($len - 1)" />
    </xsl:if>
  </xsl:function>

  <!-- convert an array/nodeset to a string -->
  <xsl:function name="rg:arr_to_string">
    <xsl:param name="arr" />
    <xsl:param name="len" />
      <xsl:value-of select="$arr" />
  </xsl:function>

</xsl:stylesheet>

back to Eratosthenes page

stats

It is Saturday May 17, 2008 11:04 am
This page served 62 times
This page last modified: April 18, 2008 10:46 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 11:04:18 up 23 days, 11:46, 0 users, load average: 0.02, 0.08, 0.03