Mercury-Language/mercury — pull request #13 by mgudemann (2014-02-09 15:06:38+00:00)
Title: Add integer multiplication based on Karatsuba's algorithm

This adds Karatsuba's algorithm to integer.m.

For the tests I did see https://github.com/mgudemann/mercury-contribs
executing these tests (without the comparison at the end) takes
* ca. 4m10s for the original implementation
* ca 50s with the new implementation in single thread mode
* and ca 35s in parallel mode

all in asm_fast.gc grades with mmc 13.05.02 on a laptop with Core i5 @ 2.5Ghz

At less than 35 14-bit digits it falls back to quadratic multiplication and for less than 350 14-bit digits there are not parallel conjunctions. These values seem to be reasonable choices after some tests on two different computers.

btw. when I compile the biginttest.m program using
```% mmc -O6 --intermod-opt --make --rebuild biginttest```
I get the following error:
```Uncaught Mercury exception: Software Error: ll_backend.code_info: predicate ll_backend.code_info.get_containing_goal_map_det'/2: Unexpected: no map
Stack dump not available in this grade. ** Error making `Mercury/cs/biginteger.c'.```

without `--intermod-opt' or without `-O6' it works just fine.

---

library/integer.m:
Adds Karatsuba based fast integer algorithm in the function
`pos_mul_karatsuba' which replaces the call to `pos_mul_list' in `pos_mul'.

It is a divide and conquer algorithm which uses O(n^1.585) basic operations
instead of O(n^2). The function expects two integer variables, the first
must be smaller than the second. It falls back to quadratic multiplication
if the larger factor has less than `karatsuba_threshold' digits.

If compiled in a parallel grade, the function uses parallelism for the
divide and conquer part for numbers with more than
`karatsuba_parallel_threshold' digits.

The current values for `karatsuba_threshold' is 35,
`karatsuba_parallel_threshold' is 10 times this value.