Testing for primality

How to test a huge number for primality? Provides an implementation of the famous Miller-Rabin algorithm using the widely available ‘bc’ (basic calculator) tool. Suitable both for Linux and Windows.

Testing if a number is prime is an interesting problem. Prime numbers have uses in many fields especially Cryptography. Here we show a technique through which we can verify if a number is prime or composite (not with 100% guarantee though). The algorithm we use is called Miller-Rabin.

I have, in another blogpost, talked about a tool available on Unix called bc which stands for basic calculator. In truth, its not ‘basic’ by any stretch of imagination. For my Windows brethren, a version is part of UnxUtils. This tool allows you to do large number, arbitrary precision calculations. It also allows you to write scripts. The script to implement this test is called pcheck.bc.

On Unix, it can be run using ./pcheck.bc while on windows it needs to be run like this:

bc pcheck.bc -ql.

The '-l' option is for bc to load math. library, and the '-q' option is to stop bc from boasting when it runs.

First, it will ask you for an option. The algorithm runs in iterations, each iteration requiring the given number (called p) to be tested against another number from a set (called s). If p is composite against s, then p is composite else p is probably prime. In order to increase this probability, this implementation tests against 30 given numbers. If option is entered as ‘0’, the program will read the numbers in set from the input and you can enter the numbers suitably. If its entered as ‘1’, the program will automatically select the set. If you are able to enter random numbers then select option ‘0’ else select ‘1’. I may talk about generating arbitrary long random numbers in a future blogpost.

Second, it will ask you for the number to test. Enter any large odd number (even numbers are composite). Sample:

900900900900990990990991 (prime)
900900900900990990990993 (composite)
359334085968622831041960188598043661065388726959079839 (prime)

Third, if you selected option ‘0’, it will prompt you for the 30 random numbers.

Read the code to understand further – its not very difficult to understand. Have questions, post comments.

This can be further extended to search for primes: start at any big odd number, test it – it its prime report and stop, if not add 2 to the number and test again. I used this code to search for very large primes. In fact, I used it to prove 2^600-95 is a 181 digit prime.

Being blind

Talks about what, according to Guru Nanak, is the definition of being blind.

While reading from Sri Guru Granth Sahib, I came across the following:

ਸੋ ਕਿਉ ਅੰਧਾ ਆਖੀਐ ਜਿ ਹੁਕਮਹੁ ਅੰਧਾ ਹੋਇ॥
ਨਾਨਕ ਹੁਕਮੁ ਨ ਬੁਝਈ ਅੰਧਾ ਕਹੀਐ ਸੋਇ ॥ ੩ ॥

This is Unicode text for Gurmukhi so hopefully everyone should be able to read. If not, try downloading Unicode font. If there are still problems, here is a transliteration:
So kyo andha aakhiye ji Hukamo andha hoye, Nanak Hukam na bujhayi andha kahiye soyi.

Here is what it means:
How can someone be called blind if he was made blind through the God’s Will? Says Nanak, one who does not understand God’s Will is the one who should be called blind.

In other words, Guru Nanak wants us to understand that nothing is within our control, and everything is happening through His Will. Unless we can understand that, imbibe that in our lives – we are blind.

I encourage readers to try and understand Gurbani – any translation can never create the same feelings as the original. While translation can be a means, it is not an end. I enjoyed reading this, and wanted to share the Guru’s definition of blindness.

SFTP>FTP+GPG

Shows that FTP+GPG combination cannot be used in place of SFTP – SFTP is still more secure. Also includes a howto document on setting up passwordless SFTP based automated file transfers.


Recently, we needed to setup secure file transfer with a third party that did not support SFTP. Hence we decided to use FTP+GPG – which includes transfer of GPG encrypted files with FTP. For more details on GPG, visit the homepage http://www.gnupg.org/. It can also operate in ‘portable’ mode – from a USB key.

