sec_karatsuba

[bodrato at mail.dm.unipi.it]

Ciao!

I tried to write a _sec_ version of Karatsuba multiplication. It is not
intended for 5.2, of course, but it is ready and I like to share it. It is
attached.

It obviously is slower than the non_sec toom22, but not terribly:

        mpn_mul_basecase mpn_toom22_mul  mpn_sec_kara
8        #0.000000127        1.3499        1.5853
9        #0.000000168        1.3025        1.4783
10       #0.000000200        1.1455        1.2907
11       #0.000000233        1.2152        1.3538
12       #0.000000277        1.0681        1.1969
13       #0.000000329        1.0855        1.2190
14        0.000000383       #0.9695        1.0928
15       #0.000000433        1.0242        1.1646
16        0.000000492       #0.9268        1.0198
17        0.000000555       #0.9826        1.0996
18        0.000000635       #0.9079        1.0035
19        0.000000677       #0.9722        1.0510
20        0.000000761       #0.8829        0.9771
21        0.000000833       #0.9291        0.9859
22        0.000000917       #0.8786        0.9304
23        0.000000988       #0.8943        0.9717
24        0.000001063       #0.8830        0.9479
25        0.000001168       #0.9002        0.9648

I used evaluation in +1 instead of -1, to avoid branches due to the sign,
and of course using _sec_add_1 to propagate carries is not very
efficient...

By the way, if you have the time to look at the code and comment, I'll
appreciate.

Regards,
m

-- 
http://bodrato.it/toom-cook/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sec_toom2_mul.c
Type: text/x-csrc
Size: 3527 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20140211/0a3e37ca/attachment.bin>