Description
1. Algebraic Operations on Binary Values
In this exercise you are required to implement addition and multiplication, as efficiently as possible.
One way to maximize algebraic efficiency is to operate directly on the binary representation of the
manipulated numbers. Three such bitwise algorithms are described in the appendix at the end of this
document. We recommend to read this appendix now. Note that for completing this exercise you
need to understand how the algorithms work, not why they are efficient.
The supplied BinOps class represents binary numbers using integer arrays of length n=16, in which
each value is 0 or 1. The algorithms described in the appendix operate efficiently on any given n,
and thus the 16 constant is not important. Further, theses algorithms can be implemented in either
hardware and software.
• Start by implementing and testing the bin2String function.
• Then implement and test the add function, following the addition algorithm presented in the
appendix.
• Next, implement the shift and then the mult functions, following the multiplication algorithm
presented in the appendix.
• Finally, implement the int2bin and bin2int functions. Lecture 2-2 presented binary-to-decimal
and decimal-to-binary algorithms. The former algorithm was inefficient, and both algorithms
operated on strings rather than arrays. So now you need to come up with a better binary-todecimal algorithm, and implement both algorithms in the BinOps class.
Read the appendix now, and then follow the implementation guidelines.
Implementation guidelines
• In the addition and multiplication algorithms, proceed from right to left, and operate on all n bitpairs.
• In all the algorithms, if the left-most carry bit is 1, ignore it. The resulting value will be correct
up to n bits, and that’s fine.
• In add(int[] x, int[] y) and mult(int[] x, int[] y) you can assume that x and y are of
the same length.
• In int2bin(int x) it is safe to assume that x is positive and smaller then 216, so that the retuned
array is of length n=16.
• In all functions you can assume that input arrays (int[] x and int[] y) are binary, that is, the
array values are either 0 or 1.
Examples:
% java BinOps 15 add 5
20
% java BinOps 15 mult 5
75
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 2
Appendix: Algorithms1
Computers perform algebraic operations like addition, subtraction, multiplication and division by
operating directly on n-bit binary values, n typically being 16, 32 or 64 bits, depending on the
operands’ data types. Ideally, we seek algebraic algorithms whose running time is proportional in
this parameter n. Algorithms whose running time is proportional to the values of n-bit numbers are
unacceptable, since these values are exponential in n. For example, suppose we implement the
multiplication operation � ∗ � naïvely, using the repeated addition
algorithm sum = 0, i = 1 … y {sum = sum + x}, return sum. If y is 64-bit wide, its value may well be
greater than 9,000,000,000,000,000, implying that the loop may run for billions of years before
terminating.
In sharp contrast, the running times of the algebraic algorithms that we present below are
proportional not to the values of these n-bit numbers, which may be as large as 2&, but rather to n,
the number of their digits. When it comes to algebraic efficiency, that’s the best that we can possibly
hope for.
Addition
The addition of three bits generates one sum bit and one carry bit. This operation is defined as
follows:
To add two n-bit binary values, we proceed from right to left, adding each pair of bits and the carry
bit from the previous addition. The first carry bit is 0. Here is an example (n=16):
The running time of this addition algorithm is the time it takes to perform n 3-bit additions.
Formally, we say that the running time is a polynomial function of n, the number of bits (in this
example, n=16).
Technical comment: In principle, we can stop the bitwise addition operations once we have only 0
bits remaining in both operands. However, since in the worst case we have to perform n iterations,
and since n is always a small constant like 16, 32, or 64, we’ll always operate on all the bit-pairs,
from right to left.
1 This appendix is an excerpt from The Elements of Computing Systems, by Nisan and Schocken.
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 3
Multiplication
Consider the standard multiplication method taught in elementary school. To compute 356 times 73,
we line up the two numbers one on top of the other, right-justified. Next, we multiply 356 by 3.
Next, we “shift” 356 to the left one position, and multiply 3560 by 7 (which is the same as
multiplying 356 by 70). Finally, we sum up the columns and obtain the result. This procedure is
based on the insight that 356 × 73 = 356 × 70 + 356 × 3. The binary version of this procedure is
illustrated below, using another example:
Let’s inspect the multiplication procedure illustrated at the left of this figure. For each i’th bit of y,
we “shift” x i times to the left (same as multiplying x by 2/
). Next, we look at the i’th bit of y: If it’s
1, we add the shifted x to an accumulator; otherwise, we do nothing. The algorithm shown on the
right formalizes this procedure. Note that 2 * shiftedx can be computed efficiently by either leftshifting the bit-wise representation of shiftedx, or by adding shiftedx to itself.
Running time: The multiplication algorithm performs n iterations, where n is the bit-width of the
inputs. In each iteration, the algorithm performs a few addition and comparison operations. It
follows that the total running-time of the algorithm is � + � ∙ � , where a is the time it takes to
initialize a few variables, and b is the time it takes to perform a few addition and comparison
operations. Formally, the algorithm’s running time is a polynomial function of n, the bit-width of the
inputs.
To reiterate, the running time of this � × � algorithm does not depend on the values of x and y;
rather, it depends on the bit-width of the inputs. In computers, the bit-width is normally a small
constant like 16 (short), 32 (int), or 64 (long), depending on the data types of the inputs. Suppose
that the data type is short. If we assume that each iteration of the multiplication algorithm entails
about 10 machine instructions, it follows that each multiplication operation will require at most 160
computer cycles, irrespective of the size of the operands. Compare this to the 10 ∙ 245 = 655,350
cycles that will be needed by algorithms whose worst case running time is proportional not to the
bit-width , but rather to the values, of their inputs.
Technical comment: Same as in the end of the addition algorithm.
Division
(This is an optional section. You don’t have to read it nor implement the division algorithm).
The naïve way to compute the division of two n-bit numbers x / y is to count how many times y can
be subtracted from x, until the remainder becomes less than y. The running time of this algorithm is
proportional to the value of the dividend x, and thus is unacceptably exponential in the number of
bits n.
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 4
To speed up things, we can try to subtract large chunks of y’s from x in each iteration. For example,
suppose we have to divide 175 by 3. We start by asking: What is the largest number, x = (90, 80, 70,
… 20, 10) so that 3 ∙ � ≤ 175? The answer is 50. In other words, we managed to subtract 50 3’s from
175, shaving 50 iterations from the naïve approach. This accelerated subtraction leaves a remainder
of 175 − 3 ∙ 50 = 25. Moving along, we now ask: What is the largest number, x = (9, 8, 7, … 2, 1) so
that 3 ∙ � ≤ 25? The answer is 8, so we managed to make 8 additional subtractions of 3, and the
answer, so far, is 50 + 8 = 58. The remainder is 25 − 3 ∙ 8 = 1, which is less than 3, so we stop the
process and announce that 175 / 3 = 58 with a remainder of 1.
The technique just described is the rationale behind the dreaded school procedure known as long
division. The binary version of this algorithm is identical, except that instead of accelerating the
subtraction using powers of 10 we use powers of 2. The algorithm performs n iterations, n being the
number of digits in the dividend, and each iteration entails a few multiplication (actually, shifting),
comparison, and subtraction operations. Once again, we have an �/ � algorithm whose running time
does not depend on the values of x and y. Rather, the running time is a polynomial function of n, the
bit-width of the inputs.
Writing down this algorithm as we have done for multiplication is not difficult. To make things
interesting, the following figure presents another division algorithm which is just as efficient, but
more elegant and easier to implement.
Suppose we have to divide 480 by 17. The algorithm shown above is based on the insight:
480/17 = 2 ∙ (240/17) = 2 ∙ (2 ∙ (120/17)) = 2 ∙ (2 ∙ (2 ∙ (60/17))) = …, and so on. The depth of this
recursion is bounded by the number of times y can be multiplied by 2 before reaching x. This also
happens to be, at most, the number of bits required to represent x. Thus the running time of this
algorithm is also a polynomial function of n, the bit-width of the inputs.
One snag in this algorithm is that each multiplication operation also requires n operations. However,
an inspection of the algorithm’s logic reveals that the value of the expression (2 * q * y) can be
computed without multiplication. Instead, it can be obtained from its value in the previous recursion
level, using addition.
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 5
2. Prime numbers
A prime number is a natural number that is divisible only by 1 and itself. There is an infinite
number of prime numbers; some examples are: 2, 3, 5, 7, 11, 13, 17, and 19.
Write a program Primes that reads a command-line integer N, and prints all the prime numbers
smaller than N. You may assume N is even and larger than 2.
Your program should implement the Sieve of Sundaram, which is somewhat more sophisticated
than the Sieve of Eratosthenes presented in lecture 4-2. The Sieve of Sundaram sieves out the
composite numbers just as the Sieve of Eratosthenes does, but even numbers are not considered. The
algorithm of the sieve of Sundaram is presented below.
1. Start with the integers from 1 to n, where n=(N-2)/2.
2. Remove all integers of the form i + j + 2ij where:
a. 1 ≤ � ≤ �
b. � + � + 2�� ≤ �
3. The remaining numbers are doubled and incremented by one, producing all the odd prime
numbers (i.e., all primes except 2) below 2n + 2.
Think: when iterating over i and j, what should be the bounds on i and j?
Here are examples of the program execution (the main function is supplied in Primes.java):
% java Primes 40
The prime numbers up to 40 are:
2 3 5 7 11 13 17 19 23 29 31 37
% java Primes 400
The prime numbers up to 400 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127
131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257
263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 6
3. Language identification
In many applications of natural language processing (NLP) the first step is to identify the language
in question. A simple method for language identification is to compare the frequencies of letters to
known distributions for a set of languages. For example, in English the most frequent letters are
etaoi, in French they are esait, and in German they are ensri.
Implement a program LetterFreq that reads text from the input, computes the frequencies of each
letter in the text, and compares these letter frequencies to those of English, French, and German.
For example, for the following text in the supplied English.txt:
% more English.txt // the “more” command can be used to list the contents of a file; use “type” on windows
Like all Vogon ships it looked as if it had been not so much designed as con- gealed. The
unpleasant yellow lumps and edifices which protuded from it at unsightly angles would have
disfigured the looks of most ships, but in this case that was sadly impossible. Uglier things
have been spotted in the skies, but not by reliable witnesses. In fact to see anything much
uglier than a Vogon ship you would have to go inside and look at a Vogon. If you are wise,
however, this is precisely what you will avoid doing because the average Vogon will not think
twice before doing something so pointlessly hideous to you that you will wish you had never been
born – or (if you are a clearer minded thinker) that the Vogon had never been born.
The program will output scores for three languages; the lower the score, the more likely this is the
right language:
% java LetterFreq < English.txt
en 0.0028980848443422784
de 0.011142722614205293
fr 0.009481364988177894
% java LetterFreq < French.txt
en 0.008859697462879132
de 0.007577847692666364
fr 0.0011959851118153015
For simplicity, we focus only on the letters a-z. Uppercase letters are converted to lowercase, and all
other letters (è, ù, etc.), as well as spaces and punctuation (.,:), are disregarded. The frequencies are
saved in a double array called q. The frequencies are the number of times each letter appeared in the
text divided by the total number of letters (without punctuation, etc.). Therefore, the elements of q
are between 0 and 1 and the sum of the array is 1. The first element, q0, is the frequency of the letter
a in the text. The last element q25 is the frequency of the letter z in the text.
The score � for each language is computed by comparing its letter frequencies array to q. The
language frequencies arrays are supplied in the class LetterFreq: en for English, fr for French, and de
for German. These arrays have the same structure as the text frequencies array. The score is
computed by summing over the squared differences between the text letter frequencies and the
language letter frequencies. That is, to compare the text frequencies array q to a language
frequencies array f, we compute:
�(�, �) = D (�/ − �/)E
/∈{H,…,J}
= (�H − �H)E + (�L − �L)E + ⋯ + (�J − �J)E
To check that the implementation is correct, you can verify that S(�, �) = 0 for any language
frequencies array f, which can be either en or fr or de.
Complete the supplied LetterFreq class. To test your implementation, run it both with the file
English.txt and with the file French.txt. You can also try it with your own text.
Introduction to CS, IDC Herzliya, 2019-20 / Homework 4 / page 7
Submission
Before submitting your solution, inspect your code and make sure that it is written according to our
Java Coding Style Guidelines. Also, make sure that each program starts with the program header
described in the Homework Submission Guidelines. Both documents can be found in the Moodle
site, it is your responsibility to read them. Any deviations from these guidelines will result in points
penalty. Submit the following files only:
➢ BinOps.java
➢ Primes.java
➢ LetterFreq.java
Deadline: Submit Homework 4 no later than December 22 23:55. You are welcome to submit
earlier.
