Calculate Root of Any Whole Number in Java

The following Java program can find any root of a whole number. The logic is simple. Start by guessing some number and check if that is the correct value. If that overshoots then subtract some from the guess number else add to it. We add or subtract some fixed constant. If that constant is too big then we divide that constant by 10 to get a finer number.

#!java
public class CubeRoot {

    public static void main(String[] args) {
        System.out.println(String.format("%.2f", cubeRoot(0, 2)));
        System.out.println(String.format("%.0f", cubeRoot(8, 0)));
        System.out.println(String.format("%.4f", cubeRoot(10, 4)));

        System.out.println(String.format("%.4f", root(10, 2, 4))); // Square Root
        System.out.println(String.format("%.4f", root(100, 5, 4))); // 5th Root
    }

    private static double cubeRoot(int n, int precision) {
        return root(n, 3, precision);
    }

    private static double root(int n, int root, int precision) {
        double x = n / 5.0; // 5 is better than 4 since this will have bigger
                            // step. 3 is very bad choice since there are some
                            // no.s which will never have rational output when
                            // divided by 3, e.g. 5.
        double powX;
        double d = 10;
        double lastX = 0;
        double lastLastX = 0;
        do {
            powX = Math.pow(x, root);
            if (matches(powX, n, precision))
                return x;
            else {
                if (matches(lastLastX, x, precision)) {
                    // If the lastLast x value is same as current then we are
                    // trapped in a loop, since the current d is not small
                    // enough. We need to now step at finer precisions.
                    d /= 10;
                    if (matches(d, 0, precision + 1)) {
                        return x;
                    }
                }
                lastLastX = lastX;
                lastX = x;
                if (n < powX) {
                    x -= d;
                } else {
                    x += d;
                }
                // System.out.println("(x=" + x + ", d=" + d + ")");
            }
        } while (true);
    }

    private static boolean matches(double a, double b, int precession) {
        return ((int) (a * (long) Math.pow(10, precession)))
                - ((int) (b * (long) Math.pow(10, precession))) == 0;
    }

}

Django-Select2 version 3.1.1 released

Just released Django-Select2‘s version 3.1.1.

The key changes are:-

  • Updated Select2 Javascript library to versino 3.2. This new version fixes a lot of bugs, along with providing a high resolution icon image, to be used in Retina displays.
  • In my last release (version 3.0.2) I introduced some new template tags but unfortunately I did not update the setup.py and Manifest.in files to include that directory. That directory was missing in the released package. Now it is included and installed.

If you see the Changelog then you will notice that I jumped from version 3.0.2 to 3.1.1. In fact there was a version 3.1.0 in-between, but that was again a faulty package. That package had the templatetags directory but that does not install that. That was again due to some missing code in setup.py.

Hack sbicapsec.com to run on Firefox

`AG_BACKQUOTE_TURN_ON`

www.sbicapsec.com is State Bank of India’s online share trading portal. This is a good portal but their site’s code quality is amazingly of low quality, dare I say, crappy. SBI being a public sector government institute, we can rest assured that the code quality or bugs in it would not get fixed soon, if ever.

Anyway as of now if you try using this portal in Firefox or Chrome, then maybe you will endup with a screen like this.

sbicapsec.com after login in Firefox. Notice no applet running, instead we have weird “:10”.

Notice the weird “:10” character in the screenshot, instead of the Java Applet.

Fixing sbicapsec.com to run in Firefox

Don’t worry the “hack” here is not illegal. This is used merely as an expression for making things work the way you want it which requires a lot of technical trickery to get it right.

The following has been tested in Firefox 13 and 14 in Mac OSX and Windows XP. You are free to try this as you may want it though. Also this should work in Chrome too.

Now let’s get into fixing this in few simple steps:-

  1. For your sake, open this blog page in your Firefox browser.
  2. Install GreaseMonkey browser extension. You may need to restart your browser.
  3. Install my GreaseMonkey user script by clicking on the link here – AppVersion Patch for SBICAPSEC.
  4. Click on Install button in the dialog box that you get.

That is it! You should now get the applet after login.

Fixed sbicapsec.com, after login.

How the fix works (for the technically inclined)

This section is for geeks, who would like to know how the script works. Also it is better to understand this, so that you understand, there is no malicious code in my script.

What is wrong in sbicapsec.com’s site? (Root cause)

The portal’s JS code assumes that `navigator.appVersion` will always return a string which will have a semi-colon (;). In fact that is true for IE and Chrome (in Mac OSX version only), but not for others. After this failure everything goes down like dominoes.

The popup we get after login has a `frameset` with three frames. The second one is the one which is supposed to present the Java applet. The layout of that page is roughly as below:-

[code lang=”html”]
<body>

<applet>
<param>
<param>
<param>

</applet>
</body>
[/code]

It seems the devs there had a requirement to set the `width` and `height` of the `applet` based on user screen’s dimension. For this they modified the code to use JS to dynamically generate the upper `applet` tag.

[code lang=”html”]
<body>

<script>
// This script will generate the upper applet tag with appropriate width and height.
</script>
<param>
<param>
:10
<param>

</applet>
</body>
[/code]

It is in the above `script` tag where it reads `navigator.appVersion` and tries to split it by `;` and then read the other part. When that errors out, so does the code following it. That code is supposed to write the upper `applet` tag. So, at the end we are left with many `param` tags and a dangling `</applet>` tag. The weird `:10` characters are written between two `param` tags.

