Merge C version of decimal into py3k.

[mdickinson]

BPO	7652
Nosy	@malemburg, @rhettinger, @amauryfa, @mdickinson, @pitrou, @vstinner, @ericvsmith, @benjaminp, @cedk, @asvetlov, @skrah, @ericsnowcurrently, @jimjjewett
Files	49433f35a5f8.diff bba956250186.diff be8a59fcba49.diff: fixed all comments except the ones in ISSUES.txt ppro-mulmod.txt: Proof for x87 FPU modular multiplication 40917e4b51aa.diff 9b3b1f5c4072.diff api-demo.c

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/skrah' closed_at = created_at = labels = ['extension-modules', 'library', 'performance'] title = 'Merge C version of decimal into py3k.' updated_at = user = 'https://github.com/mdickinson' ``` bugs.python.org fields: ```python activity = actor = 'skrah' assignee = 'skrah' closed = True closed_date = closer = 'skrah' components = ['Extension Modules', 'Library (Lib)'] creation = creator = 'mark.dickinson' dependencies = [] files = ['22404', '23822', '23959', '23966', '24615', '24776', '25049'] hgrepos = ['25'] issue_num = 7652 keywords = ['patch'] message_count = 83.0 messages = ['97347', '97348', '97355', '97372', '97373', '97377', '97382', '97411', '97412', '97719', '98161', '120305', '120674', '121452', '138029', '138583', '148650', '148652', '148669', '148677', '148678', '148680', '148682', '148687', '148688', '148689', '148690', '148691', '148721', '149556', '149557', '149559', '149567', '149600', '153447', '153506', '153507', '154074', '154988', '154992', '155031', '155034', '155036', '155045', '155046', '155047', '155050', '155059', '155070', '155071', '155079', '155082', '155083', '155085', '155086', '155087', '155088', '155093', '155095', '155107', '155135', '155331', '155359', '155381', '155419', '155644', '155649', '155743', '155744', '156402', '156480', '156500', '156671', '156890', '156952', '164470', '165329', '165330', '165339', '165341', '168034', '168035', '169692'] nosy_count = 19.0 nosy_names = ['lemburg', 'rhettinger', 'amaury.forgeotdarc', 'mark.dickinson', 'pitrou', 'vstinner', 'casevh', 'eric.smith', 'benjamin.peterson', 'jjconti', 'Arfrever', 'ced', 'asvetlov', 'skrah', "Amaury.Forgeot.d'Arc", 'python-dev', 'eric.snow', 'Ramchandra Apte', 'Jim.Jewett'] pr_nums = [] priority = 'normal' resolution = 'fixed' stage = 'resolved' status = 'closed' superseder = None type = 'performance' url = 'https://bugs.python.org/issue7652' versions = ['Python 3.3'] ```

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Benjamin Peterson \report@bugs.python.org\ wrote:

The scripts for generating code would preferably go in a Tools/decimal directory.

Hmm, do you mean the gen.py scripts? The output is generated by decimal.py and used for testing libmpdec. While the syntax resembles that of the \.decTest files, only tests/runtest can handle the format.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Benjamin Peterson \report@bugs.python.org\ wrote:

Speaking of inline, the "inline" keyword will have to go because it's not C89.

Do you happen to know a free compiler that builds Python but does not understand "inline"? I'm asking because without testing you can never really be sure:

For example I added support for compilers without uint64_t, but all major compilers (gcc, suncc, icc, VS) of course have uint64_t.

Then I finally found CompCert, and discovered that a couple of things were missing in the headers.

[pitrou]

Do you happen to know a free compiler that builds Python but does not understand "inline"? I'm asking because without testing you can never really be sure:

You could use Py_LOCAL_INLINE, but most compilers should inline small functions automatically, AFAIK.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Case Van Horsen \report@bugs.python.org\ wrote:

cdecimal 2.3 does not support the __ceil and __floor

Thanks. I'll look into that.

