Pollard's Rho in Java

This is a Pollard's Rho implementation in java. Not very fast, but works for uva online judge. The reason behind using java is the default support of the BigInteger class.

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;

public class PollardRho {

    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    static Vector<BigInteger> v = new Vector<BigInteger>();

    public static BigInteger rho(BigInteger N) {

        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        if (N.compareTo(ONE) == 0) return;

        if (N.isProbablePrime(20)) {
            v.add(N);
            return;
        }

        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) throws Exception {

        String string = "";
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while(null != (string = reader.readLine())) {
            BigInteger N = new BigInteger(string);
            v.clear();
            factor(N);
            Collections.sort(v);
            for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
            System.out.println();
        }
    }
}

I have seen this piece of code years ago somewhere in the internet, but can't remember exactly where. So, I will be glad if anyone can comment/mail me the original source. However, for spoj, I need to write a much much better version of this in C++ :( Exam sucks life...

Java Access Modifiers

Overview:

There are 4 types of access modifiers which are applicable to the members of a class, i.e. the variables and methods. Namely:

1. Public


2. Protected


3. Default or no modifier


4. Private

However, for a class declaration, protected and private are not allowed, and in a .java file, there can be only one public class, the rest must have been declared with default access. Well, we are more concerned about the access modifiers for the members of a class, as they are quite confusing on some aspects. Each of the four types is described below:

Public

As we can guess, the public members are visible from anywhere regardless of which package or file it is in. Then can be accessible from any other class of same or another package using just a '.' {dot} operator with the class reference.

Protected

This is probably most confusing modifier of java. Protected members are similar as members having default modifier, however, the difference is, protected members can be accessible outside the package it is in through inheritance, i.e. extending the parent class.

Default or no modifier

When no modifier is specified explicitly, it becomes the default modifier. Default modifiers can be thought of as a subset of the Public modifier. As, they are essentially same as Public when they are in the same package. However, members with default modifiers are not accessible from anywhere outside the package the class is in. When we don't specify a package, still there is a default package maintained by the java environment.

Private

It is also straight-forward as public, a private member can not be accessed from anywhere out side the class it is in.

More on "protected"

There are something more notable regarding protected type. As they are often very confusing with it's two near relatives, default and public.

Say, we have a "protected int x" in "class A" in package "pack1". And we derived "class B" from "class A" in package "pack2". In this case, variable x in "class B" is known as if it is just a member of "class B". so, in "class B", we can write in a method "System.out.println(x);". But note, we can't do this: "System.out.println(new A().x);". So, if the subclass is outside the package, we can't access it's parent class' protected member by a class reference. There is another interesting thing, Say, we have another "class C" which is extending the above "class B", then in "class C", we can't use 'x' as when a derived class have some protected member, it becomes a private data in the derived class, so farther extensions can not use those variables anymore.

Summery of the above

	public	protected	no modifier	private
Same class	Yes	Yes	Yes	Yes
Same package subclass	Yes	Yes	Yes	No
Same package non-subclass	Yes	Yes	Yes	No
Different package subclass	Yes	Yes	No	No
Different package non-subclass	Yes	No	No	No

I think these are the cases.

Blogger Spacing Problem

Spacing problems in blogger blogs

Blogger blogs have some serious spacing issues, especially with some specific html tags, for example, if you use a <table> tag on your post, you will see it leaves a huge blank spot before and after it. Same things might happen for your <pre> or <p> tags. This is probably because blogger treats every line breaking white space to be a <br/>. However, we can easily overcome this by adding a simple css script in the post (So, we will be using the "Edit Html" option, and in my opinion, the Rich Text Editor is shit. If you are not familiar of what we are talking about, don't be afraid, you'll see, your posts are going to be just fine).

Just add the following css in your post to create a class, and name it whatever you like, I'll call it 'nobr':

<style type="text/css">
.nobr br { display: none; }
</style>

Don't worry, it will not be visible in your actual post. Now, wrap around the elements for which you don't want to see extra line gaps before and after it using this class:

<div class="nobr">
<!-- your elements -->
</div>

Here is an example for using a <table> tag using and not using the above "nobr" class:
[Not using]

---

Name	Age
Pulok	17
Payel	20

---

[using]

---

Name	Age
Pulok	17
Payel	20

---

So, the spacing problem is significantly reduced. Hope you'll give it a try!