A Simple Program to Calculate Integer Square Root
This example Fortress program takes command line input, does a relatively simple calculation, and prints results. Tests are provided, and the complete program text is given.
We use Newton's method ( http://en.wikipedia.org/wiki/Newtons_method) to calculate integer square-root (isqrt), the largest integer less than or equal to the real square-root. Only integer operations are used, allowing us to operate on large numbers.
A Basic Complete Program
Let's start with the whole file.
First is the standard prelude, which names the component. Note that the component name, isqrt, must match the file name, isqrt.fss. We also export the Executable interface, which means that the component can be executed as a program, e.g., from the command line.
We define a helper function inrange that takes 2 integers, x and root, both of type ZZ (also known as a bignum); inrange checks that root is the integer square-root of x and returns a boolean.
Next is the definition of the function isqrt, which takes one bignum argument x, and returns a bignum, the integer square-root of x. We declare a variable bignum approx with initial value x. (You can tell that it's a variable, and not a constant, because of the symbol := in the definition.) As long as our approximation is not in the desired range, we refine it using Newton's method. When we are in range, we return the value of approx.
When a Fortress program is run from the command line, the run function is called and passed an array of Strings, which are the command-line arguments. The run function
1) takes the first command-line argument and converts it to an integer using the helper function getArg
2) calls isqrt, and
3) prints the result and a newline.
The program is called on the number 21 as follows:
fortress isqrt.fss 21
The following output is produced:
~/PFC/bin/fortress isqrt.fss 21 Guessing FORTRESS_HOME=/Users/steve/PFC 4
Note that the call is visible at the top of the output. That's all there is to it.
Adding a Test
Any method or function definition preceded by the keyword test has a special status.
The numbers and strings to the right of println are concatenated; before concatenation, the numbers are converted to strings. We loop with i taking on values in the range 0 to 15 and x taking on corresponding powers of 10. The big function gives us a bignum 10. (This will happen automatically when the typechecker inserts automatic coercion --- Real Soon Now!) After we call isqrt, we assert that the result is in range.
To run the test, we use the fortress test command:
~/PFC/bin/fortress test isqrt.fss Guessing FORTRESS_HOME=/Users/steve/PFC Check some powers of 10 10^0 => isqrt (1) = 1 10^8 => isqrt (100000000) = 10000 10^1 => isqrt (10) = 3 10^2 => isqrt (100) = 10 10^9 => isqrt (1000000000) = 31622 10^3 => isqrt (1000) = 31 10^4 => isqrt (10000) = 100 10^10 => isqrt (10000000000) = 100000 10^5 => isqrt (100000) = 316 10^6 => isqrt (1000000) = 1000 10^11 => isqrt (100000000000) = 316227 10^7 => isqrt (10000000) = 3162 10^14 => isqrt (100000000000000) = 10000000 10^12 => isqrt (1000000000000) = 1000000 10^13 => isqrt (10000000000000) = 3162277 10^15 => isqrt (1000000000000000) = 31622776
That's a weird order --- oh yes --- Fortress does stuff in parallel. It looks like my two-processor laptop assigned iterations to both processors --- nice. To get the test cases to happen in order, replace 0:15 with seq(0:15).
~/PFC/bin/fortress test isqrt.fss Guessing FORTRESS_HOME=/Users/steve/PFC Check some powers of 10 10^0 => isqrt (1) = 1 10^1 => isqrt (10) = 3 10^2 => isqrt (100) = 10 10^3 => isqrt (1000) = 31 10^4 => isqrt (10000) = 100 10^5 => isqrt (100000) = 316 10^6 => isqrt (1000000) = 1000 10^7 => isqrt (10000000) = 3162 10^8 => isqrt (100000000) = 10000 10^9 => isqrt (1000000000) = 31622 10^10 => isqrt (10000000000) = 100000 10^11 => isqrt (100000000000) = 316227 10^12 => isqrt (1000000000000) = 1000000 10^13 => isqrt (10000000000000) = 3162277 10^14 => isqrt (100000000000000) = 10000000 10^15 => isqrt (1000000000000000) = 31622776
More Argument Parsing
Suppose we'd like a little more flexibility in specifying input. We may wish to specify usage info.
To accomplish this, we need to do a little argument parsing.
The | surround operator gets us the size of the argument list and is used by a case statement to operate on a single value, a range, or a strided range.
We used a compact notation for looping over the values generated by the ranges.
is equivalent to
To print the usage info, we can make a call with no arguments.
~/PFC/bin/fortress isqrt.fss Guessing FORTRESS_HOME=/Users/steve/PFC Compute the integer square root by Newton's method: root^2 <= x < (root+1)^2 1 arg ... the number to sqrt 2 args ... the range to sqrt 3 args ... the range and stride to sqrt else ... print this usage info Examples: => fortress isqrt.fss [print this usage info] => fortress isqrt.fss 9 isqrt (9) = 3 => fortress isqrt.fss 1 4 isqrt (1) = 1 isqrt (2) = 1 isqrt (3) = 1 isqrt (2) = 2 => fortress isqrt.fss 1 10 3 isqrt (1) = 1 isqrt (4) = 2 isqrt (7) = 2 isqrt (10) = 3 => fortress test isqrt.fss [compute and verify a bunch of values]
And now a call with three arguments.
~/PFC/bin/fortress isqrt.fss 1 10 3 Guessing FORTRESS_HOME=/Users/steve/PFC isqrt (1) = 1 isqrt (4) = 2 isqrt (7) = 2 isqrt (10) = 3
The Complete Program
This program must be stored in file isqrt.fss. Two more tests were added; all tests are run when the test flag is used.
The Test Output
~/PFC/bin/fortress test isqrt.fss Guessing FORTRESS_HOME=/Users/steve/PFC Check some powers of 10 10^0 => isqrt (1) = 1 10^1 => isqrt (10) = 3 10^2 => isqrt (100) = 10 10^3 => isqrt (1000) = 31 10^4 => isqrt (10000) = 100 10^5 => isqrt (100000) = 316 10^6 => isqrt (1000000) = 1000 10^7 => isqrt (10000000) = 3162 10^8 => isqrt (100000000) = 10000 10^9 => isqrt (1000000000) = 31622 10^10 => isqrt (10000000000) = 100000 10^11 => isqrt (100000000000) = 316227 10^12 => isqrt (1000000000000) = 1000000 10^13 => isqrt (10000000000000) = 3162277 10^14 => isqrt (100000000000000) = 10000000 10^15 => isqrt (1000000000000000) = 31622776 Check the 200 consecutive integers in [10^40, 200+10^40) 10000000000000000000000000000000000000000................................................. 10000000000000000000000000000000000000050................................................. 10000000000000000000000000000000000000100................................................. 10000000000000000000000000000000000000150................................................. Check all the integers in [0, 10^5] 0.........1000.........2000.........3000.........4000......... 5000.........6000.........7000.........8000.........9000......... 10000.........11000.........12000.........13000.........14000......... 15000.........16000.........17000.........18000.........19000......... 20000.........21000.........22000.........23000.........24000......... 25000.........26000.........27000.........28000.........29000......... 30000.........31000.........32000.........33000.........34000......... 35000.........36000.........37000.........38000.........39000......... 40000.........41000.........42000.........43000.........44000......... 45000.........46000.........47000.........48000.........49000......... 50000.........51000.........52000.........53000.........54000......... 55000.........56000.........57000.........58000.........59000......... 60000.........61000.........62000.........63000.........64000......... 65000.........66000.........67000.........68000.........69000......... 70000.........71000.........72000.........73000.........74000......... 75000.........76000.........77000.........78000.........79000......... 80000.........81000.........82000.........83000.........84000......... 85000.........86000.........87000.........88000.........89000......... 90000.........91000.........92000.........93000.........94000......... 95000.........96000.........97000.........98000.........99000......... 100000
