• O(n²), n is the number of bits

public class M
{
	public static int multiply(int x, int y)
	{
		if(y == 0)
			return 0;

		if(y%2 == 0)
			return 2*multiply(x, y>>1);
		else
			return x + 2*multiply(x, y>>1);
	}

	public static void main(String args[])
	{
		System.out.printf("10 * 5 = %d\n", multiply(10, 5));
		System.out.printf("10 * 8 = %d\n", multiply(10, 8));
	}
}
			

• O(n²), n is the number of bits

import javafx.util.*;

public class D
{
	public static Pair<Integer, Integer> divide(int x, int y)
	{
		if(x==0)
			return (new Pair<Integer, Integer>(0, 0));

		Pair p = divide(x>>1, y);

		int q = 2*(int)p.getKey();
		int r = 2*(int)p.getValue();

		if(x%2 != 0)
			r += 1;
		if(r > y)
		{
			r -= y;
			q += 1;
		}

		return (new Pair<Integer, Integer>(q, r));
	}

	public static void main(String args[])
	{
		Pair<Integer, Integer> p = divide(10, 3);

		System.out.printf("10/3 = (%d, %d)\n", p.getKey(), p.getValue());
	}
}
			

• gcd(a, b) = gcd(b, a mod b)

public class G
{
	public static int gcd(int a, int b)
	{
		if(b == 0)
			return a;

		return gcd(b, a%b);
	}

	public static void main(String args[])
	{
		System.out.printf("GCD of (121, 77): %d\n", gcd(121, 77));
	}
}
			

• Algorithm, by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani