#!/bin/bash
# psieve.ssh
# Sieve of Eratosthenes (master/slave ssh version)
#
# Example:
# (make sure nap is running)
# ./psieve.ssh 1000 5 n2 n3 n4 n1
#
# The example computes the primes less than 1000 using five processes.
# The first process runs locally as the master. The remaining four are
# run on nodes n2 n3 n4 and n1. 

# Check arguments and make sure a nap server is running
[ $# -lt 3 ] && [ $# -ne 0 ] && { echo "psieve.ssh <number> <parts> <node1> <node2> ..."; exit 1; }
nap_dump >/dev/null 2>&1
[ $? -ne 0 ] && { echo "This program requires nap. Type \"man nap\" for help."; exit 1; }

# --------------------------------------------------------------------------
# Slave process
# --------------------------------------------------------------------------
if test $# -eq 0; then
  p=( $(nin partition) )
  P=( $(seq ${p[0]} 2 ${p[1]}) )
  n=${#P[*]}
  while true; do
# Read in the next prime
    m=$(nin "P${p[0]}")
    let mm=$m*$m
# Zero is the exit code
    [ $m -eq 0 ] && break; 
# Determine the next largest odd multiple of $m in our range:
    if test $(( ${p[0]} % $m )) -eq 0; then
      k=${p[0]}
    else
      k=$(( ((${p[0]} + $m - ${p[0]} % $m) / $m) * $m ))
      k=$(( $k + (($k % 2 + 1) % 2) * $m ))
    fi
    [ $k -lt  $mm ] && k=$mm;
# Convert to an index in the array
    k=$(( ($k - ${p[0]}) / 2 ))
    [ $k -gt $n ] && continue;
    while test $k -lt $n; do
      unset P[$k]
      let k=$k+$m
    done
  done
  echo ${P[*]} | nbout "Q${p[0]}"
  exit 0
fi


# --------------------------------------------------------------------------
# Master process
# --------------------------------------------------------------------------

M=$1
C=$2

# Collect the list of nodes
declare -a NODE
shift
shift
np=0
while test "$#" -ge 1; do
  NODE[$np]=$1
  let np+=1
  shift
done

N=$(echo "scale=0;sqrt($M)/2 + 1" | bc)
h=$(($M / $C))
n=$(($h + $h % 2 - 1))
n2=$(($n / 2))
h=$(($n + 1))
k=$(($n + 2))

# The first partition must contain sqrt(M)
[ $n -lt $N ] && echo "Too many partitions" && exit 1

# Set up the partitions, including one to run on the master
P=( $(seq 3 2 $n) )
c=0;
while test $k -lt $M; do
  l=$(($k + $h))
  [ $l -gt $M ] && l=$M
  echo "$k $l"    | nbout partition
  W[$c]=$k
  let k=$l+2
  let c=$c+1
done
c=$(seq 0 $(($c - 1)))

# Start up the slave processes on the listed nodes
for i in $c; do
  j=$(($i % $np))
  echo ssh -f ${NODE[$j]} $(pwd)/$0
  ssh -f ${NODE[$j]} $(pwd)/$0
done

# Run the sieve
j=0
while test $j -le $N; do
  if test -n "${P[$j]}"; then
# Send the next prime to each slave ($c of them)
    for k in $c; do
      echo ${P[$j]} | nout "P${W[$k]}"
    done
    k=$(((${P[$j]} * ${P[$j]})/2 - 1))
    until test $k -gt $n2; do
      unset P[$k]
      let k+=${P[$j]}
    done
  fi
  let j+=1
done

# Instruct the slaves to print results and exit
for k in $c; do
  echo 0 | nbout "P${W[$k]}"
done

# Collect and print results in order
echo -n 2 ${P[*]}  				
echo -n " "
for k in $c; do
  echo -n "$(nin "Q${W[$k]}") "		
done
echo