Many months ago I submitted to the xsl list a small programming challenge:
http://www.biglist.com/lists/xsl-list/archives/200506/msg00848.html
Let me first appologize for the delay in summarizing the solution(s)
-- it's part of me being busy/lazy, part due to unexpected unwelcome
events.
This puzzle was inspired by the less difficult but now famous Google puzzle
{first 10-digit prime found in consecutive digits of e}.com
http://www.npr.org/programs/morning/features/2004/sep/googlead/billboard.html
and
Dan Brown's "The Da Vinci code".
The purpose was to once again show that such problems can be solved
both efficiently and elegantly in XSLT.
As originally stated, the problem was to
" Find the first 10-digit prime in consecutive digits of F-3000"
The problem consists of two separate sub-problems:
1. Calculate F-3000
2. Find the first 10-digit substring that represents a prime number
My initial solution of the first subproblem was to simply use the
wellknown recursive definition of a Fibonacci number:
F(N+1) = F(N) + F(N-1)
combined with the saxon:memo-function="yes" attribute, which produces
F(N) with O(N) (linear) time complexity.
F-3000 was chosen not by chance -- one cannot calculate F-3000 in
Saxon 8.x using the above formula, because of stack overflow (even big
arithmetic faces the hardware limits of a computer).
However, it was possible to calculate F-3000 with the above method
using Saxon.NET.
Then, in the ensueing thread I wrote:
"Andrew,
Yes, I have a solution and I know of a better solution, which will run
even faster and will not use any extensions."
At the same time I received a solution from David Carlisle, which used
exactly this faster algorithm.
This exploits a general idea of calculating any function F(N) (not
only the one that produces Fibonacci numbers), if
F(2N) and F(2N+1) can be expressed by F(N).
Then, recursively, one calculates F(N), F(N/2), F(N/4),..., F(0) or F(1)
The above sequence has Log2(N) elements and if the calculations from N
to 2N are not very complicated, one may generally expect a time
complexity close to O(log2(N)).
For example, if
F(M) = x^M,
then we have:
F(2M) = F(M)*F(M)
F(2M+1) = x*F(2M)
and therefore, one can calculate a^N in O(log2(N)) -- much faster than
in linear time.
The corresponding formulas for Fib(N), which both David and I used
(but I derived these formulas without reading them in a textbook) can
be found at:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#fibinits
F(2N) = F(N) * F(N) + f(N-1) * F(N-1)
F(2N+1) = (2F(N-1) + F(N)) * F(N)
Then the algorithm is easy to write, it is fast and efficient and
produces F-3000 in Saxon 8.x without a problem.
The second subproblem is the classic one of determining if a given
number is a prime one.
David is using the little Fermat's theorem to eliminate all numbers
that are not primes.
The little Fermat's theorem states that:
if p is prime, then
a^(p-1) mod p = 1 (1)
So, we can safely conclude that a number N is not prime if
not(a^(N-1) mod N = 1)
However, from
a^(N-1) mod N = 1
it still does not follow that N is a prime. For example:
2^341 - 2 is divisible by 341,
but 341 is composite: 341 = 31 x 11
What David didn't complete in his solution was that he didn't perform
any additional checks in the case when formula (1) above did hold
(when the sequence of ten consecutive digits was a Fermat's
pseudo-prime).
In this case luckily the first ten consecutive digit
Fermat'spseudo-prime in F-3000 is also the first ten consecutive digit
prome in F-3000.
I conclude this long post by listing below the two solutions: David
Carlisle's and mine.
I want to express my gratitude to David Carlisle for his love of
challenging problems, which has promoted the quality of this mailing
list. I also thank Tommie for her understanding and permitting me to
post this, despite some initial doubts that such posts truly fall into
the subjectmatter of the xsl list.
David Carlisle's solution:
From David Carlisle:
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
61219257396449810982999820391132226802809465132446349331994409434926019045342723
74918853031699467847355132063510109961938297318162258568733693978437352789755548
94868417261317338143401291756224504216051010258971732359906627702037564387865175
30547101123748849140252686120104032647025145598956675902135010566909783124959436
46982555831428970135422715178460286571078062467510705656982282054284666032181383
88962758197532813714918090044122191248563751216948117287242136678145773266185214
78357661859018967313354840178403197559969056510791709859144173304364898001
1st (fermat base 2 pseudo-)prime:
72280217
:
Execution time: 501 milliseconds
Calling template x
:
f3000: 6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342723
74918853031699467847355132063510109961938297318162258568733693978437352789755548
94868417261317338143401291756224504216051010258971732359906627702037564387865175
30547101123748849140252686120104032647025145598956675902135010566909783124959436
46982555831428970135422715178460286571078062467510705656982282054284666032181383
88962758197532813714918090044122191248563751216948117287242136678145773266185214
78357661859018967313354840178403197559969056510791709859144173304364898001
1st (fermat base 2 pseudo-)prime:
72280217
:
Execution time: 180 milliseconds
Calling template x
:
f3000: 6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342723
74918853031699467847355132063510109961938297318162258568733693978437352789755548
94868417261317338143401291756224504216051010258971732359906627702037564387865175
30547101123748849140252686120104032647025145598956675902135010566909783124959436
46982555831428970135422715178460286571078062467510705656982282054284666032181383
88962758197532813714918090044122191248563751216948117287242136678145773266185214
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:
664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
Is: 0072280217
--
Cheers,
Dimitre Novatchev
---------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all.
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--