CODEWITHSUNDEEP
algorithmbitmultiplicationbigint
Dr. Van Nostrand
Dr. Van Nostrand

Reputation: 1

Arithmetic Operations using only 32 bit integers

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

Upvotes: 0

Views: 1378

Answers (2)

Spektre
Spektre

Reputation: 51923

  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

Upvotes: 0

user1084944
user1084944

Reputation:

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.

Upvotes: 1

Related Questions