Skip to main content
gamedev.net
🔒 Locked

Multiplication.

Started by Nice Coder 15 replies 2k views
Original Post
Nice Coder
Nice Coder
I've been thinking, about multiplication (and also division, but less so) on divises which has no mult/div support. My first one: Multiplication between two bit numbers. You first check to see if the first byte ise larger then zero. If it is, then you go and you go and do the following algorithm: 

Do until Numb = 0
y = v & (v - 1)
x = (v - y) >> bitt[z]
Output += Numa << lut[x]
Numb = y
Loop
What i am trying to do, is to get the computer to multiply, just like you were taught in school (1x4 = 4, multidigit multiplication). I go and, i seperate the lowest bit (using x), and i look that up on the table. (i first scale it back, so that no matter which byte it is, it is always 1,2,4,8,16,32,64 ect. up to 256, And not larger po2's). I then use the lut, for use in the bitshift (you know like you add the zeros on the left when multeplying? Same thing). Is there a nicer way to do multiplication (which is easier on the cpu)? Is there something like this for division too? From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Oluseyi
Oluseyi
Quote:
Original post by Nice Coder
I've been thinking, about multiplication [...] on devices which has no mult/div support.
Like what?
Nice Coder
Nice Coder
Pics, mostly.

There are also a few other devises (like some calcs, and some processors) which have no mult, and or no div support (most don't have hw div support).

From,
Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Zipster
Zipster
I don't know if the lookup table would be necessary really. I mean, something like this would suffice:
char a = 7;char b = -10;short p = (b & 0xFF);for(int i = 8; i > 0; --i){  p += (p & 1) ? (a << 8) : 0;  p >>= 1;}char o = p & 0xFF;

This will work for any combination of signed inputs a and b, given that the result is within the range of the signed char result o. Of course if you're writing a multiply routine for real it would probably be in the assembly language of your target platform.
doynax
doynax
Here's another (fast) way to do it:
Let f(x) = x^2 / 4. Thena*b = f(a+b) - f(a-b)
That way you only need a 9-bit LUT to multiply 8-bit numbers, and other operations can often be embedded directly into the table (such as scaling).
Additionally divisions are often optimized through the use of reciprocal tables.
lucky_monkey
lucky_monkey
Quote:
Original post by Nice Coder
There are also a few other devises (like some calcs, and some processors) which have no mult, and or no div support (most don't have hw div support).
I don't think that I'd buy a calculator without support for multiplication (not that I'd buy a callculator anyway, but that's beside the point)...
MrEvil
MrEvil
Quote:
Original post by Oluseyi
Quote:
Original post by Nice Coder
I've been thinking, about multiplication [...] on devices which has no mult/div support.
Like what?

This, maybe?
(It's a chip designed with hardware intercal support)
ToohrVyk
ToohrVyk
Many embedded devices do not have hardware division support, however it is implemented in software.

This does of course not mean that it's fast. We (at int13) use a lookup table method for divisions by non-powers-of-two because it is faster than standard division.

Concerning multiplication, I will direct you to the Karatsuba multiplication, which is O( n ln 3 ).

Multiplying numbers (a << n) + b and (c << n) + d, of length 2n bits.

u = (a + b)*(c + d);
v = a * c;
w = b * d;
z = (v << n) + ((u - v - w) << (n/2)) + w

Where the three multiplications are multiplications of numbers of n bits, and n, n/2 are known constants. Solve recursively until n = 1.
Blog — Facebook
Zipster
Zipster
I haven't studied the Karatsuba multiplication algorithm much, but from what I've read it's a lot better for values with a large number of digits, otherwise all the additions, subtraction, shifts, and recursion can get to you. However I would be interested in seeing it in an expanded longhand form for 8-bit operands (without solving the recurrence relation myself of course, hehe [wink]) so the recursive element can be eliminated, just to see how it compares to an 8 iteration loop. Technically the loop is linear-time on the number of bits and Karatsuba is exponential-time on the number of bits, but the loop has two branches. Maybe I could unroll the loop to. Right now I'm trying to figure out how to get MSVC to give me an optimized /O2 disassembly, but apparently that and Edit and Continue are incompatible or something, grr.
doynax
doynax
Quote:
Original post by Zipster
I haven't studied the Karatsuba multiplication algorithm much, but from what I've read it's a lot better for values with a large number of digits, otherwise all the additions, subtraction, shifts, and recursion can get to you. However I would be interested in seeing it in an expanded longhand form for 8-bit operands (without solving the recurrence relation myself of course, hehe [wink]) so the recursive element can be eliminated, just to see how it compares to an 8 iteration loop. Technically the loop is linear-time on the number of bits and Karatsuba is exponential-time on the number of bits, but the loop has two branches. Maybe I could unroll the loop to. Right now I'm trying to figure out how to get MSVC to give me an optimized /O2 disassembly, but apparently that and Edit and Continue are incompatible or something, grr.
Here's the table based version too (for multiplying two signed 8-bit integers). Kinda meaningless to try this in MSVC but I guess it could still help in roughly estimating their relative complexity.
static struct {	int base[256];	int main[256];}m_tab;void m_setup() {	int i, j, *p;	j = 65536;	p = m_tab.base;	for(i = -512; i < 512; i += 2) {		*p++ = j;		j += i + 1;	}}int m_mult(int a, int b) {	int r = m_tab.main[a + b] - m_tab.main[a - b];	return r >> 2;}
In any real implementation you'd probably skip the last right shift and either loose some precision and/or incorporate a final fixed point shift directly into the table (a table with entries 32-bit seems redudant when you'd probably get away with 8-bit ones).
Nice Coder
Nice Coder
I've been dong a little bit of thinking...

For 32 and 64 bit mults the table cannot be used, unless we use it for bytes.

The first byte of the 64 bit result of two 64 numbers being multed, is only numa[0] * numb[0], Where 0 is the byte number.

All the rest don't matter.

So, you can go and build up a mult table (64K required), and do the whole thing with less the 256 Lookups (much much less), for 64 bit numbers!.

I'll come back later, with which numebr is made up of which other bits of the other nums.

From,
Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Zipster
Zipster
A 64K lookup table for multiplication alone! Yikes. I guess it depends on the memory/speed requirements of your software, however most of these small embedded devices don't have much memory to be storing large lookup tables for "trivial" operations. Then again they don't have much speed either. You'd really have to find a good solution on a per device basis.
iMalc
iMalc
Hmm, I'd probably do something like this:
int mult(int a, int b) {int result  = (a    ) & ((b<<31)>>31);    result += (a<< 1) & ((b<<30)>>31);    result += (a<< 2) & ((b<<29)>>31);    result += (a<< 3) & ((b<<28)>>31);    ...    result += (a<<28) & ((b<< 3)>>31);    result += (a<<29) & ((b<< 2)>>31);    result += (a<<30) & ((b<< 1)>>31);    result += (a<<31) & ((b    )>>31);    return result;}
Untested though, and I doubt it works with signed numbers. Not to mention it relies on sign-extending right-shifts.
Zipster
Zipster
I believe the default is an arithmetic shift on signed variables and logical shift otherwise.
Skizz
Skizz
Quote:
Original post by Oluseyi
Quote:
Original post by Nice Coder
I've been thinking, about multiplication [...] on devices which has no mult/div support.
Like what?

Well, I'd hazard a guess that most of the biggest selling processors around don't have divide instructions and some of those don't have multiply instructions. These are: ARM (no divide but does have multiply - used in almost every mobile phone), Z80, 6502, 6800 (yes, the old 8 bit CPUs are still used a lot - the GBC being a recent example).

The x86 line is only really used in PC's and (some) Servers.

As for the algorithms of multiplying and dividing - this has come up a couple of times before and I wrote a class to do multiplication and division on real numbers (any length with floating decimal point) and is available here. It uses the f(x)=x2/4 lookup table (the table is 756 entries).

Skizz

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.