MATH6005 Graduate Assignment B, 2021 ANU

Question 1 (You may wish to write code to answer these questions)

If p is a prime, and g is an integer from the set {1,2, . . . , p − 1}, we say that g is a

companion of p when

{ga mod p a ∈ Z and 1 ≤ a < p} = {1,2, . . . , p − 1}.

(A) Find all of the companions of 11. Justify your answer.

(B) Describe how you would go about proving or disproving the following statement:

104651 is prime and 24578 is a companion of 104651.

(C) Here is a four-step method to quickly compute gs modulo p without ever computing

or storing a number that exceeds p2:

Step (1) Complete a table of values like the one below, where m is the largest

power of 2 that does not exceed p:

t gt mod p

1

2

4

8

16⋮

m

Step (2) Write s as a sum of powers of 2 (this is like finding a representation of s

in binary).

Step (3) Use the result of Step (2) to find integers x1, x2, . . . , xc such that

gs mod p = x1x2 . . . xc mod p

and each each xi is in the right-hand column of the table you made in part

Step (1).

Step (4) Evaluate gs mod p by completing a table like the one below:

x1x2 mod p =(x1x2)x3 mod p =(x1x2x3)x4 mod p =⋮ ⋮(x1x2x3 . . . xc−1)xc mod p =

Let p = 104651, g = 24578 and s = 100418. Compute gs mod p, showing all your

working. In your working you should never compute or write down a number that

exceeds p2.

(D) Let s be an integer such that 1 ≤ s < 104651 and

24578s mod 104651 = 3190

Find s and explain how you found it.

Page 3 of 5.

MATH6005 Graduate Assignment B, 2021 ANU

Question 2 A new 16-bit standard for storing floating point numbers, called bfloat16,

has become popular in the last couple of years for use in machine learning programs. It

is a truncated form of single precision floating point (which uses 32 bits) but is di↵erent

to half precision floating point (which also uses 16 bits). Please read the Wikipedia ar-

ticle https://en.wikipedia.org/wiki/Bfloat16_floating-point_format before at-

tempting the questions below. The article is self contained, so it is not necessary to first

know the details of single precision floating point.

For the questions below, show how you obtain your answer - do not use an on-line con-

verter!

(A) What is the value (expressed in decimal notation) of the number stored in bfloat16

format as BADE16?

(B) What is the (very small) value of the number stored in bfloat16 format as 800816?

Express your answer in decimal scientific form with two decimal places. Careful!

(C) In bfloat16 format, the word 7FC016 does not store a number. Why not?

(D) When one million is stored (approximately) in bfloat16 format, what is the exact

(decimal) value of the number stored?

(E) The bfloat16 format is not recommended for storing integer values. What is the

least n ∈ N which cannot be stored exactly in bfloat16 format?

Page 4 of 5.

MATH6005 Graduate Assignment B, 2021 ANU

Question 3 A popular method of sorting a sequence is called Insertion Sort (or

InsertionSort). You can read about it in our recommended textbook1 by Epp in §11.3

(4&5ed), §9.3 (3ed) and on many websites including Wikipedia https://en.wikipedia.

org/wiki/Insertion_sort and Khan Academy https://www.khanacademy.org/computing/

computer-science/algorithms/insertion-sort/a/insertion-sort. (That one has

a nice slow animation.)

Here is a slightly modified version of an algorithm for Insertion Sort given in Epp:

INPUT: Natural number n, a sequence (ai)1..n ⊆ S and an ordering rule for S.

OUTPUT: The members of the sequence (ai)1..n reordered into a new sequence in

non-decreasing order with respect to .

METHOD:

i← 2 (i is the item counter)

while i ≤ n

x← ai (x holds the next item to be inserted)

j ← i − 1 (j marks the position of the item to which x is to be compared)

while j > 0

if x aj (should x be moved left (again) ? )

then

aj+1 ← aj (yes, so slide aj right)

j ← j − 1

else

aj+1 ← x (no, insert x here)

j ← −1

end if

end while

if j = 0 then a1 ← x (if x has not yet been inserted, insert it now)

i← i + 1

end while

END METHOD

(A) Apply the algorithm to sort the sequence F,D,C,E,B,C into alphabetical order. Show

the state of the sequence each time the ‘i ≤ n’ test in line 2 of the method is

performed.

(B) How many item comparisons ‘x aj’ are performed for the application (A)?

(C) In no more that 50 words compare the eciencies of Selection Sort and Insertion

Sort, mentioning any situations where one is superior to the other. Be sure to

reference any sources you use for your answer. (References are not included in the

word count.)

(D) Rewrite the algorithm using indirect addressing, so that no sequence items are actu-

ally moved. The INPUT should be unchanged, but the OUTPUT should now read:

OUTPUT: A permutation ⇡ ∶ {1, .., n} → {1, .., n} for which the sequence (a⇡(i))1..n

is

in non-decreasing order with respect to .

End of Questions for Assignment B

1Susanna Epp: Discrete Mathematices with Applications. Cengage 1990-2020

Page 5 of 5.

欢迎咨询51作业君