cdecimal.Decimal instances do not emulate the various single-underscore methods of a decimal.Decimal instance. In gmpy2, I use _int, _exp, _sign, and _is_special to convert a decimal.Decimal into an exact fraction. I realize the issue is with gmpy2 and I will fix gmpy2, but there may be other code that uses those methods.

There seems to be a real need for getting (sign, coeff, exp). I think psycopg2 uses a painful way to get an integer coefficient via as_tuple(). What should really be added is either as_triple(), which would return (sign, coeff, exp) with an integer coefficient or make these attributes official:

Decimal.sign Decimal.coeff Decimal.exp

I have to think about implementing Decimal._int etc. Somehow I feel that doing so would send a wrong signal: People shouldn't assume that they'll get away with using private methods and attributes.

Also, of course they'll keep using these private methods until they are finally deprecated, and *then* they'll have to change things.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Antoine Pitrou \report@bugs.python.org\ wrote:

You could use Py_LOCAL_INLINE, but most compilers should inline small functions automatically, AFAIK.

At the time I wrote it I benchmarked everything. I'm pretty sure that gcc did not inline larger functions like mpd_qresize_zero() and mpd_word_digits() and even some smaller ones that are declared ALWAYS_INLINE. Also, the static inline functions in the header files are absolutely crucial for speed.

I recall that Mark initially said that in the Modules hierarchy not every module would need to compile. Now, _decimal is already tested with gcc, clang, icc, suncc, Visual Studio, and success has been reported with xlc[1]. CompCert compiles libmpdec but not Python.

_ctypes does not compile with icc and suncc. Unlike _ctypes, _decimal has a fallback in the form of decimal.py. So, perhaps as an alternative we could leave the inlines and wait for build failure reports?

[1] compilation success, one of the numerous AIX issues on bugs.python.org with loading the module was encountered IIRC.

[pitrou]

_ctypes does not compile with icc and suncc. Unlike _ctypes, _decimal has a fallback in the form of decimal.py. So, perhaps as an alternative we could leave the inlines and wait for build failure reports?

Sounds good to me.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Jim Jewett \report@bugs.python.org\ wrote:

implementation details. Are there are clear distinctions (type info/python bindings/basic arithmetic/advanced algorithms/internal-use-only/???)

I failed to mention that libmpdec also has complete documentation. Perhaps that can answer some questions:

http://www.bytereef.org/mpdecimal/doc/libmpdec/index.html http://www.bytereef.org/mpdecimal/doc/libmpdec/functions.html#quiet-functions

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Marc-Andre Lemburg \report@bugs.python.org\ wrote:

Does the C version have a C API importable as capsule ?

Not yet. I'll try to make a list with proposed function names and post it here.

If not, could you add one and a decimal.h to go with it ?

Yes, sure.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

This issue was raised by Jim on Rietveld:

Currently, the order of arguments in Context.__init__() differs from repr(Context):

>>> Context()
Context(prec=28, rounding=ROUND_HALF_EVEN, Emin=-999999999, Emax=999999999, capitals=1, flags=[], traps=[DivisionByZero, Overflow, InvalidOperation])
>>> 
>>> Context(28, ROUND_HALF_EVEN, -999999999, 999999999, 1, [], [DivisionByZero, Overflow, InvalidOperation])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.2/decimal.py", line 3774, in __init__
    flags = dict([(s, int(s in flags)) for s in _signals])
  File "/usr/lib/python3.2/decimal.py", line 3774, in <listcomp>
    flags = dict([(s, int(s in flags)) for s in _signals])
TypeError: argument of type 'int' is not iterable
>>> 

I find this quite ugly. The repr() order is the good one, since it moves the flag dictionaries to the end. I wanted to change the order in Context.__init__() to match repr(), but I'm not sure if such a change is possible.

I don't think Python code would initialize a context without keywords, but C extensions might.

[74c4563b-ab1c-43d8-9219-30c4eca796bc]

On Wed, Mar 7, 2012 at 5:28 AM, Stefan Krah \stefan-usenet@bytereef.org\ added the comment:

