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

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

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