1 use core::cmp;
2 use core::iter::repeat;
3
4 use crate::algorithms::{adc, add2, sub2, sub_sign};
5 use crate::big_digit::{BigDigit, DoubleBigDigit, BITS};
6 use crate::bigint::Sign::{Minus, NoSign, Plus};
7 use crate::biguint::IntDigits;
8 use crate::{BigInt, BigUint};
9
10 #[inline]
mac_with_carry(a: BigDigit, b: BigDigit, c: BigDigit, acc: &mut DoubleBigDigit) -> BigDigit11 pub fn mac_with_carry(a: BigDigit, b: BigDigit, c: BigDigit, acc: &mut DoubleBigDigit) -> BigDigit {
12 *acc += a as DoubleBigDigit;
13 *acc += (b as DoubleBigDigit) * (c as DoubleBigDigit);
14 let lo = *acc as BigDigit;
15 *acc >>= BITS;
16 lo
17 }
18
19 /// Three argument multiply accumulate:
20 /// acc += b * c
mac_digit(acc: &mut [BigDigit], b: &[BigDigit], c: BigDigit)21 pub fn mac_digit(acc: &mut [BigDigit], b: &[BigDigit], c: BigDigit) {
22 if c == 0 {
23 return;
24 }
25
26 let mut carry = 0;
27 let (a_lo, a_hi) = acc.split_at_mut(b.len());
28
29 for (a, &b) in a_lo.iter_mut().zip(b) {
30 *a = mac_with_carry(*a, b, c, &mut carry);
31 }
32
33 let mut a = a_hi.iter_mut();
34 while carry != 0 {
35 let a = a.next().expect("carry overflow during multiplication!");
36 *a = adc(*a, 0, &mut carry);
37 }
38 }
39
40 /// Three argument multiply accumulate:
41 /// acc += b * c
mac3(acc: &mut [BigDigit], b: &[BigDigit], c: &[BigDigit])42 pub fn mac3(acc: &mut [BigDigit], b: &[BigDigit], c: &[BigDigit]) {
43 let (x, y) = if b.len() < c.len() { (b, c) } else { (c, b) };
44
45 // We use three algorithms for different input sizes.
46 //
47 // - For small inputs, long multiplication is fastest.
48 // - Next we use Karatsuba multiplication (Toom-2), which we have optimized
49 // to avoid unnecessary allocations for intermediate values.
50 // - For the largest inputs we use Toom-3, which better optimizes the
51 // number of operations, but uses more temporary allocations.
52 //
53 // The thresholds are somewhat arbitrary, chosen by evaluating the results
54 // of `cargo bench --bench bigint multiply`.
55
56 if x.len() <= 32 {
57 long(acc, x, y)
58 } else if x.len() <= 256 {
59 karatsuba(acc, x, y)
60 } else {
61 toom3(acc, x, y)
62 }
63 }
64
65 /// Long multiplication:
long(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit])66 fn long(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
67 for (i, xi) in x.iter().enumerate() {
68 mac_digit(&mut acc[i..], y, *xi);
69 }
70 }
71
72 /// Karatsuba multiplication:
73 ///
74 /// The idea is that we break x and y up into two smaller numbers that each have about half
75 /// as many digits, like so (note that multiplying by b is just a shift):
76 ///
77 /// x = x0 + x1 * b
78 /// y = y0 + y1 * b
79 ///
80 /// With some algebra, we can compute x * y with three smaller products, where the inputs to
81 /// each of the smaller products have only about half as many digits as x and y:
82 ///
83 /// x * y = (x0 + x1 * b) * (y0 + y1 * b)
84 ///
85 /// x * y = x0 * y0
86 /// + x0 * y1 * b
87 /// + x1 * y0 * b + x1 * y1 * b^2
88 ///
89 /// Let p0 = x0 * y0 and p2 = x1 * y1:
90 ///
91 /// x * y = p0
92 /// + (x0 * y1 + x1 * y0) * b
93 /// + p2 * b^2
94 ///
95 /// The real trick is that middle term:
96 ///
97 /// x0 * y1 + x1 * y0
98 /// = x0 * y1 + x1 * y0 - p0 + p0 - p2 + p2
99 /// = x0 * y1 + x1 * y0 - x0 * y0 - x1 * y1 + p0 + p2
100 ///
101 /// Now we complete the square:
102 ///
103 /// = -(x0 * y0 - x0 * y1 - x1 * y0 + x1 * y1) + p0 + p2
104 /// = -((x1 - x0) * (y1 - y0)) + p0 + p2
105 ///
106 /// Let p1 = (x1 - x0) * (y1 - y0), and substitute back into our original formula:
107 ///
108 /// x * y = p0
109 /// + (p0 + p2 - p1) * b
110 /// + p2 * b^2
111 ///
112 /// Where the three intermediate products are:
113 ///
114 /// p0 = x0 * y0
115 /// p1 = (x1 - x0) * (y1 - y0)
116 /// p2 = x1 * y1
117 ///
118 /// In doing the computation, we take great care to avoid unnecessary temporary variables
119 /// (since creating a BigUint requires a heap allocation): thus, we rearrange the formula a
120 /// bit so we can use the same temporary variable for all the intermediate products:
121 ///
122 /// x * y = p2 * b^2 + p2 * b
123 /// + p0 * b + p0
124 /// - p1 * b
125 ///
126 /// The other trick we use is instead of doing explicit shifts, we slice acc at the
127 /// appropriate offset when doing the add.
karatsuba(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit])128 fn karatsuba(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
129 /*
130 * When x is smaller than y, it's significantly faster to pick b such that x is split in
131 * half, not y:
132 */
133 let b = x.len() / 2;
134 let (x0, x1) = x.split_at(b);
135 let (y0, y1) = y.split_at(b);
136
137 /*
138 * We reuse the same BigUint for all the intermediate multiplies and have to size p
139 * appropriately here: x1.len() >= x0.len and y1.len() >= y0.len():
140 */
141 let len = x1.len() + y1.len() + 1;
142 let mut p = BigUint {
143 data: smallvec![0; len],
144 };
145
146 // p2 = x1 * y1
147 mac3(&mut p.data[..], x1, y1);
148
149 // Not required, but the adds go faster if we drop any unneeded 0s from the end:
150 p.normalize();
151
152 add2(&mut acc[b..], &p.data[..]);
153 add2(&mut acc[b * 2..], &p.data[..]);
154
155 // Zero out p before the next multiply:
156 p.data.truncate(0);
157 p.data.extend(repeat(0).take(len));
158
159 // p0 = x0 * y0
160 mac3(&mut p.data[..], x0, y0);
161 p.normalize();
162
163 add2(&mut acc[..], &p.data[..]);
164 add2(&mut acc[b..], &p.data[..]);
165
166 // p1 = (x1 - x0) * (y1 - y0)
167 // We do this one last, since it may be negative and acc can't ever be negative:
168 let (j0_sign, j0) = sub_sign(x1, x0);
169 let (j1_sign, j1) = sub_sign(y1, y0);
170
171 match j0_sign * j1_sign {
172 Plus => {
173 p.data.truncate(0);
174 p.data.extend(repeat(0).take(len));
175
176 mac3(&mut p.data[..], &j0.data[..], &j1.data[..]);
177 p.normalize();
178
179 sub2(&mut acc[b..], &p.data[..]);
180 }
181 Minus => {
182 mac3(&mut acc[b..], &j0.data[..], &j1.data[..]);
183 }
184 NoSign => (),
185 }
186 }
187
188 /// Toom-3 multiplication:
189 ///
190 /// Toom-3 is like Karatsuba above, but dividing the inputs into three parts.
191 /// Both are instances of Toom-Cook, using `k=3` and `k=2` respectively.
192 ///
193 /// The general idea is to treat the large integers digits as
194 /// polynomials of a certain degree and determine the coefficients/digits
195 /// of the product of the two via interpolation of the polynomial product.
toom3(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit])196 fn toom3(acc: &mut [BigDigit], x: &[BigDigit], y: &[BigDigit]) {
197 let i = y.len() / 3 + 1;
198
199 let x0_len = cmp::min(x.len(), i);
200 let x1_len = cmp::min(x.len() - x0_len, i);
201
202 let y0_len = i;
203 let y1_len = cmp::min(y.len() - y0_len, i);
204
205 // Break x and y into three parts, representating an order two polynomial.
206 // t is chosen to be the size of a digit so we can use faster shifts
207 // in place of multiplications.
208 //
209 // x(t) = x2*t^2 + x1*t + x0
210 let x0 = BigInt::from_slice_native(Plus, &x[..x0_len]);
211 let x1 = BigInt::from_slice_native(Plus, &x[x0_len..x0_len + x1_len]);
212 let x2 = BigInt::from_slice_native(Plus, &x[x0_len + x1_len..]);
213
214 // y(t) = y2*t^2 + y1*t + y0
215 let y0 = BigInt::from_slice_native(Plus, &y[..y0_len]);
216 let y1 = BigInt::from_slice_native(Plus, &y[y0_len..y0_len + y1_len]);
217 let y2 = BigInt::from_slice_native(Plus, &y[y0_len + y1_len..]);
218
219 // Let w(t) = x(t) * y(t)
220 //
221 // This gives us the following order-4 polynomial.
222 //
223 // w(t) = w4*t^4 + w3*t^3 + w2*t^2 + w1*t + w0
224 //
225 // We need to find the coefficients w4, w3, w2, w1 and w0. Instead
226 // of simply multiplying the x and y in total, we can evaluate w
227 // at 5 points. An n-degree polynomial is uniquely identified by (n + 1)
228 // points.
229 //
230 // It is arbitrary as to what points we evaluate w at but we use the
231 // following.
232 //
233 // w(t) at t = 0, 1, -1, -2 and inf
234 //
235 // The values for w(t) in terms of x(t)*y(t) at these points are:
236 //
237 // let a = w(0) = x0 * y0
238 // let b = w(1) = (x2 + x1 + x0) * (y2 + y1 + y0)
239 // let c = w(-1) = (x2 - x1 + x0) * (y2 - y1 + y0)
240 // let d = w(-2) = (4*x2 - 2*x1 + x0) * (4*y2 - 2*y1 + y0)
241 // let e = w(inf) = x2 * y2 as t -> inf
242
243 // x0 + x2, avoiding temporaries
244 let p = &x0 + &x2;
245
246 // y0 + y2, avoiding temporaries
247 let q = &y0 + &y2;
248
249 // x2 - x1 + x0, avoiding temporaries
250 let p2 = &p - &x1;
251
252 // y2 - y1 + y0, avoiding temporaries
253 let q2 = &q - &y1;
254
255 // w(0)
256 let r0 = &x0 * &y0;
257
258 // w(inf)
259 let r4 = &x2 * &y2;
260
261 // w(1)
262 let r1 = (p + x1) * (q + y1);
263
264 // w(-1)
265 let r2 = &p2 * &q2;
266
267 // w(-2)
268 let r3 = ((p2 + x2) * 2 - x0) * ((q2 + y2) * 2 - y0);
269
270 // Evaluating these points gives us the following system of linear equations.
271 //
272 // 0 0 0 0 1 | a
273 // 1 1 1 1 1 | b
274 // 1 -1 1 -1 1 | c
275 // 16 -8 4 -2 1 | d
276 // 1 0 0 0 0 | e
277 //
278 // The solved equation (after gaussian elimination or similar)
279 // in terms of its coefficients:
280 //
281 // w0 = w(0)
282 // w1 = w(0)/2 + w(1)/3 - w(-1) + w(2)/6 - 2*w(inf)
283 // w2 = -w(0) + w(1)/2 + w(-1)/2 - w(inf)
284 // w3 = -w(0)/2 + w(1)/6 + w(-1)/2 - w(1)/6
285 // w4 = w(inf)
286 //
287 // This particular sequence is given by Bodrato and is an interpolation
288 // of the above equations.
289 let mut comp3: BigInt = (r3 - &r1) / 3;
290 let mut comp1: BigInt = (r1 - &r2) / 2;
291 let mut comp2: BigInt = r2 - &r0;
292 comp3 = (&comp2 - comp3) / 2 + &r4 * 2;
293 comp2 = comp2 + &comp1 - &r4;
294 comp1 = comp1 - &comp3;
295
296 // Recomposition. The coefficients of the polynomial are now known.
297 //
298 // Evaluate at w(t) where t is our given base to get the result.
299 add2(acc, r0.digits());
300 add2(acc, (comp1 << (BITS * 1 * i)).digits());
301 add2(acc, (comp2 << (BITS * 2 * i)).digits());
302 add2(acc, (comp3 << (BITS * 3 * i)).digits());
303 add2(acc, (r4 << (BITS * 4 * i)).digits());
304 }
305
306 #[cfg(test)]
307 mod tests {
308 use super::*;
309
310 #[cfg(feature = "u64_digit")]
311 #[test]
test_mac3_regression()312 fn test_mac3_regression() {
313 let b = [
314 6871754923702299421,
315 18286959765922425554,
316 16443042141374662930,
317 11096489996546282133,
318 2264777838889483177,
319 504608311336467299,
320 9259121889498035011,
321 10723282102966246782,
322 14152556493169278620,
323 3003221725173785998,
324 12108300199485650674,
325 4411796769581982349,
326 1472853818082037140,
327 3839812824768537141,
328 566677271628895470,
329 17571088290177630367,
330 4074015775889626747,
331 16783683502945010460,
332 3672532206031614447,
333 13187923513085484119,
334 7867853909525328761,
335 12950070983027918062,
336 16468847655795609604,
337 16236260173878013911,
338 13584046646047390182,
339 3459823911019550977,
340 852221229786155372,
341 13320957730746441063,
342 15903144185056949084,
343 17968961288800765765,
344 3314535850615883964,
345 11164774408693138937,
346 296795981573878002,
347 13439622819313871747,
348 975505461732298298,
349 6320248106127902035,
350 1292261367530037116,
351 5457288991919109645,
352 9156327436088586665,
353 13214259773135401786,
354 11894959382522647196,
355 7347087210697207182,
356 10866433221888385981,
357 11517455022886216566,
358 16002875401603965132,
359 14910152116859046022,
360 13121658696980417474,
361 9896002308546761527,
362 2508026143263419489,
363 5630957157948330915,
364 14741609094906545841,
365 17816841519612664975,
366 7969630003685849408,
367 155645440736526982,
368 12636207152988003561,
369 11423906424129622745,
370 7683636929614516252,
371 18373475843711518761,
372 12517632064609218689,
373 9229683610001203481,
374 7466784812824133107,
375 669533494937267490,
376 5082436863236123102,
377 13002655060148900023,
378 13744987998466735055,
379 11291793723517314998,
380 13019038669516699882,
381 16709997141197914794,
382 5635685992939170942,
383 11675574645907803567,
384 4594226142456014804,
385 16573646927735932410,
386 1485870256663971571,
387 15846713039191416692,
388 6268579197046091479,
389 4148711486149996258,
390 12289594343226957541,
391 7248423051711675098,
392 11690743363052255577,
393 3624472201995805474,
394 8537222754743368136,
395 9139752523777531093,
396 10332892792833338770,
397 7037635035632196817,
398 4496405835920050629,
399 17391917705588355794,
400 14117717411488825371,
401 5230286663558119879,
402 17825506019213671261,
403 17404129971477111108,
404 11521727676625909194,
405 5238690179323183699,
406 5727780062420810465,
407 9632453973638740648,
408 337811100863346570,
409 13073228541428212927,
410 17709844765172234384,
411 13208921325370991444,
412 5431840578699639395,
413 17077925307816799261,
414 7209340156697508529,
415 12028994618496870845,
416 2544500160865141031,
417 11649654461126310578,
418 9365483541048471688,
419 14612538420978379687,
420 9873239918327058306,
421 1157472058577394095,
422 12375928197270581863,
423 11259024417929344257,
424 3285662610711925103,
425 1050951962862248344,
426 13573242938330525645,
427 6481773409427626042,
428 16024681689552681567,
429 2220783933082287757,
430 8929560899664301451,
431 64015232882626853,
432 11408281661939521111,
433 878781900624570608,
434 9905479987547252164,
435 5731582277472653511,
436 17783362590834199727,
437 13132721837581513886,
438 11245310560513633279,
439 7644137013939043642,
440 13922828459616614595,
441 448705611699584512,
442 11371313753562743476,
443 1574633155961622201,
444 2301463292785650126,
445 741402366344950323,
446 14185352113401593236,
447 9211130877800459742,
448 11565822612758649320,
449 14182824194529562358,
450 4341494334831461293,
451 15108767488023246095,
452 4205441133931479958,
453 17825783968798375241,
454 5574097067573038154,
455 16531064653177298756,
456 17267304977208102577,
457 928672208065810133,
458 8205510594424616558,
459 12543833966918246257,
460 86136389231850233,
461 16025485094311428670,
462 5207828176013117610,
463 13359327193114550712,
464 2794955638345677576,
465 3993304349404239314,
466 4994255720172128836,
467 7135313309521261953,
468 3325716756157017100,
469 4584134963117073140,
470 88101658911197316,
471 3369567695997157158,
472 6461054377325416109,
473 17386668567122758604,
474 3597625436035211312,
475 18145298865089787176,
476 11816690578299880852,
477 7452950893647760052,
478 1177645126198066735,
479 10342535382097449475,
480 598208441320935865,
481 12921535255416124667,
482 13109196922707708559,
483 8670507722665163833,
484 17373614756345962119,
485 3224893480553906007,
486 14808009166588879477,
487 14704014108115963684,
488 1462864287248162745,
489 4880369798466033386,
490 6588737531985967098,
491 7946857775405689623,
492 12748319198997944814,
493 9326770283997092048,
494 17003595393489642565,
495 17484594608149336453,
496 4190950067408592109,
497 17824678462034741067,
498 15702236130638266509,
499 5273424187690232454,
500 12023318566452513739,
501 7102078857285715052,
502 4369802176505332167,
503 10699689773538544377,
504 730467711008420891,
505 10262119215370320651,
506 6690738779737159913,
507 10562916257987913949,
508 14972385366243262684,
509 17611612385937387126,
510 14205605578073512987,
511 8713489693924424056,
512 16616344708337664878,
513 16742234424573023464,
514 2902884815897074359,
515 9156119555166935389,
516 9080622094288708744,
517 3581449124220285742,
518 15398432395479402853,
519 6362303494565643898,
520 15212154657001712988,
521 18252754350443257897,
522 12244862614504808605,
523 8814921661269777610,
524 5889164750855440803,
525 13877154483979742237,
526 1975853494990494526,
527 1453591120623605828,
528 1561842305134808950,
529 4104017706432470283,
530 18374510210661965759,
531 9803038902053058582,
532 15551403297159148863,
533 16533913772549484823,
534 14544914922020348073,
535 10919410908966885633,
536 17470299067773730732,
537 11601114871272073512,
538 14664333496960392615,
539 13186665624854933887,
540 14081619270477403715,
541 4675338296408349354,
542 13005625866084099819,
543 9826340006565688690,
544 8509069870313784383,
545 11413525526571910399,
546 6807684484531234716,
547 4618621816574516038,
548 4883039215446200876,
549 5183393926532623768,
550 10445125790248504163,
551 8703300688450317851,
552 1810657058322023328,
553 13343323798867891831,
554 1114348861126534128,
555 13117683625674818191,
556 6927011828473571783,
557 3034582737565944267,
558 4121820627922246500,
559 2068319599019676600,
560 4767868471095960483,
561 2803257298179131000,
562 9209930851438801799,
563 18163819238931070567,
564 13128522207164653478,
565 18335828098113199965,
566 8486377462588951609,
567 3277957111907517760,
568 2754092360099151521,
569 8933647340064032887,
570 11308566144424423461,
571 8932492907767510893,
572 17676321536634614180,
573 10916845309604942594,
574 1541736640790756953,
575 6693084648846615663,
576 2461388895988176852,
577 18262736604025878520,
578 15216140684185826151,
579 3888640441711583463,
580 14630778656568111440,
581 3821930990083597884,
582 6592159409049154819,
583 5773800580147691268,
584 14025025753393817356,
585 1143462425860692308,
586 7310246890521674728,
587 12759899287196682624,
588 17074850912425975309,
589 13639540485239781443,
590 11594492571041609459,
591 8086375866615071654,
592 2458700273224987435,
593 14188836372085884816,
594 14151374325605794048,
595 12856075220046811900,
596 17507597135374598747,
597 12763964479839179724,
598 3365341110795400221,
599 13808931773428143133,
600 17033299610882243549,
601 18227238137056935396,
602 14979713927050719147,
603 4275831394949546984,
604 8603067650574742183,
605 15568230725728908493,
606 2983251846901576618,
607 4855005009090541140,
608 8978290455364410739,
609 7585912958100257345,
610 7889636089238169609,
611 6157281389499351077,
612 16013269622819602387,
613 9224246297875214668,
614 4138161347252674082,
615 10318658241432357882,
616 9402564329926365826,
617 17394083647841321487,
618 4542513014713923099,
619 8667322649378182890,
620 576180375143955900,
621 18021784748061793599,
622 13203834948982480414,
623 13904284351856275257,
624 4244818956425434151,
625 1076055980570550161,
626 2674096971027047948,
627 104304434704934006,
628 2062855556986682483,
629 5786781659542854036,
630 6853220200637113363,
631 9593939255297136609,
632 1066166708380361418,
633 14725348327737457961,
634 16150748104690835108,
635 17931164130540362944,
636 18218341517410521707,
637 6187428325833810419,
638 9690875880801108718,
639 5756353469528306968,
640 2503319654515164798,
641 13274927231487272946,
642 10638128257539555489,
643 5896639022976119702,
644 15161011556181302784,
645 2677346843481863572,
646 604789272653420187,
647 13360196803831848409,
648 10012996491423918567,
649 5044454426037856014,
650 10524057648033789107,
651 5649671761089989854,
652 7387534256772100838,
653 8924072651833780120,
654 3785979389901456766,
655 2050691721810266829,
656 15376099431140621558,
657 17511662813348858473,
658 12,
659 ];
660 let c = [
661 13147625290258353449,
662 13817956093586917764,
663 18028234882233861888,
664 4293751923287888052,
665 14564141039952372119,
666 2676734207017121597,
667 6459642599270298327,
668 10514787163962869530,
669 3464485178085199795,
670 11257474764035059331,
671 12181451147060151288,
672 7771786629160476887,
673 5728497381328758601,
674 5895875676429179638,
675 16679607158645743277,
676 10404047442430847790,
677 16582081384308902247,
678 12490779806977231913,
679 11404651769234278221,
680 17022469412583392578,
681 16439338230633175949,
682 1063962396022446422,
683 4870572923632948252,
684 10243077795083132155,
685 17682233381781162062,
686 3717510388192897304,
687 10472572278890160024,
688 4405755291195612194,
689 17627642736326682742,
690 15119177646289231784,
691 14667151155773252610,
692 1618000287928404571,
693 13586901368491466481,
694 9480801770542358210,
695 11591874296843194205,
696 8397058357928253365,
697 578589728443805743,
698 1598611175229035508,
699 17769761727743406958,
700 8701373647057001365,
701 3491199179963360183,
702 14734752687818620066,
703 5882881716069715431,
704 17867956461647398152,
705 14317425986826618884,
706 3190976033715157155,
707 16025482572482863452,
708 198303002951605721,
709 13239788634860069155,
710 9176490930959914357,
711 13789370614942093263,
712 8719316129258342716,
713 8953451100830410047,
714 5127100131850962987,
715 5042215589496218651,
716 12195935831432585004,
717 16271477124635191788,
718 17042607302458382021,
719 6909951113544811251,
720 15867944577589614763,
721 12869536415455501541,
722 13449373980179917814,
723 5429607781375702916,
724 14690315137615067697,
725 6423399543123234984,
726 15319364673671319937,
727 5766347079728187383,
728 9497305192864606751,
729 2186351927817601391,
730 10726914960258697501,
731 6088420666246691919,
732 1588440693016474445,
733 2604959928768677511,
734 17616186617681342252,
735 10535006669694135493,
736 13489006267185033075,
737 15502143361666125994,
738 16502406772857573234,
739 10575734691312906463,
740 10716474667815258981,
741 9710545289905473439,
742 3854962820702807947,
743 5378807396667958578,
744 12445857039679749013,
745 3960937645922969357,
746 9829760523341564006,
747 9212167324275861816,
748 11422368668113634154,
749 10684460016299893830,
750 11389419764702616711,
751 3899200183251946009,
752 2093729712958211017,
753 8420392268215053797,
754 6398774523536552388,
755 10852749009148352925,
756 5289144597498232565,
757 17703908865205386695,
758 6907742189144573057,
759 1784946329061543285,
760 15480049270321874965,
761 12069121519676878616,
762 17812799898774546955,
763 11948193027013007431,
764 3884323573006797139,
765 6847241152178866159,
766 12199935709218616587,
767 3955204591920032162,
768 14878266626017125196,
769 7278030477420395848,
770 10161863746736807272,
771 9207356190672684457,
772 4601854808843007498,
773 6775986836344704023,
774 17288427592206154151,
775 484532203475900068,
776 18118416415768866724,
777 6355480490988086744,
778 3208810669246831205,
779 13957974139288542819,
780 8396394607132645103,
781 15228026780031354119,
782 14498855337604982920,
783 14141161076130564520,
784 6588603191636571246,
785 3999628253355964982,
786 575393068537655797,
787 5657615255395137815,
788 5633326538404084103,
789 12326562882758080143,
790 3543480102419886151,
791 6824968844300019651,
792 3267458303116092202,
793 6237792365531735545,
794 7469544494204334597,
795 15133093961814251253,
796 6772265097243462865,
797 5750218230297679586,
798 15133043154817660619,
799 13838897645290708193,
800 1698455434074605058,
801 1416851634747812455,
802 1433730608162832030,
803 4396199899836953731,
804 11478281064341415007,
805 1199305835874995069,
806 12461220549480843598,
807 3786960620800323764,
808 1359737533861421574,
809 5683800489224722555,
810 580114063914071460,
811 3757480794795278521,
812 13350893050786101167,
813 5864294767515313613,
814 13667186506174093283,
815 10644721863115106069,
816 4089596839694426493,
817 837360057072705787,
818 14661298745941209853,
819 3135603497841243154,
820 8588389252943247567,
821 3180539906709497729,
822 9920619693463058306,
823 4532986872992016572,
824 16671485218531724914,
825 16237535739330707258,
826 3392767051844917712,
827 6253243888910507007,
828 6138565275365265434,
829 10788645409322247025,
830 2998545083522261349,
831 4393635535422254464,
832 162283948928616560,
833 6581058835892498610,
834 9044842225211179928,
835 3359587585025090294,
836 4774711746392882472,
837 12671200872687548503,
838 5910134937871058397,
839 5003751340241222878,
840 4967360099981268641,
841 8911591385760571590,
842 8159270265734967930,
843 5250229866305601451,
844 9551428753943119262,
845 8689322272982432960,
846 10836071047039045386,
847 17213966296648357737,
848 9670979912487313863,
849 8149443095351359584,
850 5882663205147794724,
851 1077285439953280724,
852 9538056828068584607,
853 6534627272003475907,
854 4182635403810470796,
855 4332023173746385204,
856 18043427676849450827,
857 1544903479164552030,
858 12808718740097386201,
859 4743835518042863198,
860 17533308810746778943,
861 2436162195122352530,
862 13717567738827779707,
863 16498190890660698054,
864 8446479819925879748,
865 13026080039828457667,
866 10242288816864319380,
867 16805676933455246691,
868 8854224454209663170,
869 12881936897446363181,
870 14318173900990076031,
871 17263412233699302472,
872 1175398600063038674,
873 12303198178060136245,
874 5262693362410688618,
875 2449023658743880786,
876 7851992903947432349,
877 15279972405631504407,
878 12782492794198106006,
879 454161448971247291,
880 7208428618685987862,
881 2808315703288943474,
882 15547213201445152112,
883 4195163971319471362,
884 5077844356227078783,
885 6228496807545876867,
886 8018540845186766480,
887 12802276286029182659,
888 17873658985235511282,
889 405964923119895900,
890 17005602789111483415,
891 15323511615180015542,
892 3777673967701314271,
893 11241595450806936514,
894 18094205811239804553,
895 4945226306748157777,
896 13126826405187610008,
897 18401109742831785725,
898 12038829763881934869,
899 6883152103015744232,
900 6888604044125585130,
901 10327133149324643136,
902 9786783078753767897,
903 7728244798165310883,
904 13992043126602427065,
905 12760431374402895816,
906 10556094269445313552,
907 370205722038466820,
908 2237385387127770787,
909 3008501418666326571,
910 2147796682874314438,
911 11177403945853274771,
912 394056223101551114,
913 17534487287334816941,
914 881808126732102067,
915 4246224751203270716,
916 6113128358498682501,
917 1188932545968905738,
918 12765644408650990762,
919 8081000787691948556,
920 648553016175951475,
921 13679613339055618508,
922 13341452083201419987,
923 16710796306331641196,
924 14950547258962926774,
925 5807411999567421647,
926 51486220608905397,
927 11495154677696979138,
928 9566551468999057159,
929 9404650285252518485,
930 15936039807347909292,
931 9926926746640651811,
932 8137529358194870999,
933 8409600195382297763,
934 7353893979385221928,
935 13160302875690198406,
936 348690545671757035,
937 9037218723869788888,
938 17926585726505969574,
939 10803900675631258757,
940 6393072209298283246,
941 16096417936354328220,
942 9646360537089934694,
943 13770356122351384928,
944 16836674286434938459,
945 7541946872500761286,
946 9048263944605955661,
947 16780366954521256652,
948 7343863344205297175,
949 12789916470639650059,
950 5777346297355673119,
951 3199552193495347726,
952 12230742086629356177,
953 7003231206534047938,
954 15090957803858528744,
955 17037481317622823117,
956 3297597585907869563,
957 2697945267713108093,
958 4292423210234323248,
959 3611346819357503037,
960 7143735793987221927,
961 7192307513286386565,
962 17787283681233014873,
963 12357966577423097448,
964 8897136197269501397,
965 11902132993155439534,
966 3134549357805042842,
967 13190859350132812532,
968 2953055179222338302,
969 14072479035614746298,
970 623716608321502842,
971 13012840714155111804,
972 9113471173003784658,
973 3832090523063788219,
974 11686697139180356613,
975 9220715948534448005,
976 10475815552871271805,
977 13316455608734752259,
978 3256936992714735238,
979 11886029809711683060,
980 1154889652278063077,
981 2634050492458919284,
982 15799574960065328453,
983 4854385868907776158,
984 4308561300452445774,
985 18158501743185507870,
986 494961281052444285,
987 13230103283989646999,
988 4290343182499439317,
989 2897833401622123527,
990 1828737779143272347,
991 10192978009672844498,
992 10197386440201448306,
993 16716143215455134742,
994 15610114368473665198,
995 6236681643047286973,
996 12762824210749799030,
997 10807635853279558353,
998 11353446277082394704,
999 7511532745578783402,
1000 7171399474829708082,
1001 2443271458861652456,
1002 18046286184730984000,
1003 1631291998347686895,
1004 5333915858453483562,
1005 4279428177587669193,
1006 4079835446959802508,
1007 14290782115827722683,
1008 6259655031577342838,
1009 14581460384506564304,
1010 235151974716865360,
1011 2375317628907755058,
1012 12458887693759984881,
1013 2860995391934282660,
1014 17774376172142139929,
1015 17358804008079603231,
1016 2216198936056406536,
1017 2563098348647162202,
1018 774854408223515953,
1019 12219835071659426404,
1020 2185427726156502437,
1021 8977240783566213019,
1022 10950053189740163780,
1023 15333460456641375067,
1024 15414859166425218506,
1025 16627722666231706432,
1026 14933789823667915188,
1027 7893509177447272752,
1028 5576840844608359783,
1029 9639046067346127903,
1030 6034870669926683205,
1031 11074229566077202561,
1032 7734172323678793750,
1033 1797022077506253706,
1034 4175135546481691973,
1035 4576531916446872861,
1036 11073018132808499885,
1037 9004329344974888991,
1038 2579957018554908013,
1039 16723993098086799559,
1040 8849326108645639933,
1041 1190731350374367414,
1042 15196122081549855262,
1043 16510124270150231915,
1044 1447369806052266158,
1045 1774117429703831561,
1046 3272947319047150592,
1047 6086749417328134594,
1048 114186026684487132,
1049 15881404973090653236,
1050 9002767864228350415,
1051 8632935895349074342,
1052 14189358814161984679,
1053 7273121617103693424,
1054 3720897725211288407,
1055 17385088912598509226,
1056 17763377168623207811,
1057 3011652710253791434,
1058 13026181299902362083,
1059 7673465031457219376,
1060 8976686724731444924,
1061 1602632530339248239,
1062 7322563236300692731,
1063 17611256894860100558,
1064 6585524259854016494,
1065 13024412741537787009,
1066 6490348356225390820,
1067 10475028766694832415,
1068 4171072186129163678,
1069 8067851189059922503,
1070 13321938328018146758,
1071 2388045447565404129,
1072 12628485341454603822,
1073 10515272459175323665,
1074 5141134415272454070,
1075 15533371382800133770,
1076 5089921040728608575,
1077 9922174346147797518,
1078 2286765044618595826,
1079 458550603008652679,
1080 1895551360015713043,
1081 17608310488293104847,
1082 3041900727372287447,
1083 14788640656316180904,
1084 8006597265367839623,
1085 6172940096066506343,
1086 5001938689099706064,
1087 11456390799634570508,
1088 58114059478872995,
1089 13813208350157959983,
1090 7192129467061995988,
1091 15458065357391712248,
1092 1184709156376072909,
1093 4997369113101583984,
1094 11962098224621896302,
1095 15957925570647432972,
1096 9768648025404723859,
1097 16066042591100391809,
1098 14826843103086137650,
1099 15530089295707983043,
1100 14757548535314259278,
1101 12272651610971114578,
1102 11815510217344882354,
1103 7863174743199280885,
1104 17755545598189623361,
1105 3623688651342862124,
1106 846900727574364473,
1107 4058087733004472364,
1108 9766249185594229219,
1109 8203083537227057882,
1110 2514240782116496856,
1111 13013220914916706232,
1112 7479093476304703557,
1113 13599783865226501576,
1114 15101635775647230555,
1115 7679618582697439061,
1116 3809012502593902516,
1117 17181248094867317535,
1118 9184314850829556852,
1119 17135643679321121988,
1120 16551911434983848191,
1121 16563989164660839146,
1122 5244550954203347299,
1123 7468243134930758384,
1124 13848792956096067953,
1125 299147213373350316,
1126 4234339785402518959,
1127 8316379046881991503,
1128 15054498767105089317,
1129 15245345469072520312,
1130 169003686610660574,
1131 8905168983426000291,
1132 14079614647232314662,
1133 10677487605853621326,
1134 486644500614977963,
1135 4315204642211280928,
1136 13378617481135356106,
1137 17475120936205263193,
1138 7054688890001081620,
1139 4890150051524335365,
1140 16929286679364707850,
1141 12404641144465776093,
1142 85729750914301011,
1143 7518958607192096844,
1144 12335244912121726376,
1145 441058371959341821,
1146 15283845211776523277,
1147 11365329781782022447,
1148 7176368314974115909,
1149 13402576699022366440,
1150 9612930864140895738,
1151 1551492131293754732,
1152 15625022379217650131,
1153 16853815349026997223,
1154 10176564334158763844,
1155 11561712818786302756,
1156 10721760754726884570,
1157 16211944886847212142,
1158 6455169008048578331,
1159 16442277863996881453,
1160 11966295676197364531,
1161 17131994341597087852,
1162 10178415200084263095,
1163 17241579229376875844,
1164 16595331811574273072,
1165 15514521091896721175,
1166 10273857151649071793,
1167 16902595879470117012,
1168 17044001876395421463,
1169 6241464946584582238,
1170 6948336526969806585,
1171 618342450528567894,
1172 11266394538973042131,
1173 13911827545633749019,
1174 5770757761516661921,
1175 4237426824475464361,
1176 6137903415464019236,
1177 16948218557528241218,
1178 13342541955783637763,
1179 12228044034020334487,
1180 3753346696590480376,
1181 12798240801313956988,
1182 16337512518975517925,
1183 17029293450980009677,
1184 17889170535515757468,
1185 14215875855934760379,
1186 6048723980155309955,
1187 7751681766991188778,
1188 9324053942011976933,
1189 6806752775473648551,
1190 16491946688185935526,
1191 17973734037621739928,
1192 16521618754491099078,
1193 15814146101747955693,
1194 17072736172673770992,
1195 560386638362049457,
1196 9315742694497383404,
1197 14003511454248083195,
1198 505571467191783211,
1199 15321198489161153019,
1200 67644988835003625,
1201 422740534693308350,
1202 1588696840338933253,
1203 17633924999495432514,
1204 3578955538397900717,
1205 4350434105925504139,
1206 17520065248429114920,
1207 15948482628426996406,
1208 16339123994002177423,
1209 14962340825416078820,
1210 16377030826129395507,
1211 3728945733790793859,
1212 14040902081706983834,
1213 6245445984351877668,
1214 15109200712778355913,
1215 6876007592769255303,
1216 2817332194593868297,
1217 14642462812181536002,
1218 13241495844336600578,
1219 17508429190834543309,
1220 9979949640512203943,
1221 11024829646351554638,
1222 16593085213286597946,
1223 3786341713932228381,
1224 4854315828914728926,
1225 4226218666904293494,
1226 8427728822561673998,
1227 7350284610946156715,
1228 15819368048130139112,
1229 8256096529517474967,
1230 3164838434037013186,
1231 7181083254407808229,
1232 14392138511139873518,
1233 17742848920305479369,
1234 14254286401886846925,
1235 13172848038012405804,
1236 203991661409228704,
1237 12155338881267997435,
1238 15596778231824136139,
1239 4270398294351523748,
1240 841800590896491878,
1241 1324356347939565174,
1242 1635131684701069722,
1243 9402955035355081296,
1244 1217032459175096228,
1245 814223664322441499,
1246 15135019617633870019,
1247 12555639443566847383,
1248 11065144808269184833,
1249 1793647298364803083,
1250 744335551991850623,
1251 8586945353992422223,
1252 13891984397850330431,
1253 13168278299568698045,
1254 2545505069878626309,
1255 2345784529656940996,
1256 11238050768519698690,
1257 145002862188778047,
1258 14056901992927566251,
1259 7146776997541924640,
1260 11964908621390755985,
1261 3287082359454318848,
1262 7997294085866872179,
1263 5423940255508089295,
1264 4669857898097690050,
1265 11333522019809124025,
1266 7524197645486269287,
1267 17976672080799403364,
1268 9172262822040915360,
1269 158857927726516306,
1270 7825225378554946108,
1271 9418576621795701508,
1272 7633907046040364747,
1273 18268626574958706065,
1274 3209003992606419777,
1275 16433724431228669029,
1276 11533879023784257295,
1277 7352494819227083416,
1278 9550528667280588513,
1279 17649577381405647635,
1280 3464121828599745965,
1281 10524312096092076686,
1282 16298229441805025435,
1283 12299501175855694268,
1284 5234483534956328223,
1285 6842998262033517680,
1286 3405412371253551971,
1287 12961834222487484113,
1288 8329667703663634728,
1289 10113768572787795201,
1290 437973618905269097,
1291 10518227023647484735,
1292 15505971298645719880,
1293 16080360285628075895,
1294 3253079608258240664,
1295 9442135189206070131,
1296 2620029667482460392,
1297 13058843258931508372,
1298 13398588232276089878,
1299 2013946258885953106,
1300 2777554235294156890,
1301 7727335788600791403,
1302 64926713702036664,
1303 7017058603665827477,
1304 3038023548514697220,
1305 1884676627569135536,
1306 11691207067273431143,
1307 10072076283563998720,
1308 13307639350090691756,
1309 16097417013067765232,
1310 1046820113070464713,
1311 686419524967082232,
1312 16868023154965697840,
1313 9866592207237669169,
1314 434426218272207007,
1315 15594721674408845443,
1316 4951793482938178894,
1317 5328839429244804401,
1318 6948444829657740645,
1319 1250147824386974181,
1320 3550991145492617480,
1321 6903375020760383265,
1322 5556228127567021487,
1323 13761117792143803710,
1324 15185125920584997092,
1325 8186466630413736182,
1326 4802907899488331586,
1327 15305034246197656170,
1328 15396976225074357341,
1329 5898890255224717338,
1330 3615484144772658086,
1331 18255788598509486615,
1332 224652660554020763,
1333 13466057775273969203,
1334 2077408507156283322,
1335 2342023270473665603,
1336 8947077544711176259,
1337 5306736138640896482,
1338 4480826977335219320,
1339 3788577265714804046,
1340 115308722462922151,
1341 7375990846913556901,
1342 11736854490599587323,
1343 5076771704562414238,
1344 15553536672697466685,
1345 18090905433616951399,
1346 4188493781910494747,
1347 15181059585004440209,
1348 12728148632534416192,
1349 6722182881759806025,
1350 13780369372289967994,
1351 3732668177228110489,
1352 3787487561117269614,
1353 5162113090068803421,
1354 4321209401054627716,
1355 5448669100032977354,
1356 18291843216134979053,
1357 16776289611211531598,
1358 1885119013176564798,
1359 9819767057810457229,
1360 9641605351052741528,
1361 15675183391486745167,
1362 7616169275030402931,
1363 15993936796479971901,
1364 9454285932998973051,
1365 17536483736707322645,
1366 13392933552816987057,
1367 8637439302534754550,
1368 540899472066855809,
1369 16629709388332749089,
1370 13733105412819355808,
1371 14746175220939553318,
1372 2846952298407666021,
1373 2891977601791383828,
1374 5696908477729602226,
1375 11016605210700034776,
1376 16941067307488182843,
1377 6211355506521287507,
1378 16542299272345996744,
1379 3303613293413685324,
1380 1629768918920532660,
1381 4206151598734336232,
1382 8856046512946232478,
1383 4907901964445375077,
1384 14400940791045719898,
1385 6525037265010054850,
1386 2845928272349757088,
1387 15487802580883373670,
1388 9169720274701972562,
1389 5985973322812415499,
1390 13260753279459456665,
1391 17130834352417810395,
1392 10504159994735949472,
1393 3619665201800936886,
1394 6177405351801242874,
1395 17314717210185132120,
1396 10635416390598362752,
1397 3965067791232986010,
1398 4137222868235076149,
1399 7349861099139148757,
1400 13855902416442714188,
1401 3758295764877447132,
1402 2127539446373659348,
1403 7398648921373235157,
1404 10530977609779069122,
1405 2057082983915369887,
1406 15095469010920249805,
1407 1580580744862861737,
1408 1385280835524895944,
1409 3735648750536184988,
1410 13975651103105108932,
1411 12560143273028504000,
1412 213932257778062629,
1413 14025207273678863547,
1414 1676558185650908917,
1415 3681689509396718388,
1416 3722143195009944583,
1417 6372328340754588443,
1418 10661271971253598404,
1419 12865667632468835094,
1420 16100956261366638373,
1421 11045168180887164035,
1422 5967989014180680940,
1423 15635382253084283895,
1424 10672630067495824386,
1425 3671716856885117446,
1426 10087953011045522378,
1427 12966649859522423914,
1428 7760990551799493049,
1429 6773507642155574420,
1430 14320444088036226729,
1431 996203594183873620,
1432 6192894784937493039,
1433 4156453068089966167,
1434 14572012258150145006,
1435 12694436615363442069,
1436 9393452532594598725,
1437 7073980584197012440,
1438 3092044667654940896,
1439 13855475386227226214,
1440 4309098798809069243,
1441 17846796523885690871,
1442 13567621519152235542,
1443 15083768013978066571,
1444 4928428566683275123,
1445 6358144983716124065,
1446 5815136002584686049,
1447 8730978481571655079,
1448 7899439375250672635,
1449 14524588032253020995,
1450 9810453005255777832,
1451 4283615174004546182,
1452 4910404083022612904,
1453 5889820858976629278,
1454 16526481241932287977,
1455 9532234053410906113,
1456 12393033057707332749,
1457 12925587840306057080,
1458 10366100576119055483,
1459 6171980884320519881,
1460 6370785275483681135,
1461 8381526621841046029,
1462 5551091520919536756,
1463 12950765990114654837,
1464 6451545362694246818,
1465 212258237904426316,
1466 17609333615515129459,
1467 16595363338989541409,
1468 17025961636346735400,
1469 10271948129080248406,
1470 10944228647786476233,
1471 5467386369086945871,
1472 1304225602762032822,
1473 16166120916726245386,
1474 9432487283289925931,
1475 3403761315752290587,
1476 3141021554091328928,
1477 10971462138407674348,
1478 10105449417179637906,
1479 3942240849395932405,
1480 10366411633985305351,
1481 659554731028325691,
1482 17091333474944352463,
1483 612319979868231629,
1484 17382969496671106101,
1485 3825928121744631575,
1486 6919629698697448941,
1487 3047982536888198540,
1488 8582263155177383434,
1489 10489954932217807453,
1490 18043360586501370656,
1491 16839643971175241779,
1492 3859513000284354780,
1493 10803271797516731820,
1494 8797248475477069569,
1495 4834788502968724109,
1496 10636072941935319265,
1497 15738621943484162587,
1498 3646521574321304278,
1499 16944083908124496190,
1500 16148256726139579321,
1501 1609665271498664710,
1502 1362054633058989594,
1503 13973388908791057772,
1504 6345006526009146382,
1505 2518534936752010021,
1506 659541823645224189,
1507 10968167928774784973,
1508 7543306179097411926,
1509 9456023891569360398,
1510 5349741969482277027,
1511 8323748029139171407,
1512 11280182066584422642,
1513 3780197930314489144,
1514 11850380628777309039,
1515 9657986102535984497,
1516 5218157717868740572,
1517 7171503646973777516,
1518 5852967071087962442,
1519 17762051133445851451,
1520 13539879275779472444,
1521 10231713150096078048,
1522 13415553313620113202,
1523 12765372888710309095,
1524 15057130630522842392,
1525 14677710651300800748,
1526 10692853438748252520,
1527 12459043459128327446,
1528 2895873908250910074,
1529 12414654299833871003,
1530 13971031683534816634,
1531 13847640779080634026,
1532 217295692307502497,
1533 7750768797035502178,
1534 290949611993301720,
1535 10199100136702866567,
1536 15495972441839001396,
1537 13198452434198427151,
1538 2440498893626898052,
1539 15118747988064647069,
1540 6537279940542355961,
1541 8712445311047767491,
1542 17256665922722282910,
1543 13175508019793567143,
1544 10218901675074990248,
1545 13394299990216654516,
1546 5977932445410319532,
1547 5913587457706598533,
1548 18017099150205847183,
1549 10803505436178917593,
1550 15504988698835663005,
1551 11647690777417283778,
1552 13263578958104628128,
1553 6887980138658259663,
1554 12615506930751501449,
1555 4362286963260481429,
1556 17936849618704425417,
1557 8369687071549056310,
1558 6873677162393948122,
1559 8962347665252911678,
1560 6575009038253218272,
1561 17049757839609406426,
1562 18000487384002665628,
1563 17743261078931639159,
1564 7069552289073828088,
1565 2053907584370525129,
1566 6092754463992814730,
1567 7835970278896264421,
1568 8747049071648962742,
1569 9020604727379960828,
1570 9632547032149786788,
1571 16485371852605585328,
1572 589786022609761499,
1573 14198172759212036212,
1574 3179321442557148353,
1575 9275833134889979290,
1576 4203798446932368841,
1577 1997647913473930975,
1578 2518811456650703083,
1579 7750350188524367372,
1580 8204413870688842329,
1581 4683962365740774568,
1582 1038502292158797902,
1583 416255872857165019,
1584 89452159243564340,
1585 5029544632341923837,
1586 9006839419087725471,
1587 6081309378730152882,
1588 6841819644499887187,
1589 1989550502574820483,
1590 13603604083811099797,
1591 17579259537599657917,
1592 3688889816642246075,
1593 8365081349347412069,
1594 9781470991802711607,
1595 5096192245902990289,
1596 1498837910524874201,
1597 8053001241713783407,
1598 13235502474453488717,
1599 14236495286020360865,
1600 1736617016599872719,
1601 6171162219819586226,
1602 10365771078075021733,
1603 7005440335994057913,
1604 15987156790865471266,
1605 6743350458772878812,
1606 13939320505807395210,
1607 18411835973679513875,
1608 14557893705645834250,
1609 11183480228569397732,
1610 2863370600396906941,
1611 3249734688507432577,
1612 10075558144505269497,
1613 2962113710307186842,
1614 14006648851316589492,
1615 7556865444223108417,
1616 16635752120601038989,
1617 2805784706247063393,
1618 1921256089647591677,
1619 10043101807995880550,
1620 17183135665189377543,
1621 15209331403547677849,
1622 9759674000009984076,
1623 6188634504854345563,
1624 17429444123311113173,
1625 12716643325990854245,
1626 4404673046468281426,
1627 14977242545159900045,
1628 2353738321397058672,
1629 2217587216444012952,
1630 17848724221428205646,
1631 7788107721465269627,
1632 4209425388750317735,
1633 15986838006612180795,
1634 10448760854792387460,
1635 2181718159289817159,
1636 10626737123343057134,
1637 8531679111527745250,
1638 2221563690578844859,
1639 7279790679521017728,
1640 10678979618998152285,
1641 17119267278437855914,
1642 14741366633087203734,
1643 13977821575914403172,
1644 13984542610460459828,
1645 17859323614174580751,
1646 8221319720268548319,
1647 7448166339196439012,
1648 9427945230078429775,
1649 15205875846647517591,
1650 16806327021489489097,
1651 3923284971739738878,
1652 8300291583515256892,
1653 5684696181844315010,
1654 4112709175543117372,
1655 1305238720762,
1656 ];
1657
1658 let a1 = &mut [0; 1341];
1659 let a2 = &mut [0; 1341];
1660 let a3 = &mut [0; 1341];
1661
1662 //print!("{} {}", b.len(), c.len());
1663 long(a1, &b, &c);
1664 karatsuba(a2, &b, &c);
1665
1666 assert_eq!(&a1[..], &a2[..]);
1667
1668 // println!("res: {:?}", &a1);
1669 toom3(a3, &b, &c);
1670 assert_eq!(&a1[..], &a3[..]);
1671 }
1672 }
1673