Skip to content

Instantly share code, notes, and snippets.

@fgrosse
Created November 13, 2012 09:44
Show Gist options
  • Save fgrosse/4064924 to your computer and use it in GitHub Desktop.
Save fgrosse/4064924 to your computer and use it in GitHub Desktop.
Implementation of the karatsuba multiplication
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Karatsuba {
private static final BigInteger ONE = new BigInteger("1");
private static final BigInteger TWO = new BigInteger("2");
public Karatsuba() {
System.out.println("Karatsuba Multiplication Application");
BigInteger a = readSingleValue("a");
BigInteger b = readSingleValue("b");
BigInteger result = multiply(a, b);
System.out.println("The result is: " + result);
}
private BigInteger readSingleValue(String valueName) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
do {
try {
System.out.print("Input numeric value " + valueName + ": ");
return new BigInteger(reader.readLine());
} catch (Exception e) {
System.err.println("Could not read your input. Please input a valid number");
}
} while(true);
}
private BigInteger multiply(BigInteger a, BigInteger b) {
//TODO Bits auffüllen
int nHalf = a.bitCount()/2;
BigInteger r = a.shiftRight(nHalf);
// Bitsmaske = 2^(n+1)-1
createBitmask(nHalf);
// BigInteger s = a.and(val)
return null;
}
private BigInteger createBitmask(int nHalf) {
return TWO.pow(nHalf+1).subtract(ONE);
}
/**
* @param args
*/
public static void main(String[] args) {
new Karatsuba();
}
}
@fgrosse
Copy link
Author

fgrosse commented Nov 13, 2012

Not yet finished

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment