1 (*<*) |
|
2 theory a5 = Main: |
|
3 (*>*) |
|
4 |
|
5 subsection {*BIGNAT - Specification and Verification*}; |
|
6 |
|
7 text{* |
|
8 Hardware platforms have a limit on the largest number they can represent. This is normally fixed by the bit lengths of registers and ALUs used. In order to be able to perform calculations that require arbitrarily large numbers, the provided arithmetic operations need to be extended in order for them to work on an abstract data type representing numbers of arbitrary size. |
|
9 |
|
10 In this exercise we will build and verify an implementation for BIGNAT, an abstract data type representing natural numbers of arbitrary size. |
|
11 *} |
|
12 |
|
13 text {*\subsubsection*{Representation}*} |
|
14 |
|
15 text{* |
|
16 A BIGNAT is represented as a list of natural numbers in a range supported by the target machine. In our case, this will be all natural numbers in the range [0, BASE-1]. (Note: natural numbers in Isabelle are of arbitrary size) |
|
17 *} |
|
18 |
|
19 types |
|
20 bigNat = "nat list" |
|
21 |
|
22 text{* |
|
23 Define a function @{term "valid"} that takes a value for BASE, and checks if the given BIGNAT is valid. |
|
24 *} |
|
25 |
|
26 consts valid :: "nat \<Rightarrow> bigNat \<Rightarrow> bool" |
|
27 |
|
28 text{* |
|
29 Define a function @{term "val"} that takes a BIGNAT and its corresponding BASE, and returns the natural number represented by it. *} |
|
30 |
|
31 consts val :: "nat \<Rightarrow> bigNat \<Rightarrow> nat" |
|
32 |
|
33 text {*\subsubsection*{Addition}*} |
|
34 |
|
35 text{* |
|
36 Define a function @{term "add"} that adds two BIGNATs with the same value for BASE. Make sure that your algorithm preserves the validity of the BIGNAT representation. |
|
37 *} |
|
38 |
|
39 consts add :: "nat \<Rightarrow> bigNat \<Rightarrow> bigNat \<Rightarrow> bigNat" |
|
40 |
|
41 text{* |
|
42 Using @{term "val"}, verify formally that your function @{term "add"} computes the sum of two BIGNATs correctly.*} |
|
43 |
|
44 text{* |
|
45 Using @{term "valid"}, verify formally that your function @{term "add"} preserves the validity of the BIGNAT representation.*} |
|
46 |
|
47 |
|
48 text {* |
|
49 \subsubsection*{Multiplication}*} |
|
50 |
|
51 text{* |
|
52 Define a function @{term "mult"} that multiplies two BIGNATs with the same value for BASE. You may use @{term "add"}, but not so often as to make the solution trivial. Make sure that your algorithm preserves the validity of the BIGNAT representation. |
|
53 *} |
|
54 consts mult :: "nat \<Rightarrow> bigNat \<Rightarrow> bigNat \<Rightarrow> bigNat" |
|
55 text{* |
|
56 Using @{term "val"}, verify formally that your function @{term "mult"} computes the product of two BIGNATs correctly.*} |
|
57 |
|
58 text{* |
|
59 Using @{term "valid"}, verify formally that your function @{term "mult"} preserves the validity of the BIGNAT representation.*} |
|
60 |
|
61 |
|
62 (*<*) end (*>*) |
|
63 |
|
64 |
|
65 |
|
66 |
|