Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static LargeInt karatsubaMul(LargeInt first, LargeInt second) {
- try {
- if(first.numbers.size() <= 1 || second.numbers.size() <= 1)
- return hiSchoolMul(first, second);
- } catch (NumberFormatException e) {}
- /* calculates the size of the numbers */
- int m = Math.max(first.numbers.size(), second.numbers.size());
- int m2;
- if(m % 2 != 0)
- m2 = (m / 2) + 1;
- else
- m2 = m / 2;
- /* split the digit sequences about the middle
- high1, low1 = split_at(num1, m2)
- high2, low2 = split_at(num2, m2) */
- if(!greaterList(first.numbers, second.numbers)) {
- LargeInt temp = first;
- first = second;
- second = temp;
- }
- LargeInt high1 = new LargeInt();
- LargeInt high2 = new LargeInt();
- LargeInt low1 = new LargeInt();
- LargeInt low2 = new LargeInt();
- first.numbers.resetForward();
- for(int i = 0; i < first.numbers.size(); i++) {
- if(i > m2)
- high1.numbers.addEnd(first.numbers.getNextElement());
- else
- high2.numbers.addEnd(first.numbers.getNextElement());
- }
- second.numbers.resetForward();
- for(int i = 0; i < second.numbers.size(); i++) {
- if(i > m2)
- low1.numbers.addEnd(second.numbers.getNextElement());
- else
- low2.numbers.addEnd(second.numbers.getNextElement());
- }
- /* 3 calls made to numbers approximately half the size */
- LargeInt z0 = karatsubaMul(low1,low2);
- LargeInt z1 = karatsubaMul(add(low1, high1), add(low2,high2));
- LargeInt z2 = karatsubaMul(high1,high2);
- return add(add((hiSchoolMul(z2,new LargeInt("" + (10 ^ (2*m2))))),
- (hiSchoolMul(subtract(subtract(z1,z2),z0),new LargeInt("" + (10^(m2)))))), (z0));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement