# 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 $v$. 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 $v$:

So, for a given $v$ and $f(x)=x^2 - v$, we want to find $f(x) = 0$. 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 $x$ ($x_0$) you can use a reasonable initial guess (e.g. $\frac{v}{2}$).
• 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 $10^{-4}$ 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 $[0, 5)$.

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.