We did not realise that this combination is still significantly less secure that SFTP based transfer. The threats it does not cater to, which SFTP can combat are:

  • Someone can come to know about the username, password used in the connection since this is still being transferred un-encrypted
  • Using this, someone can load their own files into the server which can be designed to either infect the system, or upload malicious information

Even if GPG signatures are used (as we did after coming to know about these shortcomings), there is still the risk of someone replaying the same files that we received. Even this can cause problems in certain situations. Hence, we had to resort to fixing the source IP to combat the problems. Due to using signatures and IP fixing, it all turned out to be more cumbersome, and still less secure.

The best way currently to establish automated file transfers is to do a password-less SFTP. It does not require any password transfer over the network at all, keeps everything encrypted, and: a disgruntled employee who happens to remember a password (in case of password based SFTP) cannot disrupt your services.

This document contains instructions on how to set this up: Password SFTP – How to setup. There is also an online version of the same document. If you have any questions, please post as comments.

When I left GNPS

I was a student of Guru Nanak Public School, Chandigarh from class III to X. I have a lot of fond memories of the school, and want to visit it again some day. I found and visited the website of the school today (it did not have one those days, of course) and was glad to know that few of the teachers – Mrs. T. Gill, Mrs. Satnam, Mrs. Veena (Music), Mrs. Daljit (Religious studies) are still with the school. The then Principal, Mr. Romesh Puri is not with the school, but the supervisor Mrs. Aparajita still is. The English and Maths teachers respectively – Mrs. Lehri and Mr. Barun are not listed. I could not find anyone known to me in the alumni list – in fact there seemed to be no one from our batch. Our batch just seems to have vanished into thin air – they are not even on Orkut!

When I was leaving the school, this is what the English teacher wrote in my autograph book:

Dearest Hardeep,

Life is like a garden – full of flowers and thorns – tread carefully and you’ll have the best of Nature and God’s creations. Be like the flower that gives out fragrance to everyone, pleases everyone with its beauty and leaves its mark on every heart. May God be with you in all spheres of life.

With all my love and blessings
Mari Lehri
15th May, 93

Nice – isnt it? I am trying hard, Ma’am 🙂 Have I lived life this way so far? That’s hard to decide – may be not.

Eclipse 1 Aug 2008

I just now watched and photographed the solar eclipse from New Delhi in India. Here we had only a partial view.

Ok, here is the much awaited photograph:

Eclipse 1st Aug 2008
Eclipse 1st Aug 2008

The sun shining on the right is a photograph of the overall scene where I was. Eclipses continue to entice me – I have been avidly following them since 1995 when I saw a total solar eclipse in Ranchi. Even the birds seemed confused when the sun rays were blocked.

Here is computer colored image that shows a total solar eclipse in its full glory.

In Hindu mythology, Arjuna vowed to kill Jaidhrath before Sunset, else he would commit suicide. The opponents made Jaidhrath to hide thinking that since Arjuna would be unable to find him, he wouldn’t kill him and would have to commit suicide. However, on the day of the battle, towards the evening, a total solar eclipse occurred and everybody thought the day has ended. Jaidhrath came out of the hiding thinking that Arjuna would commit suicide. At just that moment the eclipse ended, the sun shone brightly and Arjuna, realising that the day is not yet over, killed Jaidhrath.

I have a collection of Eclipses (both Lunar and Solar) from many different sources – some my own and others from magazines.

Using SQL potential

How to use the database SQL to its full potential. The idea is to reduce procedural coding and thereby improve performance, reduce defects.

I like to use the database to its full potential. For example, suppose someone has a list of vouchers and needs to find the vouchers that were paid later than the due date. One way to do this might be to read the vouchers one by one from the database, compare the due date with the payment date and determine the results. The other, recommended method will be to add the required criteria to the query itself so that only the exact result is obtained. With the second method, only 5% or 10% of the vouchers will need to be transferred from the database to the application while in the first method, all vouchers will need to be transferred.

In other words, the exact business requirements should determine the query. While you are at it, you should also keep in mind the indexes. Queries should always be written to minimise Disk I/O and transfers between the DB and the Application (server).

