tag:blogger.com,1999:blog-49437585726565543972024-02-18T22:51:00.818-08:00rtybaseRuslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.comBlogger49125tag:blogger.com,1999:blog-4943758572656554397.post-36626821707869210442023-07-23T16:16:00.000-07:002023-07-23T16:16:20.867-07:00The final piece of the puzzle<p>The sweat on your face,<br />
A sign of hard work,<br />
Is finally getting colder.</p>
<p>The fever you felt,<br />
It was a mark<br />
Of the upcoming game over.</p>
<p>It took a while<br />
To see the truth,<br />
You finally see the impalpable.</p>
<p>I mean that part,<br />
Which drove you mad,<br />
The final piece of the puzzle.</p>
Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-36243926529139721472022-09-08T16:07:00.004-07:002023-07-23T16:18:57.474-07:00The verse of the innevitable ...<p>The chapter is closed and as it turns,<br />
The chapter has many pages.<br />
What was recorded, the things you deserve,<br />
Will stay in the book for ages.</p>
<p>The words in those pages, they will reveal<br />
The happy, the struggle, the challenge.<br />
The way it was handled, the power of will<br />
Sometimes, the lack of courage.</p>
<p>The letters, in opening, start like a breeze,<br />
Then the gusts get stronger and stronger.<br />
The ending is like the calm of the seas<br />
When the hurricane is over.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-49065857595751834082021-04-12T10:21:00.005-07:002021-04-12T10:32:21.801-07:00Golden ratio, Fibonacci numbers and ... another sequence<p>Over the last weekend, another <a href="https://math.stackexchange.com/questions/4096723/iterated-function-an-lfloor-n-phi-0-5-rfloor/">question was asked and later disappeared</a> on/from <a href="https://math.stackexchange.com/">Math StakExchange</a>. The sequence, from that question, is too nice to "let it go", thus, copy/pasting my answer here.</p>
<p><i>Let's define the following sequence $$a(n)=\left\lfloor n\cdot\phi + \frac{1}{2}\right\rfloor$$
where $\phi$ is the <a href="https://en.wikipedia.org/wiki/Golden_ratio">golden ratio</a>. Is there a closed form for the following sequence
$$a^{\circ k}(n)=\underbrace{a(((...a(n)...)))}_{k \text{ times}}$$?</i></p>
<p><a href="https://www.wolframalpha.com/input/?i=floor%281%2F2+%2B+n*%281%2Bsqrt%285%29%29%2F2%29+for+n+from+1+to+25">Calculating a few values of the sequence</a> reveals that this is the <a href="https://oeis.org/A007067">A007067</a>, with the property that $$a(a(n))=a(n)+n \tag{1}$$
a result proved in 2006. Let's show it ...</p>
<hr/>
<p><b>Proposition 1.</b> $\left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor=n$</p>
<p><a href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Definition_and_properties">Given</a> $x-1 < \lfloor x\rfloor \leq x$, we have
$$n\phi - \frac{1}{2} < a(n)\leq n\phi + \frac{1}{2} \iff \\
n-\frac{1}{2\phi} < \frac{a(n)}{\phi}\leq n+\frac{1}{2\phi} \iff \\
n+\frac{1}{2}-\frac{1}{2\phi} < \frac{a(n)}{\phi}+\frac{1}{2}\leq n+\frac{1}{2}+\frac{1}{2\phi}$$ </p>
<p><a href="https://en.wikipedia.org/wiki/Golden_ratio#Calculation">Given</a> $1+\frac{1}{\phi}=\phi$ and $\frac{1}{2}-\frac{1}{2\phi} > 0$, then
$$n < n+\frac{1}{2}-\frac{1}{2\phi} < \frac{a(n)}{\phi}+\frac{1}{2}\leq n+\frac{\phi}{2} < n+1$$</p>
<p>or
$$n < \frac{a(n)}{\phi}+\frac{1}{2} < n+1 \Rightarrow
\left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor=n$$</p>
<hr/>
<p><b>Proposition 2.</b> $a(a(n))=a(n)+n$.</p>
<p>Obviously $a(n)\in\mathbb{N}$, <a href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Equivalences">then</a>
$$a(a(n))= \left\lfloor a(n)\cdot\phi + \frac{1}{2}\right\rfloor=
\left\lfloor a(n)\cdot\left(1+\frac{1}{\phi}\right) + \frac{1}{2}\right\rfloor=\\
a(n)+\left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor = ...$$</p>
<p>applying <b>Proposition 1</b>
$$...= a(n)+n$$</p>
<hr/>
<p><a href="https://en.wikipedia.org/wiki/Fibonacci_number">Now</a> back to the original question, a few observations, using $(1)$
$$a^{\circ 2}(n)=a(a(n))=F_2\cdot a(n) + F_1\cdot n$$
$$a^{\circ 3}(n)=a(a(\color{red}{a(n)}))=a(\color{red}{a(n)})+\color{red}{a(n)}=\\
2\cdot a(n)+n=F_3\cdot a(n) + F_2\cdot n$$
$$a^{\circ 4}(n)=a(a(a(\color{blue}{a(n)})))=2\cdot a(\color{blue}{a(n)})+\color{blue}{a(n)}=\\
3\cdot a(n)+2n=F_4\cdot a(n) + F_3\cdot n$$</p>
<p>It's easy to see, by induction, this is
$$a^{\circ k}(n)=F_k\cdot a(n) + F_{k-1}\cdot n \tag{2}$$</p>
<p>because
$$a^{\circ (k+1)}(n)=a^{\circ k}(a(n))=F_k\cdot a(a(n)) + F_{k-1}\cdot a(n)=\\
(F_k+F_{k-1})\cdot a(n) + F_{k}\cdot n=F_{k+1}\cdot a(n) + F_{k}\cdot n$$</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-53985603840722198712020-11-06T11:53:00.006-08:002020-11-06T11:57:36.642-08:00An interesting trigonometric identity<p>Questions follow a complex life cycle on <a href="https://math.stackexchange.com/">Math StackExchange</a>. Some questions are deleted, because they don't meet the community standards. Nonetheless, some of those deleted questions are interesting and non-trivial. In this post, I will cover <a href="https://math.stackexchange.com/questions/3796635/how-can-i-prove-left-prod-limits-k-1219994-sin2-left-frac-k%CF%802/">one of those questions</a> (you may not be able to see it, without sufficient privilege). I spent a few good hours to spot the pattern, so it won't feel like I wasted that time :) ... and you might like the question as well.</p>
<p><i>Is it true that
$$\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)=-1$$?</i></p>
<p>It seems so. Given <a href="https://www.wolframalpha.com/input/?i=1-cos%282x%29%3D2+sin%5E2%28x%29">this</a> and <a href="https://www.wolframalpha.com/input/?i=-cos%28pi%2F2-x%29%3Dcos%28pi%2F2%2Bx%29">this</a> identities:$$\color{red}{\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)}=
\prod\limits_{k=1}^{2^{1999}} \left(\left(2-2\cos{\frac{k\pi}{2^{1999}}} \right)-3\right)=\\
\prod\limits_{k=1}^{2^{1999}} \left(-1-2\cos{\frac{k\pi}{2^{1999}}} \right)=
\prod\limits_{k=1}^{2^{1999}} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1999}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot 1 \cdot
\prod\limits_{k=2^{1998}+1}^{2^{1999}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{\left(2^{1998}+k\right)\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\left(\frac{\pi}{2}+\frac{k\pi}{2^{1999}}\right)} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\left(\frac{\pi}{2}-\frac{k\pi}{2^{1999}}\right)} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\frac{\left(2^{1998}-k\right)\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)
\cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\frac{k\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}-1} \left(1-4\cos^2{\frac{k\pi}{2^{1999}}} \right)=
-\prod\limits_{k=1}^{2^{1998}} \left(1-4\cos^2{\frac{k\pi}{2^{1999}}} \right)=\\
-\prod\limits_{k=1}^{2^{1998}} \left(1-4\left(1-\sin^2{\frac{k\pi}{2^{1999}}} \right)\right)=
-\color{red}{\prod\limits_{k=1}^{2^{1998}} \left(4\sin^2{\frac{k\pi}{2^{1999}}}-3\right)}$$</p>
<p>By induction:
$$\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)=
-\prod\limits_{k=1}^{2^{1998}} \left(4\sin^2{\frac{k\pi}{2^{1999}}}-3\right)=\\
(-1)^2 \prod\limits_{k=1}^{2^{1997}} \left(4\sin^2{\frac{k\pi}{2^{1998}}}-3\right)=\\
(-1)^n \prod\limits_{k=1}^{2^{1999-n}} \left(4\sin^2{\frac{k\pi}{2^{1999-n+1}}}-3\right)=\\
(-1)^{1999} \prod\limits_{k=1}^{1} \left(4\sin^2{\frac{k\pi}{2}}-3\right)=(-1)^{1999}$$</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-42976742068529472062020-07-25T11:31:00.000-07:002020-07-25T11:31:26.579-07:00A few words about ConcurrentHashMap, compute() method<p>There is one ambiguous moment in the <a href="https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#compute-K-java.util.function.BiFunction-">Java documentation</a> of the <i>compute()</i> method from the <i>ConcurrentHashMap</i> class:</p>
<p><i>Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this Map.</i></p>
<p>It's not clear what is being blocked. Is it the access to the entire map or to the key? Let's find out, by conducting a few experiments with the following code:</p>
<pre>
<span class="Apple-style-span" style="color: #073763; font-size: x-small;">package tests.concurrency;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ConcurrentHashMap;
public class TestConcurrentHashMapCompute implements Runnable {
private static final Map<Key, String> MAP = new ConcurrentHashMap<>();
private static final int MAX_RUNS = 100;
private static final long SLEEP_TIME = 5000;
public static void main(String[] args) {
Thread th1 = new Thread(new TestConcurrentHashMapCompute());
Thread th2 = new Thread(new TestConcurrentHashMapCompute());
th1.start();
th2.start();
}
@Override
public void run() {
final String name = Thread.currentThread().getName();
for (int i = 0; i < MAX_RUNS; i++) {
final String value = MAP.compute(new Key(name), (k, v) -> {
System.out.println(name + ": enters");
sleep();
System.out.println(name + ": exits");
return name;
});
System.out.println(name + ": " + value);
}
}
private static void sleep() {
try {
Thread.sleep(SLEEP_TIME);
} catch (Exception ex) {}
}
private static class Key {
private final String value;
private Key(String value) {
this.value = value;
}
@Override
public int hashCode() {
return 1;
// return Objects.hash(value);
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Key other = (Key) o;
return Objects.equals(value, other.value);
}
}
}</span></pre>
<p>It's nothing complicated, two threads calling the <i>compute()</i> method of a shared <i>ConcurrentHashMap</i> instance, using <i>Key</i> class instances as the key for the map. However, pay attention to the <i>hashCode()</i> method inside the <i>Key</i> class:</p>
<pre>
<span class="Apple-style-span" style="color: #073763; font-size: x-small;"> @Override
public int hashCode() {
return 1;
// return Objects.hash(value);
}
</span></pre>
<p>Depending on what is being returned (comment/uncomment the relevant lines), you will see different behaviour. And, by the way, <i>return 1</i> is a valid <i>hashCode()</i> implementation, according to the <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--">Java documentation</a>:</p>
<p><i>- If two objects are equal according to the equals() method, then calling the hashCode method on each of the two objects must produce the same integer result.<br/>
- It is <b>not required</b> that if two objects are unequal according to the equals() method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.</i></p>
<p>The result is:<br/>
- With <i>return Objects.hash(value)</i>, i.e. <i>String</i>'s descent <i>hashCode()</i> implementation, the threads run in parallel, as if the block was on the <i>Key</i>.<br/>
- With <i>return 1</i>, the threads run sequentially, as if the block was on the entire <i>Map</i>.</p>
<p>In fact, <b>the block is on the bucket</b> indexed by the <i>Key</i>. That's what the <i>hashCode()</i> method is about, to quickly access the relevant bucket. <i>HashMap</i>, for example, <a href="https://stackoverflow.com/questions/30957699/why-does-hashmap-internally-use-linkedlist-instead-of-arraylist">uses a singly linked list</a> as the storage for the buckets.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-77680575940277449842019-07-03T14:12:00.000-07:002019-12-25T17:20:11.606-08:00401 and/or 403 and a short story of secure RESTful<p>The problem of what HTTP codes to use inevitably comes when designing RESTful services. There is a bit of subtlety, however, with regards to the 401 and 403 status codes. <a href="https://medium.com/studioarmix/learn-restful-api-design-ideals-c5ec915a430f">Here and there</a> you will read advices suggesting to use:
<ul>
<li><b>401</b> for when an access token isn’t provided, or is invalid.</li>
<li><b>403</b> for when an access token is valid, but requires more privileges.</li>
</ul>
and people will follow these advices without considering the security part of the problem.<p>
<p>And the problem is that such an implementation can leak sensitive information. <a href="https://medium.com/@ruslan.ciurca/re-2c3954857192">Here is my reply</a> to the above mentioned article. In cryptography this is known as <a href="https://en.wikipedia.org/wiki/Test_oracle">oracle</a> and can lead to <a href="https://en.wikipedia.org/wiki/Padding_oracle_attack">pretty serious attacks</a>.</p>
<p>If the attacker sees a 403 status code, after a huge array of failed attempts with 401, this means that whatever the attacker tried passed the authentication phase, but failed the authorisation. Bingo, they just figured out a valid set of credentials (or tokens or ...) and your system said that in "clear text". It is similar to the <a href="https://security.stackexchange.com/questions/17816/username-and-or-password-invalid-why-do-websites-show-this-kind-of-message-i">"Username or password invalid"</a> best practices (and don't read things like <a href="https://it.slashdot.org/story/17/12/22/1618241/username-or-password-is-incorrect-security-defense-is-a-weak-practice">this</a>!).</p>
<p>How to avoid the problem? Stick with one status code (e.g. 403) for both cases (failed authentication and failed authorisation), avoid being too user (or client) friendly. You can log the incident and return a unique request ID to the client. If a genuine client reports the problem, that request ID should help finding more details in logs. And of course track/monitor all the authentication/authorisation failures for anomaly detection purposes.</p>
<p>Now the fun part, all of the above as a mathematical proof. Let's assume a system where the maximum number of credentials possible is $N$, has $M$ registered users and $K$ of those users have access to a specific resource that the attacker tries to brute-force, $N>M\geq K$. Let's consider the following propositions/events:
<ul>
<li>$A$ - guess a credential by accessing the given resource.</li>
<li>$B$ - The system is designed to return: HTTP 200 for valid credentials with access to the resource, HTTP 403 for valid credentials with no access to the resource, HTTP 401 for invalid credentials. For simplicity, we can say $B=\{200\}\bigcup \{403\}\bigcup \{401\}$.</li>
<li>$C$ - The system is designed to return: HTTP 200 for valid credentials with access to the resource, HTTP 403 for valid credentials with no access to the resource or invalid credentials. Or $C=\{200\}\bigcup \{403\}$</li>
</ul></p>
<p>In other words:
<ul>
<li>Cardinality of $A$ givnen $B$ is: $K$ possible cases of HTTP 200, plus $M-K$ possible cases of HTTP 403. Grand total is $M$.</li>
<li>Cardinality of $A$ givnen $C$ is: $K$ possible cases of HTTP 200, which is also the grand total.</li>
</ul>
</p>
<p>Now let's compute probabilities:
$$P(A \mid B)=\frac{M}{N}$$
and
$$P(A \mid C)=\frac{K}{N}$$
Obviously (because $M \geq K$)
$$P(A \mid B) \geq P(A \mid C)$$
which means, a system designed like $B$ gives greater chances to the attacker to guess credentials. Obviously, it doesn't matter when all the registered users have access to the resource (i.e. $K=M$). End of discussion!</p>
<p>P.S. The way I computed probabilities may look a bit superficial, here is another way using <a href="https://en.wikipedia.org/wiki/Law_of_total_probability">total probabilities</a> or
$$P(A\mid B) = \frac{P(A \cap B)}{P(B)}=\sum\limits_{C_n} \frac{P(A \cap B \cap C_n)}{P(B)}=\\
\sum\limits_{C_n} \frac{P(A \cap B \cap C_n)}{P(B\cap C_n)}\cdot \frac{P(B\cap C_n)}{P(B)}=\\
\sum\limits_{C_n} P(A \mid B \cap C_n)\cdot P(C_n\mid B)$$
Then:
<ul>
<li>$$P(A\mid B)=P(A\mid B \cap \{200\})\cdot P(\{200\}\mid B)+\\
P(A\mid B \cap \{403\})\cdot P(\{403\}\mid B)+\\
P(A\mid B \cap \{401\})\cdot P(\{401\}\mid B)=\\
P(A\mid \{200\})\cdot P(\{200\}\mid B)+
P(A\mid \{403\})\cdot P(\{403\}\mid B)+\\
P(A\mid \{401\})\cdot P(\{401\}\mid B)=\\
1\cdot P(\{200\}\mid B)+
1\cdot P(\{403\}\mid B)+
0\cdot P(\{401\}\mid B)=\\
\frac{K}{N}+\frac{M-K}{N}=\frac{M}{N}
$$</li>
<li>$$P(A\mid C)=P(A\mid C \cap \{200\})\cdot P(\{200\}\mid C)+\\
P(A\mid C \cap \{403\})\cdot P(\{403\}\mid C)=\\
P(A\mid \{200\})\cdot P(\{200\}\mid C)+
P(A\mid \{403\})\cdot P(\{403\}\mid C)=\\
1\cdot P(\{200\}\mid C)+
0\cdot P(\{403\}\mid C)=\frac{K}{N}$$</li>
</ul>
</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-71381440972710950862018-09-22T10:00:00.000-07:002018-09-22T10:16:34.997-07:00Generating Subsets<p>Every once in a while I am being challenged with problems involving optimal subsets from a given set of objects. It happened again a few weeks ago. The problem was of a knapsack style (finding the most profitable subset of items of bounded
total size) and ... of course I forgot how to tackle it using <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in-advance_algorithm">dynamic programming</a>. But, many years ago I learned a very simple (to memorise) algorithm which saved the day and I will describe it in this article.</p>
<p>The <a href="https://www.amazon.co.uk/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/">Algorithm Design Manual</a>, page $453$, defines it as <i><b>binary counting</b></i>. The idea behind it is the one to one mapping between the numbers $0 \rightarrow 2^{n-1}$ (total number of numbers is $2^n$) and binary strings of length $n$ (total number of strings is $2^n$) where bit $1$ at the index $i$ means <i>"consider the object at the index $i$ in the original set for the given subset"</i>. We also know that the total <a href="https://en.wikipedia.org/wiki/Binomial_coefficient#Sums_of_the_binomial_coefficients">number of subsets of a set</a> of size $n$ is $2^n$. We have $2^n$ everywhere, awesome!</p>
<p>Let's see it in action by looking at a simple example, a small set $\left\{A, B, C\right\}$ with $n=3$. We are not interested in the empty set, thus we will ignore the $0$-th iteration, leaving us with a total of $2^3-1=7$ subsets:</p>
<table border="1" style="border-collapse: collapse;">
<tr><th nowrap style="padding: 5px;">Iteration</th><th style="padding: 5px;">Binary string</th>
<th style="padding: 5px;">Indexes of the objects to consider</th><th style="padding: 5px;">Subset</th></tr>
<tr><td align="center">1</td><td align="center">001</td>
<td align="center">1</td><td align="center">$\left\{A\right\}$</td></tr>
<tr><td align="center">2</td><td align="center">010</td>
<td align="center">2</td><td align="center">$\left\{B\right\}$</td></tr>
<tr><td align="center">3</td><td align="center">011</td>
<td align="center">1 and 2</td><td align="center">$\left\{A, B\right\}$</td></tr>
<tr><td align="center">4</td><td align="center">100</td>
<td align="center">3</td><td align="center">$\left\{C\right\}$</td></tr>
<tr><td align="center">5</td><td align="center">101</td>
<td align="center">1 and 3</td><td align="center">$\left\{A, C\right\}$</td></tr>
<tr><td align="center">6</td><td align="center">110</td>
<td align="center">2 and 3</td><td align="center">$\left\{B, C\right\}$</td></tr>
<tr><td align="center">7</td><td align="center">111</td>
<td align="center">1, 2 and 3</td><td align="center">$\left\{A, B, C\right\}$</td></tr>
</table>
<p>I need to stress the fact that it's an exponential (or $O\left(2^n\right)$) <a href="https://en.wikipedia.org/wiki/Time_complexity#Exponential_time">complexity</a> algorithm. It is very inefficient for big sets. Here is a code example:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.util.LinkedHashSet;
import java.util.Set;
public class AllSubSets {
public static void main(String args[]) {
String[] setValues = new String[] { "A", "B", "C", "D", "E",
"F", "G", "H", "I", "J" };
long limit = 1 << setValues.length; // this is 2^length
for (long l = 1; l < limit; l++) {
Set<String> subSet = new LinkedHashSet<>();
for (int i = 0; i < setValues.length; i++) {
if ((l & (1 << i)) > 0) {
subSet.add(setValues[i]);
}
}
subSet.forEach(System.out::print);
System.out.println();
}
}
}
</span></pre>
<p>and the result:
<hr />
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">A
B
AB
C
AC
BC
ABC
D
... (trimmed due to the size) ...
CDEFGHIJ
ACDEFGHIJ
BCDEFGHIJ
ABCDEFGHIJ
</span></pre>
<hr /></p>
<p>A careful reader will almost immediately reply that this version is limited to sets with maximum 64 objects (with Java 8, <i>long</i> is <a href="https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html">limited to 64 bits and can be treated as unsigned</a>). <i><a href="https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html">BigInteger</a></i>, which supports bitwise operations, addresses this limitation. And yes, the extra subset construction loop makes it an $O(n\cdot2^n)$ algorithm, it's still exponential though.</p>
<p>However, as it was mentioned earlier, this is not an efficient algorithm. Anything bigger than 64 objects will produce more than $2^{64}$ subsets and this is a big number. Even $2^{32}$ is pretty decent in size, so don't use this algorithm for big sets.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-29052122890730797652018-08-13T03:26:00.001-07:002022-08-31T05:53:19.479-07:00To Optional or not to Optional <p>I recently had an interesting conversation with my colleagues about the usage of Optional's in Java. It all revolves around <a href="https://struscode.com/code/java/java-optional-problems-solutions/">this article</a>.</p>
<p>So, I quickly sketched the following code to highlight the idea:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.util.Optional;
public class OptionalEvaluationTest {
public static void main(String[] args) {
test1(); // non lazy execution of orElse().
test2();
test3();
test4();
}
private static void test1() {
System.out.println("Test 1");
Optional<Integer> oi = Optional.ofNullable(3);
oi.map(OptionalEvaluationTest::intToString)
.orElse(defaultString());
System.out.println("----");
}
private static void test2() {
System.out.println("Test 2");
Optional<Integer> oi = Optional.ofNullable(null);
oi.map(OptionalEvaluationTest::intToString)
.orElse(defaultString());
System.out.println("----");
}
private static void test3() {
System.out.println("Test 3");
Optional<Integer> oi = Optional.ofNullable(3);
oi.map(OptionalEvaluationTest::intToString)
.orElseGet(OptionalEvaluationTest::defaultString);
System.out.println("----");
}
private static void test4() {
System.out.println("Test 4");
Optional<Integer> oi = Optional.ofNullable(null);
oi.map(OptionalEvaluationTest::intToString)
.orElseGet(OptionalEvaluationTest::defaultString);
System.out.println("----");
}
private static String intToString(int i) {
System.out.println("converter called!");
return Integer.toString(i);
}
private static String defaultString() {
System.out.println("default called!");
return "default";
}
}</span></pre>
<p>which yields the following result:
<hr />
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Test 1
converter called!
default called!
----
Test 2
default called!
----
Test 3
converter called!
----
Test 4
default called!
----</span></pre>
<hr /></p>
<p>What we see is that <i>.orElse()</i> is executed always, aka is not lazy executed. This may become a performance issue if used unwisely. Tend to prefer <i>.orElseGet()</i> instead.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-4223130274284722522017-08-12T10:35:00.000-07:002018-09-09T03:25:36.220-07:00The matter of squares and rectangles<p>Being in Oxford and not dedicating some time to browse the local book shops is, imho, a crime. In one of my recent visits I found this recreational maths book "Mathematics and Chess" (Dover Publications, 1997) by <a href="https://en.wikipedia.org/wiki/Miodrag_Petkovi%C4%87">Miodrag Petković</a>. The very first problem in this book is:</p>
<p><i>Prove that the total number of rectangles that can be found on a generalized $n \times n$ board is a perfect square of a natural number.</i></p>
<p>You know, those squares from <a href="http://www.programmerinterview.com/index.php/puzzles/find-number-of-squares-chessboard/">job interviews</a> and <a href="http://puzzles.nigelcoldwell.co.uk/twentyseven.htm">puzzles</a>? Yes, those! So this almost popular matter needs to be sorted out. I will skip the proofs, since almost everything is on Wikipedia these days and the proofs aren't complicated, simple applications of induction. The <a href="https://en.wikipedia.org/wiki/Squared_triangular_number">formula for rectangles</a> is simply beautiful:
$$\sum_{k=1}^{n} k^3=\left ( \sum_{k=1}^{n} k \right )^2=\left [ \frac{n(n+1)}{2} \right ]^2$$
Squares and cubes, amazing, isn't it?</p>
<p>While the <a href="https://en.wikipedia.org/wiki/Square_pyramidal_number">formula for squares</a> is simply:
$$\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}$$</p>
Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-84044648255193826312016-05-28T03:50:00.001-07:002016-05-28T16:35:07.619-07:00Just a beautiful inequality<p>Last week, Worldwide Center of Mathematics posted <a href="https://www.youtube.com/watch?v=P3Dy2XdH64s">this</a> problem on their <a href="https://www.facebook.com/centerofmath/photos/a.495490599888.262197.86190804888/10154174066174889/">Facebook page</a>. So, I felt challenged. The solution turned to be quite simple, but that's not the point. The point is, this inequality simply looks beautiful.</p>
<p>Long story short, the task is to prove the following $$e^{\pi} > \pi^{e}$$</p>
<p>I will use few tricks, in form of <a href="https://www.jstor.org/stable/3615890?seq=1#page_scan_tab_contents">this well known inequality</a> $$x-1 \geq \ln(x), \forall x >0$$
and the fact that $x=\ln(\pi) > \ln(e)=1$. In fact this inequality is strict for $\forall x > 1$</p>
<p>As a result $$\ln(\pi)-1 > \ln(\ln(\pi)) \Leftrightarrow \ln(\pi) > 1+\ln(\ln(\pi)) $$</p>
<p>Luckily, exponential function $f(x)=e^x$ is strictly ascending, thus: $$e^{\ln(\pi)} > e^{1+\ln(\ln(\pi))} \Leftrightarrow \pi > e \cdot \ln(\pi) \Leftrightarrow \pi > \ln(\pi^e)$$</p>
<p>Using the exponential function trick again $$e^{\pi} > e^{\ln(\pi^e)} \Leftrightarrow e^{\pi} > \pi^e$$</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-39877134471779705092013-06-23T09:57:00.001-07:002013-06-23T09:58:23.133-07:00Another number theory problem<p>This is the second post dedicated to the problems set posted on "Math, Math Education, Math Culture" LinkedIn group. <a href="http://www.linkedin.com/groupAnswers?viewQuestionAndAnswers=&discussionID=232087396&gid=33207">Here</a> is the original LinkedId discussion, again ... if you happen to have a LinkedIn account. Here is the problem:</p>
<p style="color: grey;"><i>Prove that the sequence a<sub>1</sub>=1, a<sub>2</sub>=11, a<sub>3</sub>=111, a<sub>4</sub>=1111,... contains an infinite sub-sequence whose terms are pairwise relatively prime.</i></p>
<p>Few observations first of all, without proving them as it should be fairly trivial, e.g. using induction: $$a_{m+n}=a_{m}\cdot 10^{n}+a_{n}$$</p>
<p>From the above: $$a_{m\cdot n} = a_{(m - 1)\cdot n}\cdot 10^{n} + a_{n} = a_{n}\cdot 10^{n\cdot (m-1)} + a_{n}\cdot 10^{n\cdot (m-2)} + ... + a_{n}\cdot 10^{n} + a_{n} $$</p>
<p>So if $a_{n}$ is divisible by $t\in \mathbb{N}, t>1$ then $a_{m\cdot n}$ is also divisible by $t$ <b>(1)</b>.</p>
<p>Now, let's consider the sub-sequence $\left \{ a_{p_{k}} \right \}_{k=1}^{\infty } \subset \left \{ a_{n} \right \}_{n=1}^{\infty }$, where $p_{k}$- k-th prime. I state that this sub-sequence satisfies the condition of the problem. Let's prove it by contradiction.</p>
<p>I.e. let's assume there $\exists k \neq m$ such that $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$. Because $\gcd\left ( p_{m}, p_{k}\right )= 1$ (i.e. both are prime numbers), then, by applying <a href="http://en.wikipedia.org/wiki/B%C3%A9zout's_identity">Bezout's theorem</a> (or <a href="http://www.proofwiki.org/wiki/B%C3%A9zout's_Lemma">lemma</a>), there $\exists r,s\in \mathbb{Z}$ such that: $$r\cdot p_{m} + s\cdot p_{k}=1$$</p>
<p>Both $r,s$ can't be negative and positive as the same time, so we can rewrite it this way: $$r\cdot p_{m} = s\cdot p_{k} + 1$$ assuming both $r$ and $s$ are positive this time.</p>
<p>Because we assumed $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$, then $d$ should also divide both $a_{r\cdot p_{m}}, a_{s\cdot p_{k}}$ (using <b>(1)</b> proved above). But $$a_{r\cdot p_{m}} = a_{s\cdot p_{k}+1} = a_{s\cdot p_{k}} \cdot 10 + a_{1}$$ which means $d>1$ also divides $a_{1}=1$. Contradiction.</p>
<p>As a result $\forall k \neq m$, $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= 1$.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-3208151619645726712013-06-08T13:51:00.000-07:002013-06-08T13:51:29.076-07:00Another probability problem <p>An interesting set of problems was posted on "Math, Math Education, Math Culture" LinkedIn group few weeks ago. I engaged myself in addressing few of them, so I will be posting my solutions in the next few posts. Just to clarify this from the beginning, interesting doesn't necessarily mean difficult. This particular post is dedicated to the probability problem and <a href="http://www.linkedin.com/groupAnswers?viewQuestionAndAnswers=&discussionID=232164971&gid=33207">here</a> is the original LinkedId discussion, if you happen to have a LinkedIn account. Otherwise, continue reading this post. Here is the problem ...</p>
<p style="color: grey;"><i>We have <b>n</b> urns, each of these urns contains <b>A</b> white balls and <b>B</b> black balls. We assume a ball from the first urn is randomly picked and then placed into the second urn, then another ball from the second urn is randomly picked and then placed into the third urn, and so on, until a ball from the last urn is finally randomly picked. If this last ball is white, what probability has this fact?</i></p>
<p>One way to attack the problem is to use <a href="http://mathworld.wolfram.com/TotalProbabilityTheorem.html">total probability</a> (<a href="http://en.wikipedia.org/wiki/Law_of_total_probability">Wikipedia</a> is probably more descriptive on this topic).</p>
<p>Let's define the following two events:<br/>
- W<sub>i</sub> - white ball is picked from <b>i</b>-th urn<br/>
- B<sub>i</sub> - black ball is picked from <b>i</b>-th urn.<br/>
It is worth noting that $P\left ( W_{i} \right )+P\left ( B_{i} \right )=1$.</p>
<p>Now, applying total probability we have: $$P\left ( W_{n} \right ) = P\left ( W_{n} | W_{n-1} \right )\cdot P\left ( W_{n-1} \right )+P\left ( W_{n} | B_{n-1} \right )\cdot P\left ( B_{n-1} \right )$$
Where:<br/>
- $P\left ( W_{n} | W_{n-1} \right )=\frac{A+1}{A+B+1}$ - translated as "probability to pick a white ball from <b>n</b>-th urn, knowing that a white ball was picked from <b>n-1</b>-th urn"<br/>
- $P\left ( W_{n} | B_{n-1} \right )=\frac{A}{A+B+1}$ - translated as "probability to pick a white ball from <b>n</b>-th urn, knowing that a black ball was picked from <b>n-1</b>-th urn".</p>
<p>Putting all these together, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot \frac{1}{A+B+1}+\frac{A}{A+B+1}$$
Or, if we note $k= \frac{1}{A+B+1}$, then: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot k+A\cdot k$$</p>
<p>Continuing doing this recursively, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{1} \right )\cdot k^{n-1} + A\cdot \left ( k^{n-1}+k^{n-2}+...+k^{2}+k \right )$$
Where (because W<sub>1</sub> relates to the very first urn): $$P\left ( W_{1} \right )=\frac{A}{A+B}=A\cdot \frac{k}{1-k}$$</p>
<p>Finally: $$P\left ( W_{n} \right )=A\cdot \frac{k^{n}}{1-k}+A\cdot \frac{k^{n}-k}{k-1}=\frac{A}{A+B}$$</p>
<p>Which means, the trick with picking randomly a ball and moving it to the next urn has no effect on the final probability. Interesting, isn't it?</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-86973301107015642492013-05-26T09:40:00.000-07:002019-04-13T10:10:21.516-07:00Tackling Andrica's conjecture. Part 3<p>Here is an interesting, but slightly detached from the <a href="https://rtybase.blogspot.co.uk/2012/11/tackling-andricas-conjecture-part-2.html">previous two articles</a>, result.
Let's look at the following two sequences: $$a_{n}=\sqrt{p_{n+1}} - \sqrt{p_{n}}$$ $$b_{n}=\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}}$$</p>
<p><a href="https://github.com/rtybase/andrica-conjecture/blob/master/code/andricas-test-2.py">Here is a short Python code</a> to visualise the sequences.</p>
<p>And here is how both sequences look like ($a_{n}$ the first and $b_{n}$ the second): <a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEm8cq6PaYKBotkDkdf7T9AZQIWZH30vjm5VSUgH3MAu0b2i-_MQUjolIdtVWHAa_G6_9vg0tmCTXmGhmPaaeEBCsZ6B0voJf_mIvo2bJfyMcN7ZJna-4q4LQtRXnj2aiAj3Pa4Snl6sM/s1600/result.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEm8cq6PaYKBotkDkdf7T9AZQIWZH30vjm5VSUgH3MAu0b2i-_MQUjolIdtVWHAa_G6_9vg0tmCTXmGhmPaaeEBCsZ6B0voJf_mIvo2bJfyMcN7ZJna-4q4LQtRXnj2aiAj3Pa4Snl6sM/s520/result.png" width="520" /></a> Quite <a href="https://en.wikipedia.org/wiki/Asymptotic_analysis">asymptotic</a>, aren't they? Indeed they are ...</p>
<p><b><i><u>Lemma 3.</u> $$\sqrt{p_{n+1}} - \sqrt{p_{n}} \leq \ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}} \leq \left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\cdot \left ( \sqrt{p_{n+1}} - \sqrt{p_{n}} \right )$$</i></b></p>
<p>Let's look at this function $f_{6}(x)=\frac{\sqrt{p_{n+1}}}{1+x\cdot \sqrt{p_{n+1}}}$. Obviously, ${\ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )}'=f_{6}(x)$. As a result $$\int\limits_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = \ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )|_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1}=\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )$$</p>
<p>According to <a href="https://en.wikipedia.org/wiki/Mean_value_theorem#Mean_value_theorems_for_integration">Mean Value Theorem</a>, $\exists \mu \in \left (\sqrt{\frac{p_{n}}{p_{n+1}}} ,1 \right )$ such that: $$\int\limits_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = f_{6}\left ( \mu \right )\cdot \left ( 1- \sqrt{\frac{p_{n}}{p_{n+1}}} \right )$$</p>
<p>Putting all together: $$\ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right ) = \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\mu \cdot \sqrt{p_{n+1}}}$$</p>
<p>Because $$\sqrt{\frac{p_{n}}{p_{n+1}}}< \mu < 1 \Rightarrow 1+\sqrt{p_{n}}< 1+\mu \cdot \sqrt{p_{n+1}} < 1+\sqrt{p_{n+1}} $$</p>
<p>And we get $$\frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\leq \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n}}}$$ which proves this lemma.</p>
<p>Noting $\Delta_{n}=\sqrt{p_{n+1}}-\sqrt{p_{n}}$, this becomes: $$\frac{\Delta_{n}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )\leq \frac{\Delta_{n}}{1+\sqrt{p_{n}}}$$ or $$\frac{1+\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq \ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}}\leq 1$$</p>
<p>Is this result of any use? I don't know yet, but it looks like: $$\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}} \rightarrow e, n \to \infty$$
using <a href="https://math.stackexchange.com/questions/144539/limit-inferior-of-the-quotient-of-two-consecutive-primes/">this</a> result.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-4774287003681599382013-05-07T16:14:00.001-07:002020-07-25T10:18:15.316-07:00A few cloud based APIs<p>If you came to the point of being ready to start a new project, here are few links to some cloud based APIs to consider:</p>
<p>1. <a href="http://www.stormpath.com/monthly-pricing-plans">StormPath</a> - quite good a user management and you get free perks as well.</p>
<p>2. <a href="http://mandrill.com/pricing/">Mandrill</a> - if you need a good notification (email based) system. Again, quite a decent free of charge limit.</p>
<p>3. <a href="https://mongolab.com/products/pricing/">MongoLab</a> - well, that's MongoDB. And if you don't know what it is by now, then you shouldn't worry about it at all (caught your attention? Google for it then). Free 0.5Gb instance is a good starting point.</p>
<p>4. <a href="https://developers.google.com/chart/">Google Chart API</a> - Not the best one, but it's free and quite ok(ish) for building dashboards.</p>
<p>5. <a href="http://www.geckoboard.com/plans-and-pricing/">GeckoBoard</a> - a better dashboard API, with HTML5 support (WebSockets and all that stuff), not for free though ...</p>
<p>And of course, you can test all that with <a href="http://aws.amazon.com/ec2/pricing/">Amazon</a> for free for one year.</p>
<p>This is it for now, I will do my best to keep this list updated.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-37894022843699494392012-11-11T12:00:00.000-08:002013-05-26T07:51:54.832-07:00Tackling Andrica's conjecture. Part 2With <a href="http://rtybase.blogspot.co.uk/2012/09/tackling-andricas-conjecture.html">the previous post</a>, I stopped at the argument that $f_{4}(x)=\pi (x) - \sqrt{x}$ seems to be ascending for prime arguments. Apparently, this is a necessary and sufficient condition, i.e.:<br />
<b><i><u>Lemma 1.</u> Andrica's conjecture is true iff function $f_{4}(x)=\pi (x) - \sqrt{x}$ is strictly ascending ($x < y \Rightarrow f(x) < f(y)$) for prime arguments.</i></b><br />
The proof is given in the <a href="http://math.stackexchange.com/questions/206815/is-there-a-way-to-show-that-sqrtp-n-n">following discussion</a> with the <a href="http://math.stackexchange.com/">math.stackexchange.com</a> community.<br />
It is worth mentioning that $f_{4}(x)$ is descending in between prime numbers. For example for $\forall x\in \left ( p_{n}, p_{n+1} \right )$, $f_{4}(x)=n - \sqrt{x}$ and ${f_{4}}'(x)=-\frac{1}{2\cdot \sqrt{x}} < 0$.<br />
In fact the purpose of the discussion was to prove that $$\sqrt{p_{n}} < n$$ which turns to be true for $\forall n \geq 2$, using <a href="http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number">Rosser's theorem</a>.<br />
Interesting result, out of this inequality, is that $$\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ because $\sqrt{p_{1}}=\sqrt{2} > 1$. However, $$\sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right )=\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ and as a result $$\frac{1}{n-1}\cdot \sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right ) < 1$$ or, in other words, on average Andrica's conjecture seems to be true.<br />
But, leaving the statistical argument aside, how do we prove that $f_{4}(x)$ is ascending for prime arguments?<br />
I don't have the answer yet, but here is where I stuck ...<br />
Let's have a look at the following function $$f_{5}(x)=1 - \sqrt{p_{n+1} + x} + \sqrt{p_{n} + x}$$ This function is ascending $\forall x \geq -p_{n}$ $${f_{5}(x)}'= -\frac{1}{2\cdot \sqrt{p_{n+1} + x}} + \frac{1}{2\cdot \sqrt{p_{n} + x}} > 0$$ because $\sqrt{p_{n+1} + x} > \sqrt{p_{n} + x}$, for $\forall x \geq -p_{n}$.<br />
This function also has a zero, $1=\sqrt{p_{n+1} + x} - \sqrt{p_{n} + x} \Leftrightarrow $ $$1 = p_{n+1}+p_{n} +2\cdot x -2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)} \Leftrightarrow $$ $$2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)}=p_{n+1}+p_{n} +2\cdot x - 1 \Leftrightarrow $$ $$4\cdot (p_{n+1} + x)\cdot (p_{n} + x)=p_{n+1}^{2}+p_{n}^{2}+4\cdot x^{2}+1+2\cdot p_{n+1}\cdot p_{n}+$$ $$+4\cdot p_{n+1}\cdot x-2\cdot p_{n+1}+4\cdot p_{n}\cdot x-2\cdot p_{n}-4\cdot x \Leftrightarrow $$ jumping ahead $$2\cdot p_{n+1}\cdot p_{n}=p_{n+1}^{2}+p_{n}^{2}+1-2\cdot p_{n+1}-2\cdot p_{n}-4\cdot x \Leftrightarrow $$ $$4\cdot x=(p_{n+1}-p_{n})^{2}-2\cdot (p_{n+1}+p_{n})+1=(p_{n+1}-p_{n}-1)^{2}-4\cdot p_{n}$$ as a result $$x_{0}=\left( \frac{p_{n+1}-p_{n}-1}{2} \right)^{2}-p_{n}$$ Obviously, $x_{0} > -p_{n}$.<br />
And now:<br />
<b><i><u>Lemma 2.</u> $f_{4}(p_{n+1}) > f_{4}(p_{n})$ iff $x_{0} < 0$, where $x_{0}$ is zero of $f_{5}(x)$.</i></b><br />
First of all $$x_{0} < 0 \Leftrightarrow p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$$<br />
As a result, if $f_{4}(p_{n+1}) > f_{4}(p_{n})$ this is equivalent (from Lemma 1) with $\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$ (Andrica's inequality for $p_{n}, p_{n+1}$). But then $$p_{n+1} - p_{n}=(\sqrt{p_{n+1}}-\sqrt{p_{n}})\cdot (\sqrt{p_{n+1}}+\sqrt{p_{n}}) < \sqrt{p_{n+1}}+\sqrt{p_{n}}$$ and applying Andrica's inequality again $$p_{n+1} - p_{n} < \sqrt{p_{n}}+1+\sqrt{p_{n}}=2\cdot \sqrt{p_{n}}+1$$ so $x_{0} < 0$.<br />
Now, if $x_{0} < 0$, where we know that $x_{0} > -p_{n}$, and the fact that $f_{5}(x)$ is ascending then we have $$x_{0} < 0 \Rightarrow 0=f_{5}(x_{0}) < f_{5}(0)=1 - \sqrt{p_{n+1}} + \sqrt{p_{n}}$$ or $$\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$$ and then (Lemma 1) $f_{4}(p_{n+1}) > f_{4}(p_{n})$.<br />
Do we know if $p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$ for $\forall n$?<br />
Not yet, but we are close. <a href="http://en.wikipedia.org/wiki/Martin_Huxley">One result, proved by Martin Huxley,</a> states that $p_{n+1}-p_{n} < p_{n}^{\theta }$ for $\theta > \frac{7}{12}$ and sufficiently large $n$. In our case, $\theta =0.5$<br />
<a href="http://en.wikipedia.org/wiki/Prime_gap#Upper_bounds">Another result by Baker, Harman and Pintz</a> states that $\theta$ may be taken to be 0.525.Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-7134040358171511142012-09-23T08:56:00.001-07:002019-04-13T10:05:21.371-07:00Tackling Andrica's conjecture. Part 1<p>
<a href="https://en.wikipedia.org/wiki/Andrica's_conjecture">Andrica's conjecture</a> is one of those mathematical statements which are extremely easy to formulate, but complicated to prove. In fact it hasn't been proved yet, to be more precise. Here we go, for all consecutive prime numbers $p_{n}$ and $p_{n+1}$, it happens that: $$\sqrt{p_{n+1}} - \sqrt{p_{n}}< 1$$</p><p>
<b>1. The first attempt</b></p><p>
Let's start with an analogy, <a href="https://en.wikipedia.org/wiki/Prime_gap#Upper_bounds">here is an inequality</a> $p_{n+1} < 2\cdot p_{n}$ which is a direct result from <a href="https://en.wikipedia.org/wiki/Bertrand%27s_postulate">Bertrand's postulate</a>, proved by Chebyshev. As a result of this inequality, we have: $$0 < \ln(p_{n+1}) - \ln(p_{n}) < \ln(2) < 1$$
But what is the relationship between natural logarithm and square root functions?</p><p>
Well, let's have a look at the following function: $f_{1}(x)=\sqrt{x} - \ln(x)$. First derivative of this function is ${f_{1}}'(x) = \frac{1}{2\cdot \sqrt{x}} - \frac{1}{x}=\frac{1}{x}\cdot \left ( \frac{\sqrt{x}}{2} -1\right )\geq 0$, for $\forall x\geq 4$. This means that $f_{1}(x)$ is ascending for $\forall x\geq 4$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (because $p_{3}=5$) $\Rightarrow f_{1}(p_{n}) \leq f_{1}(p_{n+1})$ or $$\sqrt{p_{n}} - \ln(p_{n}) \leq \sqrt{p_{n+1}} - \ln(p_{n+1})$$
Finally: $$0< \ln(p_{n+1}) - \ln(p_{n}) \leq \sqrt{p_{n+1}} - \sqrt{p_{n}}, \forall n\geq 3$$
As we can see, the analogy isn't of any use really, though we have a nice inequality.</p><p>
<b>2. The second attempt</b></p>
<p>
Let's have a look at another function: $f_{2}(x)=\frac{x}{\ln(x)} - \sqrt{x}$. Its first derivative is $${f_{2}}'(x)=\frac{\ln(x)-1}{(\ln(x))^{2}}-\frac{1}{2\cdot \sqrt{x}}=\\
\frac{1}{2\cdot \sqrt{x}\cdot (\ln(x))^{2}}\cdot \left ( 2\cdot \sqrt{x}\cdot \ln(x)-2\cdot \sqrt{x}-(\ln(x))^{2} \right )$$</p>
<p>
For the first term we have: $\frac{1}{2\cdot \sqrt{x}\cdot (\ln(x))^{2}}> 0$, for $\forall x> 0$.</p>
<p>
Let's check the second term: $\left ( 2\cdot \sqrt{x}\cdot \ln(x)-2\cdot \sqrt{x}-(\ln(x))^{2} \right )=$ $\left (-x+2\cdot \sqrt{x}\cdot \ln(x)-(\ln(x))^{2}-2\cdot \sqrt{x}+x \right )=$ $\left [ -\left ( x-2\cdot \sqrt{x}\cdot \ln(x)+(\ln(x))^{2} \right ) +\left ( 1- 2\cdot \sqrt{x}+x\right )-1\right ]=$ $\left [ \left ( \sqrt{x}-1\right )^{2}-\left ( \sqrt{x}-\ln(x) \right )^{2} -1\right ]$ and we are not done yet. Using $a^{2}-b^{2}=(a-b)\cdot (a+b)$, we have: $\left ( 2\cdot \sqrt{x}\cdot \ln(x)-2\cdot \sqrt{x}-(\ln(x))^{2} \right )=$ $\left [ \left ( \ln(x)-1 \right )\cdot \left ( \sqrt{x}-1+\sqrt{x}-\ln(x) \right )-1 \right ]$.</p>
<p>
What we have so far: <ul>
<li>$\ln(x)-1 \geq 1$, for $\forall x \geq e^{2}$</li>
<li>$\sqrt{x}-1 \geq 1$, for $\forall x \geq 4$</li>
<li>$\sqrt{x}-\ln(x)>0$, for $\forall x \geq 4$, this is, by the way, $f_{1}(x)$, so $f_{1}(x)\geq f_{1}(4)>0$</li>
</ul>
Altogether: $\left ( 2\cdot \sqrt{x}\cdot \ln(x)-2\cdot \sqrt{x}-(\ln(x))^{2} \right )\geq 0$, for $\forall x\geq e^{2}$.</p>
<p>
This means ${f_{2}}'(x)\geq 0$ and $f_{2}(x)$ is ascending, for $\forall x\geq e^{2}$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (the cases for $p_{3}=5$, $p_{4}=7$ and $p_{5}=11$ can be verified with a calculator) $\Rightarrow f_{2}(p_{n}) \leq f_{2}(p_{n+1})$ or $$\frac{p_{n}}{\ln(p_{n})} - \sqrt{p_{n}}\leq \frac{p_{n+1}}{\ln(p_{n+1})} - \sqrt{p_{n+1}}$$
Final result is (let's note it as <a name="2"><b>(2)</b></a>): $$ \sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{\ln(p_{n+1})} - \frac{p_{n}}{\ln(p_{n})}, \forall n\geq 3$$</p>
<p>
<b>2.1 A negative result of the second attempt</b></p>
<p>
It is worth mentioning that function $\frac{x}{\ln(x)}$ has a special role in the number theory. According to the <a href="https://en.wikipedia.org/wiki/Prime_number_theorem">Prime Number Theorem</a>: $\displaystyle\smash{\lim_{x \to \infty }}\tfrac{\pi (x)}{x/\ln(x)}=1$, where $\pi (x)$ is the <a href="https://en.wikipedia.org/wiki/Prime-counting_function">prime counting function</a>.</p>
<p>
Obviously, $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n})}{p_{n}/\ln(p_{n})}=1$ and $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n+1})}{p_{n+1}/\ln(p_{n+1})}=1$ (as sub-sequences).</p><p>Also $\pi (p_{n})=n$ and $\pi (p_{n+1})-\pi (p_{n})=1$.</p>
<p>
If we put all these together, does it mean that $\displaystyle\smash{\lim_{n \to \infty }} \left ( \frac{p_{n+1}}{\ln(p_{n+1})} - \frac{p_{n}}{\ln(p_{n})} \right )=1$?</p>
<p>
Nope, it doesn't, check <a href="https://math.stackexchange.com/questions/114427/ratio-of-limits">this link</a> for more details.</p>
<p>
<b>2.2 A positive result of the second attempt</b></p>
<p>
According to the <a href="https://en.wikipedia.org/wiki/Prime_gap">following article</a>, in 2005 it was proved that $\displaystyle\smash{\lim_{n \to \infty }}\inf \frac{g_{n}}{\ln(p_{n})}=0$, where $g_{n}=p_{n+1}-p_{n}$ or the n-th gap.</p>
<p>
It is also obvious that $\frac{p_{n+1}}{\ln(p_{n+1})} < \frac{p_{n+1}}{\ln(p_{n})}$ (because $p_{n} < p_{n+1}$ and $\ln(p_{n}) < \ln(p_{n+1})$). As a result: $$ \sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{\ln(p_{n+1})} - \frac{p_{n}}{\ln(p_{n})}\leq \frac{g_{n}}{\ln(p_{n})}, \forall n\geq 3$$
Or $$\displaystyle\smash{\lim_{n \to \infty }}inf\left ( \sqrt{p_{n+1}}- \sqrt{p_{n}} \right )=0$$
This means that Andrica's conjecture is true for an infinity pairs of $p_{n}$ and $p_{n+1}$. It doesn't prove the conjecture though, which states "it is true for all $p_{n}$ and $p_{n+1}$"</p>
<p>
<b>3. The third attempt</b></p>
<p>
How about the following function $f_{3}(x)=\pi (x) - \frac{x}{\ln(x)}$? Well, for this case I used a little Python program, the <a href="https://github.com/rtybase/andrica-conjecture/blob/master/code/andricas-test-1.py">code is here</a>.
First of all, $f_{3}(23)=1.66463325521 > f_{3}(29)=1.38774807317$. So, $f_{3}(x)$ is not ascending. The general tendency of $f_{3}(x)$ seems to be ascending though, according to this graphic (click to enlarge): <div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj19XXxCnaYEGpJb2T0jG_fzs2QGMCf8U5gTFBdBekKT2hoxRS64YeZojW58fHaWXM4Ybi19cOAapqrYp3NTnfwUZ1Nsq-z8xgyCpi3ytiFI4wyTi-hCWVQNst3xlkO6ajgx1qVg15jGDE/s1600/primes1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj19XXxCnaYEGpJb2T0jG_fzs2QGMCf8U5gTFBdBekKT2hoxRS64YeZojW58fHaWXM4Ybi19cOAapqrYp3NTnfwUZ1Nsq-z8xgyCpi3ytiFI4wyTi-hCWVQNst3xlkO6ajgx1qVg15jGDE/s320/primes1.png" width="320" /></a></div>
At least, for the areas where the function is ascending for consecutive primes (update the program to plot just <i>plt.plot(x1, y1)</i>, i.e. primes and values of the function for the prime arguments), Andrica's conjecture is true, because if $$\pi (p_{n+1}) - \frac{p_{n+1}}{\ln(p_{n+1})} \geq \pi (p_{n}) - \frac{p_{n}}{\ln(p_{n})}$$ then (also consider <a href="#2"><b>(2)</b></a>) $$1=\pi (p_{n+1}) - \pi (p_{n}) \geq \frac{p_{n+1}}{\ln(p_{n+1})} - \frac{p_{n}}{\ln(p_{n})}$$
Still, this is not a proof.</p>
<p>
<b>4. What's next?</b></p>
<p>
Well, probably the next logical thing is to analyse the function $f_{4}(x)=\pi (x) - \sqrt{x}$. At least it seems to be ascending for prime arguments.
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk0dlltDMHRYMxERrnJ6eg0dDz-RPYCPbWD5g7yFo_caUwHQPigQWRG5g0ObiHYkvKjk4E8aqu-ybLzPI_7nVcV9uHaejhERqHUgSI6Uz6AmX-KroDkh1g00GCKLnmv8Z7Bgi-F0v6GnE/s1600/primes2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjk0dlltDMHRYMxERrnJ6eg0dDz-RPYCPbWD5g7yFo_caUwHQPigQWRG5g0ObiHYkvKjk4E8aqu-ybLzPI_7nVcV9uHaejhERqHUgSI6Uz6AmX-KroDkh1g00GCKLnmv8Z7Bgi-F0v6GnE/s320/primes2.png" width="320" /></a></div>
But the work is still in progress...</p>
Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-24187784142362301562012-05-22T07:58:00.000-07:002018-08-13T03:48:20.121-07:00Factoring big numbers and RSA<p>Last week I came across <a href="https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs/">this article</a>. It's an interesting report indeed and with this post I will explain what is the implication. But first of all, let's quickly recall what <a href="http://en.wikipedia.org/wiki/RSA_(algorithm)">RSA encryption</a> is.</p>
<p>There is a message <i>m</i> which needs to be encrypted. There is a public key <i>(e, n)</i> and a private key <i>(d, n)</i>. Message is encrypted in the following way <i>c = m<sup>e</sup> (mod n)</i>. Cipher text is decrypted in the following way <i>m = c<sup>d</sup> (mod n)</i>. Puting all these together <i>m<sup>e⋅d</sup> ≡ m (mod n)</i> and if <i>m</i> and <i>n</i> are co-prime then <i>m<sup>e⋅d-1</sup> ≡ 1 (mod n)</i>. <i>n</i> is selected to be a product of two distinct prime numbers <i>n = p⋅q</i> and, according to the <a href="http://en.wikipedia.org/wiki/Euler%27s_theorem">Euler's theorem</a>, <i>m<sup>φ(n)</sup> ≡ 1 mod n</i>. Now <i>e</i> and <i>d</i> (exponents of the public/private keys) are selected so that <i>e⋅d - 1 ≡ 0 (mod φ(n))</i> or <i>e⋅d - 1 = k⋅φ(n)</i>, <i>k</i> - integer.</p>
<p>Because <i>n</i> is a product of really big prime numbers (thus <i>n</i> is a big number itself), then factoring it is a really complicated problem, considering "limited" computational power of the modern computers and the fact that factoring is an exponential (in terms of complexity) problem. As a result, computing <i>φ(n)</i>, which in this particular case is <i>φ(n) = (p - 1)⋅(q - 1)</i>, is also a complicated problem.</p>
<p>However, computing the <a href="http://en.wikipedia.org/wiki/Greatest_common_divisor">greatest common divisor (GCD)</a> isn't a complicated problem. As a result, if two public keys <i>(e1, n1)</i> and <i>(e2, n2)</i> are spotted, so that <i>GCD(n1, n2) > 1</i>, then decoding the relevant messages <i>m1</i> and <i>m2</i> becomes and easy task and this is the topic of the article I have mentioned at the top of this post.</p>
<p>Now, let's do a quick test. Imagine the following two public keys and associated cipher texts:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">e1 = 65537
n1 = 59271838373237712241010698426785545947980750376894660532845611609385295
49357464245996603984250810283460055082118943354872215289998388427726673
74160929852573051680099378617005092405110706474184136037559125038434888
56979904991517729100725512850421664634705274281314737938901139871448406
073842088742598680079967
cipher1 = "J\u00c1R\u0090\u00e1\u00f4\u008b5My\u00f8\u00a1\u00f4>\u00a2\u00c3\u0010
\u00bd\u00eb\u00cc&\u007fb\u001aC$\u001d\u00c5\u00b7\u00cdz\u00b7\u0017
\u008a#9\u0012\u0089\u00feao\u0019\u009c\u00eb\u00b0>\u0086\u009b
\u001d3~b0-u\u00fc\u0004!\rc\\\u00cb$\u0091\u009e\u00a1N\u009d2\u00ff
\u0019\u009a9vH.\u00d5\u00e7m\u00a9m\u00ea^\u00d3T$\u00d7\u00d7\u0011
\u0081\u00e4B\u009b~\u008c$\u00a6K\u008a\u00dc`\u00b4\u009cu\u00fb\u00c2
\u0006\u00d1\u00bb\u00b9\u00a0\u008f\u00d2\u00bc\u0002\u00f6#\u001f\u001dM
\u00bb\u0098\u00f2\u00a0\u009fO\u0080"
e2 = 65537
n2 = 72216220929585874029800250341144628594049328751082632793975238142970345
80195859400832155769761460789049220801438471143407662437503457520665980
33488377571129629910281750410842883648532072455460838627134172456428247
65387577331828704441227356582723560291425753389466410790421096831823015
438162111864463275922441
cipher2 = ".\u00fd9\u008dc\u00da\u00f9o\u00f5Vl\u00fb\u0087\u00ed\u00d5 \u00ee\u00cf
\u0097~\u00d8T\u00f9.\u0018\u00b1\u00d5n^\u00a0\rA\u00e0\u001d\u00d5
\u00c8:D\u00c9\u0014o\u00de\u00dbo\u00f9>)bc'a\u00a2\u008e\u00c1|\u00dd
\r[q1\u00ac\u000f^\u0082b/A\u0010\u0087\u00ff\u00e4k=\u00c8\u00d6\u001c\u007f
\u00fb\u00db\u00da&\u00d9\u00c5\u00c4\u008a#\u00a0u\u0003J&\n\u0083
\u00a0\u00e1.\u00ba\u00fd\u008a0s?\u00deg\u00d50\u0015\u00eb\u0091
\u00b3E\u00c7\u0015O\u00f3r\u00e3`~8\u00b4\u00b5=\u0089U\u007f\u00fa\u0019"
</span></pre>
<p>Check <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations">this link</a> for the easiest implementation of the GCD algorithm. I won't implement it, because Java has it out of the box, as part of the <a href="http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html#gcd(java.math.BigInteger)">BigInteger class</a>. Here is my code:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.math.BigInteger;
import java.security.MessageDigest;
import java.util.Arrays;
public class RSATest {
private static final long MAX_ITER = 100000;
private static final int MAX_TRY = 5;
private static final int BLOCK = 128;
// hash function used by OAEP deoceder
private static byte[] hash(byte[] b) throws Exception {
assert b.length == BLOCK/2;
MessageDigest algo = MessageDigest.getInstance("SHA-512");
algo.reset();
algo.update(b);
return algo.digest();
}
// converts a String to a BigIntteger
// convertion is performed as if the String were
// in base 256
public static BigInteger stringToInt(String str) {
int sz = str.length();
BigInteger ret = new BigInteger("0");
BigInteger v256 = new BigInteger("256"); // the base
BigInteger mul = new BigInteger("1");
for (int i = sz - 1; i >= 0; --i) {
int v = str.charAt(i);
ret = ret.add((new BigInteger("" + v)).multiply(mul));
mul = mul.multiply(v256);
}
return ret;
}
// a simple method for xor-ing to byte arrays
private static byte[] xor(byte[] b, byte[] a) {
assert b.length == BLOCK/2;
assert b.length == a.length;
byte[] ret = new byte[BLOCK/2];
for (int i = 0; i < BLOCK/2; ++i) ret[i] = (byte) (a[i] ^ b[i]);
return ret;
}
// decodes an OAEP array, google for OAEP padding
private static byte[] oaepDecode(byte[] b) throws Exception {
assert b.length == BLOCK;
byte[] first = Arrays.copyOfRange(b, 0, BLOCK/2);
byte[] second = Arrays.copyOfRange(b, BLOCK/2, BLOCK);
byte[] r = xor(second, hash(first));
byte[] m = xor(first, hash(r));
return m;
}
// converts a BigInteger into a String
// if withOAEP is set to true, then also applies
// OAEP decoding
public static String intToString(BigInteger n, boolean withOAEP)
throws Exception {
byte[] b_r_n = n.toByteArray();
int b_sz = b_r_n.length;
// apply OAEP decoding
if (withOAEP) {
if (b_sz > BLOCK) {
// make sure we pass the right size, i.e. of one BLOCK
b_r_n = Arrays.copyOfRange(b_r_n, b_sz - BLOCK, b_sz);
}
b_r_n = oaepDecode(b_r_n);
}
return new String(b_r_n);
}
// a simple decoder with the private key (d, n)
public static void decode(BigInteger d, BigInteger n, String cipherText)
throws Exception {
BigInteger cipherInt = stringToInt(cipherText);
BigInteger messageInt = cipherInt.modPow(d, n);
// a simple note that if messageInt is a solution for the
// above modulo congruence eq, then messageInt + k*n is also
// a solution
for (int i = 0; i < MAX_TRY; ++i) {
System.out.println("Try: " + i);
System.out.println("Integer message: " + messageInt);
System.out.println("String message (flat) = " +
intToString(messageInt, false));
System.out.println("String message (oaep) = " +
intToString(messageInt, true));
System.out.println();
messageInt = messageInt.add(n);
}
}
// this method attempts to decode the cipher by pretending
// it knows "p" which is a composition of "n", i.e. n = p*q
public static void decode_with_p(long e, BigInteger n, String cipher,
BigInteger p) throws Exception {
BigInteger q = n.divide(p);
BigInteger phi = q.subtract(BigInteger.ONE).multiply(
p.subtract(BigInteger.ONE));
BigInteger E = new BigInteger("" + e);
for (long k = 0; k < MAX_ITER; k++) {
BigInteger r = phi.multiply(
new BigInteger("" + k)).add(BigInteger.ONE);
BigInteger[] qr = r.divideAndRemainder(E);
if (qr[1].equals(BigInteger.ZERO)) {
// remainder is ZERO
System.out.println("Cycle: " + k);
System.out.println("Try private key: " + qr[0]);
decode(qr[0], n, cipher);
System.out.println();
}
}
}
public static void main(String[] args) throws Exception {
long e1 = 65537;
BigInteger n1 = new BigInteger(
"592718383732377122410106984267855459479807503768946" +
"605328456116093852954935746424599660398425081028346" +
"005508211894335487221528999838842772667374160929852" +
"573051680099378617005092405110706474184136037559125" +
"038434888569799049915177291007255128504216646347052" +
"74281314737938901139871448406073842088742598680079967");
String cipher1 =
"J\u00c1R\u0090\u00e1\u00f4\u008b5My\u00f8\u00a1\u00f4>" +
"\u00a2\u00c3\u0010\u00bd\u00eb\u00cc&\u007fb\u001aC$" +
"\u001d\u00c5\u00b7\u00cdz\u00b7\u0017\u008a#9\u0012" +
"\u0089\u00feao\u0019\u009c\u00eb\u00b0>\u0086\u009b" +
"\u001d3~b0-u\u00fc\u0004!\rc\\\u00cb$\u0091\u009e" +
"\u00a1N\u009d2\u00ff\u0019\u009a9vH.\u00d5\u00e7m" +
"\u00a9m\u00ea^\u00d3T$\u00d7\u00d7\u0011\u0081\u00e4B" +
"\u009b~\u008c $\u00a6K\u008a\u00dc`\u00b4\u009cu" +
"\u00fb\u00c2\u0006\u00d1\u00bb\u00b9\u00a0\u008f\u00d2" +
"\u00bc\u0002\u00f6#\u001f\u001dM\u00bb\u0098\u00f2" +
"\u00a0\u009fO\u0080";
long e2 = 65537;
BigInteger n2 = new BigInteger(
"722162209295858740298002503411446285940493287510826" +
"327939752381429703458019585940083215576976146078904" +
"922080143847114340766243750345752066598033488377571" +
"129629910281750410842883648532072455460838627134172" +
"456428247653875773318287044412273565827235602914257" +
"53389466410790421096831823015438162111864463275922441");
String cipher2 =
".\u00fd9\u008dc\u00da\u00f9o\u00f5Vl\u00fb\u0087\u00ed" +
"\u00d5 \u00ee\u00cf\u0097~\u00d8T\u00f9.\u0018\u00b1" +
"\u00d5n^\u00a0\rA\u00e0\u001d\u00d5\u00c8:D\u00c9" +
"\u0014o\u00de\u00dbo\u00f9>)bc'a\u00a2\u008e\u00c1|" +
"\u00dd\r[q1\u00ac\u000f^\u0082b/A\u0010\u0087\u00ff" +
"\u00e4k=\u00c8\u00d6\u001c\u007f\u00fb\u00db\u00da&" +
"\u00d9\u00c5\u00c4\u008a#\u00a0u\u0003J&\n\u0083" +
"\u00a0\u00e1.\u00ba\u00fd\u008a0s?\u00deg\u00d50\u0015" +
"\u00eb\u0091\u00b3E\u00c7\u0015O\u00f3r\u00e3`~8\u00b4" +
"\u00b5=\u0089U\u007f\u00fa\u0019";
// this is really quick
BigInteger p = n1.gcd(n2);
System.out.println("p = " + p);
System.out.println();
decode_with_p(e1, n1, cipher1, p);
decode_with_p(e2, n2, cipher2, p);
}
}
</span></pre>
<p>Execute it with the following command line:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">java -ea RSATest > results.txt
</span></pre>
<p>Inside the garbage, within the <i>results.txt</i> file, you should notice the following:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">String message (oaep) = What could go wrong: http://pastebin.com/hNz9gZbe
...
String message (oaep) = A real example: http://digitaloffense.net/tools/debian-openssl
</span></pre>
<p><b>To conclude</b>, take care when you generate the keys for RSA encryption (and yes, go through <a href="http://digitaloffense.net/tools/debian-openssl/">this link</a>)!</p>
<p>If you'd like to go through more such quests, try <a href="http://www.udacity.com/overview/Course/cs387/CourseRev/apr2012">this course</a> (a really nice one).</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com1tag:blogger.com,1999:blog-4943758572656554397.post-54991482623208948082012-04-30T17:34:00.001-07:002020-07-25T10:20:02.276-07:00A few words about ConcurrentHashMap<p>There is a popular belief that, because <i>ConcurrentHashMap</i> is part of the <i>java.util.concurrent</i> package then it is designed to deal with multi-threading only. However, <i>ConcurrentHashMap</i> also has quite a useful property that I will exploit in this post, without mentioning multi-threading at all.</p>
<p>Let's start with the following code:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.util.Map;
import java.util.HashMap;
public class HashMapTest {
// creates a map with the keys from an array and
// initializes the values with zero
public static Map<String, Integer> prepareMap(String[] arr) {
Map<String, Integer> map = new HashMap<String, Integer>();
for (String str : arr) {
map.put(str, new Integer(0));
}
return map;
}
// updates the map, i.e. increases the values by one
public static void updateMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
Integer i = map.get(str);
map.put(str, new Integer(i.intValue() + 1));
}
}
// prints the map content
public static void printMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
System.out.println(str + " -- " + map.get(str));
}
}
static public void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H"};
Map<String, Integer> map = prepareMap(arr);
printMap(map);
updateMap(map);
printMap(map);
}
}</span></pre>
<p>Nothing complicated, we generate a map and process it within the <i>updateMap</i> method. Everything works fine at this point. However, let's imagine that we need a slightly more complicated processing of the map, e.g. if we encounter the key "C", then we need to add a new entry to the map, something like this:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;"> // updates the map, i.e. increases the values by one
public static void updateMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
Integer i = map.get(str);
map.put(str, new Integer(i.intValue() + 1));
if (str.equals("C")) {
// we have a special case, let's treat it
map.put("C1", new Integer(0));
}
}
}
</span></pre>
<p>Now, when we execute the updated code, it fails (run time) with the following exception:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(Unknown Source)
at java.util.HashMap$KeyIterator.next(Unknown Source)
at HashMapTest.updateMap(HashMapTest.java:19)
at HashMapTest.main(HashMapTest.java:55)
</span></pre>
<p>And this is exactly what we are told by <a href="http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html#keySet()">the specification</a>:</p>
<p><i>"Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined."</i></p>
<p>In other words, HashMap (in fact, this isn't specific to HashMap only) doesn't allow for "updates while iterating", more specifically adding new entries with new keys.</p>
<p><a name="HashSet">One way to fix the problem is to create a copy of the key set, something like this:</a></p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.util.Map;
import java.util.HashMap;
import java.util.HashSet;
public class HashMapTest {
// creates a map with the keys from an array and
// initializes the values with zero
public static Map<String, Integer> prepareMap(String[] arr) {
Map<String, Integer> map = new HashMap<String, Integer>();
for (String str : arr) {
map.put(str, new Integer(0));
}
return map;
}
// updates the map, i.e. increases the values by one
public static void updateMap(Map<String, Integer> map) {
HashSet<String> keys = new HashSet<String>(map.keySet());
for (String str : keys) {
Integer i = map.get(str);
map.put(str, new Integer(i.intValue() + 1));
if (str.equals("C")) {
// we have a special case, let's treat it
map.put("C1", new Integer(0));
}
}
}
// prints the map content
public static void printMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
System.out.println(str + " -- " + map.get(str));
}
}
static public void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H"};
Map<String, Integer> map = prepareMap(arr);
printMap(map);
updateMap(map);
printMap(map);
}
}
</span></pre>
<p>But, if we look at the output, we will mention that "C1" node is unprocessed:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;"> ...
A -- 1
B -- 1
C -- 1
C1 -- 0
H – 1
...
</span></pre>
<p>As a result, we will need a new routine to process the unprocessed data. There is a different solution though, to use <i>ConcurrentHashMap</i>, which according to <a href="http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentHashMap.html">the specification</a>:</p>
<p><i>"Retrievals reflect the results of the most recently completed update operations holding upon their onset."</i></p>
<p><a name="ConcurrentHashMap">And here is the final code:</a></p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class HashMapTest {
// creates a map with the keys from an array and
// initializes the values with zero
public static Map<String, Integer> prepareMap(String[] arr) {
Map<String, Integer> map = new ConcurrentHashMap<String, Integer>();
for (String str : arr) {
map.put(str, new Integer(0));
}
return map;
}
// updates the map, i.e. increases the values by one
public static void updateMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
Integer i = map.get(str);
map.put(str, new Integer(i.intValue() + 1));
if (str.equals("C")) {
// we have a special case, let's treat it
map.put("C1", new Integer(0));
}
}
}
// prints the map content
public static void printMap(Map<String, Integer> map) {
for (String str : map.keySet()) {
System.out.println(str + " -- " + map.get(str));
}
}
static public void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H"};
Map<String, Integer> map = prepareMap(arr);
printMap(map);
updateMap(map);
printMap(map);
}
}
</span></pre>
<p>All the entries are processed accordingly.</p>
<p>Now, let's check the efficiency, by executing the following code:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;"> static public void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H"};
long total = 0;
int max = 1000000;
for (int i = 0; i < max; i++) {
long start = System.currentTimeMillis();
Map<String, Integer> map = prepareMap(arr);
updateMap(map);
long end = System.currentTimeMillis();
total += end - start;
}
System.out.println("Average time " + ((1.0*total)/max) + "ms");
}
</span></pre>
<p>Average for the <a href="#ConcurrentHashMap">ConcurrentHashMap version</a>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Average time 0.0022ms</span></pre>
<p>Average for the <a href="#HashSet">HashMap and HashSet version</a>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Average time 0.0010ms</span></pre>
<p>Indeed, <a href="#ConcurrentHashMap">ConcurrentHashMap</a> brings some (worth to consider) performance penalties. But it isn't like it is twice slower than the <a href="#HashSet">HashMap and HashSet version</a>, because in this example we are operating with a small number of entries:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H"};</span></pre>
<p>If we increase the number of entries to e.g. 259 (from "A0", "A1", ... to "Z9", excluding "C1"), then we have the following figures:</p>
<p>For the <a href="#ConcurrentHashMap">ConcurrentHashMap version</a>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Average time 0.048ms</span></pre>
<p>For the <a href="#HashSet">HashMap and HashSet version</a>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">Average time 0.033ms</span></pre>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-56813037083072414102012-02-29T05:08:00.000-08:002019-05-23T11:33:56.060-07:00The Game Of Life<p>Did I manage to drag your attention with the title? Good. Let's proceed to the lyrical part of this post then. A few years ago I watched <a href="https://www.youtube.com/watch?v=jqxENMKaeCU">this film</a> and found the statistics starting at 1:16:56 being quite alarming. Not that I didn't know about most of those details, but it is totally different when you see them altogether. I encourage you to watch it as well. However, for the sake of this post, let's retain the following: <b>"20% of the world's population consumes 80% of its resources"</b>.</p>
<p>Now, let's proceed to the technical part. My son started to learn Pascal at school and from time to time I give him "advanced" assignments, to polish his programming (and thinking) technique. After a few complaints from him, of the sort of "I am tired of doing nonsenses like calculate π, sorting etc. I want to do something ... real!" (well, he is just 12 years old), I decided to give him something "more real", a very basic Monte-Carlo simulation that I called "The Game Of Life". The reaction was quite unexpectedly expected, he got dragged by the title :)</p>
<p>So, what is the game about? Basically, let's imagine a world with limited resources (I don't think it is difficult to imagine this), which in the language of the game is called simply "wealth". We have a population of players with the total number of PLAYERS=100. Each player has two attributes, "wealth" and "power". The game starts with a equal distribution of wealth between the players and the "power=0" for each player. With each iteration, we can call it "a year", each player plays against a randomly selected player (players can't play with themselves). The rules for winning a turn are quite simple:
<ul>
<li>The player with greater "power" wins.</li>
<li>If the players have the same power, the richest one wins.</li>
<li>If the players have the same power and wealth, the winner is selected randomly.</li>
<li>The winner gets a reward, which means their "power" increases by 1 and if the loser has sufficient "wealth", the winner's "wealth" increases by 1, the loser's wealth decreases by 1 respectively (so we keep the resources constant).</li>
</ul>
The game continues for 10000 iterations.
</p>
<p>Here is the code (slightly adjusted with my help):
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
program montecarlosimulation;
uses wincrt;
const
PLAYERS = 100;
YEARS = 10000;
var
i,j:integer;
x,y:integer;
wealth:array[1..PLAYERS] of longint;
power :array[1..PLAYERS] of longint;
tmp:longint;
poor:integer;
// p1 is the winner!!!
procedure reward(p1, p2:integer);
begin
if wealth[p2] > 0 then begin
wealth[p1] := wealth[p1] + 1;
wealth[p2] := wealth[p2] - 1;
end;
power[p1] := power[p1] + 1;
end;
// decide who is the winner and apply the reward
procedure decision(a, b:integer):integer;
var
d:integer;
begin
// same power
if power[b] = power[a] then begin
// same wealth
if wealth[a] = wealth[b] then begin
// pick the winner randomly
d := random(2);
if d = 0 then reward(a,b)
else reward(b,a);
end
else begin
if wealth[b] > wealth[a] then reward(b,a)
else reward(a,b);
end;
end
else begin
if power[b] > power[a] then reward(b,a)
else reward(a,b);
end;
end;
begin
// initialise the players' values
// total wealth is PLAYERS*1000
for i := 1 to PLAYERS do begin
wealth[i] := 1000;
power[i] := 0;
end;
// the actual game
randomize;
for i := 1 to YEARS do begin
for x := 1 to PLAYERS do begin
y := random(PLAYERS) + 1;
// the actual play
if x <> y then decision(y, x);
end;
end;
// sorting the results, wealthiest on top
for i := 1 to PLAYERS do begin
for j:=i+1 to PLAYERS do begin
if wealth[i] < wealth[j] then begin
tmp := wealth[i];
wealth[i] := wealth[j];
wealth[j] := tmp;
tmp := power[i];
power[i] := power[j];
power[j] := tmp;
end;
end;
end;
// printing the results
poor := 0;
for i := 1 to PLAYERS do begin
if (wealth[i] = 0) then poor := poor + 1;
writeln('person[', i,'] has ', wealth[i],' wealth and ',power[i],' power');
end;
// printing statistics
writeln(poor, ' of ', PLAYERS, ' are poor.');
end.
</span></pre>
This code was compiled using <a href="http://www.freepascal.org/">Free Pascal IDE</a>.</p>
<p>Now, let's look at the results. After executing this code several times, the number of wealthy players (those with "wealth" > 0) is in between 20-23, from 100. This is ~20%. Setting YEARS = 15000 will decrease the result to 16%. But let's get back to the 20% figure, is this a coincidence with the 20% from the lyrical part on top of the post? The decision to set YEARS = 10000 was somewhat random, but later we (I and my son) figured out that ... <a href="https://en.wikipedia.org/wiki/History_of_the_world">check this out</a> "<i>Human prehistory begins in the Paleolithic Era, or "Early Stone Age". Later, during the Neolithic Era (New Stone Age), came the Agricultural Revolution(between 8000 and 5000 BCE) in the Fertile Crescent, where humans first began the systematic husbandry of plants and animals</i>".</p>
<p>Couple of interesting facts as you may see. Obviously, the code is a way too simple to pretend to model a real game of life, e.g. the number of players is constant, there is no way for the poor players to ever win (which can happen in real life), lots of rich people are also philanthropists, "brain" (and "faith") attribute isn't considered at all, two or more poor players with total "power" greater than the "power" of a rich player can compete against that player, an "insufficiently" rich player can bribe a richer and more powerful player to win the play with another player etc. This, of course, will make the game more real and complicated (for my son, who still learns Pascal, while his father "plays" the game).</p>
<p>Anyway, if I managed to drag your attention to this subject, feel free to write a better version of "The Game Of Life" and drop me a note with your results. I am really curious.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com2tag:blogger.com,1999:blog-4943758572656554397.post-43766763288345920252012-01-27T13:29:00.000-08:002012-08-07T08:50:08.479-07:00Scope of variables in Java, nulling and why this might be important<p>While playing with some performance improvements this week, I came across <a href="http://mattfleming.com/node/306">this article</a>. Weird you'd say, but let me show my version of the test scenario.</p>
<p>First of all, I am using Java 1.6.0_24 HotSpot 64-bit and executing the code with the following options (i.e. limiting the heap size to 64Mb):</p>
<pre><span class="Apple-style-span" style="color: #073763;">
java -Xms64m -Xmx64m MemTest
</span></pre>
<p>Here is the first version of the code:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
public class MemTest {
public static int avg(int[] ns) {
long sum = 0;
for (int i = 0; i < ns.length; i++) sum += ns[i];
return (int) (sum/ns.length);
}
public static void main(String[] args) {
int[] nums = null;
for (int j = 0; j < 1000000; j++) {
System.out.print("Iteration: ");
System.out.println(j);
int sz = 2<<(j % 30);
if (sz > 11162611) sz = 11162611;
System.out.print("Dynamic size: ");
System.out.println(sz);
nums = new int[sz];
for (int i = 0; i < nums.length; i++) nums[i] = i;
int avr = avg(nums);
System.out.print("Average: ");
System.out.println(avr);
}
}
}
</span></pre>
<p>There is nothing complicated in this code, we allocate an array (<i>int[] nums</i>) outside the main <i>"for"</i> loop (this is the key point of this post by the way) and calculate the average. Everything works fine so far. Now let's remove the <i>"for"</i> loop responsible for assignments:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
public class MemTest {
public static int avg(int[] ns) {
long sum = 0;
for (int i = 0; i < ns.length; i++) sum += ns[i];
return (int) (sum/ns.length);
}
public static void main(String[] args) {
int[] nums = null;
for (int j = 0; j < 1000000; j++) {
System.out.print("Iteration: ");
System.out.println(j);
int sz = 2<<(j % 30);
if (sz > 11162611) sz = 11162611;
System.out.print("Dynamic size: ");
System.out.println(sz);
nums = new int[sz];
int avr = avg(nums);
System.out.print("Average: ");
System.out.println(avr);
}
}
}
</span></pre>
<p>Now the execution fails with the <i>OutOfMemoryError</i>. Odd, isn't it? What do we typically do in such cases? Increase the heap size? Well, but the previous version was working fine with the same heap size. Ok, now let's do something which isn't considered as a good practise by adding the line <i>"nums = null;"</i>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
public class MemTest {
public static int avg(int[] ns) {
long sum = 0;
for (int i = 0; i < ns.length; i++) sum += ns[i];
return (int) (sum/ns.length);
}
public static void main(String[] args) {
int[] nums = null;
for (int j = 0; j < 1000000; j++) {
System.out.print("Iteration: ");
System.out.println(j);
int sz = 2<<(j % 30);
if (sz > 11162611) sz = 11162611;
System.out.print("Dynamic size: ");
System.out.println(sz);
nums = new int[sz];
int avr = avg(nums);
nums = null; // <<-- HERE IS THE NEW LINE
System.out.print("Average: ");
System.out.println(avr);
}
}
}
</span></pre>
<p>Hey, fantastic, it works again! And now let's do it properly by changing <a href="http://java.sun.com/docs/books/jls/third_edition/html/statements.html#5920">the scope</a> of the <i>"int[] nums"</i>:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
public class MemTest {
public static int avg(int[] ns) {
long sum = 0;
for (int i = 0; i < ns.length; i++) sum += ns[i];
return (int) (sum/ns.length);
}
public static void main(String[] args) {
for (int j = 0; j < 1000000; j++) {
System.out.print("Iteration: ");
System.out.println(j);
int sz = 2<<(j % 30);
if (sz > 11162611) sz = 11162611;
System.out.print("Dynamic size: ");
System.out.println(sz);
int[] nums = new int[sz]; // <<-- LOCAL SCOPE
int avr = avg(nums);
System.out.print("Average: ");
System.out.println(avr);
}
}
}
</span></pre>
<p>And it works again.</p>
<p>So, why is this happening? I have no idea. It could be a particularity of the JVM implementation, as the author of the article, I mentioned at the top, suggests. But, obviously we can draw a conclusion, variable scope is something worth considering (and probably coding standards aren't always just "cosmetic" features).</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com1tag:blogger.com,1999:blog-4943758572656554397.post-75805510442126886602012-01-25T05:45:00.000-08:002012-01-25T06:11:54.940-08:00Getting ready for Oracle Certified Professional Java SE Programmer?<p>Few years ago I passed <a href="http://en.wikipedia.org/wiki/Sun_Certified_Professional">SCJP (Sun Certified Java Programmer)</a> certification and, during the preparation for the test, compiled a short, 18 pages, document containing some key facts required for passing the test successfully. I "accidently" found it in my archives and decided to share it, <a href="https://docs.google.com/document/d/1p1R27eiPxp3rPeKVsnqPLvFpAoAfDCEiDnEvFi9p1sU/edit">here is the link</a>.<p>
<p>The document is a collection of various facts, gathered from various books/articles as well as code examples written by me while experimenting. It doesn't always clarify each topic with great details, but this wasn't the purpose of the document. So, if you struggle with a topic and want to know more, I always recommend to consult <a href="http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html">JLS (Java Language Specification)</a>.</p>
<p>You are more than welcome to use it and I will be happy to know if it helped you to pass the test (or at least you find it useful) ;)</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com2tag:blogger.com,1999:blog-4943758572656554397.post-40588731241339389532011-12-14T16:28:00.000-08:002018-08-13T03:53:52.492-07:00Jail Break Quiz<p>Everything was quiet and peaceful today, until Google Reader brought to my attention <a href="http://plus.maths.org/content/jail-break">this puzzle from plus.maths.org</a>.</p>
<p>So, I said, why not writing a little Java program to resolve this? Here is the code:</p>
<pre><span class="Apple-style-span" style="color: #073763; font-size: x-small;">
public class Puzzle1 {
static public final int MAX = 100;
static public void printDoors(boolean[] doorIsOpen) {
int count = 0;
for (int i = 0; i < doorIsOpen.length; i++) {
if (doorIsOpen[i]) {
System.out.print("o");
count++;
}
else System.out.print("c");
}
System.out.println(" =" + count + " open doors");
}
static public void main(String[] args) {
boolean[] doorIsOpen = new boolean[MAX];
for (int i = 1; i <= MAX; i++) {
for (int j = i; j <= MAX; j+=i) {
doorIsOpen[j-1] = !doorIsOpen[j-1];
}
printDoors(doorIsOpen);
}
}
}
</span></pre>
<p>The result was <b>"10 prisoners have escaped"</b>, as per the last line printed by the program:</p>
<pre><span class="Apple-style-span" style="color: #073763;">
<font color="red">o</font>cc<font color="red">o</font>cccc<font color="red">o</font>cccccc<font color="red">o</font>cccccccc<font color="red">o</font>cccccccccc<font color="red">o</font>
cccccccccccc<font color="red">o</font>cccccccccccccc<font color="red">o</font>cccccccc
cccccccc<font color="red">o</font>cccccccccccccccccc<font color="red">o</font>
=10 open doors
</span></pre>
<p>The most interesting part of the puzzle, though, is the <b>"why"</b> one. Have a look at the sequence; 1st position (cell in this case) contains "o" (from "open"), 4 - "o", 9 - "o", 16 - "o", 25 - "o", 36 - "o", 49 - "o", 64 - "o", 81 - "o", 100 - "o". Basically, every number of type q<sup>2</sup>≤100 corresponds to an "o". Now, this is weird ... but not for a long time.</p>
<p>Let's stick with an easier example (10 rather than 100):
<table border="0">
<tr><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>o</td><td>c</td><td>o</td><td>c</td><td>o</td><td>c</td><td>o</td><td>c</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>c</td><td>o</td><td>o</td><td>o</td><td>c</td><td>c</td><td>c</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>o</td><td>o</td><td>o</td><td>o</td><td>c</td><td>c</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>o</td><td>o</td><td>o</td><td>c</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>c</td><td>o</td><td>o</td><td>c</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>c</td><td>c</td><td>o</td><td>c</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>c</td><td>c</td><td>c</td><td>c</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>c</td><td>c</td><td>c</td><td>o</td><td>o</td></tr>
<tr><td>o</td><td>c</td><td>c</td><td>o</td><td>c</td><td>c</td><td>c</td><td>c</td><td>o</td><td>c</td></tr>
</table>
<ul>
<li>1st cell (column from the left) is visited one time and remains opened and unvisited after that. Also number 1 has one divisor {1}.</li>
<li>2nd cell is visited two times (one "o" and one "c") and remains closed and unvisited after that. Also number 2 has two divisors {1, 2}.</li>
<li>3rd cell is visited two times (one "o" and one "c") and remains closed and unvisited after that. Also number 3 has two divisors {1, 3}.</li>
<li>4th cell is visited three times (one "o", one "c" and one "o") and remains opened and unvisited after that. Also number 4 has three divisors {1, 2, 4}.</li>
<li>...</li>
</ul></p>
<p>It turns out that the number of visits is equal to the number of divisors the number, corresponding to the cell (column from the left), has. <a href="http://primes.utm.edu/glossary/xpage/Tau.html">Here is the formula</a> and this statement is easy to prove (e.g. using <a href="http://en.wikipedia.org/wiki/Mathematical_induction">induction</a>).
<ul>
<li>Now, if the number of divisors is even (we have a whole number of pairs {"o", "c"}), because the sequence always starts with "o" then it must end with "c".</li>
<li>However, if the number of divisors is odd (we have a whole number of pairs {"o", "c"} plus one extra {"o"}), the sequence ends with "o".</li>
</ul></p>
<p>So far so good, but when the number of divisors is an odd number? According to <a href="http://primes.utm.edu/glossary/xpage/Tau.html">the formula</a> mentioned above the number<br/>
τ(n)=(e<sub>1</sub>+1)⋅(e<sub>2</sub>+1)⋅(e<sub>3</sub>+1)⋅...⋅(e<sub>k</sub>+1)<br/>
is odd when each of these numbers e<sub>1</sub>, e<sub>2</sub>, e<sub>3</sub>,...,e<sub>k</sub> is even, but this means that n is of type q<sup>2</sup>. Q.E.D.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-3271239689518727362011-12-12T09:06:00.002-08:002023-04-24T04:13:18.701-07:00K-Means Clustering Algorithm<p>This post is dedicated to <a href="https://en.wikipedia.org/wiki/K-means_clustering">K-Means Clustering Algorithm</a>, used for <a href="https://en.wikipedia.org/wiki/Unsupervised_learning">unsupervised learning</a>. <a href="https://www.youtube.com/watch?v=jAA2g9ItoAc">Here</a> is a short introduction into the unsupervised learning subject. <a href="https://www.youtube.com/watch?v=hDmNF9JG3lo">This video</a> shows the algorithm at work.</p>
<p>So, how does it work?</p>
<p><b>1.</b> First of all we have the number <i>K</i> (the number of clusters) and the data set <i>X<sub>1</sub></i>,...,<i>X<sub>m</sub></i> as inputs, <i>K < m</i> and <i>X<sub>j</sub> ∈ ℜ<sup>n</sup></i> for <i>∀j=1..m</i>. Considering that clustering is used as a task in data mining (e.g. including text), it is a nice exercise indeed to formalise a problem in a way where data is represented by vectors :)</p>
<p><b>2.</b> At this step we randomly initialise <i>K</i> cluster centroids <i>μ<sub>1</sub></i>,...,<i>μ<sub>K</sub></i>, <i>μ<sub>j</sub> ∈ ℜ<sup>n</sup></i> for <i>∀j=1..K</i>. The recommended way is to randomly initialise the centroids from the data set <i>X<sub>1</sub></i>,...,<i>X<sub>m</sub></i> and make sure that <i>μ<sub>i</sub>≠μ<sub>j</sub></i> for <i>∀ i≠j</i>.</p>
<p><b>3.</b> At this step we execute the loop:
<pre><span class="Apple-style-span" style="color: #073763;">
Repeat {
//cluster assignment step
For <i>i=1..m</i> {
Find the closest centroid for <i>X<sub>i</sub></i>, i.e.
<i>min{||X<sub>i</sub>-μ<sub>j</sub>||}</i>, <i>∀j=1..K</i>, e.g. it is <i>μ<sub>t</sub></i>;
Assign <i>c<sub>i</sub>=t</i>;
//in this case <i>c<sub>i</sub></i> is the index of
//the closest centroid for <i>X<sub>i</sub></i>
}
//move centroids step, if a particular cluster
//centroid has no points assigned to it,
//then eliminate it
For <i>j=1..K</i> {
<i>old_μ<sub>j</sub></i> = <i>μ<sub>j</sub></i>;
<i>μ<sub>j</sub></i> = average (mean) of all <i>X<sub>i</sub></i> where <i>c<sub>i</sub>=j</i>, <i>∀i=1..m</i>;
}
}
</span></pre>
This loop ends when all the centroids stop "moving", i.e. <i>||old_μ<sub>j</sub> - μ<sub>j</sub>|| < ε</i>, <i>∀j=1..K</i>, where <i>ε</i> is an error we are happy with (e.g. 0.01 or 0.001).</p>
<p>This is pretty much the algorithm. However, in this form, there is a risk to get stuck in a local minima. By local minima I mean the local minima of the cost function:<br/>
<i>J(X<sub>1</sub>,...,X<sub>m</sub>,c<sub>1</sub>,...c<sub>m</sub>,μ<sub>1</sub>,...,μ<sub>K</sub>) = (1 ⁄ m)⋅∑||X<sub>i</sub> – μ<sub>c<sub>i</sub></sub>||<sup>2</sup></i>, sum is for <i>i=1..m</i></p>
<p>In order to address this, the algorithm (steps 2, 3) are executed several times (e.g. 100). Each time the cost function (<i>J(...)</i>) is computed and the clustering with the lowest <i>J(...)</i> is picked up. E.g.
<pre><span class="Apple-style-span" style="color: #073763;">
For <i>p=1..100</i> {
Perform step 2;
Perform step 3;
Calculate cost function <i>J(...)</i>;
}
Pick up clustering with the lowest cost <i>J(...)</i>;
</span></pre></p>
<p>In order to make it more interactive, I and my son spent couple of hours implementing a JavaScript version of this algorithm using <i><canvas></i> tag from HTML5 (my son studies HTML at school, so it was an interesting exercise). <a href="https://github.com/rtybase/ml-ai-stats/blob/master/clustering/k-means-clustering.html">Here</a> is the link to the page (excuse me and my son for our non OOP approach to JavaScript :)). If you want to have a look at the sources, feel free to download that page (we didn't provide comments, but hopefully this article explains everything). We tested it with Google Chrome and Internet Explorer 9 (if you have problems with IE9, please consult the <a href="https://stackoverflow.com/questions/5016513/ie9-support-for-html5-canvas-tag">following link</a>).</p>
Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0tag:blogger.com,1999:blog-4943758572656554397.post-65018741566699830752011-11-22T05:53:00.002-08:002023-07-15T13:06:46.146-07:00A* Search<p>Algorithms form an important part of the problem solving process in Artificial Intelligence. One useful algorithm is <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A* Search</a>, which is an extension of another useful algorithm called <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra's algorithm</a>. <a href="http://www.youtube.com/watch?v=_CBhTubi-CU">This video</a> is a short introduction to the subject.</p>
<p>So, the key part of this algorithm is the evaluation function
$$f(\text{node})=g(\text{node})+h(\text{node})$$
(note that in the video "state" is treated as a "node"), where<br/>
- $g(\text{node})$ is the cost from the "Start" node to the current node and<br/>
- $h(\text{node})$ is the heuristic (estimated) cost from the current node to the "Goal".<br/>
The algorithm works by always expanding the path which has the minimum value of $f(\text{node})$ first (cheapest first). The search terminates when the "Goal" node is chosen for expansion or there are no more nodes to expand.</p>
<p>For the heuristic function to be <a href="http://en.wikipedia.org/wiki/Admissible_heuristic">admissible (or optimistic, which is the same)</a> it is important that for any node $h(\text{node}) \le$ actual cost from the node to the "Goal".
If this is true, then "A* Search" will always find the lowest cost path from the "Start" to the "Goal", <a href="http://www.youtube.com/watch?v=3Vmn9Rn-lDM">this video</a> explains this principle with more details.</p>
<p>As you could mention, the last video operates with another term called "search frontier". It is a "characteristic" of the algorithm or the way it progresses to/with expanding the nodes. For example:<br/>
- <a href="http://artint.info/html/ArtInt_54.html">this article</a> shows how the search frontier looks for the Breadth-First Search algorithm and<br/>
- <a href="http://artint.info/html/ArtInt_53.html">this article</a> shows how the search frontier looks for the Depth-First Search algorithm.</p>
<p>An implementation of this algorithm would use a priority queue, where priority is dictated by the function <i>f</i>.</p>
<p>Now, let's consolidate this material with an exercise:</p>
<p style="color: grey;">For heuristic function <i>h</i> and cost of action 10 (per step), find the order (1, 2, 3, ...) of the nodes expansion (the node is expanded when it is removed from queue). Start with "1" at the "Start" state at the top. Indicate the nodes that will never be expanded. Is the heuristic function admissible?
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_XVsGRBYR1qm2p9nAmLXRb8CBgBR4arEyNlvtO6KMZ_YjJeV43cXD_oDq5w-fgsGw1Id1-gtskqK0mGu0_bF8sWJHgAcwH3Gg9c_7IRPjJ0XeUCgy8fen3r7XcVGoOe5k08EKrMCcNWEdwxZsgxrJ0EeGcITMxUCKlFYwfXNwweVzLMKPV8viJv1sQ2I/s437/A-Search.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="400" data-original-height="241" data-original-width="437" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_XVsGRBYR1qm2p9nAmLXRb8CBgBR4arEyNlvtO6KMZ_YjJeV43cXD_oDq5w-fgsGw1Id1-gtskqK0mGu0_bF8sWJHgAcwH3Gg9c_7IRPjJ0XeUCgy8fen3r7XcVGoOe5k08EKrMCcNWEdwxZsgxrJ0EeGcITMxUCKlFYwfXNwweVzLMKPV8viJv1sQ2I/s400/A-Search.png"/></a></div></p>
<p>First of all the heuristic function is not admissible because <i>h(B5)=20 > 10</i>, where 10 is the actual cost from B5 to the "Goal".</p>
<p>Now, let's start with the expansion. The frontier is at the "Start".</p>
<p><b>1.</b> <i>f(A1)=10+11=21</i>, <i>f(A2)=18</i>, <i>f(A3)=17</i>, <i>f(A4)=16</i>, <i>f(A5)=20</i>. The frontier moves to A1, A2, A3, A4, A5 (this is the content of the queue).</p>
<p><b>2.</b> A4 is the node (in the queue) with the minimum <i>f</i> (=16), so it's the second node to be expanded (removed from the queue). <i>f(B4)=10+10+5=25</i>, <i>f(B5)=40</i>. The frontier moves to A1, A2, A3, B4, B5, A5.</p>
<p><b>3.</b> A3 is the next node with the minimum <i>f</i> (=17), so it's the third node to be expanded. But there is nothing to add to the queue. The frontier now is A1, A2, B4, B5, A5.</p>
<p><b>4.</b> A2 is the next node with the minimum <i>f</i> (=18), so it's the forth node to be expanded. <i>f(B2)=10+10+3=23</i>, <i>f(B3)=29</i>. The frontier moves to A1, B2, B3, B4, B5, A5.</p>
<p><b>5.</b> A5 is the next node (again, in the queue) with the minimum <i>f</i> (=20), so it's the fifth node to be expanded. <i>f("Goal")=10+10+0=20</i>. The frontier moves to A1, B2, B3, B4, B5, "Goal".</p>
<p><b>6.</b> The "Goal" is the next node (from the queue) with the minimum <i>f</i> (=20), so it's the sixth node to be expanded and, because it is the "Goal", it is also the last one to be expanded (i.e. end of the search).</p>
<p>Here is the expansion order: "Start"-1, A4-2, A3-3, A2-4, A5-5, "Goal"-6.</p>
<p>The nodes which were never expanded: A1, B1, B2, B3, B4 and B5.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com1tag:blogger.com,1999:blog-4943758572656554397.post-87107169351301061532011-11-17T07:36:00.001-08:002011-11-17T07:52:52.420-08:00Dimensionality Reduction<p>Another interesting Machine Learning algorithm (unsupervised learning this time) is <a href="http://en.wikipedia.org/wiki/Principal_component_analysis">Dimensionality Reduction</a>.</p>
<p><a href="http://www.youtube.com/watch?v=5m6TeKw_e1M">Here is a short video</a> explaining the theory. In the example presented in this video the mean (μ vector) is the simple arithmetic average per column of the matrix X. Σ (or <a href="http://en.wikipedia.org/wiki/Covariance_matrix">covariance</a>) matrix is simply (1 ⁄ M)⋅(X-μ)<sup>T</sup>⋅(X-μ) (where X-μ is per column operation, i.e. mean is extracted from each element of the relevant column, T – is transpose operator and M is the number of rows in the matrix X). <a href="http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors">Eigen values and vectors</a> are of the Σ matrix, i.e. satisfying Σ⋅v=λ⋅v, where λ is a scalar value.</p>
<p>And <a href="http://www.youtube.com/watch?v=KuSZmepQA_s">here is another video</a> explaining the algorithm's applicability.</p>Ruslan Ciurcahttp://www.blogger.com/profile/08484954220135697976noreply@blogger.com0