num_bigint_dig/algorithms/

mac.rs

use core::cmp;
use core::iter::repeat;

use crate::algorithms::{adc, add2, sub2, sub_sign};
use crate::big_digit::{BigDigit, DoubleBigDigit, BITS};
use crate::bigint::Sign::{Minus, NoSign, Plus};
use crate::biguint::IntDigits;
use crate::{BigInt, BigUint};

#[inline]
pub fn mac_with_carry(a: BigDigit, b: BigDigit, c: BigDigit, acc: &mut DoubleBigDigit) -> BigDigit {
    *acc += a as DoubleBigDigit;
    *acc += (b as DoubleBigDigit) * (c as DoubleBigDigit);
    let lo = *acc as BigDigit;
    *acc >>= BITS;
    lo
}

/// Three argument multiply accumulate:
/// acc += b * c
pub fn mac_digit(acc: &mut [BigDigit], b: &[BigDigit], c: BigDigit) {
    if c == 0 {
        return;
    }

    let mut carry = 0;
    let (a_lo, a_hi) = acc.split_at_mut(b.len());

    for (a, &b) in a_lo.iter_mut().zip(b) {
        *a = mac_with_carry(*a, b, c, &mut carry);
    }

    let mut a = a_hi.iter_mut();
    while carry != 0 {
        let a = a.next().expect("carry overflow during multiplication!");
        *a = adc(*a, 0, &mut carry);
    }
}

/// Three argument multiply accumulate:
/// acc += b * c
pub fn mac3(acc: &mut [BigDigit], b: &[BigDigit], c: &[BigDigit]) {
    let (x, y) = if b.len() < c.len() { (b, c) } else { (c, b) };

    // We use three algorithms for different input sizes.
    //
    // - For small inputs, long multiplication is fastest.
    // - Next we use Karatsuba multiplication (Toom-2), which we have optimized
    //   to avoid unnecessary allocations for intermediate values.
    // - For the largest inputs we use Toom-3, which better optimizes the
    //   number of operations, but uses more temporary allocations.
    //
    // The thresholds are somewhat arbitrary, chosen by evaluating the results
    // of `cargo bench --bench bigint multiply`.

    if x.len() <= 32 {
        long(acc, x, y)
    } else if x.len() <= 256 {
        karatsuba(acc, x, y)
    } else {
        toom3(acc, x, y)
    }
}

/// Long multiplication:
fn long(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
    for (i, xi) in x.iter().enumerate() {
        mac_digit(&mut acc[i..], y, *xi);
    }
}

/// Karatsuba multiplication:
///
/// The idea is that we break x and y up into two smaller numbers that each have about half
/// as many digits, like so (note that multiplying by b is just a shift):
///
/// x = x0 + x1 * b
/// y = y0 + y1 * b
///
/// With some algebra, we can compute x * y with three smaller products, where the inputs to
/// each of the smaller products have only about half as many digits as x and y:
///
/// x * y = (x0 + x1 * b) * (y0 + y1 * b)
///
/// x * y = x0 * y0
///       + x0 * y1 * b
///       + x1 * y0 * b       + x1 * y1 * b^2
///
/// Let p0 = x0 * y0 and p2 = x1 * y1:
///
/// x * y = p0
///       + (x0 * y1 + x1 * y0) * b
///       + p2 * b^2
///
/// The real trick is that middle term:
///
///   x0 * y1 + x1 * y0
/// = x0 * y1 + x1 * y0 - p0 + p0 - p2 + p2
/// = x0 * y1 + x1 * y0 - x0 * y0 - x1 * y1 + p0 + p2
///
/// Now we complete the square:
///
/// = -(x0 * y0 - x0 * y1 - x1 * y0 + x1 * y1) + p0 + p2
/// = -((x1 - x0) * (y1 - y0)) + p0 + p2
///
/// Let p1 = (x1 - x0) * (y1 - y0), and substitute back into our original formula:
///
/// x * y = p0
///       + (p0 + p2 - p1) * b
///       + p2 * b^2
///
/// Where the three intermediate products are:
///
/// p0 = x0 * y0
/// p1 = (x1 - x0) * (y1 - y0)
/// p2 = x1 * y1
///
/// In doing the computation, we take great care to avoid unnecessary temporary variables
/// (since creating a BigUint requires a heap allocation): thus, we rearrange the formula a
/// bit so we can use the same temporary variable for all the intermediate products:
///
/// x * y = p2 * b^2 + p2 * b
///       + p0 * b + p0
///       - p1 * b
///
/// The other trick we use is instead of doing explicit shifts, we slice acc at the
/// appropriate offset when doing the add.
fn karatsuba(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
    /*
     * When x is smaller than y, it's significantly faster to pick b such that x is split in
     * half, not y:
     */
    let b = x.len() / 2;
    let (x0, x1) = x.split_at(b);
    let (y0, y1) = y.split_at(b);

    /*
     * We reuse the same BigUint for all the intermediate multiplies and have to size p
     * appropriately here: x1.len() >= x0.len and y1.len() >= y0.len():
     */
    let len = x1.len() + y1.len() + 1;
    let mut p = BigUint {
        data: smallvec![0; len],
    };

    // p2 = x1 * y1
    mac3(&mut p.data[..], x1, y1);

    // Not required, but the adds go faster if we drop any unneeded 0s from the end:
    p.normalize();

    add2(&mut acc[b..], &p.data[..]);
    add2(&mut acc[b * 2..], &p.data[..]);

    // Zero out p before the next multiply:
    p.data.truncate(0);
    p.data.extend(repeat(0).take(len));

    // p0 = x0 * y0
    mac3(&mut p.data[..], x0, y0);
    p.normalize();

    add2(&mut acc[..], &p.data[..]);
    add2(&mut acc[b..], &p.data[..]);

    // p1 = (x1 - x0) * (y1 - y0)
    // We do this one last, since it may be negative and acc can't ever be negative:
    let (j0_sign, j0) = sub_sign(x1, x0);
    let (j1_sign, j1) = sub_sign(y1, y0);

    match j0_sign * j1_sign {
        Plus => {
            p.data.truncate(0);
            p.data.extend(repeat(0).take(len));

            mac3(&mut p.data[..], &j0.data[..], &j1.data[..]);
            p.normalize();

            sub2(&mut acc[b..], &p.data[..]);
        }
        Minus => {
            mac3(&mut acc[b..], &j0.data[..], &j1.data[..]);
        }
        NoSign => (),
    }
}

