# multiplication with insufficiently long registers [duplicate]

I want to multiply two numbers but since I don’t have long enough registers in the current architecture need to “break them down” into shorter ones and somehow perform the calculation.

For example:

2048.125 x 2048.125 (2048.125 =>4001hex) but with the binary point beyond the 4th bit position (Q12.4 signed) and upwards .

Is there any way to split up the operation, and combine the results in the end?

Unfortunately the configuration am working on does not support well known libraries thus,I have to build one by myself.

Please provide any pointers that could lead to mathematical oriented implementation.Something that could possibly emerge out of manipulation of the partial products or similar.

Thanks

• Hint: How do you multiply two large numbers on paper, even though each "register" can only hold numbers 0-9? What if humans didn't have 10 fingers but 2**32? Oct 2, 2015 at 10:03
• Let's try this again. How do you multiply numbers in base 10? Now do the same with digits that are 8 bits, 16 bits or 32 bits in size. It's ordinary arithmetic. Oct 2, 2015 at 10:37
• Read the Wikipedia article and the section that begins with the phrase "To multiply two fixed-point numbers, ...". Oct 2, 2015 at 10:59
• @GiwrgosRizeakos You have just named it in your question - partial products ! To be frank I don't even know what it is that you think you don't understand, as it seems that you have already understood it. Oct 2, 2015 at 11:03
• @GiwrgosRizeakos: don't comment your own question but edit your question to improve it. Oct 2, 2015 at 11:22

## 1 Answer

I would try to avoid coding in assembler, and if possible adapt an existing C compiler to your target processor.

With GCC you have a lot of targets which could inspire you for your processor, and there are lots of documentation for that (see references in http://gcc-melt.org/docum.melt for more). Indeed it requires some effort (months of work).

Wide (but fixed size, e.g. two native `int`s -wide, such as 64 bits arithmetic on processors with 32 bits-wide words) arithmetic is done in GCC inside its libgcc/ directory, and most of that is coded in C (but depends a lot on how your GCC is configured and targeted). Even if you don't use or port GCC to your architecture (and I believe you really should), that `libgcc` should be inspirational (and IIRC, some books by Knuth explain the underlying algorithms, most of them being fairly intuitive.). Read also wikipage on fixed-point arithmetic.

If you want arbitrarily large integers, you need a bignum library. Don't reinvent your own (there are many tricky algorithms more efficient than the naive way you have learned at school, and you'll find several books and many research articles and conferences on the subject; you still can get a PhD on bignums and spend a full work life on them). Use an existing one, e.g. GMPlib.

Even for your own target processor, you should not code much in assembler. You'll better port some existing C compiler to it (and practically you need one, if you want your processor to be used).

• thank you Basile for your effort but as I highlighted above "The question is more of mathematical nature rather than language specific shortcuts".So what am asking effectively is of a mathematical oriented method to break down the operation instead of using the language's or library's capabilities.I am looking for a known algorithm to implemented myself because my current configuration does not allow none of the above. Oct 2, 2015 at 10:56
• Either you want fixed multi-word arithmetic, then look inside the algorithms of `libgcc`. Or you want arbitrarily large integers (bignums are a very complex algorithmic subject; there are many books on that, and you can get a PhD on the subject). Then better use an existing library Oct 2, 2015 at 10:59