Skip to content

Latest commit

 

History

History

fannkuch_redux

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
src
src
 
 
Cargo.toml
Cargo.toml
 
 
readme.md
readme.md
 
 

readme.md

Fannkuch redux

This is the fannkuch redux benchmark from the benchmarksgame.

Background and description

The fannkuch benchmark is defined by programs in Performing Lisp Analysis of the FANNKUCH Benchmark, Kenneth R. Anderson and Duane Rettig. FANNKUCH is an abbreviation for the German word _Pfannkuchen, or pancakes, in analogy to flipping pancakes. The conjecture is that the maximum count is approximated by n*log(n) when n goes to infinity.

Each program should:

  • Take a permutation of {1,...,n}, for example: {4,2,1,5,3}.

  • Take the first element, here 4, and reverse the order of the first 4 elements: {5,1,2,4,3}.

  • Repeat this until the first element is a 1, so flipping won't change anything more: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3,1,5}, {1,3,2,4,5}.

  • Count the number of flips, here 5.

  • Keep a checksum

    • checksum = checksum + (if permutation_index is even then flips_count else -flips_count)

    • checksum = checksum + (toggle_sign_-1_1 * flips_count)

  • Do this for all n! permutations, and record the maximum number of flips needed for any permutation.

Usage

It takes two arguments in this order:

  • n: the input sequence length: {1, ..., n}
  • (optional) algorithm: the algorithm to use - defaults to the fastest one.
    • 0: scalar algorithm
    • 1: SIMD algorithm