The database itself is quite powerful (esp Oracle) and I feel that its potential is always under-utilised. Let me show through an example.

I once had a requirement that there is a table having first, middle and last names of employees and the email ID. Something like this, ignoring the datatypes – assume all are VARCHAR2:

create table userlist(fname,mname,lname,emailid);

Each employee has middle name blank. Its possible that multiple employees have identical fname, lname with each other. For example, there can be two people having name ‘Hardeep Singh’. In this case, if the emailid of the two employees is same that means they are the same person having multiple rows, else they are different persons having the same name.

For example:

  1. Hardeep Singh alpha@gmail.com
  2. Hardeep Singh beta@gmail.com
  3. Hardeep Singh beta@gmail.com
  4. Satinder Singh gamma@gmail.com
  5. Satinder Singh gamma@gmail.com
  6. Gorakh Nath gn@gmail.com

In this case, 2 & 3 are the same person and 4 & 5 are also the same person. 1 & 2 are two different people.

Now the requirement is that we have to modify the middle name by adding a number such that every different person has a unique name. In the example above, the names should be:

  1. Hardeep Singh '1' alpha@gmail.com
  2. Hardeep Singh ‘ ′ beta@gmail.com
  3. Hardeep Singh ‘ ′ beta@gmail.com
  4. Satinder Singh ‘ ′ gamma@gmail.com
  5. Satinder Singh ‘ ′ gamma@gmail.com
  6. Gorakh Nath ‘ ′ gn@gmail.com

Now we know that ‘1’ is different from ‘2’ and ‘3’ because he has a different middle name.

The middle name to be added is given at the end of the name, in quotes. Gorakh Nath does not get any middle name since his name is unique. Any Tom, Dick or Harry would do this requirement in the following way: Read all the details one by one, look for people having the same name, then check the emailID then issue an UPDATE like this:

UPDATE userlist SET mname='1' where emailID='alpha@gmail.com';

Such UPDATES would need to be issued one for each person. However, this can be done through just a single UPDATE statement, without reading the list of employees at all. Here is the query:

update userlist a
set mname=(select x from (select rownum x,emailid,fname,
                                 lname
                          from userlist xa
                          where exists
                          (select 1
                           from userlist xb
                           where xa.lname=xb.lname and
                           xa.mname=xb.mname and
                           xa.fname=xb.fname and
                           xa.emailid<>xb.emailid))
                          ord
           where ord.emailid=a.emailid and
                 ord.fname=a.fname and
                 ord.lname=a.lname)
where exists(select 1
             from userlist b
             where a.lname=b.lname and
                   a.mname=b.mname and
                   a.fname=b.fname and
                   a.emailid<>b.emailid);
  

I guess an explanation is owed as to how it works. To my knowledge this query would work only in Oracle – but there would be ways to make it work in other Databases as well.

‘rownum’ returns the number of that particular row in the result set. The ‘exists’ clause at the end makes sure only people with same names are processed (‘gn@gmail.com’ is ignored). The part:

