HW#3.3 notes D.W. Matula, March. 23, MMVI

HW#3.4 notes D.W. Matula, Oct. 01, 03

For b):

Let’s use the patent example:

For c):

Let’s use the same values as in the b) example:

N/D = .3657483750 / .784731

Short reciprocal (for .784731) SR = 1.28

Multiplying N and D with SR:

N/D = SR*N / SR*D;

Values are:

.3657483750 / .784731 = .3657483750*1.28 / .784731*1.28

.3657483750 / .784731 = .46815792 / 1.00445568

This gives the first couple digits or the result (.46). In order to get the next two multiply the digits just determined with the new D:

.46* 1.00445568 = 0.4620496128

and subtract the result:

.46815792 - 0.4620496128 = 0.0061083072

Continue until desired accuracy is obtained.

For d):

Let N = 12345; D = 6789.

N/D = 12345 / 6789;

N/D = 12345 / .6789 * 10⁴;

Let’s consider .6789 = 1-Eps => Eps = 1-.6789 = 0.3211.

(1+Eps) = 1.3211

so,

N/D = 12345 / .6789 * 10^4;

N/D = 12345 * 10^-4/ .6789;

N/D = 12345 * 10^-4/ (1-Eps);

N/D = 12345 * 10^-4 * (1+Eps) / (1-Eps)* (1+Eps);

N/D = 12345 * 10^-4 * (1+Eps) / (1- Eps²);

N/D = 12345 * 10^-4 * 1.3211 / (1- 0.10310521);

N/D = 12345 * 10^-4 * 1.3211 / 0.89689479;

N/D = 1.63089795 / 0.89689479;

Next step is to multiply both nominator and denominator with (1 + Eps²); this way the next denominator will be (1- Eps⁴) which is much closer to 1 than (1- Eps²);

Iterate until desired precision is reached.

HW#3.5 notes

For a):

Complete Covering Strings

D.W. Matula, Oct. 01, 03

Claim: For every k there is a binary (circular) string of length 2^k such that the 2^k k-bit substrings are all distinct.

Example: For k = 3 let b₀ b₁...b₇ = 0001110100…

0: 000

1: 001

3: 011

7: 111

6: 110

5: 101

2: 010

4: 100

Argument: Create a 2^k-1 vertex directed graph with the vertices labeled by the substrings having binary values 0,1,…, 2^k-1-1. For any k-bit string c₁ c₂...c_k , introduce an edge directed from node c₁ c₂...c_k-1 to node c₂ c₃...c_k labeled c_k.

Then note:

• The graph is unique for each k.
• The graph is regular with indegree and outdegree 2 at each node, counting the loops at nodes O^[k-1] and 1^[k-1].

• The graph is strongly connected.
• The graph has a directed Eulerian Cycle.
• Enumeration of the labels on the directed edges of any Eulerian Cycle provides a circular string of length 2^k satisfying the claim.

Example: For k = 4 the graph is:

Note the symmetry about the vertical axis (attributable to complimenting the strings).

Claim (General): For every k and β ≥ 2, there is a (circular) β-ary string of length β^k such that the β^k k-digit substrings are all distinct.

Argument: Create a graph on β^k-1 vertices and β^k directed edges with each (k-1) tuple from digits {0, 1, 2, … , β-1} a vertex and for each k-digit string d₁ d₂…d_k, provide a directed edge from vertex d₁d₂…d_k-1, to vertex d₂ d₃…d_k labeled d_k. The graph is regular of in and out degree β and is Eulerian. The labels on an Eulerian cycle provide the desired circular string.