Susam Pal
http://susam.in/blog/
A blog on puzzles, mathematics, science and technologyenTwinkle twinkle little star
http://susam.in/blog/twinkle-twinkle-little-star/
<p>
<a href="https://www.youtube.com/watch?v=3hyeNNpxhp4">Twinkle twinkle
little star</a> is a short musical piece I composed and recorded last
evening.
</p><p>
This piece consists of 56 measures. It is 1 minute 52 seconds long. The
music is composed of four tracks. This is my second attempt at recording
music with multiple tracks. The last such attempt was more than two
years ago when I composed and recorded <a href="/blog/a-few-notes/">'A
few notes'</a>.
</p>
<p>
The links to the audio files, sheet music, etc. are provided below. The
files reside in my website. In case, my website is down, the YouTube
link provided below should still work.
</p> <div id="twinkle-twinkle-little-star" class="music"> <!-- Audio -->
<audio controls="controls" preload="none">
<source src="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.mp3" type="audio/mpeg"></source>
<source src="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.ogg" type="audio/ogg"></source>
</audio>
<div class="links">
<!-- MP3 -->
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.mp3"><img style="position: relative; top: 3px"
title="Download audio in MP3 format"
src="/images/audio.png"></a>
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.mp3" title="Download audio in MP3 format">MP3</a>
<span class="separator">|</span>
<!-- OGG -->
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.ogg"><img style="position: relative; top: 3px"
title="Download audio in OGG Vorbis format"
src="/images/audio.png"></a>
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.ogg" title="Download audio in OGG Vorbis format">OGG</a>
<span class="separator">|</span>
<!-- Youtube -->
<a href="http://www.youtube.com/watch?v=3hyeNNpxhp4"><img style="position: relative; top: 2px"
title="Listen to 'Twinkle twinkle little star' on YouTube"
src="/images/youtube.png"></a>
<a href="http://www.youtube.com/watch?v=3hyeNNpxhp4" title="Listen to 'Twinkle twinkle little star' on YouTube">YouTube</a>
<span class="separator">|</span>
<!-- Score -->
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.pdf"><img style="position: relative; top: 5px"
height="22px"
title="PDF sheet music for 'Twinkle twinkle little star'"
src="/images/gclef.png"></a>
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.pdf" title="PDF sheet music for 'Twinkle twinkle little star'">Score</a>
<span class="separator">|</span>
<!-- LilyPond -->
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.ly"><img style="position: relative; top: 5px"
width="22px"
title="LilyPond source for PDF sheet music"
src="/images/lilypond.gif"></a>
<a href="/files/music/twinkle-twinkle-little-star/twinkle-twinkle-little-star.ly" title="LilyPond source for PDF sheet music">LilyPond</a> </div> <!-- End of links -->
</div> <!-- End of music --><p>
The four tracks in this piece are:
</p>
<ol>
<li>Grand piano</li>
<li>Slow strings</li>
<li>Xenon pad</li>
<li>Music box</li>
</ol>
<p>
This arrangement is based on the popular melody of the nursery rhyme
called <em>Twinkle, twinkle, little star</em>. The melody is played with
the treble notes of the piano. I wrote the bass notes for the piano and
the strings, and the high notes for the pad and the music box to fill
the music with emotions of love and happiness. I recorded this after
about two hours of practice.
</p> Thu, 14 Feb 2013 08:00:00 +0000Susam Palhttp://susam.in/blog/twinkle-twinkle-little-star/AUTH CRAM-MD5
http://susam.in/blog/auth-cram-md5/
<p>
I was playing with a few SMTP authentication mechanisms while setting up
my SMTP server. I found CRAM-MD5 authentication mechanism particularly
interesting as it is a challenge-response authentication mechanism and
involves HMAC-MD5. Let me first show a complete session with an SMTP
server before coming to CRAM-MD5. Note that I am not using TLS or SSL in
the sessions displayed below so that the SMTP traffic can be seen as
plaintext.
In practice, any email program should be configured to use
TLS or SSL while having a session with an SMTP server. In the following
session, I have selected the PLAIN authentication mechanism.
</p>
<pre class="terminal">
susam@nifty:~$ <kbd>telnet susam.in 25</kbd>
Trying 106.187.41.241...
Connected to susam.in.
Escape character is '^]'.
220 tesseract.susam.in ESMTP Exim 4.72 Mon, 07 Nov 2011 20:27:56 +0530
<kbd>EHLO nifty.localdomain</kbd>
250-tesseract.susam.in Hello nifty.localdomain [122.167.80.194]
250-SIZE 52428800
250-PIPELINING
250-AUTH PLAIN LOGIN CRAM-MD5
250-STARTTLS
250 HELP
<kbd>AUTH PLAIN AGFsaWNlAHdvbmRlcmxhbmQ=</kbd>
235 Authentication succeeded
<kbd>MAIL FROM:<alice@susam.in></kbd>
250 OK
<kbd>RCPT TO:<example.recipient@gmail.com></kbd>
250 Accepted
<kbd>DATA</kbd>
354 Enter message, ending with "." on a line by itself
<kbd>Date: Mon, 07 Nov 2011 20:28:00 +0530
From: Alice <alice@susam.in>
To: Example Recipient <example.recipient@gmail.com>
Subject: Test email
This is a test email.
.</kbd>
250 OK id=1RNQef-0004e7-7s
<kbd>QUIT</kbd>
221 tesseract.susam.in closing connection
Connection closed by foreign host.
</pre>
<p>
In the AUTH PLAIN line I have sent the base64 encoding of the string
<code>\0alice\0wonderland</code>. <code>\0</code> indicates a null
character, <code>alice</code> is the sender's user name and
<code>wonderland</code> is the sender's password. If an eavesdropper
intercepts this network traffic, he can easily find the user's password
by simply decoding the base64 response sent by the client. This is also
susceptible to replay attacks as the eavesdropper can use the <code>AUTH
PLAIN</code> line containing the base64 encoded credentials to log into
the server in future. This is why it is very important to secure the
connection with TLS or SSL while having a session with the SMTP server.
</p><p>
Now, let me quickly show only the relevant lines for an authentication
using the LOGIN mechanism.
</p>
<pre class="terminal">
<kbd>AUTH LOGIN</kbd>
334 VXNlcm5hbWU6
<kbd>YWxpY2U=</kbd>
334 UGFzc3dvcmQ6
<kbd>d29uZGVybGFuZA==</kbd>
235 Authentication succeeded
</pre>
<p>
What is happening here becomes clear by decoding the base64 encoded
messages. The following statements in Python 2.7.2 decode these
messages.
</p>
<pre class="terminal">
>>> <kbd>'VXNlcm5hbWU6'.decode('base64')</kbd>
'Username:'
>>> <kbd>'YWxpY2U='.decode('base64')</kbd>
'alice'
>>> <kbd>'UGFzc3dvcmQ6'.decode('base64')</kbd>
'Password:'
>>> <kbd>'d29uZGVybGFuZA=='.decode('base64')</kbd>
'wonderland'
</pre>
<p>
If the session isn't encrypted, LOGIN authentication mechanism is
susceptible to the same problems that PLAIN authentication mechanism is
susceptible to. Now, let me describe the CRAM-MD5 authentication
mechanism. When the client selects the CRAM-MD5 authentication
mechanism, the server sends a base64 encoded challenge as shown below.
</p>
<pre class="terminal">
<kbd>AUTH CRAM-MD5</kbd>
334 PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg==
</pre>
<p>
An HMAC is calculated for this challenge with the password as the key
and MD5 as the hash function. A string is formed by concatenating the
user name, a space and the hexadecimal representation of the HMAC. The
base64 encoding of this string is sent as the response by the client.
The following statements I tried in Python 2.7.2 show how a response can
be formed for the above challenge.
</p>
<pre class="terminal">
>>> <kbd>'PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg=='.decode('base64')</kbd>
'<17893.1320679123@tesseract.susam.in>'
>>> <kbd>import hmac, hashlib</kbd>
>>> <kbd>hmac.new('wonderland', '<17893.1320679123@tesseract.susam.in>', hashlib.md5).hexdigest()</kbd>
'64b2a43c1f6ed6806a980914e23e75f0'
>>> <kbd>'alice 64b2a43c1f6ed6806a980914e23e75f0'.encode('base64')</kbd>
'YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=\n'
</pre>
<p>
Of course, this can be written as a small function:
</p>
<pre class="code">
import hmac, hashlib
def cram_md5_response(username, password, base64challenge):
return (username + ' ' +
hmac.new(password,
base64challenge.decode('base64'),
hashlib.md5).hexdigest()).encode('base64')
</pre>
<p>
The following snippet shows the SMTP server accepting the
client-response.
</p>
<pre class="terminal">
<kbd>AUTH CRAM-MD5</kbd>
334 PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg==
<kbd>YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=</kbd>
235 Authentication succeeded
</pre>
<p>
CRAM-MD5 authentication mechanism is relatively more secure than the
other two mechanisms even if the connection is not secured because the
password cannot be retrieved by decoding the base64 encoded
client-response. The password is used as the key to calculate the HMAC
but the password is not present anywhere in the response. It prevents
replay attacks too because the server sends an unpredictable challenge
for every authentication. The client-response computed for a certain
challenge is invalid for further authentications which will involve
different unpredictable challenges.
</p>
<p>
Here is a list of hyperlinks for further reading:
</p>
<ol>
<li><a href="http://tools.ietf.org/html/rfc4954">RFC 4954</a>:
SMTP Service Extension for Authentication
</li>
<li><a href="http://tools.ietf.org/html/rfc4616">RFC 4616</a>:
The PLAIN Simple Authentication and Security Layer (SASL) Mechanism
</li>
<li><a href="http://tools.ietf.org/html/rfc2195">RFC 2195</a>:
IMAP/POP AUTHorize Extension for Simple Challenge/Response
</li>
<li><a href="http://tools.ietf.org/html/rfc2104">RFC 2104</a>:
HMAC: Keyed-Hashing for Message Authentication</li>
</ol> Mon, 07 Nov 2011 20:27:56 +0000Susam Palhttp://susam.in/blog/auth-cram-md5/When worse is better
http://susam.in/blog/when-worse-is-better/
<p>
Let me begin this post with a puzzle.
</p>
<div class="problem">
<p>
Alex and Bob worked as financial advisers for the same company. They
drew equal salaries from the company. They behaved well at the office.
Both worked on similar assignments. Each assignment required a yes-no
decision. The company used the decisions made by them to make profits.
</p><p>
After the recession hit the company very badly, they have to fire one of
them. Both Alex and Bob have worked on almost the same number of
assignments in the last ten years. Alex has been consistently taking
about 80% decisions correctly every year. Bob, on the other hand, has
been taking only about 5% correct decisions every year.
</p><p>
The company has decided to keep Bob and fire Alex. Why?
</p>
</div>
<p>
If you want to solve this puzzle yourself, you might want to stop here
and think for a while. There are spoilers ahead.
</p><p>
Before giving away the solution to this puzzle, let me discuss
something else.
</p>
Shannon's noisy channel coding theorem guarantees that in a binary
symmetric channel with an error rate \(p\), it is possible to transmit
digital data with arbitrarily small probability of error up to a
transmission rate of
\[
1 + p \mathop{\log_2} p + (1 - p) \mathop{\log_2} (1 - p)
\]
</p><p>
We'll call this the optimal transmission rate. The error rate \(p\) is
the probability that the channel will corrupt a bit from 1 to 0 or vice
versa. The transmission rate is the ratio of the number of data bits to
the total number of bits used to represent them. If we employ
error-correcting codes, the transmission rate would be less than 1
because we'll need extra bits for error correction. As a result, the
number of bits used to represent them would be more than the number of
data bits.
</p>
<div class="center">
<img src="/files/blog/when-worse-is-better/transmission-rate.png"
alt="graph">
</div>
<p>
For \(p = 0\), the transmission rate is maximum. That's obvious.
Loosely speaking, if the channel is error-free, we do not need extra
bits for error correction. The transmission rate is poorest when
\(p = \frac{1}{2}\). In this case, each bit
received is completely random since the channel is just as likely to
send 0 or 1 irrespective of the original bit sent by the transmitter.
However, it might be surprising that as the error rate increases from
\(0.5\) to \(1\), the optimal transmission rate increases. When
\(p = 1\), the optimal transmission rate is maximum again. It is
easy to undersand this intuitively. At \(p = 1\), the channel is
guaranteed to corrupt each bit. The receiver can correct the error by
inverting each bit in the received message, so we do not need extra bits
for error correction in this case as well.
</p><p>
Now, let me get back to the puzzle I mentioned while beginning this
post.
</p><p>
The company decided to keep Bob because he was more useful to the
company. He helped the company to take 95% correct decisions. They
simply did the opposite of what Bob recommended and made huge profits in
the last ten years. Alex on the other hand helped them take only 80%
decisions correctly, so he has to go. It's unfair but it's more
profitable.
</p> Sat, 29 Oct 2011 02:00:00 +0000Susam Palhttp://susam.in/blog/when-worse-is-better/Re: Infosys, TCS, or Wipro?
http://susam.in/blog/re-infosys-tcs-or-wipro/
<p>
The <a href="/blog/infosys-tcs-or-wipro/">'Infosys, TCS, or Wipro?'</a>
post is doing the rounds again and some hatred as well as love is
arriving on my email.
</p><p>
I can understand when someone dislikes the way I have expressed the
whole matter in that blog post. But I fail to understand the motivation
behind any employee of these organizations trying to justify that
working there is almost as good as working for a company where you can
work with a team of very talented engineers. There have been <a
href="http://hackerstreet.in/item?id=6323">plenty</a> <a
href="http://news.ycombinator.com/item?id=2628318">of</a> <a
href="http://www.reddit.com/r/india/comments/lqemo/why_a_fresher_should_not_join_infosys_tcs_or_wipro/">arguments</a>
on the web. I'll discuss some of the points made in the arguments.
</p>
<ol class="contentlist">
<li><a href="#india">India needs IT services companies</a></li>
<li><a href="#business-vs-engineering">Business problems vs. engineering problems</a></li>
<li><a href="#business-and-engineering">Business problems and
engineering problems</a></li>
<li><a href="#engineering">Engineering in Adobe, Amazon, Google, etc.</li>
<li><a href="#passion">Passionate people can do engineering anywhere</a></li>
<li><a href="#cannot">But everyone cannot join Adobe, Amazon, Google, etc.</a></li>
<li><a href="#engineers">Infosys, TCS and Wipro have good engineers</a></li>
<li><a href="#training">Training</a></li>
<li><a href="#meritocracy">Meritocracy</a></li>
<li><a href="#leaving">Leaving Infosys, TCS, or Wipro</a></li>
<li><a href="#algorithms">Solving algorithm problems vs. editing configuration</a></li>
</ol>
<ol class="paralist">
<li id="india"><b>India needs IT services companies:</b>
The most popular argument by Indians has been that India needs IT
services companies because they make a lot of money and boost India's
economy. I don't understand why anyone would attack my post with this
point when I have never said anything to the contrary. In fact, I agree
with this point. Therefore this argument is nothing more than a
strawman. However, in my opinion, students who have learnt their
engineering well during the course, and now want to improve their
engineering skills during work shouldn't work for one of these
companies. They should join <a
href="/blog/infosys-tcs-or-wipro/#suggestion">a start-up or a company
known for hiring skilled engineers</a>.
</li>
<li id="business-vs-engineering"><b>Business problems vs. engineering
problems:</b> Another popular argument has been that a software
company is not a place to showcase your engineering talent. Many argue
that it is a place to solve business problems, not engineering problems.
I disagree with this very firmly. Business problems and engineering
problems are not mutually exclusive. The reason why many employees of
these companies feel that solving a business problem wouldn't involve an
engineering problem is that they are not technically sound enough to
even realize whether a particular problem needs to be solved with some
concept they learnt in their engineering course. I've said this before
and I'll say it again. Engineering problems are there in every software
company. It needs the mind of an engineer to identify those problems and
solve them correctly. Not all string parsing problems should be solved
with a chain of string library functions stitched together. Some string
processing and parsing work can be done more efficiently and reliably by
coding a simple <a
href="http://en.wikipedia.org/wiki/Deterministic_finite-state_machine">DFA</a>.
Not all data should be stored as records in an array. Some need to be
stored as <a href="http://mathworld.wolfram.com/Graph.html">graphs</a>.
Knowing regular expressions can be dangerous if one doesn't know what
kind of patterns they cannot express.
</li>
<li id="business-and-engineering"><b>Business problems & engineering
problems:</b> If you want to solve business problems and keep your
customers happy, Infosys, TCS, or Wipro might be the right place for
you. If you want to solve business problems, keep your customers happy
and learn a great deal of engineering while doing all these, you need to
find another workplace where you can work with a team of skilled
engineers who you can give you constructive feedback or criticism on
your work.
</li>
<li id="engineering"><b>Engineering in Adobe, Amazon, Google, etc.:</b>
A popular myth that prevails among many is that there is no engineering
to do in the Indian offices of Adobe, Amazon, Google, etc.
I'll reiterate that there is engineering to do in every
software company, even in Infosys, TCS and Wipro. It really depends on
the people whether they want to do engineering sincerely or not. Some
people would somehow develop the required software by stitching together
libraries and give up or look for less-efficient workarounds when a
particular task requires inventing a new engineering solution. There is
another kind of people who are ready to invent new engineering solutions
with all the engineering knowledge they have acquired during college and
professional life. They do not hesitate to re-invent the wheel when the
existing libraries do not meet the requirements of the particular
problem at hand. Such engineers are more in number in start-ups like
Gluster, Parallocity, SlideShare, etc. and companies like Adobe,
Amazon, Google, etc. These companies also collaborate with universties
to learn new techniques and concepts to solve business problems. These
companies do not look for less-efficient workarounds when faced with a
brick wall. They challenge themselves and do everything possible to
solve a problem in the best possible way. These are the places where
freshers can hope to learn a great deal of engineering from people around
them.
</li>
<li id="passion"><b>Passionate people can do engineering anywhere:</b>
Another popular argument is that it doesn't matter where you work. One
can do engineering anywhere, be it Google or Infosys. I agree with this.
But then, given a place like Adobe, Amazon, or Google where you can get
very good feedback on your work from talented colleagues around you and
another place like Infosys, TCS, or Wipro where clueless people around
you would call you great because you solved a problem and hail you as a
genius, where do you think you are going to learn more and improve
yourself faster?
</li>
<li id="cannot"><b>But everyone cannot join Adobe, Amazon, Google, etc.:</b>
Well, I never said that everyone should get into a reputed software product
company. Not everyone wants to make a career in engineering. Some people
have other goals in life. They just want a regular job. It sounds
perfectly fine to me. My post was written for those who aspire to make a
career in engineering. In my opinion, they should try to get into a
reputed software product company or a start-up that is known to hire
skilled engineers. If they aren't well prepared, the only thing they can
do is to prepare well to fulfill their aspirations. Some people say that
they should join Infosys, TCS and Wipro to earn a living while they are
preparing and I think it's a great advice. I'll suggest considering
contributing some new features or bug-fixes they would like to see in
some open source project. <a href="http://incubator.apache.org/">Apache
Incubator</a> has a lot of budding projects. They can try solving
problems at <a href="http://community.topcoder.com/tc">TopCoder</a>, <a
href="http://www.codechef.com/">CodeChef</a>, <a
href="http://www.spoj.pl/">SPOJ</a>, <a
href="http://projecteuler.net/">Project Euler</a>, etc. All these things
are good ways of preparing in my opinion.
</li>
<li id="engineers"><b>Infosys, TCS and Wipro have good engineers:</b>
Many people have told me that there are good engineers in Infosys, TCS
and Wipro as well. I agree. I never mentioned that 100% of the engineers
in these companies don't do engineering. I mentioned that the majority
of them don't do it. In fact, drawing from my personal experience, I
quoted a figure that only 1 out of 200 are capable of engineering in
these companies. Like most guess work, this figure could be wrong but I
am pretty confident that the bigger picture I am trying to paint here
isn't.
</li>
<li id="training"><b>Training:</b>
Many claimed that I am wrong about the poor standard of training in
Infosys, TCS, or Wipro. I must tell them that I have attended some of
these training programmes. Among the many horror stories pertaining to
training in these companies, I'll share only one with you to make my
point. In the training assessments, the instructors set question papers
containing problems with <a href="/blog/sequence-points/">code that
invokes undefined behaviour</a> and ask you to predict its output. 'It
invokes undefined behaviour' is not provided as an option you can select
as the correct answer. Such training and knowledge is not only inaccurate
but also very dangerous if you care about robustness and security of the
software you create.
</li>
<li id="meritocracy"><b>Meritocracy:</b>
A few people felt that I should have mentioned that these companies
do not practice meritocracy. Anyone with sufficient number of years of
experience can get a promotion in these companies. This is true. It
didn't occur to me while writing that post. I was focussed on the
popular myths about these companies that prevail among college students
while writing the post.
</li>
<li id="leaving"><b>Leaving Infosys, TCS, or Wipro:</b>
Some people commented that people like me just leave these companies and
discourage others from joining them. They feel that we choose the easy
way out. They would rather have us stay in these companies and improve
them. Firstly, getting a job in a reputed company where you can get an
opportunity to work on interesting engineering problems is not easy. You
have to be passionate about your area of interest. You have to work and
prepare yourself for it. Secondly, Infosys, TCS and Wipro were made by
their founders with a particular vision of providing IT services. They
have achieved what they wanted with great success. The improvements that
you want to make in these companies may not be consistent with the
vision of the founders.
</li>
<li id="algorithms"><b>Solving algorithm problems vs. editing configuration:</b>
This has to be the strangest argument I have come across. Someone
mentioned that a person who solves algorithm problems earns no more than
someone who only edits configuration files. After seeing both sides of
the software industry, I find this false. Solving an algorithm problem
is one thing. Solving an algorithm problem efficiently is an entirely
different thing. I have seen people who can solve difficult algorithm
problems efficiently earning at least twice that of an Infosys engineer.
I have numerous examples for this: a friend who is solving problems to
deliver the best news from the entire web to the users and another who
writes algorithms for a cluster of Nvidia GPUs to do real-time analysis
of network traffic to keep attackers out of the network. I have seen
people solving algorithm problems in Topcoder, Codechef, etc.
earning very well as software developers. While many argue that those
fun problems tell you nothing about one's professional programming
ability, I've found that people who successfully solve very difficult
and contrived algorithm contest problems set by some of the most
intelligent brains on the planet are actually pretty good at solving
real software engineering problems as well. The toppers from these
contests earn way more than someone who only edits configuration files.
</li>
</ol>
<p>
To summarize, that post was meant for and only for people who have what
it takes to work at a place where he can solve engineering problems. I
have known many such people who were good engineers but weren't aware of
the reality in companies like Infosys, TCS, or Wipro before joining
them. That post was meant for these people. I devoted a couple of
paragraphs in the previous post to make this clear but for some reason
most people seem to have ignored them.
</p> Fri, 28 Oct 2011 03:07:00 +0000Susam Palhttp://susam.in/blog/re-infosys-tcs-or-wipro/Solutions to 'Loopy C puzzle'
http://susam.in/blog/solutions-to-loopy-c-puzzle/
<p>
In <a href="/blog/loopy-c-puzzle/">my blog post yesterday</a>, I shared
this puzzle:
</p>
<div class="problem">
<p>
Add or modify exactly one operator in the following code such that it
prints exactly 6 dots.
</p>
<pre>
int i;
for (i = 0; i < 6; i--)
printf(".");
</pre>
</div>
<p>
Let me first list all the possible solutions I know.
</p>
<ol>
<li>
<code>for (i = 0; i < 6; i<span style="color: #008000">++</span>)</code>
</li><li>
<code>for (i = 0; i < 6; <span style="color: #008000">++</span>i)</code>
</li><li>
<code>for (i = 0; <span style="color: #008000">-</span>i < 6; i--)</code>
</li><li>
<code>for (i = 0; i <span style="color: #008000">+</span> 6; i--)</code></li>
<li><code>for (i = 0; i <span style="color: #008000">^=</span> 6; i--)</code></li>
</ol>
<p>
The last solution in the list is not quite obvious and needs a little
analysis to understand why it works. To generalize the problem, let us
use n instead of 6. So, the loop becomes:
<pre class="code">
int i;
for (i = 0; i ^= n; i--)
printf(".");
</pre>
If we use XOR to represent bitwise exclusive OR, first i is set to (n XOR i)
before we enter the loop. Since, the initial value of i is 0, this
amounts to setting i = n before we enter the loop.
</p><p>
Thereafter, every iteration prints a dot and sets
i = n XOR (i - 1). If we try to represent
two such consecutive iterations as one operation, this composite
operation prints two dots and sets
i = n XOR <big><big>(</big></big><big>(</big>n XOR (i - 1)<big>)</big> − 1<big><big>)</big></big>
where i on the RHS is the value of i before the pair of iterations and i
on the LHS is the value of i after the pair of iterations complete.
<b>… (A)</b>
</p><p>
Before we proceed further, note that
</p>
<ul>
<li>
k XOR 1 = k − 1 for an odd integer k. <b>… (1)</b>
</li><li>
k XOR 1 = k + 1 for an even integer k. <b>… (2)</b>
</li><li>
a XOR b is an odd integer if a and b have different parities. <b>… (3)</b>
</li></ul>
</ul>
<p>
I'm not presenting the proof of these results since they are very
trivial. We'll use these results in the discussion below.
</p><p>
If n is odd, i is odd initially because i is set to n before we enter
the loop. We'll show that i always remains odd and never changes for
every pair of iterations.
<p class="math">
i = n XOR <big><big>(</big></big><big>(</big>n XOR (i − 1)<big>)</big> − 1<big><big>)</big></big> … from (A)<br>
= n XOR <big><big>(</big></big><big>(</big>n XOR (i − 1)<big>)</big> XOR 1<big><big>)</big></big> … from (1) and (3)<br>
= (n XOR n) XOR <big>(</big>(i − 1) XOR 1<big>)</big> … from associativity of XOR<br>
= 0 XOR <big>(</big>(i − 1) + 1<big>)</big> … from (2) and (3)<br>
= i
</p><p>
Note that i begins as i = n. Since, i is set to n again
after every two iterations, the loop never terminates.
</p><p>
If n is even, i is even initially because i is set to n before we enter
the loop. We'll show that i always remains even and decrements by 2 for
every pair of iterations.
</p><p class="math">
i = n XOR <big><big>(</big></big><big>(</big>n XOR (i − 1)<big>)</big> − 1<big><big>)</big></big> … from (A)<br>
= n XOR <big><big>(</big></big><big>(</big>n XOR (i − 1)<big>)</big> XOR 1<big><big>)</big></big> … from (1) and (3)<br>
= (n XOR n) XOR <big>(</big>(i − 1) XOR 1<big>)</big> … from associativity of XOR<br>
= 0 XOR <big>(</big>(i − 1) − 1<big>)</big> … from (1) and (3)<br>
= i − 2
</p><p>
Since i begins as i = n and decrements by 2 for every two iterations,
the loop terminates after n iterations thereby printing n dots.
</p> Sat, 01 Oct 2011 22:46:00 +0000Susam Palhttp://susam.in/blog/solutions-to-loopy-c-puzzle/Loopy C puzzle
http://susam.in/blog/loopy-c-puzzle/
<p>
Let me share a very interesting C programming puzzle that I learnt from
one of my colleagues.
</p><p>
Consider the following code-snippet written in the C programming
language.
</p><pre class="code">
int i;
for (i = 0; i < 6; i--)
printf(".");
</pre>
This code invokes undefined behaviour. The value in variable
<code>i</code> decrements to <a
href="http://tigcc.ticalc.org/doc/limits.html">INT_MIN</a> after
|INT_MIN| + 1 iterations. In the next iteration, there is a negative
overflow which is undefined for signed integers in C. On many
implementations though, INT_MIN − 1 would result in INT_MAX which
is not less than 6 and thus the loop would terminate. With such
implementations, this code would print |INT_MIN| + 1 dots. With 32-bit
integers, that would be 2147483649 dots. However, it could also be
optimized into an endless loop by the compiler if it wants to exploit
the fact that a negative overflow for signed integers is undefined. gcc
in fact does optimize that to an endless loop if you compile it with the
<code>-O3</code> option.
</p><p>
Now, here is the puzzle.
</p>
<div class="problem">
<p>
Add or modify exactly one operator in the following code such that it
prints exactly 6 dots.
</p>
<pre class="code">
int i;
for (i = 0; i < 6; i--)
printf(".");
</pre>
</div>
</p><p>
An obvious solution is:
</p>
<pre class="code">
int i;
for (i = 0; i < 6; i<b style="color: red">++</b>)
printf(".");
</pre>
<p>
There are at least 3 other solutions. I found one of them very
interesting. I'll discuss the interesting solution tomorrow. Till then,
feel free to try and post your solutions below as comments.
</p><p>
<b>Update:</b> The discussion on the solution is now available at: <a
href="/blog/solutions-to-loopy-c-puzzle/">Solutions to 'Loopy C Puzzle'</a>.
</p> Sat, 01 Oct 2011 01:45:00 +0000Susam Palhttp://susam.in/blog/loopy-c-puzzle/From the Tower of Hanoi to counting bits
http://susam.in/blog/from-tower-of-hanoi-to-counting-bits/
<p>
<a href="/files/blog/tower-of-hanoi/rise_of_the_planet_of_the_apes.jpg">
<img width="216"
src="/files/blog/tower-of-hanoi/rise_of_the_planet_of_the_apes.jpg"
alt="Rise of the Planet of the Apes (Poster)"
style="float: right; margin-left: 10px"></a>
A few weeks ago, I watched <a
href="http://www.imdb.com/title/tt1318514/">Rise of the Planet of the
Apes</a> in a movie theatre. The movie showed a genetically engineered
chimpanzee trying to solve a puzzle involving 4 discs, initially stacked
in decreasing size on one of three pegs. The chimpanzee was supposed to
transer the entire stack to one of the other pegs, moving only one disc
at a time and never moving a larger one onto a smaller one.
</p><p>
The problem was called <em>the Lucas' problem</em> in the movie. I
couldn't help myself from remarking to my friend sitting next to me that
the problem is actually known as <em>the Tower of Hanoi</em> and the
minimum number of moves required to solve the problem is
2<sup>n</sup> − 1</sup> if there are n discs involved.
The math lectures were not very welcome by her in the middle of the
movie.
</p><p>
During the intermission, she was curious to know why it was called the
Lucas' problem instead of the Tower of Hanoi in the movie. I think it's
probably because the puzzle was invented by the French mathematician
Édouard Lucas in 1883. There is another version of this problem known
as <em>the Tower of Brahma</em> that involves 64 discs made of pure gold
and three diamond needles. According to a legend, a group of Brahmin
priests are working at the problem and the world will end when the last
move of the puzzle is completed. Now, even if they make one move every
second, it'll take 18,446,744,073,709,551,615 seconds to complete the
puzzle. That's about 584.54 billion years.
</p><p>
<a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi">
<img src="/files/blog/tower-of-hanoi/solution.gif"
alt="Animated solution"
style="float: left; margin-right: 10px"></a>
Since, the puzzle in the movie involved only 4 discs, it can be solved
in 2<sup>4</sup> − 1 = 15 moves as illustrated in an
animated solution by André Karwath that I found in the <a
href="http://en.wikipedia.org/wiki/Tower_of_Hanoi">Wikipedia article</a>
for the puzzle.
</p><p>
I'll not discuss the solution of this puzzle in this blog post. There
are plenty of articles on the web including the Wikpedia article that
describes why it takes a minimum of 2<sup>n</sup> − 1
moves to complete the puzzle. In this post, I'll talk about an
interesting result I discovered while playing with this puzzle one April
afternoon this year.
</p><p>
An interesting thing to note is that if we use T<sub>n</sub> to denote
the minimum number of moves required to solve the Tower of Hanoi problem
involving n discs, then T<sub>n</sub> when expressed in binary is the
largest possible n-bit integer. For example,
T<sub>4</sub> = 15<sub>10</sub> = 1111<sub>2</sub>.
After all, the largest n-bit integer is
2<sup>n</sup> − 1. Now, let me describe the result I
came across while playing with it by asking a question.
<div class="problem">
<p>
This problem deals with arbitrary-precision integers. Some definitions:
</p>
<ol>
<li>A positive integer N is called an n-bit integer if and only if
the minimum number of bits required to express the integer is n, or in
other words,
⌊log<sub>2</sub>(N)⌋ + 1 = n.</li>
<li>T<sub>n</sub> represents the largest possible n-bit integer.</li>
</ol>
<p>
Some assumptions:
</p>
<ol>
<li>Let the time complexity of adding or subtracting two integers be
O(1).</li>
<li>Let the time complexity of counting the number of 1-bits in an n-bit
integer be O(n).</li>
</ol>
<p>
A positive integer n is given. What is the most efficient way, in terms
of time complexity, to compute the number of 1-bits in T<sub>1</sub> +
T<sub>2</sub> + … + T<sub>n</sub>?
</p>
</div>
<p>
The naive approach would involve adding all the n integers and counting
the number of 1-bits in the sum. The time required to add the n integers
is O(n). The sum would require (n + 1) bits to be represented.
Hence, it would take O(n) time to count the number of bits in the sum.
Since the sum is (n + 1) bits long, the naive approach
requires O(n) memory as well. If n is as large as 2<sup>64</sup>, over 2
exbibytes of memory would be required to store the sum.
</p><p>
There is a more efficient solution.
</p><p class="math">
T<sub>1</sub> + … + T<sub>n</sub><br>
= 2<sup>(n + 1)</sup> − 2 − n<br>
= [2<sup>(n + 1)</sup> − 1] − (n + 1)
</p><p>
Now, 2<sup>(n + 1)</sup> − 1 has (n + 1) 1-bits.
Subtracting (n + 1) from it is equivalent to removing one
1-bit in 2<sup>(n + 1)</sup> − 1 for each 1-bit in
(n + 1). So,
</p><p class="math">
[number of 1-bits in T<sub>1</sub> + … +
T<sub>n</sub>] = [(n + 1)] − [number
of 1-bits in (n + 1)].
</p><p>
So, the computation involves counting the number of 1-bits in
n + 1 which takes O(log n) time and subtracting it from
n + 1 which takes O(1) time. The problem is solved in
O(log n) time. It occupies O(log n) memory. What required over
2 exbibytes of memory with the naive approach requires only a little
over 8 bytes of memory with this approach.
</p> Sun, 25 Sep 2011 12:33:00 +0000Susam Palhttp://susam.in/blog/from-tower-of-hanoi-to-counting-bits/Langford pairing
http://susam.in/blog/langford-pairing/
<p>
I came across this problem more than 2 years ago when Pranave, a
colleague at <a href="http://www.rsa.com/">RSA</a>, posted this in the
internal mathematics forum.
</p>
<div class="problem">
Given a list of first n natural numbers with each natural number
occurring exactly twice in the list, we need to arrange the list in a
manner such that there are exactly k numbers between two k's for each k
in the sequence.
</div>
<p>
For a small list, say, (1, 1, 2, 2, 3, 3, 4, 4), the answer can be
obtained by trial and error: (4, 1, 3, 1, 2, 4, 3, 2).
</p><p>
But what if the list is very long? There is another important question:
Is there a solution for every possible such list? The answer turns out
to be: No. One can easily see that there is no valid arrangements for
(1, 1) or (1, 1, 2, 2) that satisfy the condition specified in the
problem statement.
</p><p>
So, we have two things to solve now.
</p>
<ol>
<li>For what values of n is the problem solvable?</li>
<li>If the problem is solvable for some value of n, how do we solve it?</li>
</ol>
<p>
In this blog post, I'll show how I solved it. I took some help from the
computer by writing a <a
href="http://susam.in/downloads/files/langford-pairing/langford.py">Python
program</a> to see if I could notice any patterns. Here is the output.
</p>
<pre class="code">
n = 1 : 0 solutions ( 0 s)
n = 2 : 0 solutions ( 0 s)
n = 3 : 2 solutions ( 0 s)
n = 4 : 2 solutions ( 0 s)
n = 5 : 0 solutions ( 0 s)
n = 6 : 0 solutions ( 0 s)
n = 7 : 52 solutions ( 0 s)
n = 8 : 300 solutions ( 0 s)
n = 9 : 0 solutions ( 1 s)
n = 10 : 0 solutions ( 6 s)
n = 11 : 35584 solutions ( 45 s)
n = 12 : 216288 solutions ( 390 s)
</pre>
<p>
From the output, I could form a conjecture:
</p>
<div class="problem">
There exists a permutation of (1, 1, 2, 2, …, n, n) such that for
each k in the sequence (1 ≤ k ≤ n) there are k numbers between the
two k's if and only if n ≡ 3 (mod 4) or n ≡ 0 (mod 4).
</div>
<p>
Let me show how I proved this conjecture.
</p>
<h3>Proof of the necessity of the condition n ≡ 3 (mod 4) or n
≡ 0 (mod 4)</h3>
<p>
Let (1, 1, 2, 2, …, n, n) be a sequence which can be rearranged
such that there are k numbers between the two k's for each k in the
sequence. Let us number the position of each number in this permutation
as 1, 2, …, 2n.
</p><p>
Partition the numbers in this partition into two halves:
<ul>
<li>Partition 1: All numbers in odd numbered positions.</li>
<li>Partition 2: All numbers in even numbered positions.</li>
</ul>
<p>
The length of each partition is n.
</p><p>
Note that if k (1 ≤ k ≤ n) is even, one of the
two k's is located on an odd numbered position and the other one on even
numbered position.
</p><p>
If k is odd the two k's are both located on odd numbered positions or
both located on even numbered positions. The two k's will never be split
in two different partitions. It will be together in one partition.
</p><p>
From the above discussion it is obvious that the number of even numbers
in each partition is equal. Let the number of even numbers in each
partition be m. Let us assume there are p pairs of odd numbers in
partition 1 and q pairs of odd numbers in partition 2. Thus, there are
2p odd numbers in partition 1 and 2q odd numbers in partition 2.
</p><p>
Since, the length of each partition is n, n = m + 2p
= m + 2q. Hence, p = q. This implies that there must
be p + q = 2p pairs of odd numbers in the two
partitions, i.e. the number of positive odd numbers less than or equal
to n is 2p.
</p><p>
In other words, the number of positive odd numbers less than or equal to
n must be even. <b>… (1)</b>
</p><p>
We know that, for a positive integer n, the number of positive odd
numbers less than or equal to n is ⌈n/2⌉. Let q be the
quotient and r be the remainder obtained after dividing n by 4. We have
four possible cases.
<ol><li>If n = 4q + 1, number of positive odd numbers less than or equal
to n is, ⌈(4q + 1)/2⌉ = 2q + 1.</li><li>If n = 4q + 2,
number of positive odd numbers less than or equal to n is, ⌈(4q +
2)/2⌉ = 2q + 1.</li><li>If n = 4q + 3, number of positive odd
numbers less than or equal to n is, ⌈(4q + 3)/2⌉ = 2q +
2.</li><li>If n = 4q + 4, number of positive odd numbers less than or
equal to n is, ⌈(4q + 4)/2⌉ = 2q + 2.</li></ol>We can see
that the number of odd numbers less than or equal to n is even if and
only if n ≡ 3 (mod 4) or
n ≡ 0 (mod 4). <b>… (2)</b>
</p><p>
From (1) and (2), the necessity of the condition n ≡ 3 (mod 4) or
n ≡ 0 (mod 4) is proven.
</p>
<h3>Proof of the sufficiency of the condition n ≡ 3 (mod 4) or n
≡ 0 (mod 4):</h3>
<p>
If we can show that we can construct a permutation that satisfies the
condition in the question for every positive integer n such that n
≡ 3 (mod 4) or n ≡ 0 (mod 4), then the proof would be
complete. We have two cases to deal with:
</p>
<ol>
<li>n ≡ 3 (mod 4)</li>
<li>n ≡ 0 (mod 4)</li>
</ol>
<p>
When, n ≡ 3 (mod 4), let
x = (n + 1) / 4. Partition the first n
natural numbers in 4 sequences, p<sub>1</sub>, p<sub>2</sub>,
p<sub>3</sub> and p<sub>4</sub> such that each sequence contains
x − 1 numbers and 3 single numbers a, b and c according
to the following rules. This is possible since, 4(x − 1)
+ 3 = 4x − 1 = n + 1 − 1 = n. The
partitioning rules are as follows.
<ol>
<li>a = 2x − 1</li><li>b = 4x − 2</li>
<li>c = 4x − 1</li><li>p<sub>1</sub> = Odd numbers
between 1 and a in ascending order. (1, …,
2x − 3).</li>
<li>p<sub>2</sub> = Even numbers between 1 and a in ascending order. (2,
…, 2x − 2).</li>
<li>p<sub>3</sub> = Odd numbers between a and b in ascending order.
(2x + 1, …, 4x − 3).</li>
<li>p<sub>4</sub> = Even numbers between a and b in ascending order.
(2x, …, 4x − 4).</li>
</ol>
<p>
It can be verified that the above
partitioning rules imply that the length of each partition p<sub>i</sub>
is x − 1 where 1 ≤ i ≤ 4. Also, all natural
numbers less than or equal to n are present in the 4 partitions and 3
single numbers above.
</p><p>
Let us consider an array A of size 2n. The first index of array is 1.
Now, a valid permutation can be formed with the following placement
rules.
</p>
<ol>
<li>A[1] to A[x − 1] contains reversed
p<sub>4</sub>.</li>
<li>A[x] to A[2x − 2] contains reversed
p<sub>1</sub>.</li>
<li>A[2x − 1] contains b.</li>
<li>A[2x] to A[3x − 2] contains p<sub>1</sub>.</li>
<li>A[3x − 1] contains c.</li>
<li>A[3x] to A[4x − 2] contains p<sub>4</sub>.</li>
<li>A[4x − 1] contains a.</li>
<li>A[4x] to A[5x − 2] contains reversed
p<sub>3</sub>.</li>
<li>A[5x − 1] to A[6x − 3] contains
reversed p<sub>2</sub>.</li>
<li>A[6x − 2] contains b.</li>
<li>A[6x − 1] contains a.</li>
<li>A[6x] to A[7x − 2] contains p<sub>2</sub>.</li>
<li>A[7x − 1] contains c.</li>
<li>A[7x] to A[8x − 2] contains p<sub>3</sub>.</li>
</ol>
<p>
Note that 8x − 2 = 2n. So, the
last rule can be rewritten as "A[7x] to A[2n] contains p<sub>3</sub>".
</p><p>
When n ≡ 0 (mod 4), let x = n / 4.
Partition the first natural numbers in 4 sequences, p<sub>1</sub>,
p<sub>2</sub>, p<sub>3</sub> and p<sub>4</sub> such that each sequence
contains x − 1 numbers and 4 single numbers a, b, c and
d. The partition rules contain the 7 rules discussed above and one more
rule. The additional rule is: d = 4x.
</p><p>
The placement are same for all cells in the array with one exception and
two additional rules for the two new cells.
</p>
<ol>
<li>A[4x − 1] = d. (Exception. Modifies rule 7.)</li>
<li>A[8x − 1] = a.</li>
<li>A[8x] = d.</li>
</ol>
<p>
With these rules it can be shown that two k's have k elements in
between. In other words, the difference in the array indices of the
cells where two k's are present is k + 1.
</p><p>
a = 2x − 1. The two a's are located at
A[4x − 1] and A[6x − 1]. The difference
in array indices is 2x. Hence, two a's have 2x − 1 = a
numbers in between. Similarly, this can be verified for b, c and d.
</p><p>
The two 1's are located at A[2x − 2] and A[2x]. The
difference in array indices is 2. Hence, the two 1's have 1 number in
between. From this it can be shown that for each k in p<sub>1</sub>,
there are k numbers in between. Take an arbitrary element m in
p<sub>1</sub>. From the construction rules, we see that, the two m's are
located in
A[2x − 2 − (m − 1)/2]
and A[2x + (m − 1)/2]. The difference in the indices is:
2x + (m − 1)/2 − 2x + 2 +
(m − 1)/2 = m + 1. Similarly, it can be shown that for
any k in any parition p<sub>i</sub> (1 ≤ i ≤ 4), there are k
numbers between the two k's.
</p><p>
Here is an example.
</p>
<pre>
n = 11
x = (11 + 1) / 4 = 3
a = 5
b = 10
c = 11
p1 = (1, 3)
p2 = (2, 4)
p3 = (7, 9)
p4 = (6, 8)
</p><p>
(a)
+------------+
(c) | |
+-----|------------|------+
(b) | | | |
+------|-----|----------+ | |
| | | | | |
8 6 3 1 10 1 3 11 6 8 5 9 7 4 2 10 5 2 4 11 7 9
=== === === === === === === ===
| | | | | | | |
| +------+ (p1) | | +--------+ (p2) |
+-----------------+ +-------------------+
(p4) (p3)
</pre>
<h3>Notes</h3>
<ol class="paralist">
<li>There is an entry for this problem in OEIS: <a
href="http://oeis.org/A014552">http://oeis.org/A014552</a>.</li>
<li>The internal symmetries in the permutation are not very obvious from
the proof but the permutation simply requires us to place a, b, c,
p<sub>1</sub>, p<sub>2</sub> and p<sub>3</sub> in this order:
(p<sub>4</sub>' p<sub>1</sub>' b p<sub>1</sub> c p<sub>4</sub> a
p<sub>3</sub>' p<sub>2</sub>' b a p<sub>2</sub> c p<sub>3</sub>) when n
≡ 3 (mod 4), where p<sub>i</sub>' is reversed p<sub>i</sub> (1
≤ i ≤ 4).</li>
<li>For n = 3, we get x = 1. So, length of the partitions p<sub>1</sub>,
p<sub>2</sub>, p<sub>3</sub> and p<sub>4</sub> is x − 1
= 0 each. So, rules that involve the partitions do not apply in case of
n = 3.</li>
<li>In this proof, I have shown one set of rules to construct a valid
permutation for a given n such that n ≡ 3 (mod 4) or n ≡ 0
(mod 4). But actually, I found 2 such sets of rules. The variables a, b,
c and d remain same in the other rule. Only the rules for
p<sub>1</sub>, p<sub>2</sub>, p<sub>3</sub>, p<sub>4</sub> and placement
rules differ.</li>
<li>The above two points imply that, except for n = 3, using
construction rules, we can construct at least two different permutations
for a given value of n such that n ≡ 3 (mod 4) or n ≡ 0 (mod
4).</li>
<li>It seemed like for values of n > 20, there might be over a
quadrillion possible solutions. It wasn't feasible to verify this on my
laptop with the program I wrote. When I discussed this with a person who
was interested in this problem, he asked, "What? Don't you have a
quad(rillion)-core processor?"</li>
<li>I worked through a Saturday night till 3:30 AM of the following
Sunday morning and I could prove only the necessity of the condition n
≡ 3 (mod 4) or n ≡ 0 (mod 4). When <a
href="http://anks007.blogspot.com/">a friend</a> asked me about the
progress, I could manage to say this, "Half of it. Need to prove a
'necessary and sufficient' condition. Proved the necessary part only but
this much is sufficient for me today. The sufficient part is necessary
for the proof to be complete but i think, now it has become necessary to
do the sufficient part tomorrow as it is too late already."</li>
<li>The above point reminds me of a famous quote by <a
href="http://en.wikipedia.org/wiki/George_Pólya">George Pólya</a>,
"Mathematics consists in proving the most obvious thing in the least
obvious way".</li>
<li>The above point reminds me of <a
href="http://humor.beecy.net/misc/principia/">http://humor.beecy.net/misc/principia/</a>.</li>
</ol>
</p> Sat, 17 Sep 2011 12:45:00 +0000Susam Palhttp://susam.in/blog/langford-pairing/The Orkut exploit
http://susam.in/blog/orkut-exploit/
<p>
I first came to know about Sunny Vaghela about one and a half years ago
when I got an email from <a
href="http://blogs.oracle.com/sandip/">Sandip Dev</a> of Sun
Microsystems (now acquired by Oracle).
</p>
<div class="email">
<div class="header">
<p>
<b>From:</b> "Sandip Dev"<br>
<b>To:</b> "Susam Pal"<br>
<b>Date:</b> Thu, Dec 10, 2009 12:23 AM IST<br>
<b>Subject:</b> The Orkut exploit
</p>
</div>
<div class="text">
<p>
Hi Susam,
</p><p>
I just read the Orkut exploit on your site <a
href="http://susam.in/security/advisory-2007-06-22.txt">http://susam.in/security/advisory-2007-06-22.txt</a>.
It seems this guy, Sunny Vaghela, claims this exploit to be his own (<a
href="http://sunnyvaghela.com/orkut-hacking.html">http://sunnyvaghela.com/orkut-hacking.html</a>).
He also claims that people from Google visited him (<a
href="http://www.techgoss.com/Story/227S12-Security-expert-starts-NGO-to-help-cyber-victims.aspx">http://www.techgoss.com/Story/227S12-Security-expert-starts-NGO-to-help-cyber-victims.aspx</a>).
Whats your take on this?
</p><p>
Regards,<br>
Sandip Dev
</p>
</div>
</div>
<div class="email">
<div class="header">
<p>
<b>From:</b> "Susam Pal"<br>
<b>To:</b> "Sandip Dev"<br>
<b>Date:</b> Thu, Dec 10, 2009 1:17 AM IST<br>
<b>Subject:</b> Re: The Orkut exploit<br>
</p>
</div>
<div class="text">
<p>
Hi Sandeep,
</p><p>
In our advisory, we have documented that the session management
vulnerability associated with orkut_session cookie was first reported by
Net-Square Solutions Private Limited. We published an advisory in 2007
because even though the Net-Square advisory mentioned that the
vulnerability is fixed, we found that it wasn't. So, we published the
results of our investigation and experiments.
</p><p>
The link that you have sent me doesn't mention that he claims the
exploit to be his own. I have not seen the Headline Today video on his
work. However, if he does claim that it is his own exploit, either he
has discovered the vulnerability independently and is unaware of related
work that has been done before or he is using information from the
advisories published by us and Net-Square, but claiming it to be his
own.
</p><p>
Regards,<br>
Susam Pal
</p>
</div>
</div>
<div class="email">
<div class="header">
<p>
<b>From:</b> "Sandip Dev"<br>
<b>To:</b> "Susam Pal"<br>
<b>Date:</b> Thu, Dec 10, 2009 9:29 AM IST<br>
<b>Subject:</b> Re: The Orkut exploit<br>
</p>
</div>
<div class="text">
<p>
Hi Susam,
</p><p>
He has put it under "Research" on his site and also in the interview he
says he "found" this exploit. Well I have reading up about him recently
and this came up. So I thought I would alert you. Thanks for the
response.
</p><p>
Regards,<br>
Sandip
</p>
</div>
</div>
<div class="email">
<div class="header">
<p>
<b>From:</b> "Susam Pal"<br>
<b>To:</b> "Sandip Dev"<br>
<b>Date:</b> Thu, Dec 10, 2009 10:18 AM IST<br>
<b>Subject:</b> Re: The Orkut exploit<br>
</p>
</div>
<div class="text">
<p>
Hi Sandip,
</p><p>
Thanks for the alert. I was assuming that he was talking about his work
in good faith. There is a possibility, no matter however small, that he
has discovered the vulnerability independently and he is not aware that
we have already investigated this and published advisories on it.
</p><p>
However, I understand that there is also a possibility that he is
violating our copyright on our work and claiming that the work is a
result of his own research. I don't mind it since most websites on the
web properly attribute the advisory and the investigation to me and
Vipul.
</p><p>
Thanks for the alert however. It was interesting to see an old work in
the news recently.
</p><p>
Regards,<br>
Susam Pal
</div>
</div>
<p>
A couple of days ago, I found him again at <a
href="http://attrition.org/">attrition.org</a>, a website that used to
be the largest mirror of defaced websites.
</p><p>
Sunny Vaghela has found a place in attrition.org's <a
href="http://attrition.org/errata/charlatan/">charlatans</a> <a
href="http://attrition.org/errata/charlatan/watch_list/">watch list</a>:
<a
href="http://attrition.org/errata/charlatan/watch_list/sunny_vaghela/orkut-claims.html">Sunny
Vaghela: Claims of Orkut Vulnerability Research</a>. He is the third
Indian to get into this list after <a
href="http://attrition.org/errata/charlatan/ankit_fadia/">Ankit
Fadia</a> and <a
href="http://attrition.org/errata/charlatan/watch_list/sahil_khan/hackers_and_crackers.html">Sahil
Khan</a>.
</p> Sat, 25 Jun 2011 11:03:00 +0000Susam Palhttp://susam.in/blog/orkut-exploit/URLs in C
http://susam.in/blog/urls-in-c/
<p>
Here is a C puzzle I like to ask my friends and colleagues. It is one of
those silly puzzles that may bring a smile on your face if you aren't
able to figure it out immediately.
</p>
<pre class="code">
#include <stdio.h>
int main()
{
http://susam.in/
printf("hello, world\n");
return 0;
}
</pre>
<p>
This code compiles and runs successfully even though the <a
href="http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf">current
draft of the C99 standard</a> doesn't mention anywhere that URLs are
valid syntactic elements in C. How does this code work then?
</p> Fri, 03 Jun 2011 10:13:00 +0000Susam Palhttp://susam.in/blog/urls-in-c/Infosys, TCS, or Wipro?
http://susam.in/blog/infosys-tcs-or-wipro/
<p>
Sometimes computer science, IT or electronic and communication
engineering students get placed in two or three major Indian IT
companies and they find it hard to decide which one to join. "Infosys,
TCS, or Wipro?" is one of the most common questions I have faced from such
students. The answer is much simpler than they think it is.
</p><p>
"None."
</p><p id="what-this-post-is-not">
This blog post is not about how these companies are large employers
creating a lot of jobs in the market. I acknowledge their efforts. This
blog post is not about undermining the efforts of these companies. They
are probably good at keeping their customers happy.
</p><p>
This blog post is about a choice that freshers usually have to make and
the information they should have before they make the choice. This blog
post is about urging the freshers who want to make a career in
engineering to not make a mistake that I did because I did not have the
necessary information at the right time; a mistake that I could correct
two years later after I realized it. This blog post is about some very
unpleasant facts about these major Indian IT companies that you wouldn't
know unless you have been a part of it.
</p>
<p>
With the above disclaimer out the way, let me start.
</p>
<ol class="paralist">
<li>
<b>Training:</b> People think that these organizations are good for
freshers because they get a lot of training which they wouldn't get in
other organizations. I must remind such people that attending training
programmes is not equivalent to learning. Indeed these organizations
provide a lot of training to freshers but only about 1% of the trainees
actually absorb the knowledge. The 1% that do absorb the training do not
stick to the organization for a long time because sooner or later they
realize that they want to do some real engineering. The figure '1%'
isn't merely a guess. This is my observation across various
trainee-batches that have been trained in one of these organizations.
Think about it. Can you learn a new programming language in just 3
days? If your answer is "no", you shouldn't join one of these
organizations. If your answer is "yes", you shouldn't join one of these
organizations.
</li><li>
<b>Engineering:</b> One can find engineering
problems in these organizations but no trace of engineering. This is
mainly due to poor guidance, high attrition rate of good engineers, and
a general lack of engineering culture. The next point elaborates
this further.
</li><li>
<b>Engineers:</b> The number of engineers in these organizations are
very very few; perhaps only 1 in every 200 is an engineer. This is a
guess, albeit not a wild one. This is why there is no engineering in
these companies despite the presence of engineering problems. "But isn't
the minimum qualification to get a job in one of these organizations
bachelor's of engineering?", you might ask. It is. Yes, all of them
have a degree in engineering or computers of some sort but only about 1
out of 200 is an engineer. The rest 199 do not understand why a bitcount
of A XOR B would give you the number of similar bits in corresponding
positions in both variables, why one can not create a POSIX compliant
regular expression to match only strings with balanced parentheses, or
how to find the shortest chain of connections between two friends in a
social network. Note that I have used 'or' as the conjunction and not
'and'. Now you might wonder why one should know these little things when
most of the things are done by libraries these days. I think such
attitude is dangerous in the world of software development especially
when robustness and security are concerns. Good understanding of
fundamentals leads to optimal and robust solutions.
</li><li>
<b>Culture:</b>
One of the worst cultures you can find in the whole of software
industry. Very few are busy trying to learn a few things mentioned in
the previous paragraph. Some employees are busy figuring out ways to
impress their female colleagues using the resources provided by the
organization rather than learning and solving problems in better ways.
Others are busy cribbing. Here is a shocking piece of information for
those who have never worked for one of these organizations. One can also
manage to find mud-slinging in company forums once in a while.
Professionalism is at its worst here.
</li>
<li>
<b>Onsite:</b> Contrary to the popular belief, the number of trips to
foreign lands isn't a measure of one's technical prowess. Onsite
opportunities depend on a variety of factors including the department
you are working in, the nature of work, etc.
</li>
</ol>
<p id="suggestion">
So, my answer to the question "Infosys, TCS, or Wipro?" is "None."
That's not very helpful. Here is a more helpful one. One can consider
applying for a job in an organization where he or she can get an
opportunity to solve some engineering problems. One cannot learn
engineering and programming merely by attending trainings. One has to
learn it by doing, solving problems, observing what experienced
engineers do, experimenting, screwing up a few times and reworking,
talking to good engineers, etc. One can try looking for an organization
where the leaders of projects are very good engineers. Start-ups are
more likely to have them. Some matured ones are
<a href="http://www.gluster.com/">Gluster</a>,
<a href="http://www.parallocity.com/">Parallocity</a>,
<a href="http://www.slideshare.net/">SlideShare</a>, etc. New start-ups
come up every year. Software companies which develop famous and
successful products are more likely to have them. Some good examples are
<a href="http://www.adobe.com/">Adobe</a>,
<a href="http://www.amazon.com/">Amazon</a>,
<a href="http://www.google.com/">Google</a>,
<a href="http://www.phoenix.com/">Phoenix</a>,
etc. So, how does one
figure whether a certain organization is an organization of engineers or
an organization of good software users?
</p><p>
The clue is: Interview.
</p><p>
Remember the questions they ask in the interview. Think about them
later. Try discussing the questions with your friends who are known for
solving tough engineering problems. An interview is not only an
opportunity for an organization to evaluate an applicant, it is also an
opportunity for the applicant to evaluate an organization.
</p>
<p class="update">
<b>Update:</b> October 28, 2011: This post got way more attention
than I wanted. It was discussed and debated <a
href="http://hackerstreet.in/item?id=6323">at</a> <a
href="http://news.ycombinator.com/item?id=2628318">various</a> <a
href="http://www.reddit.com/r/india/comments/lqemo/why_a_fresher_should_not_join_infosys_tcs_or_wipro/">places</a>
on the web. As a result, here is a follow-up post: <a
href="/blog/re-infosys-tcs-or-wipro/">Re: Infosys, TCS, or Wipro?</a>
</p> Sun, 15 May 2011 08:45:00 +0000Susam Palhttp://susam.in/blog/infosys-tcs-or-wipro/A surprise test
http://susam.in/blog/surprise-test/
<p>
I was studying in the 1st standard. Our science teacher gave us a
surprise test. I tried to answer all questions correctly. After the
corrected notebooks were returned, I found that the teacher had
incorrectly marked one of my answers as incorrect. I was sure that I was
correct. So, I showed it to the girl sitting next to me and declared
innocently, "This answer is correct. But she doesn't know. She is
stupid."
</p><p>
When she went to collect her notebook, she informed the teacher about
what I had just said. The teacher was offended and asked me to stand
outside the class. Our principal was passing through the corridor and
she was surprised to see me standing outside. She asked what I did and I
said that I called our teacher stupid. She asked me to apologize.
</p><p>
I didn't know how to do that. I started recollecting from Hindi movies.
The villian would fall at someone's feet and cry, "Mujhe maaf kar do.
Please, mujhe maaf kar do."<sup><a href="#translate">[*]</a></sup> I
thought, "I can't do this. I can't fall at her feet. That would be very
embarrassing. I said that she was stupid and I was right. Why should I
fall at her feet?" I refused to apologize, inspite of repeated warnings
and requests. I was simply not ready to fall at her feet and do the
drama.
</p><p>
The matter escalated and I was asked to leave that place. I was taken to
the reception area. I was not allowed to attend any classes. I sat there
crying the whole day. Visitors came and enquired why I was crying. I
explained. Before the final bell rang, a complaint was registered in my
diary and my parents were asked to meet the principal next day.
</p><p>
The next day, my parents met the principal. Thankfully, it went well.
She explained how she was impressed with my innocence and honesty. It
seemed as if she had called my parents only to praise me. I grew up to
be wiser and humbler. Now, I understand that falling at someone's feet
is not the only way to apologize.
</p><p>
<small>[*] <a name="translate" id="translate">Translated to English:
"Forgive me. Please, forgive me."</a></small>
</p> Sun, 08 May 2011 08:46:00 +0000Susam Palhttp://susam.in/blog/surprise-test/From out shuffles to multiplicative order
http://susam.in/blog/from-out-shuffles-to-multiplicative-order/
<p>
A colleague asked this problem.
<div class="problem">
A perfect riffle shuffle or bridge shuffle is when we split a deck of
cards into two halves (one in each hand), and then alternately drop one
card from each half till all have fallen. For the sake of this problem,
let us assume that the top card will always be the top card and the
bottom card will always be the bottom card after shuffling. However the
rest of the cards will be deranged.
</p><p>
How many such riffle shuffles do we need to perform on a deck of 52
cards, in order to obtain the exact same starting order?
</div>
Such a style of shuffling is also known as <em>out shuffle</em>.
</p><p>
Let us assume that there are 2n cards where n is a positive integer. Let
us number the positions of the cards as
0, 1, … 2n − 1 where position 0 is
the top of the deck and position 2n − 1 is the bottom of the deck.
Here is an example with 10 cards called c<sub>0</sub>, c<sub>1</sub>,
… c<sub>9</sub> with positions indicated in the first column.
<pre>
0. c<sub>0</sub> c<sub>0</sub>
1. c<sub>1</sub> c<sub>5</sub>
2. c<sub>2</sub> c<sub>1</sub>
3. c<sub>3</sub> c<sub>6</sub>
4. c<sub>4</sub> ———> Shuffling ———> c<sub>2</sub>
5. c<sub>5</sub> c<sub>7</sub>
6. c<sub>6</sub> c<sub>3</sub>
7. c<sub>7</sub> c<sub>8</sub>
8. c<sub>8</sub> c<sub>4</sub>
9. c<sub>9</sub> c<sub>9</sub>
</pre>
Let us consider a card at position k where 0 ≤ k < 2n. It is easy
to see from the description of the problem that a card at position k
moves to position 2k if the card belongs to the top half of the deck,
otherwise it moves to 2(k − n) + 1.
</p><p>
2(k − n) + 1 ≡ 2k − (2n − 1) ≡ 2k (mod 2n
− 1)
</p><p>
So, we can say that a card at position k moves to position k' ≡ 2k
mod (2n − 1) after an out shuffle where 0 ≤ k' < 2n.
</p><p>
So, after m shuffles a card at position k moves to position k` ≡
2<sup>m</sup> · k (mod 2n − 1) where 0 ≤ k` < 2n. So,
we are looking for the smallest positive integer m such that for all
integers k, where 0 ≤ k < 2n,
</p><p>
2<sup>m</sup> · k ≡ k (mod 2n − 1)
</p><p>
Removing k from both sides we get
</p><p>
2<sup>m</sup> ≡ 1 (mod
<sup>(2n−1)</sup>⁄<sub>gcd(k, 2n−1)</sub>)
</p><p>
For simplicity, let us represent
<sup>(2n−1)</sup>⁄<sub>gcd(k, 2n−1)</sub>) as
F<sub>nk</sub>. So, a card at position k returns to the same position
after m out shuffles where m is the smallest positive integer that
satisfies the congruence relation
</p><p>
2<sup>m</sup> ≡ 1 (mod F<sub>nk</sub>)
</p><p>
Since 2n − 1 is odd, F<sub>nk</sub> must be odd. So, gcd(2,
F<sub>nk</sub>) = 1. The smallest positive integer m that satisfies the
congruence relation above is known as the multiplicative order of 2
modulo F<sub>nk</sub> and is denoted as ord<sub>F<sub>nk</sub></sub>(2).
</p><p>
If n = 1, F<sub>nk</sub> = 1 and 2<sup>m</sup> ≡ 1 (mod
F<sub>nk</sub>) is true for all positive integers m. So, with two cards,
an out shuffle doesn't change the positions of the cards.
</p><p>
If n > 2, let us consider a k which is coprime to 2n − 1 and 1
< k < 2n − 1. There exists at least one such k because
φ(x) ≥ 2 for x > 2 where φ(x) is the Euler's totient of a
positive integer x which is defined as the number of positive integers
less than or equal to x that are coprime to x. Now, gcd(k, 2n − 1)
= 1. So, now the congruence relation
</p><p>
2<sup>m</sup> ≡ 1 (mod
<sup>(2n−1)</sup>⁄<sub>gcd(k, 2n−1)</sub>)
</p><p>
reduces to
</p><p>
2<sup>m</sup> ≡ 1 (mod 2n − 1)
</p><p>
So, far we understand that after ord<sub>2n−1</sub>(2) out
shuffles, any card at a position number coprime to
2n − 1 would be back to its original position. What
about cards at other positions?
</p><p>
For a card at position k such that k is not coprime to 2n − 1,
gcd(k, 2n − 1) ≠ 1. In this case the number of out shuffles
required to bring the card at its original position is
ord<sub>F<sub>nk</sub></sub>2.
</p><p>
2<sup>ord<sub>2n−1</sub>(2)</sup> ≡ 1 (mod 2n − 1)
⇒ 2<sup>ord<sub>2n−1</sub>(2)</sup> ≡ 1 (mod
F<sub>nk</sub>) … (since F<sub>nk</sub> | 2n − 1)
</p><p>
As a consequence of Lagrange's theorem, ord<sub>F<sub>nk</sub></sub>(2)
| ord<sub>2n−1</sub>(2).
</p><p>
In other words, ord<sub>2n−1</sub>(2) = c ·
ord<sub>F<sub>nk</sub></sub>(2) for some positive integer c.
</p><p>
So, performing ord<sub>2n−1</sub>(2) out shuffles is same as
repeating ord<sub>F<sub>nk</sub></sub>(2) out shuffles c times. Every
ord<sub>F<sub>nk</sub></sub>(2) shuffles brings back the card at
position k to the same position. So, repeating it c times would leave it
at the same position as well.
</p><p>
Hence, we conclude that <em>ord<sub>2n−1</sub>(2) out shuffles
would restore a deck of 2n cards to its original configuration, where n
is a positive integer.</em>
</p><p>
For a deck of 52 cards, n = 26. So, ord<sub>51</sub>(2) out shuffles
would restore the deck to its original configuration.
</p><p>
Let us compute ord<sub>51</sub>(2).
</p><p>
From Carmichael's theorem, 2<sup>λ(51)</sup> ≡ 1 (mod 51),
where λ(n) is the smallest positive integer m such that
a<sup>m</sup> ≡ 1 (mod n) for every positive integer a coprime to
and smaller than n.
</p><p>
λ(51) = lcm(λ(3), λ(17)) = lcm(2, 16) = 16.
</p><p>
Again as a consequence of Lagrange's theorem, ord<sub>51</sub>(2) |
λ(51). In other words, ord<sub>51</sub>(2) | 16.
</p><p>
Let us check all the factors of 16 and see which one is the
multiplicative order of 2 modulo 51.
</p><p>
2<sup>2</sup> ≡ 4 (mod 51)
2<sup>4</sup> ≡ 16 (mod 51)
2<sup>8</sup> ≡ 256 ≡ 1 (mod 51).
</p><p>
∴ ord<sub>51</sub>(2) = 8.
</p><p>
8 is the answer.
</p> Wed, 23 Mar 2011 04:05:00 +0000Susam Palhttp://susam.in/blog/from-out-shuffles-to-multiplicative-order/Listening to superimposed waves
http://susam.in/blog/listening-to-superimposed-waves/
<p>
Let me share a little experiment I did last night. Listen to the
following audio first. This plays a sine wave of 500 Hz for 2 seconds
followed by another sine wave of 500.1 Hz for 2 more seconds. You can
hear a tick after each second. The 500.1 Hz sine wave starts at the
second tick.
</p><p>
<div style="text-align: center"><audio tabindex="0" controls="controls">
<source
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz-sequenced.mp3"
type="audio/mpeg">
<source
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz-sequenced.ogg"
type="audio/ogg">
<embed
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz-sequenced.mp3"
type="audio/mpeg" autostart="false" loop="false" height="45"></embed>
</audio><br>
<small><a
href="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz-sequenced.mp3">Download
500Hz-500point1Hz-sequenced.mp3</a></small>
</div>
<p>
Could you notice any difference in the pitch of the two tones? The
difference in the frequencies is so small that you wouldn't be able to
notice it by hearing.
</p><p>
Now, let us see what happens when we superimpose both the waves and
listen to it.
</p><p>
<div style="text-align: center"><audio tabindex="0" controls="controls">
<source
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz.mp3"
type="audio/mpeg">
<source
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz.ogg"
type="audio/ogg">
<embed
src="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz.mp3"
type="audio/mpeg" autostart="false" loop="false" height="45"></embed>
</audio>
<br>
<small><a
href="http://susam.in/downloads/files/500Hz-500point1Hz/500Hz-500point1Hz.mp3">Download
500Hz-500point1Hz.mp3</a></small>
</div>
<p>
You would notice that the loudness decreases rapidly at about 5 seconds
and then returns to full volume by 10 seconds, decreases rapidly again
at 10 seconds and returns to full volume by 15 seconds and so on. In
other words, the loudness decreases every 10 seconds.
</p><p>
Let us see why this happens from the graph of the waves. The first wave
can be represented with the function
f(t) = 0.4 sin (2π · 500 · t)
and the second one with
g(t) = 0.4 sin (2π · 500.1 · t)
</p><p>
<div class="separator" style="clear: both; text-align: center;"><img
src="http://2.bp.blogspot.com/_CihYmKJVITc/TUngVRlppQI/AAAAAAAAA4s/c9YAJiFWqJY/separate-waves-in-phase.png"
/>
</div>
<p>
At t = 0 seconds, both the waves look very similar. The crests and
troughs of both the waves appear almost simultaneously. On
superposition, the amplitude almost doubles. The graph of the
superimposed waves is shown below. Note that the amplitude of each wave
in the figure above is 0.4 while that of superimposed waves is almost
0.8 as can be seen below. In fact, it is exactly 0.8 at t = 0 seconds
and then gradually decreases in the region 0 < t < 5.
</p><p>
<div class="separator" style="clear: both; text-align: center;"><img
src="http://3.bp.blogspot.com/_CihYmKJVITc/TUrF3c1VveI/AAAAAAAAA5s/9FgfwGxU8Uw/superimposed-waves-in-phase.png"
/></div>
<p>
The time period of the second wave is slightly shorter than the first
one as the frequency of the second wave is slightly greater than the
first one. So, the two waves are not identical. In fact, the second wave
looks like a very slightly compressed form of the first wave. At about t
= 5 seconds, the difference is obvious.
</p><p>
<div class="separator" style="clear: both; text-align: center;"><img
src="http://3.bp.blogspot.com/_CihYmKJVITc/TUq0E6hjMKI/AAAAAAAAA5g/dQOls49pgLw/separate-waves-out-of-phase.png"
/></div>
<p>
The crests and troughs of both the waves do not appear simultaneously at
around t = 5 seconds. In fact, the crest of one wave and the trough of
the other wave appear simultaneously. This cancels out each other on
superposition and thus the resultant wave has almost no amplitude at
this time.
</p><p>
<div class="separator" style="clear: both; text-align: center;"><img
src="http://1.bp.blogspot.com/_CihYmKJVITc/TUngWbfMa9I/AAAAAAAAA5E/fs_J8spSYgQ/superimposed-waves-out-of-phase.png"
/></div>
<p>
The amplitude is exactly 0 at t = 5 seconds and it increases gradually
till t = 10 seconds. At t = 10 seconds, the amplitude becomes 0.8 again
and then starts decreasing till t = 15 seconds when it becomes 0 again.
This cycle continues. This can be seen in the graph of the superimposed
waves given below.
</p><p>
<div class="separator" style="clear: both; text-align: center;"><img
src="http://3.bp.blogspot.com/_CihYmKJVITc/TUngWoWVNKI/AAAAAAAAA5M/zLQTybaKdms/superimposed-waves.png"
/></div>
<p>
Let us understand this mathematically. Let us represent both the sine
waves with the functions: y<sub>1</sub> = A sin 2πft and
y<sub>2</sub> = A sin 2π(f + Δf)t, where A is the amplitude of
the waves, and f and f + Δf are the frequency of the two waves.
</p><p>
So, the superimposed waves can be represented as
</p><p>
y<sub>1</sub> + y<sub>2</sub>
</p><p>
= A sin 2πft + A sin 2π(f + Δf)t
</p><p>
= (2A cos 2π · <sup>Δf</sup>⁄<sub>2</sub> ·
t) sin 2π(f + <sup>Δf</sup>⁄<sub>2</sub>)t
</p><p>
To understand this function intuitively, imagine it as a sine wave with
a frequency of f + <sup>Δf</sup>⁄<sub>2</sub> and an
amplitude of
2A cos 2π · <sup>Δf</sup>⁄<sub>2</sub> · t.
In our case, f + <sup>Δf</sup>⁄<sub>2</sub> = 500.5 Hz. So,
the superimposed waves look like a sine wave with a frequency of 500.5
Hz but with its amplitude varying with time at a frequency of
<sup>Δf</sup>⁄<sub>2</sub>. In other words, the amplitude
oscillates between 0 and 2A every <sup>1</sup>⁄<sub>Δf</sub>
seconds. Since Δf = 0.1 Hz and A = 0.4 in our case, we see that
the amplitude of the 500.5 Hz sine wave oscillates between 0 and 0.8
every 10 seconds.
</p> Thu, 03 Feb 2011 01:32:00 +0000Susam Palhttp://susam.in/blog/listening-to-superimposed-waves/Flowers
http://susam.in/blog/flowers/
<p>
<a href="http://www.youtube.com/watch?v=eOI6Jwx21eE">Flowers</a> is my
third attempt at composing music. I composed, played and recorded it
last year but I scribbled it down and prepared the sheet music today.
Hence, this blog post today.
</p><p>
The links to the audio files, sheet music, etc. are provided below. The
files reside in my website. In case, my website is down, the YouTube
link provided below should still work.
</p><p>
This piece consists of 161 measures. It is approximately 3 minutes 8
seconds long.
</p> <div id="flowers" class="music"> <!-- Audio -->
<audio controls="controls" preload="none">
<source src="/files/music/flowers/flowers.mp3" type="audio/mpeg"></source>
<source src="/files/music/flowers/flowers.ogg" type="audio/ogg"></source>
</audio>
<div class="links">
<!-- MP3 -->
<a href="/files/music/flowers/flowers.mp3"><img style="position: relative; top: 3px"
title="Download audio in MP3 format"
src="/images/audio.png"></a>
<a href="/files/music/flowers/flowers.mp3" title="Download audio in MP3 format">MP3</a>
<span class="separator">|</span>
<!-- OGG -->
<a href="/files/music/flowers/flowers.ogg"><img style="position: relative; top: 3px"
title="Download audio in OGG Vorbis format"
src="/images/audio.png"></a>
<a href="/files/music/flowers/flowers.ogg" title="Download audio in OGG Vorbis format">OGG</a>
<span class="separator">|</span>
<!-- Youtube -->
<a href="http://www.youtube.com/watch?v=eOI6Jwx21eE"><img style="position: relative; top: 2px"
title="Listen to 'Flowers' on YouTube"
src="/images/youtube.png"></a>
<a href="http://www.youtube.com/watch?v=eOI6Jwx21eE" title="Listen to 'Flowers' on YouTube">YouTube</a>
<span class="separator">|</span>
<!-- Score -->
<a href="/files/music/flowers/flowers.pdf"><img style="position: relative; top: 5px"
height="22px"
title="PDF sheet music for 'Flowers'"
src="/images/gclef.png"></a>
<a href="/files/music/flowers/flowers.pdf" title="PDF sheet music for 'Flowers'">Score</a>
<span class="separator">|</span>
<!-- LilyPond -->
<a href="/files/music/flowers/flowers.ly"><img style="position: relative; top: 5px"
width="22px"
title="LilyPond source for PDF sheet music"
src="/images/lilypond.gif"></a>
<a href="/files/music/flowers/flowers.ly" title="LilyPond source for PDF sheet music">LilyPond</a> </div> <!-- End of links -->
</div> <!-- End of music --><p>
This piece of music embodies love, peace and joy. After I composed the
first few notes and played it, someone told me that the notes bring an
image of flowers in the mind. Most of the music emerged naturally from
my mind. Some of the bass notes did not come out naturally and I decided
them, quite artificially, to fill the music with a pleasant and peaceful
mood. It took me a couple of days to compose this. I played and recorded
this after a day of practice.
</p> Sat, 22 Jan 2011 23:48:00 +0000Susam Palhttp://susam.in/blog/flowers/A hidden form and Fermat's Last Theorem
http://susam.in/blog/hidden-form-and-fermats-last-theorem/
<p>
Here is a problem I made one night for my friends who love to solve
mathematical puzzles.
</p>
<div class="problem">
Find all integer solutions for the equation: y<sup>2</sup> + 3 =
<sup>x<sup>3</sup></sup>⁄<sub>18</sub>.</div>
<p>
You might want to stop here and think for a while if you want to solve
this yourself. There are spoilers ahead.
</p>
<p>
In this problem, I have hidden a Diophantine equation of the form
a<sup>n</sup> + b<sup>n</sup> = c<sup>n</sup>. The first clue to this
hidden form might be the equation with its terms rearranged.
</p><p class="math">
x<sup>3</sup> = 18y<sup>2</sup> + 54
</p><p>
The right hand side is 2(9y<sup>2</sup> + 3<sup>3</sup>). This is of
the form 2(3a<sup>2</sup>b + b<sup>3</sup>) which is equal to (a +
b)<sup>3</sup> − (a − b)<sup>3</sup>. Now, the hidden form
must be clear. So, let me write down the solution to this problem
neatly.
</p><p class="math">
y<sup>2</sup> + 3 = <sup>x<sup>3</sup></sup>⁄<sub>18</sub><br>
⇒ x<sup>3</sup> = 18y<sup>2</sup> + 54<br>
⇒ x<sup>3</sup> = (y + 3)<sup>3</sup> − (y −
3)<sup>3</sup><br>
⇒ x<sup>3</sup> + (y − 3)<sup>3</sup> = (y + 3)<sup>3</sup>
</p><p>
From Fermat's last theorem, we know that an equation of the form,
a<sup>n</sup> + b<sup>n</sup> = c<sup>n</sup> has got a trivial solution
a = b = 0 and no other solutions for positive integers a, b and c when n
> 2. Now, let us examine x<sup>3</sup> + (y − 3)<sup>3</sup> =
(y + 3)<sup>3</sup> with the help of Fermat's Last Theorem. A trivial
solution in this case is ruled out because there is no value of y for
which y − 3 = y + 3 = 0.
</p><p>
However, if we consider y − 3 = 0, or y = 3, we get an equation
that is no longer of the form required by Fermat's Last Theorem.
</p><p class="math">
x<sup>3</sup> = 6<sup>3</sup><br>
⇒ x = 6
</p><p>
If we consider y + 3 = 0, or y = −3, again we get
</p><p class="math">
x<sup>3</sup> + (−6)<sup>3</sup> = 0<br>
⇒ x = 6.
</p><p>
Hence, the integral solutions to the equation are:
</p><p class="math">
x = 6<br>
y = ±3
</p> Wed, 12 Jan 2011 10:12:00 +0000Susam Palhttp://susam.in/blog/hidden-form-and-fermats-last-theorem/Squaring numbers with 5 at ends
http://susam.in/blog/squaring-numbers-with-5-at-ends/
<p>
In this post, I'll discuss some simple tricks I use to square numbers
that begin or end with the digit 5. Let me illustrate each trick with
two examples for 2-digit numbers. Later, in this post, I'll generalize
the trick for n-digit numbers where n ≥ 2 after explaining why the
tricks work using algebra.
</p><p>
<span class="leader">Squaring a 2-digit number that ends with 5</span>
</p><p>
I learnt this from a book when I was in 5th standard. For a 2-digit
number that ends with 5, let us assume that the first digit is A. So,
the number can be written as A5. The square is: A × (A + 1)
followed by 25, i.e. the first few digits of the square is given by A
× (A + 1) and the last two digits are 25. Let us try some
examples.
</p><p>
25<sup>2</sup> = 625. (2 × 3 = 6.)
85<sup>2</sup> = 7225. (8 × 9 = 72.)
</p><p>
<span class="leader">Squaring a 2-digit number that begins with 5</span>
</p><p>
After learning that trick from the book, I wondered if I could make more
tricks for myself. This is the first one I could come up with. If the
first digit of a 2-digit number is 5 and the second digit is A, i.e. if
the number is of the form 5A, the square is given by the sum of 25 and A
followed by square of A. In other words, the first two digits of the
square are obtained from 25 + A and the last two digits are obtained
from A<sup>2</sup>. Let us try some examples.
</p><p>
52<sup>2</sup> = 2704. (25 + 2 = 27 and 2<sup>2</sup> = 4.)
57<sup>2</sup> = 3249. (25 + 7 = 32 and 7<sup>2</sup> = 49.)
</p><p>
<span class="leader">Squaring an n-digit number that ends with 5</span>
</p><p>
Let us represent all digits except the last one as A. So, the number is
of the form A5 where A represents one or more digits. e.g. if the number
is 115, A = 11.
</p><p>
So, we can say that the number of the form A5 can be algebraically
expressed as 10A + 5. Now, (10A + 5)<sup>2</sup> = 100A<sup>2</sup> +
100A + 25 = 100A(A + 1) + 25. This amounts to writing A(A + 1) followed
by 25.
</p><p>
Let us try some examples:
</p><p>
115<sup>2</sup> = 13225. (11 × 12 = 132.)
9995<sup>2</sup> = 99900025. (999 × 1000 = 999000.)
</p><p>
<span class="leader">Squaring an n-digit number that begins with
5</span>.
</p><p>
Let us represent all digits except the first one as A. So the number is
of the form 5A where A represents one or more digits. e.g. if the number
is 512, A = 12.
</p><p>
So, we can say that the number of the form 5A can be algebraically
expressed as 5 × 10<sup>n</sup> + A where n is the number of digits
in A, i.e. the number of digits after the first digit which is 5. Now,
(5 × 10<sup>n</sup> + A)<sup>2</sup> = 25 × 10<sup>2n</sup> +
10<sup>n + 1</sup>A + A<sup>2</sup>. This amounts to writing 25 as the
first two digits followed by A<sup>2</sup> as the last 2n digits and
then adding A to it by placing it just below the second digit which is
5. Some examples follow.
</p><p>
502<sup>2</sup>
<pre style="color: black; margin: 0">= 250004 (2<sup>2</sup> = 4.)
+02 (02 placed under 5.)
---------
252004
---------
</pre>
512<sup>2</sup>
<pre style="color: black; margin: 0">= 250144 (12<sup>2</sup> = 144.)
+12 (12 placed under 5.)
---------
262144
---------
</pre>
<span class="leader">Using both tricks together</span>
</p><p>
5195<sup>2</sup>
<pre style="color: black; margin: 0">= 25038025 (195<sup>2</sup> =
38025; 19 × 20 = 380.)
+195 (195 placed under 5.)
-----------
26988025
-----------
</pre>
Note that in the problem above, we use the second trick to square 5195
because it begins with the digit 5. However, while doing so, we need to
figure the square of 195 and we use the first trick to do this.
</p> Tue, 21 Dec 2010 05:03:00 +0000Susam Palhttp://susam.in/blog/squaring-numbers-with-5-at-ends/π PM
http://susam.in/blog/pi-pm/
<p>
For so long, I have been wishing "Happy Pi PM" to my friends and
colleagues at 3:14 PM. However, this doesn't seem to be appropriate
since 3:14 PM is not really 3.14 PM. In fact, 3:14 PM is
3<sup>14</sup>⁄<sub>60</sub> PM which when expressed in decimal
representation turns out to be 3.23333 PM, accurate up to 5 decimal
places.
</p><p>
The value of π accurate up to 5 decimal places is 3.14159. Now,
.14159 hour = 509.724 seconds ≈ 8 minutes and 30 seconds, or
8½ minutes.
</p><p>
So, π PM turns out be 3:08:30 PM or 8½ minutes past 3 PM.
</p> Mon, 20 Dec 2010 09:38:00 +0000Susam Palhttp://susam.in/blog/pi-pm/Belated birthday
http://susam.in/blog/belated-birthday/
<p>
BELATED BIRTHDAY
</p><p>
All days come but once in annum,<br>
Amongst them all very special are few,<br>
Amongst the few you love the most is one,<br>
The day when the world got you.<br>
</p><p>
You celebrate the day you're born<br>
And want your chums to be near.<br>
I regret that I left you lorn,<br>
Hope you pardon me, O dear!<br>
</p><p>
Shamelessly I wish you, 'A belated very happy birthday'.<br>
Though I know, now it is very late;<br>
But I swear, I didn't forget your birthday<br>
I just forgot the date.<br>
</p> Wed, 01 Dec 2010 05:09:00 +0000Susam Palhttp://susam.in/blog/belated-birthday/Clumsy pointers
http://susam.in/blog/clumsy-pointers/
<p>
Here is a silly puzzle I solved exactly one month ago.
<div class="problem">
Without using <code>typedef</code>, declare a pointer to a function
which has an array of 10 pointers to functions which have int * argument
and return type void as argument, and returns a pointer to a function
which has int * argument and return type void.</div>
<p>
If the above problem statement is difficult to understand, here is the
same problem expressed in terms of <code>typedef</code>.
</p>
<div class="problem">
Without using <code>typedef</code>, declare a pointer that is equivalent
to the following declaration of <code>x</code>.
</p><pre>
typedef void (*func_t)(int *);
func_t (*x)(func_t [10]);
</pre>
</div>
<p>
I'll describe how I solve such problems. I start from the right end of
the problem and work my way to the left most end defining each part one
by one.
</p><p>
Let me start.
<div style="text-align: center"><b><code>void x(int *)</code></b><br>
A function which has int * argument and return type void.
</p><p>
<b><code>void (*x)(int *)</code></b><br>
Pointer to a function which has int * argument and return type void.
</p><p>
<b><code>void (*x())(int *)</code></b><br>
A function that returns a pointer to a function which has int * argument
and return type void.
</p><p>
<b><code>void (*x(void (*)(int *)))(int *)</code></b><br>
A function which has a pointer to a function that has int * argument and
return type void as argument, and returns a pointer to a function which
has int * argument and return type void.
</p><p>
<b><code>void (*x(void (*[10])(int *)))(int *)</code></b><br>
A function which has an array of 10 pointers to functions that has int *
argument and return type void as argument, and returns a pointer to a
function which has int * argument and return type void.
</p><p>
<b><code>void (*(*x)(void (*[10])(int *)))(int *)</code></b><br>
A pointer to a function which has an array of 10 pointers to functions
that has int * argument and return type void as argument, and returns a
pointer to a function which has int * argument and return type void.
</div>
<p>
I verified the declaration with a short code.
</p>
<pre class="code">
#include <stdio.h>
/* A function which has int * argument and return type void. */
void g(int *a)
{
printf("g(): a = %d\n", *a);
}
/* A function which has an array of 10 pointers to functions that has
* int * argument and return type void as argument, and returns a
* pointer to a function which has int * argument and return type void.
*/
void (*f(void (*a[10])(int *)))(int *)
{
int i;
for (i = 0; i < 10; i++)
a[i](&i);
return g;
}
int main()
{
/* An array of 10 pointers to functions that has int * argument and
* return type void. */
void (*a[10])(int *) = {g, g, g, g, g, g, g, g, g, g};
/* A pointer to the function which has an array of 10 pointers to
* functions that has int * argument and return type void as
* argument, and returns a pointer to a function which has int *
* argument and return type void. */
void (*(*x)(void (*[10])(int *)))(int *) = f;
/* A pointer to a function that has int * argument and return type
* void. */
void (*y)(int *a) = x(a);
int i = 10;
y(&i);
return 0;
}
</pre>
<p>
Section 5.12 (Complicated Declarations) of the second edition of <a
class="title"
href="http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628">The
C Programming Language</a> by <span class="author">Brian W.
Kernighan</span> and <span class="author">Dennis M. Ritchie</span> has
some good examples of complicated declarations of pointers although they
are less clumsy than the one in this blog post. Let me mention a couple
of interesting ones from that section.
</p><p>
<b><code>char (*(*x())[])()</code></b><br>
x: function returning pointer to array[] of pointer to function
returning char.
</p><p>
<b><code>char (*(*x[3])())[5]</code></b><br>
x: array[3] of pointer to function returning pointer to array[5] of
char.
</p> Mon, 29 Nov 2010 14:27:00 +0000Susam Palhttp://susam.in/blog/clumsy-pointers/