# Examples¶

Learning about a library is a lot easier if you have access to some examples. This page seeks to supply these examples in the form of real-life programming problems like the NQueens problem, or the prime sieve of Eratosthenes.

Algorithmically these examples won’t be explained in detail, but we’ll attempt to clarify the use of BSPy in them.

## Prime Sieve¶

This algorithm is a parallel version of the prime sieve of Eratosthenes.

```# Import the library
import BSPy
from math import *

# Defining the parallel function which takes a BSPObject as first argument
def spmd(bsp: BSPy.BSPObject, n):
# Grabbing the cores and own pid as variables
p = bsp.cores
s = bsp.pid

# If this processor is processor 0
if s == 0:
# Send the variable `n` to everyone.
for i in range(p):
bsp.send(n, i)

# Synchronise, so the messages get sent.
bsp.sync()

# Grab the variable `n` that has just been sent.
max_n = bsp.move()
sqrt_n = floor(sqrt(max_n))
sieveList = Sieve(sqrt_n+1)

# Generate list of primes this core has to do and comb them
per_core = max_n / p
start = max(2, s*per_core) # make sure we don't count 0 and 1
end = min(max_n, (s+1)*per_core)
primeList = Comb(sieveList, start = start, end = end)
primeAmount = len(primeList)

# Send the amount of primes we found to proc 0.
bsp.send(primeAmount, 0)
# Synchronise, so the messages get sent.
bsp.sync()

# If this is processor 0
if s == 0:
total = 0
for i in range(p):
# Add each of the p subtotals to total
total += bsp.move()

print("Total:", total)

def Sieve(n: int):
# Initialize primes array
primes = [1]*n
for i in range(n):
primes[i] = i

# Start sieving
foundPrimes = 0
for i in range(2,n):
# if i isn't sieved out, discard its multiples
if primes[i] != 0:
foundPrimes += 1
for j in range(2*i, n, i):
primes[j] = 0

# Fill primeList
primeList = []
for i, x in enumerate(primes[2:]): # Discard the first 2 elements (0, 1)
if x != 0:
primeList.append(i+2)

return primeList

def Comb(primesSieved: list, start: int, end: int):
# Do some type cleanup
start = int(start)
end = int(end)
# Initialize checklist
numbers = [1]*(end-start)

# comb out the non-primes
for prime in primesSieved:
# x*primeList[i] - start --> needs to be positive
pSieveSqrd = prime**2

# Ensure we we don't try to access weird indicies
if start > pSieveSqrd:
# If the start is larger than psquared, define jStart
# at the next index to cross off
if start % prime == 0:
jStart = start
else:
jStart = start + (prime - start % prime)
else:
jStart = pSieveSqrd

# Do the sieving
for j in range(jStart, end, prime):
numbers[j - start] = 0

# Go through the sieved list
primesList = []
counter = 0
for i, x in enumerate(numbers):
if x != 0:
primesList.append(start+i)

return primesList

# Enclose BSPy.run()
if __name__ == '__main__':
n = 10**5
# Run the function spmd on 4 cores with extra argument n.
BSPy.run(spmd, 4, n)
```

## NQueens¶

Another common example is the NQueens problem. This specific algorithm implementation also times how long it takes to find all the solutions.

```# Import the library
import BSPy

N = 10
max_number = 10**2
counter = 0

# Note that the NQueens function takes in a BSP object as first argument.
def NQueens(BSP):
def isSafe(N, board, row, col):
# Check this row on the left side
for i in range(col):
if board[row][i]:
return False

# Check upper diagonal on left side
i = row
j = col
while i >= 0 and j >= 0:
if board[i][j]:
return False
i -= 1
j -= 1

# Check lower left diagonal
i = row
j = col
while i < N and j >= 0:
if board[i][j]:
return False
i += 1
j -= 1

return True

def solveNQUtil(N, board, col, s):
# Return true if all queens are placed
if col == N:
global counter
counter += 1
return True

res = False
for i in range(N):
if isSafe(N, board, i, col):
board[i][col] = 1
res = solveNQUtil(N, board, col + 1, s) or res

board[i][col] = 0

return res

def solveNQ(N, s, p):
board = [[0] * N for x in range(N)]

i = s
while i < N:
board[i][0] = 1
solveNQUtil(N, board, 1, s)

board[i][0] = 0

i += p
return

#######################
## Start BSP segment ##
#######################

# Start timing
tic = BSP.time()
# Get processor data
p = BSP.cores
s = BSP.pid

# If we are proc 0, send `N` to all processors
if s == 0:
for i in range(p):
BSP.send(N, i)

# Synchronise, so that the messages actually get sent
BSP.sync()
# Grab the message we just received and store it locally
boardSize = BSP.move()

# Solve this processor's part of the NQueens problem
solveNQ(boardSize, s, p)

# Synchronise to ensure everyone is done computing
BSP.sync()

# Send our solution counter to every processor
for i in range(p):
BSP.send(counter, i)

# Synchronise to actually send the messages
BSP.sync()

# Add the sub-totals to the total
total = 0
for i in range(p):
total += BSP.move()

# Stop the timer
toc = BSP.time()

# Only proc 0 needs to print.
if s == 0:
print("we found {} solutions in {} seconds.".format(total, toc - tic))

# Note the if statement again.
if __name__ == '__main__':
BSPy.run(NQueens, 4)
```