Shootout "fannkuch"

[Miki]

Hello,

I've tried writing a a solution to shootout "fannkuch" (http://
shootout.alioth.debian.org/u32/performance.php?test=fannkuchredux),
however I seem to have a bug in the checksum. Is it just the order of
permutations or am I missing something?

Code at http://bitbucket.org/tebeka/shootout-clj/src/tip/fannkuch.clj

All the best,
--
Miki

[John Fingerhut]

Most likely.  That one I found somewhat annoying in that the checksum computation does depend upon the permutations being generated in a particular order.  It also seems to depend upon the sign flipping being done for every permutation, even those beginning with a '1', for which the pfannkuch function returns 0.

One way to find out what the order is is to download the Java benchmark, add some debug print statements, and run it with a small argument like 6 or 7.  Either that, or read and understand its permutation generating code.

Andy

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Isaac Gouy]

On Sep 2, 11:45 pm, John Fingerhut <andy.finger...@gmail.com> wrote:
> Most likely.  That one I found somewhat annoying in that the checksum
> computation does depend upon the permutations being generated in a
> particular order.

Fannkuch has required the permutations to be generated in a particular
order for years because too many programmers contributed programs that
did not generate some of the permutations or used faster algorithms to
generate the permutations.

At first the requirement was met simply by printing the first 30
permutations but too many programmers contributed programs that used
the accepted algorithm for the first 30 permutations and then did not
generate some of the permutations or used faster algorithms for the
bulk of the work - somewhat annoying.

> It also seems to depend upon the sign flipping being done
> for every permutation, even those beginning with a '1', for which the
> pfannkuch function returns 0.

"The checksum is computed as follows:

checkSum += permutationIndex % 2 == 0 ? flipsCount : -flipsCount;

where permutationIndex is determined by a fixed order in which all n!
permutations are to be generated. The goal is to prevent programs from
questionable optimizations when significant permutation subsets were
excluded from processing, in contradiction with an explicitly stated
rule prohibiting such shortcuts, thus giving those programs unfair
advantage.
The cheksum is very lightweight and can be computed in parallel."

To which I'll add - "At least one person noticed that the isEven test
reduces what needs to be known about permutationIndex - so they simply
toggle between -1 and 1."

> One way to find out what the order is is to download the Java benchmark, add
> some debug print statements, and run it with a small argument like 6 or 7.
>  Either that, or read and understand its permutation generating code.
>
> Andy
>

> On Thu, Sep 2, 2010 at 11:01 PM, Miki <miki.teb...@gmail.com> wrote:
> > Hello,
>
> > I've tried writing a a solution to shootout "fannkuch" (http://
> > shootout.alioth.debian.org/u32/performance.php?test=fannkuchredux),
> > however I seem to have a bug in the checksum. Is it just the order of
> > permutations or am I missing something?
>

> > Code athttp://bitbucket.org/tebeka/shootout-clj/src/tip/fannkuch.clj

>
> > All the best,
> > --
> > Miki
>
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.
> > To post to this group, send email to clo...@googlegroups.com
> > Note that posts from new members are moderated - please be patient with
> > your first post.
> > To unsubscribe from this group, send email to

> > clojure+u...@googlegroups.com<clojure%2Bunsu...@googlegroups.com>

[Isaac Gouy]

On Sep 2, 11:01 pm, Miki <miki.teb...@gmail.com> wrote:
> Hello,
>
> I've tried writing a a solution to shootout "fannkuch" (http://
> shootout.alioth.debian.org/u32/performance.php?test=fannkuchredux),
> however I seem to have a bug in the checksum. Is it just the order of
> permutations or am I missing something?

I've added a file of the permutations N = 7 generated by one of the
programs to the website, which may help you to debug your program -

http://shootout.alioth.debian.org/u32/iofile.php?test=fannkuchredux&file=extra

[Miki]

> Fannkuch has required the permutations to be generated in a particular
> order for years because too many programmers contributed programs that
> did not generate some of the permutations or used faster algorithms to
> generate the permutations.

I've read several implementation so far and I'm still not clear about
the exact algorithm used to generate the permutations.

[Isaac Gouy]

We all struggle with that same problem because the algorithm was taken
from program source code in the paper "Performing Lisp Analysis of the
FANNKUCH Benchmark".


The Lua program provides a succinct implementation, lines 29 through
42

http://shootout.alioth.debian.org/u32/program.php?test=fannkuchredux&lang=lua&id=1


If you find Lisp easier to read then take a look at the deprecated
fannkuch program -

http://shootout.alioth.debian.org/gp4/program.php?test=fannkuch&lang=sbcl&id=2

[Isaac Gouy]

On Sep 3, 4:24 pm, Miki <miki.teb...@gmail.com> wrote:

The permutations are generated in the same order as as permutations
generated by the Tompkins-Paige algorithm, see pages 150-151
"Permutation Generation Methods" Robert Sedgewick.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.7533