# Assignment: basic data types

Download this crate for the first homework assignment. It contains some tests, benchmarks, and function prototypes.

## 1 Population count

For some applications, we want to know how many bits in an integer are set to *1*. Counting the number of ones is often called the *population count*. For example:

```
1101 1010 = 5
1001 1000 = 3
```

Intel CPUs since Nehalem have a dedicated `POPCNT`

instruction to count the number of bits set to *1*. In this assignment, you will implement your own population count function.

### 1.1 Implement `popcnt`

Implement `popcnt`

following Brian Kernighan’s method: the expression `v & (v-1)`

clears the rightmost bit of `v`

that is set to *1*. You can do a population count by repeatedly clearing the rightmost bit set to *1*, until all bits are cleared, maintaining a counter while doing so. Write your implementation in the `popcnt`

function in `src/popcnt.rs`

. After implementing the population count, you can test its implementation with `cargo test popcnt_test`

.

**Hint:** You will probably need a `while`

loop, which has the following form in Rust:

```
while condition {
// Do something.
}
```

### 1.2 `popcnt`

time complexity

How many loop iterations does Kernighan’s method need on average for a random 64-bit integer?

### 1.3 Benchmark `popcnt`

I have provided a table-driven implementation of `popcnt`

, named `popcnt_lookup`

. Benchmark your `popcnt`

against this implementation. Benchmarks are only supported in nightly versions of Rust. Install the nightly version of Rust besides Rust stable:

```
$ rustup install nightly
```

After that, you can run the benchmarks using Rust nightly:

```
$ rustup run nightly cargo bench
```

What results do you get? Did you expect these results? Keep in mind that the lookup-table implementation always uses 8 lookups.

## 2 Computing square roots

Most, if not all, standard libraries provide a function to compute the square root of some value . Such functions typically use a processor instruction to compute the square root. In assignment, you will implement your own function to find the square root of a number iteratively. Consider the the square root of a given number :

So, for a given and , we want to find . We can use Newton’s method to iteratively find the solution:

In our case:

### 2.1 Implement `sqrt`

- Implement a function that uses this iterative method to compute the square root of a number in the
`sqrt`

function in`src/sqrt.rs`

. - For the initial value of () you can use a reasonable initial guess (e.g. ).
- Use five iterations before stopping. Newton’s method typically doubles the number of correct digits with each iteration. (Feel free to add a couple more iterations if the unit tests fail sometimes.)
- You can test your implementation with
`cargo test sqrt_test`

. This test generates random floating point numbers and check that the result of your square root implementation is within from Rust’s`sqrt`

method.

**Hint:** You can loop for five iterations by `for`

-looping over a range. For example:

```
for i in 0..5 {
// Do something.
}
```

`0..5`

is the half-open (integer) interval .

**Warning:** do not use this function in real-world projects. The standard library’s implementation is typically much faster.

**Note:** the widely used Babylonian method for finding square roots can also be derived from the form above:

## Submission

- Submit your updated project, archived as a
`tar.gz`

or`zip`

file. - Include the first names of the team members in the archive name.
- Run
`cargo clean`

before archiving the project. - Your answers to 1.2 and 1.3 must be included as a
**plain text file**(not PDF, Word, etc.) in the main project directory.

The `tar.gz`

or `zip`

file should be uploaded through this page. The deadline is April 24 at 13:00.