OK, as a basis for discussion I've added: http://hg.python.org/features/cdecimal/file/8b75c2825508/Modules/_decimal/FILEMAP.txt

That is indeed very helpful. So helpful that now I understand well enough to have additional gripes. :D

Starting from that URL, I don't actually find setup.py.

I am assuming (but would prefer to have the file explicitly state) that _decimal.c and docstrings.h are the only source files, and that setup.py would be the only build infrastructure needed if you already had libmpdec.a.

I'm not sure what sort of failures building in the normal order led to, but that is certainly something worth documenting, and (ideally) fixing.

I didn't see any mention of the literature subdirectory, which makes me wonder if there were other files not listed in the map. (Not yet curious enough to verify for myself, though.) (*.txt files?)

I suppose a subdirectory name like "python" makes sense when you look at the library as a C/C++ project that happens to provide python bindings; as part of the python core, it is misleading. It sounds like it should be named "extended_tests" or some such. (Note that this assumes it is strictly for tests; if you are also using it to provide extra functionality, or to generate some of the source code, then I agree with Benjamin that it should move to tools, and the generated code should have clear comments right at the top warning that it is generated.)

Within the library, does io.[ch] really limit itself to ASCII? If so, then I don't know why you're worried about the Turkish i. If you mean generic text, then please don't specify ASCII.

Within memory.[ch], how much of this configurability is useful (or even available) to a python user, as opposed to an extension writer? Or is it really just for testing? As in, would it be reasonable to just have a single header with a half-dozen #defines, but to replace that header when doing a memory-test build? Or at least to hide the alternative function definitions inside an obvious #ifdef, so that they don't take up memory and attention when they aren't applicable?

Under the Bignum section, it mentions that functions from these files are ultimately used in _mpd_fntmul, but doesn't mention where that is (in the main _cdecimal.c)

Also, when it talks about "large arrays", could you clarify that it isn't talking about arrays of values or even matrixes, it is just talking about numbers large enough that even representing them takes at least N bytes?

> Would it at least be OK to wrap them in stubs for exporting, so that > the test logic could be places with the others tests?  (I worry that > some tests may stop getting run if someone else modifies the build > process and doesn't notice the unusual location.)

tests/runtest.c won't compile then. I'll look into the stub and also the _testhelp suggestions.

OK, let me rephrase. Is newton division exported to users, or used internally, or is it just for testing purposes?

_mpd_qtest_newtondiv is documented as a testcase; I would rather see it move to a test file. Why can't it? If it is because of _mpd_qdiv_inf, _settriple, _mpd_qbarrett_divmod, _mpd_real_size (the only apparently internal things it uses), then why are these internal? Could they be exposed at least to test functions? If not, could they at least be wrapped in something that could exposed, such as _testhelp_mpd_qdiv_inf?

> > "Infinity", "InFinItY", "iNF" are all allowed by the specification.

> OK; so is io.c part of the library, or part of the python binding?

I see a potential source of confusion: io.c is firmly part of the library.

[And should therefore be available when used without python?]

All PEP-3101 formatting is part of libmpdec, because I like the mini language. io.c only understands ASCII and UTF-8 fill characters.

It is the *library* tests that would fail under the Turkish locale (if not for _mpd_strneq).

Are those tests relevant to a _cdecimal built in to python itself? If not, then the comment is at least misleading. Would it make sense to have a directory for files that are used only for the standalone C library, but not when built as part of python?

> Good enough, though I would rather see that as a comment near the assembly.

Comments how to enforce an ANSI build (much slower!) are in LIBTEST.txt and now also in FILEMAP.txt.

I would not have made the leap from that to "What to do if the assembly code needs to be replaced or even just changed."

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Jim Jewett \report@bugs.python.org\ wrote:

> OK, as a basis for discussion I've added: > http://hg.python.org/features/cdecimal/file/8b75c2825508/Modules/_decimal/FILEMAP.txt

Starting from that URL, I don't actually find setup.py.

It's the setup.py from the Python top level directory.

I'm not sure what sort of failures building in the normal order led to, but that is certainly something worth documenting, and (ideally) fixing.

I do not have access to AIX. On Windows the failures were locale related when mixing the dynamic and static runtimes.

I didn't see any mention of the literature subdirectory, which makes me wonder if there were other files not listed in the map. (Not yet curious enough to verify for myself, though.) (*.txt files?)

FILEMAP.txt was intended to get people started, not to be a polished work.

I suppose a subdirectory name like "python" makes sense when you look at the library as a C/C++ project that happens to provide python bindings; as part of the python core, it is misleading.

OK.

provide extra functionality, or to generate some of the source code,

There is no source code generation. I'm not sure where this idea comes from. genlocale.py e.g. has this comment:

Usage: ../../../python genlocale.py | ../tests/runtest -

Within the library, does io.[ch] really limit itself to ASCII? If so, then I don't know why you're worried about the Turkish i. If you mean generic text, then please don't specify ASCII.

I do mean ASCII. Please run this gdb session:

diff --git a/Modules/_decimal/io.c b/Modules/_decimal/io.c
--- a/Modules/_decimal/io.c
+++ b/Modules/_decimal/io.c
@@ -245,7 +245,7 @@
                if (digits > (size_t)(ctx->prec-ctx->clamp))
                        goto conversion_error;
        }