/// Toom-3 multiplication:
///
/// Toom-3 is like Karatsuba above, but dividing the inputs into three parts.
/// Both are instances of Toom-Cook, using `k=3` and `k=2` respectively.
///
/// The general idea is to treat the large integers digits as
/// polynomials of a certain degree and determine the coefficients/digits
/// of the product of the two via interpolation of the polynomial product.
fn toom3(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
    let i = y.len() / 3 + 1;

    let x0_len = cmp::min(x.len(), i);
    let x1_len = cmp::min(x.len() - x0_len, i);

    let y0_len = i;
    let y1_len = cmp::min(y.len() - y0_len, i);

    // Break x and y into three parts, representating an order two polynomial.
    // t is chosen to be the size of a digit so we can use faster shifts
    // in place of multiplications.
    //
    // x(t) = x2*t^2 + x1*t + x0
    let x0 = BigInt::from_slice_native(Plus, &x[..x0_len]);
    let x1 = BigInt::from_slice_native(Plus, &x[x0_len..x0_len + x1_len]);
    let x2 = BigInt::from_slice_native(Plus, &x[x0_len + x1_len..]);

    // y(t) = y2*t^2 + y1*t + y0
    let y0 = BigInt::from_slice_native(Plus, &y[..y0_len]);
    let y1 = BigInt::from_slice_native(Plus, &y[y0_len..y0_len + y1_len]);
    let y2 = BigInt::from_slice_native(Plus, &y[y0_len + y1_len..]);

    // Let w(t) = x(t) * y(t)
    //
    // This gives us the following order-4 polynomial.
    //
    // w(t) = w4*t^4 + w3*t^3 + w2*t^2 + w1*t + w0
    //
    // We need to find the coefficients w4, w3, w2, w1 and w0. Instead
    // of simply multiplying the x and y in total, we can evaluate w
    // at 5 points. An n-degree polynomial is uniquely identified by (n + 1)
    // points.
    //
    // It is arbitrary as to what points we evaluate w at but we use the
    // following.
    //
    // w(t) at t = 0, 1, -1, -2 and inf
    //
    // The values for w(t) in terms of x(t)*y(t) at these points are:
    //
    // let a = w(0)   = x0 * y0
    // let b = w(1)   = (x2 + x1 + x0) * (y2 + y1 + y0)
    // let c = w(-1)  = (x2 - x1 + x0) * (y2 - y1 + y0)
    // let d = w(-2)  = (4*x2 - 2*x1 + x0) * (4*y2 - 2*y1 + y0)
    // let e = w(inf) = x2 * y2 as t -> inf

    // x0 + x2, avoiding temporaries
    let p = &x0 + &x2;

    // y0 + y2, avoiding temporaries
    let q = &y0 + &y2;

    // x2 - x1 + x0, avoiding temporaries
    let p2 = &p - &x1;

    // y2 - y1 + y0, avoiding temporaries
    let q2 = &q - &y1;

    // w(0)
    let r0 = &x0 * &y0;

    // w(inf)
    let r4 = &x2 * &y2;

    // w(1)
    let r1 = (p + x1) * (q + y1);

    // w(-1)
    let r2 = &p2 * &q2;

    // w(-2)
    let r3 = ((p2 + x2) * 2 - x0) * ((q2 + y2) * 2 - y0);

    // Evaluating these points gives us the following system of linear equations.
    //
    //  0  0  0  0  1 | a
    //  1  1  1  1  1 | b
    //  1 -1  1 -1  1 | c
    // 16 -8  4 -2  1 | d
    //  1  0  0  0  0 | e
    //
    // The solved equation (after gaussian elimination or similar)
    // in terms of its coefficients:
    //
    // w0 = w(0)
    // w1 = w(0)/2 + w(1)/3 - w(-1) + w(2)/6 - 2*w(inf)
    // w2 = -w(0) + w(1)/2 + w(-1)/2 - w(inf)
    // w3 = -w(0)/2 + w(1)/6 + w(-1)/2 - w(1)/6
    // w4 = w(inf)
    //
    // This particular sequence is given by Bodrato and is an interpolation
    // of the above equations.
    let mut comp3: BigInt = (r3 - &r1) / 3;
    let mut comp1: BigInt = (r1 - &r2) / 2;
    let mut comp2: BigInt = r2 - &r0;
    comp3 = (&comp2 - comp3) / 2 + &r4 * 2;
    comp2 = comp2 + &comp1 - &r4;
    comp1 = comp1 - &comp3;

    // Recomposition. The coefficients of the polynomial are now known.
    //
    // Evaluate at w(t) where t is our given base to get the result.
    add2(acc, r0.digits());
    add2(acc, (comp1 << (BITS * 1 * i)).digits());
    add2(acc, (comp2 << (BITS * 2 * i)).digits());
    add2(acc, (comp3 << (BITS * 3 * i)).digits());
    add2(acc, (r4 << (BITS * 4 * i)).digits());
}

