Lost solutions

Let me start this post with a simple equation.

x(x − 2) = 3x

Let us solve it in a particular manner.

Dividing both sides by x we get

x − 2 = 3

Adding 2 to both sides we get

x = 5

Indeed, x = 5 is a solution to this equation. When we substitute x with 5 in the equation we get 15 on both sides. However, when we solved the equation in this manner, we lost one solution, x = 0. If we substitute x with 0, the equation still holds good as we get 0 on both sides.

Why did we lose this solution?

We lost this solution in the step where we divided both sides by x. In doing so, we made the wrong assumption that x ≠ 0. If the possibility of x = 0 is allowed, then we can not divide both sides by x since division by 0 is undefined in arithmetic.

We usually get around this problem by bringing all terms involving x to one side rather than dividing both sides by x.

x(x − 2) = 3x
⇔ x(x − 2) - 3x = 0
⇔ x(x − 2 − 3) = 0
⇔ x = 0 or x = 5

Often fallacies or spurious proofs of contradictions is formed by sneaking such a division by 0 into the proof. Here is one I could think of.

Let a = b. So,

a + b = 2a
⇔ a - b = 2a - 2b
⇔ (a - b) = 2(a - b)

Dividing both sides by a - b we get

1 = 2

We have learnt these things in our high school. However, I forgot this important lesson while solving differential equations and lost a solution. The differential equation I was trying to solve was

y' = x²y²

If we divide both sides by y², the variables separate and solving it becomes a routine job.

