extern crate num;
use self::num::*;
use std::cmp;


pub fn mult(x: &BigInt, y: &BigInt) -> BigInt {
    // base case
    if (x < &BigInt::from(10)) || (y < &BigInt::from(10)) {
        return x * y;
    }

    let m = cmp::max(x.to_string().len(), y.to_string().len());
    let split = m / 2 as usize;

    let (high1, low1) = split_at(&x, split);
    let (high2, low2) = split_at(&y, split);

    // compute partial products
    let z0 = mult(&low1, &low2);
    let z1 = mult(&(&low1+&high1), &(&low2+ &high2));
    let z2 = mult(&high1, &high2);

    return (&z2 * num::pow(BigInt::from(10), 2 * split)) +
           ((&z1 - &z2 - &z0) * num::pow(BigInt::from(10), split)) +
           &z0;
}

#[test]
fn test_mult() {
    assert_eq!(mult(&BigInt::from(5), &BigInt::from(10)), BigInt::from(50));
    
    assert_eq!(mult(&BigInt::from(4205), &BigInt::from(421234)),
               BigInt::from(1771288970));
    
   let var1 = "3141592653589793238462643383279502884197169399375105820974944592"
        .parse::<BigInt>()
        .unwrap();
   
   let var2 = "2718281828459045235360287471352662497757247093699959574966967627"
        .parse::<BigInt>()
        .unwrap();
   let expected = "8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184";

   assert_eq!(mult(&var1, &var2).to_string(), expected);

}

fn split_at(num: &BigInt, n: usize) -> (BigInt, BigInt) {
    let s = num.to_string();
    let (a, b) = s.split_at(s.len() - n);
    let c: BigInt = a.parse::<BigInt>().unwrap();
    let d: BigInt = b.parse::<BigInt>().unwrap();
    return (c, d);

}

DONT THREAD ON ME fucked around with this message at 00:03 on Dec 9, 2016

pub fn par_mult(x: &BigInt, y: &BigInt) -> BigInt {
// base case
    if (x < &BigInt::from(10)) || (y < &BigInt::from(10)) {
        return x * y;
    }

    let m = cmp::max(x.to_string().len(), y.to_string().len());
    let split = m / 2 as usize;

    let (high1, low1) = split_at(&x, split);
    let (high2, low2) = split_at(&y, split);

    // compute partial products
    let mut z0 = BigInt::from(0);
    let mut z1 = BigInt::from(0);
    let mut z2 = BigInt::from(0);
    
    rayon::join(|| z0 = par_mult(&low1, &low2),
                        || rayon::join(
                               || z1 = par_mult(&(&low1+&high1), &(&low2+ &high2)),
                               || z2 = par_mult(&high1, &high2)));
 

    return (&z2 * num::pow(BigInt::from(10), 2 * split)) +
        ((&z1 - &z2 - &z0) * num::pow(BigInt::from(10), split)) +
        &z0;
}

test tests::test_mult ... ignored
test tests::bench_builtin       ... bench:         337 ns/iter (+/- 85)
test tests::bench_karatsuba     ... bench:     836,913 ns/iter (+/- 218,827)
test tests::bench_par_karatsuba ... bench:     581,647 ns/iter (+/- 15,533)

DONT THREAD ON ME fucked around with this message at 01:20 on Dec 9, 2016