#[cfg(test)]
mod tests {
    use super::*;

    #[cfg(feature = "u64_digit")]
    #[test]
    fn test_mac3_regression() {
        let b = [
            6871754923702299421,
            18286959765922425554,
            16443042141374662930,
            11096489996546282133,
            2264777838889483177,
            504608311336467299,
            9259121889498035011,
            10723282102966246782,
            14152556493169278620,
            3003221725173785998,
            12108300199485650674,
            4411796769581982349,
            1472853818082037140,
            3839812824768537141,
            566677271628895470,
            17571088290177630367,
            4074015775889626747,
            16783683502945010460,
            3672532206031614447,
            13187923513085484119,
            7867853909525328761,
            12950070983027918062,
            16468847655795609604,
            16236260173878013911,
            13584046646047390182,
            3459823911019550977,
            852221229786155372,
            13320957730746441063,
            15903144185056949084,
            17968961288800765765,
            3314535850615883964,
            11164774408693138937,
            296795981573878002,
            13439622819313871747,
            975505461732298298,
            6320248106127902035,
            1292261367530037116,
            5457288991919109645,
            9156327436088586665,
            13214259773135401786,
            11894959382522647196,
            7347087210697207182,
            10866433221888385981,
            11517455022886216566,
            16002875401603965132,
            14910152116859046022,
            13121658696980417474,
            9896002308546761527,
            2508026143263419489,
            5630957157948330915,
            14741609094906545841,
            17816841519612664975,
            7969630003685849408,
            155645440736526982,
            12636207152988003561,
            11423906424129622745,
            7683636929614516252,
            18373475843711518761,
            12517632064609218689,
            9229683610001203481,
            7466784812824133107,
            669533494937267490,
            5082436863236123102,
            13002655060148900023,
            13744987998466735055,
            11291793723517314998,
            13019038669516699882,
            16709997141197914794,
            5635685992939170942,
            11675574645907803567,
            4594226142456014804,
            16573646927735932410,
            1485870256663971571,
            15846713039191416692,
            6268579197046091479,
            4148711486149996258,
            12289594343226957541,
            7248423051711675098,
            11690743363052255577,
            3624472201995805474,
            8537222754743368136,
            9139752523777531093,
            10332892792833338770,
            7037635035632196817,
            4496405835920050629,
            17391917705588355794,
            14117717411488825371,
            5230286663558119879,
            17825506019213671261,
            17404129971477111108,
            11521727676625909194,
            5238690179323183699,
            5727780062420810465,
            9632453973638740648,
            337811100863346570,
            13073228541428212927,
            17709844765172234384,
            13208921325370991444,
            5431840578699639395,
            17077925307816799261,
            7209340156697508529,
            12028994618496870845,
            2544500160865141031,
            11649654461126310578,
            9365483541048471688,
            14612538420978379687,
            9873239918327058306,
            1157472058577394095,
            12375928197270581863,
            11259024417929344257,
            3285662610711925103,
            1050951962862248344,
            13573242938330525645,
            6481773409427626042,
            16024681689552681567,
            2220783933082287757,
            8929560899664301451,
            64015232882626853,
            11408281661939521111,
            878781900624570608,
            9905479987547252164,
            5731582277472653511,
            17783362590834199727,
            13132721837581513886,
            11245310560513633279,
            7644137013939043642,
            13922828459616614595,
            448705611699584512,
            11371313753562743476,
            1574633155961622201,
            2301463292785650126,
            741402366344950323,
            14185352113401593236,
            9211130877800459742,
            11565822612758649320,
            14182824194529562358,
            4341494334831461293,
            15108767488023246095,
            4205441133931479958,
            17825783968798375241,
            5574097067573038154,
            16531064653177298756,
            17267304977208102577,
            928672208065810133,
            8205510594424616558,
            12543833966918246257,
            86136389231850233,
            16025485094311428670,
            5207828176013117610,
            13359327193114550712,
            2794955638345677576,
            3993304349404239314,
            4994255720172128836,
            7135313309521261953,
            3325716756157017100,
            4584134963117073140,
            88101658911197316,
            3369567695997157158,
            6461054377325416109,
            17386668567122758604,
            3597625436035211312,
            18145298865089787176,
            11816690578299880852,
            7452950893647760052,
            1177645126198066735,
            10342535382097449475,
            598208441320935865,
            12921535255416124667,
            13109196922707708559,
            8670507722665163833,
            17373614756345962119,
            3224893480553906007,
            14808009166588879477,
            14704014108115963684,
            1462864287248162745,
            4880369798466033386,
            6588737531985967098,
            7946857775405689623,
            12748319198997944814,
            9326770283997092048,
            17003595393489642565,
            17484594608149336453,
            4190950067408592109,
            17824678462034741067,
            15702236130638266509,
            5273424187690232454,
            12023318566452513739,
            7102078857285715052,
            4369802176505332167,
            10699689773538544377,
            730467711008420891,
            10262119215370320651,
            6690738779737159913,
            10562916257987913949,
            14972385366243262684,
            17611612385937387126,
            14205605578073512987,
            8713489693924424056,
            16616344708337664878,
            16742234424573023464,
            2902884815897074359,
            9156119555166935389,
            9080622094288708744,
            3581449124220285742,
            15398432395479402853,
            6362303494565643898,
            15212154657001712988,
            18252754350443257897,
            12244862614504808605,
            8814921661269777610,
            5889164750855440803,
            13877154483979742237,
            1975853494990494526,
            1453591120623605828,
            1561842305134808950,
            4104017706432470283,
            18374510210661965759,
            9803038902053058582,
            15551403297159148863,
            16533913772549484823,
            14544914922020348073,
            10919410908966885633,
            17470299067773730732,
            11601114871272073512,
            14664333496960392615,
            13186665624854933887,
            14081619270477403715,
            4675338296408349354,
            13005625866084099819,
            9826340006565688690,
            8509069870313784383,
            11413525526571910399,
            6807684484531234716,
            4618621816574516038,
            4883039215446200876,
            5183393926532623768,
            10445125790248504163,
            8703300688450317851,
            1810657058322023328,
            13343323798867891831,
            1114348861126534128,
            13117683625674818191,
            6927011828473571783,
            3034582737565944267,
            4121820627922246500,
            2068319599019676600,
            4767868471095960483,
            2803257298179131000,
            9209930851438801799,
            18163819238931070567,
            13128522207164653478,
            18335828098113199965,
            8486377462588951609,
            3277957111907517760,
            2754092360099151521,
            8933647340064032887,
            11308566144424423461,
            8932492907767510893,
            17676321536634614180,
            10916845309604942594,
            1541736640790756953,
            6693084648846615663,
            2461388895988176852,
            18262736604025878520,
            15216140684185826151,
            3888640441711583463,
            14630778656568111440,
            3821930990083597884,
            6592159409049154819,
            5773800580147691268,
            14025025753393817356,
            1143462425860692308,
            7310246890521674728,
            12759899287196682624,
            17074850912425975309,
            13639540485239781443,
            11594492571041609459,
            8086375866615071654,
            2458700273224987435,
            14188836372085884816,
            14151374325605794048,
            12856075220046811900,
            17507597135374598747,
            12763964479839179724,
            3365341110795400221,
            13808931773428143133,
            17033299610882243549,
            18227238137056935396,
            14979713927050719147,
            4275831394949546984,
            8603067650574742183,
            15568230725728908493,
            2983251846901576618,
            4855005009090541140,
            8978290455364410739,
            7585912958100257345,
            7889636089238169609,
            6157281389499351077,
            16013269622819602387,
            9224246297875214668,
            4138161347252674082,
            10318658241432357882,
            9402564329926365826,
            17394083647841321487,
            4542513014713923099,
            8667322649378182890,
            576180375143955900,
            18021784748061793599,
            13203834948982480414,
            13904284351856275257,
            4244818956425434151,
            1076055980570550161,
            2674096971027047948,
            104304434704934006,
            2062855556986682483,
            5786781659542854036,
            6853220200637113363,
            9593939255297136609,
            1066166708380361418,
            14725348327737457961,
            16150748104690835108,
            17931164130540362944,
            18218341517410521707,
            6187428325833810419,
            9690875880801108718,
            5756353469528306968,
            2503319654515164798,
            13274927231487272946,
            10638128257539555489,
            5896639022976119702,
            15161011556181302784,
            2677346843481863572,
            604789272653420187,
            13360196803831848409,
            10012996491423918567,
            5044454426037856014,
            10524057648033789107,
            5649671761089989854,
            7387534256772100838,
            8924072651833780120,
            3785979389901456766,
            2050691721810266829,
            15376099431140621558,
            17511662813348858473,
            12,
        ];
        let c = [
            13147625290258353449,
            13817956093586917764,
            18028234882233861888,
            4293751923287888052,
            14564141039952372119,
            2676734207017121597,
            6459642599270298327,
            10514787163962869530,
            3464485178085199795,
            11257474764035059331,
            12181451147060151288,
            7771786629160476887,
            5728497381328758601,
            5895875676429179638,
            16679607158645743277,
            10404047442430847790,
            16582081384308902247,
            12490779806977231913,
            11404651769234278221,
            17022469412583392578,
            16439338230633175949,
            1063962396022446422,
            4870572923632948252,
            10243077795083132155,
            17682233381781162062,
            3717510388192897304,
            10472572278890160024,
            4405755291195612194,
            17627642736326682742,
            15119177646289231784,
            14667151155773252610,
            1618000287928404571,
            13586901368491466481,
            9480801770542358210,
            11591874296843194205,
            8397058357928253365,
            578589728443805743,
            1598611175229035508,
            17769761727743406958,
            8701373647057001365,
            3491199179963360183,
            14734752687818620066,
            5882881716069715431,
            17867956461647398152,
            14317425986826618884,
            3190976033715157155,
            16025482572482863452,
            198303002951605721,
            13239788634860069155,
            9176490930959914357,
            13789370614942093263,
            8719316129258342716,
            8953451100830410047,
            5127100131850962987,
            5042215589496218651,
            12195935831432585004,
            16271477124635191788,
            17042607302458382021,
            6909951113544811251,
            15867944577589614763,
            12869536415455501541,
            13449373980179917814,
            5429607781375702916,
            14690315137615067697,
            6423399543123234984,
            15319364673671319937,
            5766347079728187383,
            9497305192864606751,
            2186351927817601391,
            10726914960258697501,
            6088420666246691919,
            1588440693016474445,
            2604959928768677511,
            17616186617681342252,
            10535006669694135493,
            13489006267185033075,
            15502143361666125994,
            16502406772857573234,
            10575734691312906463,
            10716474667815258981,
            9710545289905473439,
            3854962820702807947,
            5378807396667958578,
            12445857039679749013,
            3960937645922969357,
            9829760523341564006,
            9212167324275861816,
            11422368668113634154,
            10684460016299893830,
            11389419764702616711,
            3899200183251946009,
            2093729712958211017,
            8420392268215053797,
            6398774523536552388,
            10852749009148352925,
            5289144597498232565,
            17703908865205386695,
            6907742189144573057,
            1784946329061543285,
            15480049270321874965,
            12069121519676878616,
            17812799898774546955,
            11948193027013007431,
            3884323573006797139,
            6847241152178866159,
            12199935709218616587,
            3955204591920032162,
            14878266626017125196,
            7278030477420395848,
            10161863746736807272,
            9207356190672684457,
            4601854808843007498,
            6775986836344704023,
            17288427592206154151,
            484532203475900068,
            18118416415768866724,
            6355480490988086744,
            3208810669246831205,
            13957974139288542819,
            8396394607132645103,
            15228026780031354119,
            14498855337604982920,
            14141161076130564520,
            6588603191636571246,
            3999628253355964982,
            575393068537655797,
            5657615255395137815,
            5633326538404084103,
            12326562882758080143,
            3543480102419886151,
            6824968844300019651,
            3267458303116092202,
            6237792365531735545,
            7469544494204334597,
            15133093961814251253,
            6772265097243462865,
            5750218230297679586,
            15133043154817660619,
            13838897645290708193,
            1698455434074605058,
            1416851634747812455,
            1433730608162832030,
            4396199899836953731,
            11478281064341415007,
            1199305835874995069,
            12461220549480843598,
            3786960620800323764,
            1359737533861421574,
            5683800489224722555,
            580114063914071460,
            3757480794795278521,
            13350893050786101167,
            5864294767515313613,
            13667186506174093283,
            10644721863115106069,
            4089596839694426493,
            837360057072705787,
            14661298745941209853,
            3135603497841243154,
            8588389252943247567,
            3180539906709497729,
            9920619693463058306,
            4532986872992016572,
            16671485218531724914,
            16237535739330707258,
            3392767051844917712,
            6253243888910507007,
            6138565275365265434,
            10788645409322247025,
            2998545083522261349,
            4393635535422254464,
            162283948928616560,
            6581058835892498610,
            9044842225211179928,
            3359587585025090294,
            4774711746392882472,
            12671200872687548503,
            5910134937871058397,
            5003751340241222878,
            4967360099981268641,
            8911591385760571590,
            8159270265734967930,
            5250229866305601451,
            9551428753943119262,
            8689322272982432960,
            10836071047039045386,
            17213966296648357737,
            9670979912487313863,
            8149443095351359584,
            5882663205147794724,
            1077285439953280724,
            9538056828068584607,
            6534627272003475907,
            4182635403810470796,
            4332023173746385204,
            18043427676849450827,
            1544903479164552030,
            12808718740097386201,
            4743835518042863198,
            17533308810746778943,
            2436162195122352530,
            13717567738827779707,
            16498190890660698054,
            8446479819925879748,
            13026080039828457667,
            10242288816864319380,
            16805676933455246691,
            8854224454209663170,
            12881936897446363181,
            14318173900990076031,
            17263412233699302472,
            1175398600063038674,
            12303198178060136245,
            5262693362410688618,
            2449023658743880786,
            7851992903947432349,
            15279972405631504407,
            12782492794198106006,
            454161448971247291,
            7208428618685987862,
            2808315703288943474,
            15547213201445152112,
            4195163971319471362,
            5077844356227078783,
            6228496807545876867,
            8018540845186766480,
            12802276286029182659,
            17873658985235511282,
            405964923119895900,
            17005602789111483415,
            15323511615180015542,
            3777673967701314271,
            11241595450806936514,
            18094205811239804553,
            4945226306748157777,
            13126826405187610008,
            18401109742831785725,
            12038829763881934869,
            6883152103015744232,
            6888604044125585130,
            10327133149324643136,
            9786783078753767897,
            7728244798165310883,
            13992043126602427065,
            12760431374402895816,
            10556094269445313552,
            370205722038466820,
            2237385387127770787,
            3008501418666326571,
            2147796682874314438,
            11177403945853274771,
            394056223101551114,
            17534487287334816941,
            881808126732102067,
            4246224751203270716,
            6113128358498682501,
            1188932545968905738,
            12765644408650990762,
            8081000787691948556,
            648553016175951475,
            13679613339055618508,
            13341452083201419987,
            16710796306331641196,
            14950547258962926774,
            5807411999567421647,
            51486220608905397,
            11495154677696979138,
            9566551468999057159,
            9404650285252518485,
            15936039807347909292,
            9926926746640651811,
            8137529358194870999,
            8409600195382297763,
            7353893979385221928,
            13160302875690198406,
            348690545671757035,
            9037218723869788888,
            17926585726505969574,
            10803900675631258757,
            6393072209298283246,
            16096417936354328220,
            9646360537089934694,
            13770356122351384928,
            16836674286434938459,
            7541946872500761286,
            9048263944605955661,
            16780366954521256652,
            7343863344205297175,
            12789916470639650059,
            5777346297355673119,
            3199552193495347726,
            12230742086629356177,
            7003231206534047938,
            15090957803858528744,
            17037481317622823117,
            3297597585907869563,
            2697945267713108093,
            4292423210234323248,
            3611346819357503037,
            7143735793987221927,
            7192307513286386565,
            17787283681233014873,
            12357966577423097448,
            8897136197269501397,
            11902132993155439534,
            3134549357805042842,
            13190859350132812532,
            2953055179222338302,
            14072479035614746298,
            623716608321502842,
            13012840714155111804,
            9113471173003784658,
            3832090523063788219,
            11686697139180356613,
            9220715948534448005,
            10475815552871271805,
            13316455608734752259,
            3256936992714735238,
            11886029809711683060,
            1154889652278063077,
            2634050492458919284,
            15799574960065328453,
            4854385868907776158,
            4308561300452445774,
            18158501743185507870,
            494961281052444285,
            13230103283989646999,
            4290343182499439317,
            2897833401622123527,
            1828737779143272347,
            10192978009672844498,
            10197386440201448306,
            16716143215455134742,
            15610114368473665198,
            6236681643047286973,
            12762824210749799030,
            10807635853279558353,
            11353446277082394704,
            7511532745578783402,
            7171399474829708082,
            2443271458861652456,
            18046286184730984000,
            1631291998347686895,
            5333915858453483562,
            4279428177587669193,
            4079835446959802508,
            14290782115827722683,
            6259655031577342838,
            14581460384506564304,
            235151974716865360,
            2375317628907755058,
            12458887693759984881,
            2860995391934282660,
            17774376172142139929,
            17358804008079603231,
            2216198936056406536,
            2563098348647162202,
            774854408223515953,
            12219835071659426404,
            2185427726156502437,
            8977240783566213019,
            10950053189740163780,
            15333460456641375067,
            15414859166425218506,
            16627722666231706432,
            14933789823667915188,
            7893509177447272752,
            5576840844608359783,
            9639046067346127903,
            6034870669926683205,
            11074229566077202561,
            7734172323678793750,
            1797022077506253706,
            4175135546481691973,
            4576531916446872861,
            11073018132808499885,
            9004329344974888991,
            2579957018554908013,
            16723993098086799559,
            8849326108645639933,
            1190731350374367414,
            15196122081549855262,
            16510124270150231915,
            1447369806052266158,
            1774117429703831561,
            3272947319047150592,
            6086749417328134594,
            114186026684487132,
            15881404973090653236,
            9002767864228350415,
            8632935895349074342,
            14189358814161984679,
            7273121617103693424,
            3720897725211288407,
            17385088912598509226,
            17763377168623207811,
            3011652710253791434,
            13026181299902362083,
            7673465031457219376,
            8976686724731444924,
            1602632530339248239,
            7322563236300692731,
            17611256894860100558,
            6585524259854016494,
            13024412741537787009,
            6490348356225390820,
            10475028766694832415,
            4171072186129163678,
            8067851189059922503,
            13321938328018146758,
            2388045447565404129,
            12628485341454603822,
            10515272459175323665,
            5141134415272454070,
            15533371382800133770,
            5089921040728608575,
            9922174346147797518,
            2286765044618595826,
            458550603008652679,
            1895551360015713043,
            17608310488293104847,
            3041900727372287447,
            14788640656316180904,
            8006597265367839623,
            6172940096066506343,
            5001938689099706064,
            11456390799634570508,
            58114059478872995,
            13813208350157959983,
            7192129467061995988,
            15458065357391712248,
            1184709156376072909,
            4997369113101583984,
            11962098224621896302,
            15957925570647432972,
            9768648025404723859,
            16066042591100391809,
            14826843103086137650,
            15530089295707983043,
            14757548535314259278,
            12272651610971114578,
            11815510217344882354,
            7863174743199280885,
            17755545598189623361,
            3623688651342862124,
            846900727574364473,
            4058087733004472364,
            9766249185594229219,
            8203083537227057882,
            2514240782116496856,
            13013220914916706232,
            7479093476304703557,
            13599783865226501576,
            15101635775647230555,
            7679618582697439061,
            3809012502593902516,
            17181248094867317535,
            9184314850829556852,
            17135643679321121988,
            16551911434983848191,
            16563989164660839146,
            5244550954203347299,
            7468243134930758384,
            13848792956096067953,
            299147213373350316,
            4234339785402518959,
            8316379046881991503,
            15054498767105089317,
            15245345469072520312,
            169003686610660574,
            8905168983426000291,
            14079614647232314662,
            10677487605853621326,
            486644500614977963,
            4315204642211280928,
            13378617481135356106,
            17475120936205263193,
            7054688890001081620,
            4890150051524335365,
            16929286679364707850,
            12404641144465776093,
            85729750914301011,
            7518958607192096844,
            12335244912121726376,
            441058371959341821,
            15283845211776523277,
            11365329781782022447,
            7176368314974115909,
            13402576699022366440,
            9612930864140895738,
            1551492131293754732,
            15625022379217650131,
            16853815349026997223,
            10176564334158763844,
            11561712818786302756,
            10721760754726884570,
            16211944886847212142,
            6455169008048578331,
            16442277863996881453,
            11966295676197364531,
            17131994341597087852,
            10178415200084263095,
            17241579229376875844,
            16595331811574273072,
            15514521091896721175,
            10273857151649071793,
            16902595879470117012,
            17044001876395421463,
            6241464946584582238,
            6948336526969806585,
            618342450528567894,
            11266394538973042131,
            13911827545633749019,
            5770757761516661921,
            4237426824475464361,
            6137903415464019236,
            16948218557528241218,
            13342541955783637763,
            12228044034020334487,
            3753346696590480376,
            12798240801313956988,
            16337512518975517925,
            17029293450980009677,
            17889170535515757468,
            14215875855934760379,
            6048723980155309955,
            7751681766991188778,
            9324053942011976933,
            6806752775473648551,
            16491946688185935526,
            17973734037621739928,
            16521618754491099078,
            15814146101747955693,
            17072736172673770992,
            560386638362049457,
            9315742694497383404,
            14003511454248083195,
            505571467191783211,
            15321198489161153019,
            67644988835003625,
            422740534693308350,
            1588696840338933253,
            17633924999495432514,
            3578955538397900717,
            4350434105925504139,
            17520065248429114920,
            15948482628426996406,
            16339123994002177423,
            14962340825416078820,
            16377030826129395507,
            3728945733790793859,
            14040902081706983834,
            6245445984351877668,
            15109200712778355913,
            6876007592769255303,
            2817332194593868297,
            14642462812181536002,
            13241495844336600578,
            17508429190834543309,
            9979949640512203943,
            11024829646351554638,
            16593085213286597946,
            3786341713932228381,
            4854315828914728926,
            4226218666904293494,
            8427728822561673998,
            7350284610946156715,
            15819368048130139112,
            8256096529517474967,
            3164838434037013186,
            7181083254407808229,
            14392138511139873518,
            17742848920305479369,
            14254286401886846925,
            13172848038012405804,
            203991661409228704,
            12155338881267997435,
            15596778231824136139,
            4270398294351523748,
            841800590896491878,
            1324356347939565174,
            1635131684701069722,
            9402955035355081296,
            1217032459175096228,
            814223664322441499,
            15135019617633870019,
            12555639443566847383,
            11065144808269184833,
            1793647298364803083,
            744335551991850623,
            8586945353992422223,
            13891984397850330431,
            13168278299568698045,
            2545505069878626309,
            2345784529656940996,
            11238050768519698690,
            145002862188778047,
            14056901992927566251,
            7146776997541924640,
            11964908621390755985,
            3287082359454318848,
            7997294085866872179,
            5423940255508089295,
            4669857898097690050,
            11333522019809124025,
            7524197645486269287,
            17976672080799403364,
            9172262822040915360,
            158857927726516306,
            7825225378554946108,
            9418576621795701508,
            7633907046040364747,
            18268626574958706065,
            3209003992606419777,
            16433724431228669029,
            11533879023784257295,
            7352494819227083416,
            9550528667280588513,
            17649577381405647635,
            3464121828599745965,
            10524312096092076686,
            16298229441805025435,
            12299501175855694268,
            5234483534956328223,
            6842998262033517680,
            3405412371253551971,
            12961834222487484113,
            8329667703663634728,
            10113768572787795201,
            437973618905269097,
            10518227023647484735,
            15505971298645719880,
            16080360285628075895,
            3253079608258240664,
            9442135189206070131,
            2620029667482460392,
            13058843258931508372,
            13398588232276089878,
            2013946258885953106,
            2777554235294156890,
            7727335788600791403,
            64926713702036664,
            7017058603665827477,
            3038023548514697220,
            1884676627569135536,
            11691207067273431143,
            10072076283563998720,
            13307639350090691756,
            16097417013067765232,
            1046820113070464713,
            686419524967082232,
            16868023154965697840,
            9866592207237669169,
            434426218272207007,
            15594721674408845443,
            4951793482938178894,
            5328839429244804401,
            6948444829657740645,
            1250147824386974181,
            3550991145492617480,
            6903375020760383265,
            5556228127567021487,
            13761117792143803710,
            15185125920584997092,
            8186466630413736182,
            4802907899488331586,
            15305034246197656170,
            15396976225074357341,
            5898890255224717338,
            3615484144772658086,
            18255788598509486615,
            224652660554020763,
            13466057775273969203,
            2077408507156283322,
            2342023270473665603,
            8947077544711176259,
            5306736138640896482,
            4480826977335219320,
            3788577265714804046,
            115308722462922151,
            7375990846913556901,
            11736854490599587323,
            5076771704562414238,
            15553536672697466685,
            18090905433616951399,
            4188493781910494747,
            15181059585004440209,
            12728148632534416192,
            6722182881759806025,
            13780369372289967994,
            3732668177228110489,
            3787487561117269614,
            5162113090068803421,
            4321209401054627716,
            5448669100032977354,
            18291843216134979053,
            16776289611211531598,
            1885119013176564798,
            9819767057810457229,
            9641605351052741528,
            15675183391486745167,
            7616169275030402931,
            15993936796479971901,
            9454285932998973051,
            17536483736707322645,
            13392933552816987057,
            8637439302534754550,
            540899472066855809,
            16629709388332749089,
            13733105412819355808,
            14746175220939553318,
            2846952298407666021,
            2891977601791383828,
            5696908477729602226,
            11016605210700034776,
            16941067307488182843,
            6211355506521287507,
            16542299272345996744,
            3303613293413685324,
            1629768918920532660,
            4206151598734336232,
            8856046512946232478,
            4907901964445375077,
            14400940791045719898,
            6525037265010054850,
            2845928272349757088,
            15487802580883373670,
            9169720274701972562,
            5985973322812415499,
            13260753279459456665,
            17130834352417810395,
            10504159994735949472,
            3619665201800936886,
            6177405351801242874,
            17314717210185132120,
            10635416390598362752,
            3965067791232986010,
            4137222868235076149,
            7349861099139148757,
            13855902416442714188,
            3758295764877447132,
            2127539446373659348,
            7398648921373235157,
            10530977609779069122,
            2057082983915369887,
            15095469010920249805,
            1580580744862861737,
            1385280835524895944,
            3735648750536184988,
            13975651103105108932,
            12560143273028504000,
            213932257778062629,
            14025207273678863547,
            1676558185650908917,
            3681689509396718388,
            3722143195009944583,
            6372328340754588443,
            10661271971253598404,
            12865667632468835094,
            16100956261366638373,
            11045168180887164035,
            5967989014180680940,
            15635382253084283895,
            10672630067495824386,
            3671716856885117446,
            10087953011045522378,
            12966649859522423914,
            7760990551799493049,
            6773507642155574420,
            14320444088036226729,
            996203594183873620,
            6192894784937493039,
            4156453068089966167,
            14572012258150145006,
            12694436615363442069,
            9393452532594598725,
            7073980584197012440,
            3092044667654940896,
            13855475386227226214,
            4309098798809069243,
            17846796523885690871,
            13567621519152235542,
            15083768013978066571,
            4928428566683275123,
            6358144983716124065,
            5815136002584686049,
            8730978481571655079,
            7899439375250672635,
            14524588032253020995,
            9810453005255777832,
            4283615174004546182,
            4910404083022612904,
            5889820858976629278,
            16526481241932287977,
            9532234053410906113,
            12393033057707332749,
            12925587840306057080,
            10366100576119055483,
            6171980884320519881,
            6370785275483681135,
            8381526621841046029,
            5551091520919536756,
            12950765990114654837,
            6451545362694246818,
            212258237904426316,
            17609333615515129459,
            16595363338989541409,
            17025961636346735400,
            10271948129080248406,
            10944228647786476233,
            5467386369086945871,
            1304225602762032822,
            16166120916726245386,
            9432487283289925931,
            3403761315752290587,
            3141021554091328928,
            10971462138407674348,
            10105449417179637906,
            3942240849395932405,
            10366411633985305351,
            659554731028325691,
            17091333474944352463,
            612319979868231629,
            17382969496671106101,
            3825928121744631575,
            6919629698697448941,
            3047982536888198540,
            8582263155177383434,
            10489954932217807453,
            18043360586501370656,
            16839643971175241779,
            3859513000284354780,
            10803271797516731820,
            8797248475477069569,
            4834788502968724109,
            10636072941935319265,
            15738621943484162587,
            3646521574321304278,
            16944083908124496190,
            16148256726139579321,
            1609665271498664710,
            1362054633058989594,
            13973388908791057772,
            6345006526009146382,
            2518534936752010021,
            659541823645224189,
            10968167928774784973,
            7543306179097411926,
            9456023891569360398,
            5349741969482277027,
            8323748029139171407,
            11280182066584422642,
            3780197930314489144,
            11850380628777309039,
            9657986102535984497,
            5218157717868740572,
            7171503646973777516,
            5852967071087962442,
            17762051133445851451,
            13539879275779472444,
            10231713150096078048,
            13415553313620113202,
            12765372888710309095,
            15057130630522842392,
            14677710651300800748,
            10692853438748252520,
            12459043459128327446,
            2895873908250910074,
            12414654299833871003,
            13971031683534816634,
            13847640779080634026,
            217295692307502497,
            7750768797035502178,
            290949611993301720,
            10199100136702866567,
            15495972441839001396,
            13198452434198427151,
            2440498893626898052,
            15118747988064647069,
            6537279940542355961,
            8712445311047767491,
            17256665922722282910,
            13175508019793567143,
            10218901675074990248,
            13394299990216654516,
            5977932445410319532,
            5913587457706598533,
            18017099150205847183,
            10803505436178917593,
            15504988698835663005,
            11647690777417283778,
            13263578958104628128,
            6887980138658259663,
            12615506930751501449,
            4362286963260481429,
            17936849618704425417,
            8369687071549056310,
            6873677162393948122,
            8962347665252911678,
            6575009038253218272,
            17049757839609406426,
            18000487384002665628,
            17743261078931639159,
            7069552289073828088,
            2053907584370525129,
            6092754463992814730,
            7835970278896264421,
            8747049071648962742,
            9020604727379960828,
            9632547032149786788,
            16485371852605585328,
            589786022609761499,
            14198172759212036212,
            3179321442557148353,
            9275833134889979290,
            4203798446932368841,
            1997647913473930975,
            2518811456650703083,
            7750350188524367372,
            8204413870688842329,
            4683962365740774568,
            1038502292158797902,
            416255872857165019,
            89452159243564340,
            5029544632341923837,
            9006839419087725471,
            6081309378730152882,
            6841819644499887187,
            1989550502574820483,
            13603604083811099797,
            17579259537599657917,
            3688889816642246075,
            8365081349347412069,
            9781470991802711607,
            5096192245902990289,
            1498837910524874201,
            8053001241713783407,
            13235502474453488717,
            14236495286020360865,
            1736617016599872719,
            6171162219819586226,
            10365771078075021733,
            7005440335994057913,
            15987156790865471266,
            6743350458772878812,
            13939320505807395210,
            18411835973679513875,
            14557893705645834250,
            11183480228569397732,
            2863370600396906941,
            3249734688507432577,
            10075558144505269497,
            2962113710307186842,
            14006648851316589492,
            7556865444223108417,
            16635752120601038989,
            2805784706247063393,
            1921256089647591677,
            10043101807995880550,
            17183135665189377543,
            15209331403547677849,
            9759674000009984076,
            6188634504854345563,
            17429444123311113173,
            12716643325990854245,
            4404673046468281426,
            14977242545159900045,
            2353738321397058672,
            2217587216444012952,
            17848724221428205646,
            7788107721465269627,
            4209425388750317735,
            15986838006612180795,
            10448760854792387460,
            2181718159289817159,
            10626737123343057134,
            8531679111527745250,
            2221563690578844859,
            7279790679521017728,
            10678979618998152285,
            17119267278437855914,
            14741366633087203734,
            13977821575914403172,
            13984542610460459828,
            17859323614174580751,
            8221319720268548319,
            7448166339196439012,
            9427945230078429775,
            15205875846647517591,
            16806327021489489097,
            3923284971739738878,
            8300291583515256892,
            5684696181844315010,
            4112709175543117372,
            1305238720762,
        ];

        let a1 = &mut [0; 1341];
        let a2 = &mut [0; 1341];
        let a3 = &mut [0; 1341];

        //print!("{} {}", b.len(), c.len());
        long(a1, &b, &c);
        karatsuba(a2, &b, &c);

        assert_eq!(&a1[..], &a2[..]);

        // println!("res: {:?}", &a1);
        toom3(a3, &b, &c);
        assert_eq!(&a1[..], &a3[..]);
    }
}