y^-2y' = x²
⇔ -y^-1y' = ^x3⁄₃ + c' … (c' is constant of integration)
⇔ y = ^-3⁄_{(x³ + c)} … (c = 3c')

This is indeed a valid solution of the differential equation. However, we lost one solution while dividing both sides by y². This solution is y = 0. It can be verified that with y = 0, we get 0 on both sides of the equation.

We lost this solution in the step where we divided both sides by y². I couldn't find a way to get around this problem. So, whenever we need to divide both sides of the equation by y to separate the variables, we also need to perform an additional step of verifying whether y = 0 is a solution of the equation.

Dawn dawns

I composed this poem while watching the sunset at a sea beach.

DAWN DAWNS

When the sun goes down and the night sets in,
The colours around us are hard to see,
But look above, the stars are blinking,
Sailing across the sky very slowly.
Assuring us that time goes on,
That the night would end and dawn would dawn.

When the heart breaks and the pain is overwhelming,
Thoughts are gloomy and feelings are clumsy,
But be calm and strong, count each blessing
That is still with you, holding up firmly.
They will live and grief would be gone.
The heart would mend and joy would dawn.

Here is a piece of music with similar emotions that I composed one night: Waiting for dawn.

A kind of Bengali

I did my 11th and 12th standard studies in a residential school called DAV Public School in Purulia, West Bengal. One evening I accompanied some of my classmates who went to a shop to buy some stuff for themselves. I didn't have anything to buy. So, I was standing quietly at one corner. An old man mentioned as O below struck up a conversation with me. S is me.

O: So, are you a student?
S: Yes.
O: Which school do you study in?
S: DAV Public School.
O: Ok, what's your name?
S: Susam Pal.
O: Oh, so you are a Bengali.
S: Yes.
O: Which caste do you belong to?
S: I don't know.
O: You don't know? What kind of a Bengali are you?

From a cup of cappuccino to paradoxes

After a long meeting, I went to the cafeteria with a friend to have a cup of cappuccino, my favourite drink at office. In the dialogue below, P is my friend and colleague, and S is me.

S: Hey, they have a 'Silence Please' board here. We can't talk.
P: Rules are made to be broken.
S: So, your rule is to break rules?
P: Yes.
S: This implies that you should break your rule of breaking rules and thus not break rules and be silent.
P: Umm… My rule is to break rules made by others.
S: Ah! You avoided a self-reference there. It makes sense now.

I could have still trapped her by making a rule that P breaks rules made by others but this didn't occur to me in the cafeteria.

Such self references set up paradoxes in logic. One of the simplest ones is the liar paradox.

This statement is false.

Now, is this statement true? Is it false? Is it both true and false, or is it neither? This is discussed pretty nicely in the Wikipedia page for this paradox.

How do we avoid such paradoxes? Yes, one way is to avoid self-references by restricting a statement from talking about itself. But does it really solve the problem? Let us have a look at this.

The next statement is true.
The previous statement is false.

Is the first statement true or false? Yes, we have set up a paradox again despite avoiding self-reference here. The correct way to prevent these paradoxes from happening is to categorize the statements into various levels and allow a statement to talk about statements belonging to a lower level only.

So, if we categorize the first statement "The next statement is true" as a level 1 statement, then the next statement automatically becomes a level 2 statement as it is talking about level 1 statement. But wait! This implies that the level 1 statement is talking about level 2 statement which is illegal as per our new restriction of not allowing a statement to talk about another statement at the same or higher level. So, we see that we can avoid such paradoxes with this additional restriction.

A good friend of mine, shown as W below, often claims something strange.

W: I only ask questions in a debate. I don't take sides.
S: Ok. Let us debate this. Side 1: You take sides. Side 2: You don't take sides. Which side do you take?

Comic by Randall Munroe: http://xkcd.com/468/

Let me list down some of my favourite logical paradoxes.

• Russel's paradox: A set containing exactly the sets that are not member of themselves.
• Epimenides paradox: All Cretans are liars.
• Interesting number paradox: All natural numbers are interesting.
• Grelling–Nelson paradox: An adjective is heterological if and only if it does not describe itself.
• Barber's paradox: A barber shaves all and only those men in town who do not shave themselves.

Do go through Al Franken's advice.

Stack overwriting function

This is one of my favourite C-cum-ASM puzzles I often ask friends and colleagues who are interested in C as well as assembly language. The solution to this puzzle is implementation-dependent. I am pretty sure there is no way to solve this in an implementation-independent manner.

Here is the puzzle.

Code for the puzzle:

susam@swift:~/lab$ cat overwrite.c
#include <stdio.h>

void f()
{
}

int main()
{
    printf("1\n");
    f();
    printf("2\n");
    printf("3\n");
}

The problem is to define the function void f() in a manner such that the output is 1 followed by 3 as shown below:

susam@swift:~/lab$ gcc overwrite.c && ./a.out
1
3

Printing 3 in void f() and exiting is not allowed as a solution.

With this constraint, the puzzle essentially involves figuring out what code we can place in the body of void f() such that it causes the program to skip the instructions to carry out printf("2\n");. Let me show how I solved this for two implementations.

1. gcc 4.3.2 on 64-bit Debian 5.0.3 running on 64-bit Intel Core 2 Duo.
2. Microsoft Visual Studio 2005 on 32-bit Windows XP running on 64-bit Intel Core 2 Duo.

Let me first show step by step how I approached this problem for gcc when I first came across this puzzle. I added the statement char a = 7; to the function void f(). Next, I compiled the code and analyzed the assembly code generated for f() and main() functions.

susam@nifty:~$ cat overwrite.c
#include <stdio.h>

void f()
{
    char a = 7;
}

int main()
{
    printf("1\n");
    f();
    printf("2\n");
    printf("3\n");
    return 0;
}
susam@nifty:~$ gcc -c overwrite.c && objdump -d overwrite.o

overwrite.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <f>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   c6 45 ff 07             movb   $0x7,-0x1(%rbp)
   8:   c9                      leaveq
   9:   c3                      retq

000000000000000a <main>:
   a:   55                      push   %rbp
   b:   48 89 e5                mov    %rsp,%rbp
   e:   bf 00 00 00 00          mov    $0x0,%edi
  13:   e8 00 00 00 00          callq  18 <main+0xe>
  18:   b8 00 00 00 00          mov    $0x0,%eax
  1d:   e8 00 00 00 00          callq  22 <main+0x18>
  22:   bf 00 00 00 00          mov    $0x0,%edi
  27:   e8 00 00 00 00          callq  2c <main+0x22>
  2c:   bf 00 00 00 00          mov    $0x0,%edi
  31:   e8 00 00 00 00          callq  36 <main+0x2c>
  36:   b8 00 00 00 00          mov    $0x0,%eax
  3b:   c9                      leaveq
  3c:   c3                      retq
susam@nifty:~$

We know that when main() calls f(), the microprocessor would save the return address in the stack. Line 1d in the objdump listing for main() is the call to f(). After f() is executed, the code at line 22 is executed. So, the return address that is saved on stack is the address at which the instructions at line 22 would be present at runtime. The code highlighted in orange is the assembly code for printf("2\n");. This is the code we want to skip. In other words, we want to modify the return address in the stack to that of the instructions at line 2c. From the listing we can figure that it is equivalent to skipping 10 bytes in the instructions for main or adding 10 to the return address saved in the stack.

So, we know now how many instructions to skip. But how do we get hold of the return address saved in the stack when f() is being executed? This is where the statement char a = 7; that I added in void f() helps. The lines highlighted in yellow in the objdump listing for f() is the assembly code for this statement. We can see that the RSP (stack pointer) is copied into RBP (base pointer) and the variable a is allocated one location below memory address pointed to by RBP. Also, note that the old RBP was pushed into the stack by f() before it copied RSP to RBP.

Let us have a look at the sequence of steps performed in the call to f() and allocation of the variable a.

1. The microprocessor saves the return address by pushing RIP (instruction pointer) into the stack when main() calls f().
2. f() saves RBP by pushing it into the stack.
3. f() copies RSP to RBP and stores 7 at the memory address in RBP minus 1. In other words, the variable a is allocated in the address in RBP minus 1.

At this point, the stack would appear as below.

Content	Size (in bytes)
Return address (RIP)	8
Base pointer (RBP)	8
Variable a	1

So, we see that if we add 9 to the address of a, we get hold of the return address. So, here is the solution.

susam@nifty:~$ cat overwrite.c
#include <stdio.h>

void f()
{
    char a;
    * (char **) (&a + 9) += 10;
}

int main()
{
    printf("1\n");
    f();
    printf("2\n");
    printf("3\n");
    return 0;
}
susam@nifty:~$ gcc overwrite.c && ./a.out
1
3

Now, I will present the dumpbin listing and the solution for Visual Studio 2005.

C:\>type overwrite.c
#include <stdio.h>

void f()
{
    char a = 7;
}

int main()
{
    printf("1\n");
    f();
    printf("2\n");
    printf("3\n");
    return 0;
}

C:\>cl overwrite.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

overwrite.c
Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:overwrite.exe
overwrite.obj

C:\>dumpbin /disasm overwrite.obj
Microsoft (R) COFF/PE Dumper Version 8.00.50727.42
Copyright (C) Microsoft Corporation.  All rights reserved.


Dump of file overwrite.obj

File Type: COFF OBJECT

_f:
  00000000: 55                 push        ebp
  00000001: 8B EC              mov         ebp,esp
  00000003: 51                 push        ecx
  00000004: C6 45 FF 07        mov         byte ptr [ebp-1],7
  00000008: 8B E5              mov         esp,ebp
  0000000A: 5D                 pop         ebp
  0000000B: C3                 ret
  0000000C: CC                 int         3
  0000000D: CC                 int         3
  0000000E: CC                 int         3
  0000000F: CC                 int         3
_main:
  00000010: 55                 push        ebp
  00000011: 8B EC              mov         ebp,esp
  00000013: 68 00 00 00 00     push        offset $SG2224
  00000018: E8 00 00 00 00     call        _printf
  0000001D: 83 C4 04           add         esp,4
  00000020: E8 00 00 00 00     call        _f
  00000025: 68 00 00 00 00     push        offset $SG2225
  0000002A: E8 00 00 00 00     call        _printf
  0000002F: 83 C4 04           add         esp,4
  00000032: 68 00 00 00 00     push        offset $SG2226
  00000037: E8 00 00 00 00     call        _printf
  0000003C: 83 C4 04           add         esp,4
  0000003F: 33 C0              xor         eax,eax
  00000041: 5D                 pop         ebp
  00000042: C3                 ret

  Summary

           B .data
          57 .debug$S
          2F .drectve
          43 .text

C:\>

Just like in the objdump listing, in this listing too, the lines in yellow show where the variable a is allocated and the lines in orange show the instructions we want to skip. Here is the solution.

C:\>type overwrite.c
#include <stdio.h>

void f()
{
    char a;
    * (char **) (&a + 5) += 13;
}

int main()
{
    printf("1\n");
    f();
    printf("2\n");
    printf("3\n");
    return 0;
}

C:\>cl /w overwrite.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

overwrite.c
Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:overwrite.exe
overwrite.obj

C:\>overwrite.exe
1
3

Do you have more creative ways of solving this puzzle?

Waiting for dawn

Waiting for dawn is my second attempt at composing music. I made the first attempt while I was taking musical keyboard lessons from Jason. He is an excellent teacher and very passionate about teaching, playing and composing music. He corrected most of my bad playing habits and taught us some good stuff in a short span of time. However, I dropped out of the lessons pretty soon after a few weeks of lessons to take care of some personal affairs.

I composed this piece after dropping out of the keyboard lessons. 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.

MP3 | OGG | YouTube | Score | LilyPond

This piece consists of 147 measures. It is approximately 4 minutes 28 seconds long.

The mental image I had while composing this piece was that of a guy, sitting alone in a dark night, waiting for the night to pass and the dawn to arrive. 0:00–1:30 of the piece represents the night. 1:30–2:15 is the time when the darkness starts fading away and the sky turns red. Everything after 2:15 is about welcoming and enjoying the dawn.

For me this mental image doesn't just represent a particular night passing away due to the rotation of our planet. It represents how we should handle tough times, heartbreaks, loss, etc. in our personal lives. We should remain calm, wait for tough times to pass and good times to come, and when the bad times give way to good times again, we should welcome and enjoy the good times.

I am pretty happy with what I composed but not so happy with the way I played it on the keyboard. There are some errors in the timing and loudness of certain notes but my friends don't seem to notice them.

In case you have any feedback, suggestions and tips that would help me to improve my musical skills, please feel free to post a comment.

Telling eggs apart

Last evening after I took out boiled eggs from my electric kettle, I tested a solution to a problem I once got from Anoop, an ex-colleague and a good friend.

How can we tell raw eggs and hard-boiled eggs apart?

One solution I knew from childhood experiments involves spinning the given egg, then momentarily stopping it with hand while it is spinning and then releasing it immediately. If the egg starts spinning again, it is a raw egg. If it doesn't, it is a hard-boiled one. This can be explained with Newton's first law of motion. One might even see it as a demonstration of Newton's third law of motion.

Anoop told me about another solution which I believe is simpler and uses the same principle as the one behind the solution I mentioned above. Can you guess this simpler solution?

Do you know other ways of finding out whether an egg is boiled or not without breaking it?