(select x from (select rownum x,emailid,fname,lname
from userlist xa
where exists
(select 1
from userlist xb
where xa.lname=xb.lname and
xa.mname=xb.mname and
xa.fname=xb.fname and
xa.emailid<>xb.emailid))
ord

creates a temporary view having the number, the email ID and the firstname. In the given scenario the result from this will be something like:

  1. 1, alpha@gmail.com, Hardeep, Singh
  2. This row will be absent because of the xa.emailid<>xb.emailid clause
  3. This row will be absent because of the xa.emailid<>xb.emailid clause
  4. This row will be absent because of the xa.emailid<>xb.emailid clause
  5. This row will be absent because of the xa.emailid<>xb.emailid clause
  6. This row wont even be considered, as I explained above

 

Had there been yet another ‘Hardeep Singh’ with a different email ID, he would have got a middle name of ‘2’.
Now the last step is to copy over the numbers based on the first and last names only – that part is pretty simple. Please post any questions in the comments area.

Solution using PGSQL:

update userlist a
set mname=(select rn from (
select row_number() over(order by(select null)) rn,emailid from(
select distinct p.emailid from userlist p) x) y
where y.emailid=a.emailid)
where exists(select 1
from userlist b
where a.fname=b.fname and
a.mname=b.mname and
a.lname=b.lname and
a.emailid<>b.emailid)

Ishmeet lost

The Star voice of India, Ishmeet Singh is no longer with us. He died in Maldives where he had gone to perform, and was only 18 years old. He had a great career in front of him. Its very sad, and we cannot even begin to understand what his family must be going through.

I liked him a lot especially he was the only turbaned Sikh to reach the finals in any singing competition. During the VoI final, when Asha had to announce the winner, everybody including Harshit was praising her. However, Ishmeet informed the audience that it being Gurpurab that day, the Guru was with him and invoked the name of Waheguru. Ishmeet understood that Asha would only read what was written – praising her would not do any help.

Online judge

Sometime back I came across Sphere Online Judge (SPOJ). A ‘judge’ is a mechanism through which you can verify your programming solutions.
The SPOJ contains a huge range of programming problems. You need to code a solution in one of the supported languages (from Unix shell scripting to C to Java to esoteric languages like B**fcuk). When you submit the solution, the judge will execute your code with predetermined input and match against predetermined output. If all goes well, your solution will be accepted. Otherwise, it will say ‘compilation error’, or ‘incorrect output’ or ‘time limit exceeded’. It will not tell you the input values or expected output, nor will it tell you the input for which your program is going wrong.

Its very interesting, the problems are very challenging and I gave some problems a try. At the end of it, you can see the report generated by the judge specific to you:

http://www.spoj.com/users/hardeeps/

Also, you can see the submission history:

http://www.spoj.com/status/hardeeps/

or, showcase a signed certificate that the judge provides:

http://www.spoj.com/status/hardeeps/signedlist/

You can see that I have tried various languages, including Java, Bash (Unix shell) and Perl. I am yet to prove my programming skills in C. 🙂

The result AC means that the solution is accepted. The certificate also shows that I was able to calculate PI correctly to 2500 places of decimal in less than 24 seconds – I used the identity described in this blogpost.

I have tried to understand how to verify the digital signature on the certificate but have not been successful. The author informs me that a PHP function is being used to generate the certificate. It would be good if someone can get this working (please post in comments).

Rupee Devaluation

How do currency exchanges work?

Sometimes there would be news that the Reserve Bank of India (RBI) has decided to devalue the Rupee. I would interpret “devalue” to mean that the value of Rupee against other currencies has been decreased. However, I also knew that the Rupee changes value everyday and not just those days when there was news from RBI. I would feel curious as to how then the Rupee kept changing its value everyday.

I understood the answer only when I did my MBA. Here is a short summary:

In the good old days, every country would specify its currency in terms of Gold. However, due to the problems associated with this mechanism, especially during times of Gold scarcity – this system was scrapped.

What happens now is that each country chooses what control it wants to have over its currency. It can let the currency float – which means that the market will determine the price based on demand, supply, balance of trade etc. This is the least intrusive method and requires little action from the country’s central bank.

The other is choice the central bank can make is to tie the currency to a fixed set of other currencies. This includes deciding upon a weighted mean formula (based on the currencies in the set) to determine the currency value. All that is needed then, is to find out the values of those currencies on a daily basis and calculate the value of our currency using the formula. This lets the country control its export and import prices to some extent. In such a case, the central bank needs to have the currency partially or fully convertible – and carry out currency exchanges based on the determined formula.

When RBI changes the formula, that is called devaluation – although the rates change daily based on the formula.

Value of Pi

Pi
Pi

Wikipedia defines Pi or p as “a mathematical constant which represents the ratio of any circle’s circumference to its diameter in Euclidean geometry”. As a kid I used to be interested in the calculation of Pi. The value of Pi, to 100 places of decimal is:

3.1415 9265 3589 7932 3846 2643 3832 7950 2884 1971 6939 9375 1058 2097 4944 5923 0781 6406 2862 0899 8628 0348 2534 2117 0664

Value to 100 places
Value to 100 places

I have calculated this using the Unix command bc. The command for this is based on an identity (that I think is credited to Ramanujan) and is:
24*a(1/8)+8*a(1/57)+4*a(1/239)
where a stands for the arctangent function.

The formula is:

pi = 24*arctan(1/8)+8*arctan(1/57)+4*arctan(1/239)

First, load the bc language with associated library using “bc -l”. Then, set the scale to the number of digits using “scale=100”. Afterwards run the identity I gave above.

To experimentally calculate Pi experimentally, there are two ways: One using a random number generator and the other by physically measuring the circumference of a given circle.

Consider a square of length unity. Within that, a circle is drawn, having unity diameter. If a point is taking within the square at random, the probability of that point also lying within the circle is Pi*(1/2)*(1/2) which is Pi/4. Now, start taking points at random (x,y) and see if x*x+y*y<=1/4 or not (if it is, then that means the point lies within the circle). Maintain the count of total number of points taken (t), and the number that fell within the circle(c). Now Pi can be calculated as:

Pi=4*c/t

The other method is to take a circular bottle (measure the radius r) or tin and tie a thread around its circumference. Measure the circumference(c). Now Pi is c/2r.

The following two sentences contain the value of Pi: the number of letters in each word indicates the corresponding number in the value of Pi.

1. “May I have a large cup of coffee.”

2. “How I want a drink, alcoholic of course, after the heavy chapters involving quantum mechanics.”

This makes the value of Pi easy to remember.

Lastly, how useful are the digits of Pi as a source of random numbers? Not bad, according to a study: “while sequences of digits from pi are indeed an acceptable source of randomness – often an important factor in data encryption and in solving certain physics problems – pi’s digit string does not always produce randomness as effectively as manufactured generators do”.

Always wanting to do my own thing, I downloaded the value of Pi to one million places from a website, split it into (x,y,z) coordinates, each having 5 digit precision. Here is the graph that got generated:

Pi-randomness
Pi-randomness

A bell curve, but could have been better – seems to mimic the results from the study.

Continuous Compounding

I feel there is something mathematically wrong with the way compound interest is defined today. We say “5% per annum, semi-annually compounded”. If I have money invested, mathematically speaking, it should get compounded all the time, not just in fixed intervals.

I would like to define the term “absolute percentage” – the annual interest rate at which the money must grow all the time in order to reach the same amount as it does using normal interest rate calculation. Let me explain what that means.

If I invest amount ‘p’ for period ‘t’ years, at an ‘absolute’ interest rate of ‘rdash’, then,

a=p*e^(rdash*t/100)

where ‘e’ is a mathematical constant having value approximately 2.71828182845904.

This means, that amount ‘p’ will grow to amount ‘a’ in ‘t’ years if it compounds continuously.

Here, rdash is the absolute equivalent of rate r if
a=p*(1+r/100)^t

Here is a table that explains it. Try and understand, ok?

Gurbani Wallpaper

Attached below is a Gurbani wallpaper that I have created and intend to submit to SikhNet.com for inclusion in their wallpaper collection for downloads. It comes in six flavours, each slightly different – select the one that you like most.
Saajanada 1 Saajanada 2 Sajanada 3 Sajanada 4 Saajanada 5 Saajanada 6

The wallpaper is a composite: the pebbles background was photographed by me in Goa, the Gurmukhi text and meanings is computer graphics, but the Ik Onkar is not. The Ik Onkar is also a photograph taken in slowshutter, and with a flashlight that I moved by hand to make the shape.

TinuURL link to this entry: http://tinyurl.com/gwallpapers


Licensing and information about the blog available here.