0

How would you compute the multiplication of two 1024 bit numbers on a microprocessor that is only capable of multiplying 32 bit numbers?

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
Dr. Van Nostrand
  • 1
  • 2
  • 1
    Do you have a specific language? If you're using Java, then check out the BigInteger class in the java.math package. If not, find a similar library for what you're using. – childofsoong Mar 07 '15 at 00:59
  • Example code: https://sites.google.com/site/indy256/algo_cpp/bigint – Stephen C Mar 07 '15 at 01:02
  • No, I'm interested in the mathematics behind it, not necessarily the implementation details. – Dr. Van Nostrand Mar 07 '15 at 01:03
  • Then read about the Karatsuba algorithm: http://en.wikipedia.org/wiki/Karatsuba_algorithm. Or just generalize from the algorithm you were taught in primary school for doing long multiplication with "words" that represent the 10 possible numbers :-) – Stephen C Mar 07 '15 at 01:03
  • The following link explains how to do it for 64 bit numbers, which can easily be extended to 1024: http://stackoverflow.com/questions/15123638/fixed-point-multiplication-without-64-bit-temporary/15123849#15123849 – Ari Mar 07 '15 at 01:03
  • 1
    Just multiply like you would manually. The algorithm is basically the same... use base 2^32. – thang Mar 07 '15 at 01:05
  • The math gets a bit easier if you allow a "widening" multiplication, where the width of the result is the sum of the widths of the inputs (say, 32x32 where you get 64 bits of result). That's not something arbitrary, it's something many processors offer (even if high level languages do not). – harold Mar 07 '15 at 01:06

2 Answers2

1

The starting point is to realize that you already know how to do this: in elementary school you were taught how to do arithmetic on single digit numbers, and then given data structures to represent larger numbers (e.g. decimals) and algorithms to compute arithmetic operations (e.g. long division).

If you have a way to multiply two 32-bit numbers to give a 64-bit result (note that unsigned long long is guaranteed to be at least 64 bits), then you can use those same algorithms to do arithmetic in base 2^32.

You'll also need, e.g., an add with carry operation. You can determine the carry when adding two unsigned numbers of the same type by detecting overflow, e.g. as follows:

uint32_t x, y; // set to some value
uint32_t sum = x + y;
uint32_t carry = (sum < x);

(technically, this sort of operation requires that you do unsigned arithmetic: overflow in signed arithmetic is undefined behavior, and optimizers will do surprising things to your code you least expect it)

(modern processors usually give a way to multiply two 64-bit numbers to give a 128-bit result, but to access it you will have to use compiler extensions like 128-bit types, or you'll have to write inline assembly code. modern processors also have specialized add-with-carry instructions)

Now, to do arithmetic efficiently is an immense project; I found it quite instructive to browse through the documentation and source code to gmp, the GNU multiple precision arithmetic library.

0

  1. look at any implementation of bigint operations

    • here are few of mine approaches in C++ for fast bignum square
    • some are solely for sqr but others are usable for multiplication...

  2. use 32bit arithmetics as a module for 64/128/256/... bit arithmetics

    • see mine 32bit ALU in x86 C++
    • use long multiplication with digit base 2^32
    • can use also Karatsuba this way
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380