viff

changeset 878:f39882ce0e89

Do bitonic sort for arbitrary array sizes.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 08 Aug 2008 10:27:24 +0200
parents f12a36276d56
children 67a0628c2f83
files apps/sort.py
diffstat 1 files changed, 8 insertions(+), 11 deletions(-) [+]
line diff
     1.1 --- a/apps/sort.py	Fri Aug 08 10:23:14 2008 +0200
     1.2 +++ b/apps/sort.py	Fri Aug 08 10:27:24 2008 +0200
     1.3 @@ -41,7 +41,7 @@
     1.4  # Give a player configuration file as a command line argument or run
     1.5  # the example with '--help' for help with the command line options.
     1.6  
     1.7 -from math import log
     1.8 +from math import log, floor
     1.9  from optparse import OptionParser
    1.10  from twisted.internet import reactor
    1.11  
    1.12 @@ -56,7 +56,7 @@
    1.13  parser.add_option("--modulus",
    1.14                    help="lower limit for modulus (can be an expression)")
    1.15  parser.add_option("-s", "--size", type="int",
    1.16 -                  help="array size (must be power of 2)")
    1.17 +                  help="array size")
    1.18  parser.add_option("-m", "--max", type="int",
    1.19                    help="maximum size of array numbers")
    1.20  parser.set_defaults(modulus=2**65, size=8, max=100)
    1.21 @@ -68,10 +68,6 @@
    1.22  if len(args) == 0:
    1.23      parser.error("you must specify a config file")
    1.24  
    1.25 -log_s = log(options.size, 2)
    1.26 -if int(log_s) != log_s:
    1.27 -    parser.error("the array size must be a power of 2")
    1.28 -
    1.29  Zp = GF(find_prime(options.modulus, blum=True))
    1.30  
    1.31  class Protocol:
    1.32 @@ -113,17 +109,18 @@
    1.33          def bitonic_sort(low, n, ascending):
    1.34              if n > 1:
    1.35                  m = n // 2
    1.36 -                bitonic_sort(low, m, ascending=True)
    1.37 -                bitonic_sort(low + m, m, ascending=False)
    1.38 +                bitonic_sort(low, m, ascending=not ascending)
    1.39 +                bitonic_sort(low + m, n - m, ascending)
    1.40                  bitonic_merge(low, n, ascending)
    1.41  
    1.42          def bitonic_merge(low, n, ascending):
    1.43              if n > 1:
    1.44 -                m = n // 2
    1.45 -                for i in range(low, low + m):
    1.46 +                # Choose m as the greatest power of 2 less than n.
    1.47 +                m = 2**int(floor(log(n-1, 2)))
    1.48 +                for i in range(low, low + n - m):
    1.49                      compare(i, i+m, ascending)
    1.50                  bitonic_merge(low, m, ascending)
    1.51 -                bitonic_merge(low + m, m, ascending)
    1.52 +                bitonic_merge(low + m, n - m, ascending)
    1.53  
    1.54          def compare(i, j, ascending):
    1.55