-       else if (_mpd_strneq(s, "inf", "INF", 3)) {
+       else if (strncasecmp(s, "inf", 3) == 0) {
                s += 3;
                if (*s == '\0' || _mpd_strneq(s, "inity", "INITY", 6)) {
                        /* numeric-value: infinity */

gdb ../../python
b mpd_qset_string
r
>>> locale.setlocale(locale.LC_ALL, 'tr_TR.utf8')
'tr_TR.utf8'
>>> from decimal import *
>>> Decimal("Infinity")

(gdb) 248 else if (strncasecmp(s, "inf", 3) == 0) { (gdb) p s $1 = 0x7ffff7191280 "Infinity" (gdb) p s[0] $2 = 73 'I' (gdb) n 259 if ((coeff = scan_dpoint_exp(s, &dpoint, &exp, &end)) == NULL)

Clearly 'I' is ASCII and strncasecmp fails, exactly as written in the comment above _mpd_strneq().

Within memory.[ch], how much of this configurability is useful (or even available) to a python user, as opposed to an extension writer?

Since it is in the libmpdec section, "User" refers to the extension writer. I can simply drop the "User".

Under the Bignum section, it mentions that functions from these files are ultimately used in _mpd_fntmul, but doesn't mention where that is (in the main _cdecimal.c)

OK.

Also, when it talks about "large arrays", could you clarify that it isn't talking about arrays of values or even matrixes, it is just talking about numbers large enough that even representing them takes at least N bytes?

But it is referring to abstract sequences or arrays of values less than a certain prime. These values happen to be the coefficient of an mpd_t, but you could perform the transform on any sequence.

I thought 'Bignum' would already imply an array of machine words representing a number.

>> Would it at least be OK to wrap them in stubs for exporting, so that >> the test logic could be places with the others tests? ??(I worry that >> some tests may stop getting run if someone else modifies the build >> process and doesn't notice the unusual location.)

> tests/runtest.c won't compile then. I'll look into the stub and also > the _testhelp suggestions.

OK, let me rephrase. Is newton division exported to users, or used internally, or is it just for testing purposes?

It's used internally as _mpd_qbarrett_divmod(). When the coefficient has more than MPD_NEWTONDIV_CUTOFF words, the division functions dispatch to _mpd_qbarrett_divmod().

_mpd_qtest_newtondiv is documented as a testcase; I would rather see it move to a test file. Why can't it?

I said in my last mail that I'll look into it.

>> > "Infinity", "InFinItY", "iNF" are all allowed by the specification.

>> OK; so is io.c part of the library, or part of the python binding?

> I see a potential source of confusion: io.c is firmly part of the > library.

[And should therefore be available when used without python?]

I meant: Despite the fact that io.c might /appear/ to be specifically written for the module because of the presence of PEP-3101 references, it is part of the standalone (moduleless) library. However, _decimal.c uses all parts of io.c except for a couple of functions at the bottom of the file that are useful for debugging.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Here's a new patch that addresses several remarks:

o _decimal now has __floor and __ceilmethods.

o libmpdec is now in a separate directory.

o I removed the big libmpdec test suite. This is why:

 - It reduces the number of files that has been criticized multiple times.

 - Probably I'll be the only one who will be running the test suite.

 - The test suite is still on PyPI.

 - The test suite is so large that it's a magnet for toolchain bugs.
   For example, it found a bug in suncc (acknowledged and fixed by Sun)
   and a bug in CompCert (acknowledged and fixed by Xavier Leroy).

   I'm really worried that *if* someone runs the tests and finds
   an obscure bug, I'll have to spend hours debugging something
   that might ultimately be an external bug.

o Renamed "python" directory into "tests".

o Test functions in mpdecimal.c are removed.

o All files in libmpdec that aren't required for _decimal are removed.

o Extra functionality in _decimal.c is commented out. This does not yet cover the FloatOperation signal, which I would like to add to decimal.py as well (I'll ask later on python-dev).

[80036ac5-bb84-4d39-8416-02cd8e51707d]

Please add --with-system-libmpdec (or --with-system-mpdecimal) option in configure, similarly to --with-system-expat and --with-system-ffi options.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Benjamin Peterson \report@bugs.python.org\ wrote:

Speaking of inline, the "inline" keyword will have to go because it's not C89.

Actually the trickier instances of "inline" in the .c files are already suppressed when LEGACY_COMPILER (i.e. C89) is defined. I've now listed the machine options here:

http://hg.python.org/features/cdecimal/file/0f032cda94aa/Modules/_decimal/README.txt

As I now remember, that was in fact necessary for CompCert. The "static inline" instances in header files might not be a problem even for embedded compilers, see e.g.:

http://embeddedgurus.com/barr-code/2011/03/do-inline-function-bodies-belong-in-c-header-files/

IIRC also the Linux kernel uses "static inline" in header files.

[rhettinger]

FWIW, I think we would be better off if this patch were merged in soon. Waiting until later in the release cycle risks introducing bugs that we won't have time to notice or fix. An early merge lets more people exercise the code.

[benjaminp]

Stefan, please feel free to commit the latest patch.

[mdickinson]

FWIW, I think we would be better off if this patch were merged in soon.

+1

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Mark Dickinson \report@bugs.python.org\ wrote:

> FWIW, I think we would be better off if this patch were merged in soon.

+1

OK, I'm counting three +1 for merging soon. Thanks everyone for the encouragement!

I'll then proceed with the merge this weekend or shortly after, with one caveat:

My *second* self-review of mpdecimal.c is currently at 17%, but I can as well continue with that if the whole thing is merged. I'll probably replace the caching of ln(10) (not thread-safe, protected by the GIL) with a real thread-safe version.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Arfrever Frehtes Taifersar Arahesis report@bugs.python.org wrote:

Please add --with-system-libmpdec (or --with-system-mpdecimal) option in configure, similarly to --with-system-expat and --with-system-ffi options.

I've added that to the list of issues. However, if there is any change in the behavior of decimal.py that also applies to the library, the libmpdec shipped with Python will be silently updated.

I can probably release a matching external libmpdec with every major Python release, but I can't promise to track all minor releases.

This would mean that for Python-3.3 the yet unreleased mpdecimal-2.4, hopefully with thread-safe mpd_pow(), mpd_ln() and mpd_log10() should be used.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

We need to decide what to do with the different limits of the 64-bit and 32-bit versions:

               MAX_EMAX    

default context 10**9-1
64-bit 10**18-1 32-bit 425000000

I think it would be annoying to have the values in DefaultContext, ExtendedContext and BasicContext depend on the machine.

The best thing might be to use Emax=10**8-1 and Emin=-(10**8-1) throughout. I don't think many applications depend on having Emax=10**9-1. If they do, they'll have to use the 64-bit version.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

The best thing might be to use Emax=10**8-1 and Emin=-(10**8-1) throughout. I don't think many applications depend on having Emax=10**9-1. If they do, they'll have to use the 64-bit version.

10**6-1 would be another option. The advantage is that it's visually obvious that the default exponents have changed.

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset 7355550d5357 by Stefan Krah in branch 'default': Issue bpo-7652: Integrate the decimal floating point libmpdec library to speed http://hg.python.org/cpython/rev/7355550d5357

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset f6d646e30028 by Stefan Krah in branch 'default': Issue bpo-7652: Enable linking of _decimal.so against an installed libmpdec. http://hg.python.org/cpython/rev/f6d646e30028

[vstinner]

You may now close the issue.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

I have a couple of questions about the proposed capsule C API. In order to be useful, it should be possible to set temporary contexts and pass them to functions. For example, PyDec_Add could look like:

   PyDec_Add(PyObject *a, PyObject *b, PyObject *context);

To stay sane, either access macros or access functions to the context would need to be provided:

  CTX(workcontext)->prec = 100;
  PyDec_SetPrec(workcontext, 100);
  PyDecContext_SetPrec(workcontext, 100);

Probably flags would need to be checked at some point:

if (CTX(workcontext)->status & MPD_Underflow) if (PyDec_GetStatus(workcontext) & MPD_Underflow) if (PyDecContext_GetStatus(workcontext) & MPD_Underflow)

I wonder if users would not be better off if libmpdec functions and access macros were exposed instead. The big advantage is that errors (even malloc errors) propagate in the form of NaNs, so it is not necessary to do repeated error checking.

Also, I find things like (status & MPD_Underflow) more readable than the alternatives above.

I've attached a short (fake) example to demonstrate what I mean.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

I've opened bpo-15237 for the capsule API. I didn't add everyone to the nosy list, since I suspect it's not of general interest.

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset afdb0e1a9dac by Stefan Krah in branch 'default': Issue bpo-7652: Clean up _mpd_qinvroot() and mark it LIBMPDEC_ONLY. Use the http://hg.python.org/cpython/rev/afdb0e1a9dac

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

I switched the algorithm in mpd_qsqrt() to the one from decimal.py. Previously the square root was calculated in terms of 1/invsqrt(x).

Curiously enough this scheme _always_ seems to produce exact results when expected, but I don't have a proof. I remember I left this in because the specification gives some leeway with respect to exact results:

"Square-root can also be calculated by using the power operation (with a second operand of 0.5). The result in that case will not be exact in most cases, and may not be correctly rounded."

Anyway, the algorithm from decimal.py gives the desired guarantees and is also faster.

Since we're almost in beta-2 stage, would someone be able to do a post commit review of mpd_qsqrt()? It should be a direct translation from the function in decimal.py.

[amauryfa]

I compared both implementations, and they are the same.

I noticed that on line 7537, the call to mpd_qshiftl() may "goto malloc_error;". I think there is a memory leak in this case, "mpd_del(&c)" and 2 others lines are skipped.

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

Thanks, Amaury! -- "goto malloc_error" should not leak, because there's always a jump to the "out" label in line 7563.

I use this idiom a lot ever since I saw it in several places in the Linux kernel. Of course it's a matter of taste.

[vstinner]

Is there some remaining work on this issue? Or can it be closed?

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

I'm almost done with my (second) self-review of mpdecimal.c. The only functions missing are all Karatsuba functions and mpd_qpowmod().

If there are any takers, I would be very happy. For the Karatsuba functions you'll probably need Roman Maeder's paper, which I could send to anyone interested. All I can promise is that it's a beautiful formulation of the algorithm. :)

[5531d0d8-2a9c-46ba-8b8b-ef76132a492c]

My review is done. The Karatsuba function is basically a small stack machine and very hard to prove formally as far as I can see. The algorithm is cited in TAOCP and the subdivision is brute force tested for all combinations of coefficient lengths of the two input operands that are used in libmpdec (currently 256 \< nwords \<= 1024).