Cart
|
[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] [no subject] My entry: stylesheet and result below.
timings on a PIII 730 (I really should get a new machine, my laptop is
4 times faster but isn't here:-)
David
Saxon 8.4 from Saxonica
Java version 1.5.0_02
Stylesheet compilation time: 1552 milliseconds
Calling template x
:
f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001
1st (fermat base 2 pseudo-)prime:
72280217
:
Execution time: 501 milliseconds
Calling template x
:
f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001
1st (fermat base 2 pseudo-)prime:
72280217
:
Execution time: 180 milliseconds
Calling template x
:
f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001
1st (fermat base 2 pseudo-)prime:
72280217
:
Execution time: 180 milliseconds
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
version="2.0"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:x="data:,x">
<xsl:output method="text"/>
<xsl:function name="x:power_mod" as="xs:integer">
<xsl:param name="b" as="xs:integer"/>
<xsl:param name="e" as="xs:integer"/>
<xsl:param name="n" as="xs:integer"/>
<xsl:choose>
<xsl:when test="$e=0">
<xsl:sequence select="1"/>
</xsl:when>
<xsl:when test="$e=1">
<xsl:sequence select="$b"/>
</xsl:when>
<xsl:when test="$e>1 and ($e mod 2 = 1)">
<xsl:variable name="e2" select="x:power_mod($b,$e idiv 2,$n)"/>
<xsl:sequence select="($e2 * $e2 * $b) mod $n"/>
</xsl:when>
<xsl:when test="$e>1">
<xsl:variable name="e2" select="x:power_mod($b,$e idiv 2,$n)"/>
<xsl:sequence select="($e2 * $e2) mod $n"/>
</xsl:when>
</xsl:choose>
</xsl:function>
<xsl:function name="x:fib" as="xs:integer">
<xsl:param name="n" as="xs:integer"/>
<xsl:choose>
<xsl:when test="$n=0">
<xsl:sequence select="1"/>
</xsl:when>
<xsl:when test="$n =1">
<xsl:sequence select="1"/>
</xsl:when>
<xsl:when test="$n mod 2 = 0">
<xsl:variable name="n2" select="$n idiv 2"/>
<xsl:variable name="fn" select="x:fib($n2)"/>
<xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
<xsl:sequence select="$fn * $fn + $fn-1 * $fn-1"/>
</xsl:when>
<xsl:when test="$n mod 2 = 1">
<xsl:variable name="n2" select="($n - 1) idiv 2"/>
<xsl:variable name="fn" select="x:fib($n2)"/>
<xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
<xsl:sequence select="(2 * $fn-1 + $fn) * $fn"/>
</xsl:when>
</xsl:choose>
</xsl:function>
<xsl:template name="x">
:
<xsl:variable name="x" select="string(x:fib(3000))"/>
f3000:
<xsl:value-of select="$x"/>
1st (fermat base 2 pseudo-)prime:
<xsl:value-of select="(for $i in 1 to (string-length($x)-9)
return
xs:integer(substring($x,$i,10)))[x:power_mod(2,. - 1, .)=1][1]"
separator=" "/>
:
</xsl:template>
</xsl:stylesheet>
-----------------------------------------------------------------------------
------------------
Dimitre Novatchev's solution:
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:saxon="http://saxon.sf.net/"
xmlns:f="http://fxsl.sf.net/"
exclude-result-prefixes="xs saxon f"
>
<xsl:import href="../f/func-Fibonacci.xsl"/>
<xsl:import href="../f/func-Primes.xsl"/>
<xsl:output method="text"/>
<!--
Solves the following problem:
Find the first 10-digit prime in consecutive digits of F-3000
Where F-N is the Nth Fibonacci number.
Here are the elements of the sequence of Fibonacci numbers from 0 to 11:
Element: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
Index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Invoke on any xml file or with an initial template named "initial".
Expected result: 0072280217
-->
<xsl:variable name="vFib" select="xs:string(f:fibo(3000))"/>
<xsl:template name="initial" match="/">
The first prime from a sequence of
ten consecutive digits in Fibonacci's number F3000:
<xsl:text/>
<xsl:value-of select="$vFib"/>
Is: <xsl:text/>
<xsl:value-of select=
"(
for $n in 1 to string-length($vFib)-9
return(substring($vFib, $n, 10))
)
[f:isPrime(xs:integer(.))][1]
"/>
</xsl:template>
</xsl:stylesheet>
file: ../f/func-Fibonacci.xsl
====================
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:saxon="http://saxon.sf.net/"
xmlns:f="http://fxsl.sf.net/"
exclude-result-prefixes="f xs saxon"
>
<xsl:function name="f:fiboLimitedSeq" as="xs:integer*">
<xsl:param name="pLimit" as="xs:double"/>
<xsl:param name="pN" as="xs:integer"/>
<xsl:variable name="vVal" select="f:fibo($pN)"/>
<xsl:if test="$vVal le $pLimit" >
<xsl:sequence select=
"$vVal, f:fiboLimitedSeq($pLimit, $pN+1)"
/>
</xsl:if>
</xsl:function>
<xsl:function name="f:fibo" as="xs:integer" >
<xsl:param name="pN" as="xs:integer"/>
<xsl:sequence select=
"if ($pN gt 10)
then
if($pN mod 2 = 0)
then
for $i in $pN idiv 2,
$fi in f:fibo($i),
$fi-1 in f:fibo($i -1)
return $fi*$fi + $fi-1*$fi-1
else
for $i in ($pN -1) idiv 2,
$fi in f:fibo($i),
$fi-1 in f:fibo($i -1)
return (2*$fi-1 + $fi) * $fi
else
(1,1,2,3,5,8,13,21,34,55,89)[$pN +1]
"/>
</xsl:function>
</xsl:stylesheet>
file ../f/func-Primes.xsl
=================
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:saxon="http://saxon.sf.net/"
xmlns:gexslt="http://www.gobosoft.com/eiffel/gobo/gexslt/extension"
xmlns:f="http://fxsl.sf.net/"
exclude-result-prefixes="xs saxon f"
>
<xsl:import href="func-sqrt.xsl"/>
<xsl:output method="text"/>
<xsl:function name="f:isPrime" as="xs:boolean" saxon:memo-function="yes"
gexslt:memo-function="yes">
<xsl:param name="pNum" />
<xsl:variable name="vstrNum" select="string($pNum)" as="xs:string"/>
<xsl:variable name="vLastDigit"
select="substring($vstrNum, string-length($vstrNum))"/>
<xsl:value-of select=
"if(not(translate($vLastDigit, '024568', '')) )
then false()
else
if(f:pow2mod($pNum - 1, $pNum) ne 1)
then false()
else
empty(
(3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
(43 to xs:integer(round(f:sqrt($pNum, 0.1E0)))) )
[f:divisor(., $pNum)]
)
"/>
</xsl:function>
<!--
f:pow2mod(K, N) = 2^K mod N
-->
<xsl:function name="f:pow2mod" as="xs:integer">
<xsl:param name="pE" as="xs:integer"/>
<xsl:param name="pN" as="xs:integer"/>
<xsl:sequence select=
"if($pE eq 1)
then 2
else
for $half in f:pow2mod($pE idiv 2, $pN)
return
$half * $half * (1 + ($pE mod 2)) mod $pN
"/>
</xsl:function>
</xsl:stylesheet>
Timings on my 2-year old P-IV 3GHZ 2GB PC run with Saxon 8.6.1:
Execution time: 235 ms
Result:
The first prime from a sequence of
ten consecutive digits in Fibonacci's number F3000:
66439046036696007228021784786602838424416351245278325940557976554262121416121
92573964498109829998203911322268028094651324463493319944094349260190453427237
49188530316994678473551320635101099619382973181622585687336939784373527897555
48948684172613173381434012917562245042160510102589717323599066277020375643878
65175305471011237488491402526861201040326470251455989566759021350105669097831
24959436469825558314289701354227151784602865710780624675107056569822820542846
66032181383889627581975328137149180900441221912485637512169481172872421366781
45773266185214783576618590189673133548401784031975599690565107917098591441733
04364898001
Is: 0072280217
--
Cheers,
Dimitre Novatchev
---------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! 
Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|