From the way they have written the JS code, it seems the devs did not visualize the html page as a tree of blocks, instead for them it was a file stream; like the kind when you use your Java or C++ file output stream. The `script` block above uses `document.write()` to write the opening `applet` tag, instead of using JS to directly manipulate the DOM objects. I wonder how these devs can layout a page, who visualize it as a stream of characters? And, this is just a fraction of the real code, who knows what else is inside. It seems SBI needs to seriously train its devs. All this makes me loose faith over the security and reliability of their site.

Anyway, enough of the rant, back to the topic. The patch script I wrote will, simply try to do what there code was meant to do, add the `applet` tag. Because of the dangling `applet` end tag, I was unable to wrap my `applet` around the existing `param` tags. So, instead I detached all the `param` tags, emptied the parent (this reference was stored before detaching `param`), then added `param` tags inside the newly create `applet` tag and finally added the `applet` inside the previous parent of `param` tags.

I also tried using other techniques but they did not work. The first one was directly modifying `navigator.appVersion` to return a string with `;`, but it seems you cannot modify them. The second options was to replace existing `String.split()` function with my own version. In my version I would always return an array of at least length two, so that the code does not error out. Anyway this too did not work out since GreaseMonkey scripts are ran after the page is executed. GreaseMonkey does provide an option to run our scripts at the beginning too, but according to docs that is not supported inside frames.

Anyway, all’s well that ends well. 🙂

SplitBill: IOU manager for and by Geeks

There are hundreds of IOU software on the net. What makes SplitBill different is that it has no UI. Yes, you read that right – No UI. Now the more surprising part. It is a breeze to use and setup. In fact all you need is a sever with Python and MySql installed to host this, and then simply run the code after setting up the DB and it is ready. You might be wondering now, how do we access the system? Easy; just send a mail to a pre-configured mail box. Suppose John owes you 100 bucks then simply send a mail to SplitBill with John in CC or To fields. In subject write Loan 100 For Pizza. Now just send the mail. You are done. Moments later SplitBill will reply to your mail, confirming that your transaction has been recorded. So, SplitBill is like a command-line program, where your mail box is the Terminal window. We already have mail clients for pretty much every device hooked to the net. So, SplitBill is accessible to you from practically from everywhere. When you want to checkout who owes you or you owe whom, simply mail to SplitBill with Get in the mail’s subject. The response mail will have all the summary along with list of all last hundred transactions.

SplitBill Architecture

SplitBill Architecture

Because of the above design, SplitBill is inherently scalable. Many users can simultaneously send mails to SplitBill’s mail box without affecting it at all. It polls the mail server every five seconds (configurable) via IMAP connection and processes the mails in the order they were received. This way spikes in requests are eased out at mail server end. Mail server acts like a very large buffer for SplitBill system. Also if for some reason SplitBill crashes, the users can still file transaction, which will get processed when it is back online.

SplitBill System Design Assumptions

SplitBill is a simple product. To keep it simple to use, and light, it has only basic abuse protection facility. For example, suppose you filed a transaction that John owes you 100 bucks. Now John can command SplitBill to simply delete that transaction. SplitBill will honour that and will purge that transaction without the possibility for a rollback. However, when John is notified that his request has been fulfilled, you too will be CCed in that response mail. From the response mail you will come to know what exact transaction has been deleted. You can then use that info to refile the transaction, and give a nice little trashing to John. SplitBill has no mechanism for explicitly registering users. Whenever you send a mail to SplitBill, it will quietly register all new mail ids in it.

SplitBill recognizes a person by there mail id, so if you happen to own multiple mail ids then each one would be treated as separate user. Currently there is no way to combine them together. This is something which can be addressed in future.

SplitBill Error Handling

In spite of its simplicity it does not trade off reliability. Most of the stuffs you can checkout in its code, but there is one part you need to be aware of. When it errors out five consecutive times (configurable), then it auto shuts down. This is because if on consecutive tries if the command fails then it is assumed that something bad, like a DB crash, has happened which might take quite sometime or forever to be fixed.

It does not mark a mail as read unless and until the transaction has been successfully recorded in the database. However, if it is unable to mark the mail as read (even after retrying), then it shuts itself down to prevent recording the same transaction again. Unfortunately currently the mail UID is not recorded in database, preventing it from identifying if the current transaction has already been processed.

Whenever it shuts itself down, it sends mail to all registered owners, notifying the problem. The owners also receive mails with stack traces when they happen. Me and my friends have been using this for couple of months over two years now, and we have hardly faced any issues till now.

SplitBill Command Reference

There is already a separate page on this. Please see it here.

Get SplitBill

Get or fork SplitBill on GitHub – https://github.com/applegrew/splitbill.

Setting up SplitBill

  1. Make sure you have Python 2.6 or up installed on your server.
  2. Download and extract the splitbill sub-folder into your server.
  3. Install pytz package.
  4. Install MySql and MySql connector for Python.
  5. Run setup_db.sql script to setup your database. If you  want your schema to be named something other than splitbill, then modify this sql file.
  6. In splitbill folder you will find settings.ini. Set the DB and mail credentials and other settings as required.
  7. Finally! Run SplitBill. You can run it from the parent folder of splitbill using command nohup python -m splitbill.main &.

A Little History

SplitBill was envisioned not by me, but my friend Rohit. He designed the original system and coded that in C#. Later when we wanted to move the system to my (Linux) server, I decided to recode it in Python. This version of SplitBill is only couple of months a year old and was coded by both of us. We had used the original version for almost a year, during which time the SplitBill architecture evolved to its current state.