### Thread: Multiplication/Division Algorithem

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2002
Posts
32
Rep Power
16

#### Multiplication/Division Algorithem

I am making a class that can manipulate huge integers (40 digit ints)...

As for multiplication with simple integers, I've come up with the following:

HUGE_INT * 3 = HUGE_INT + HUGE_INT + HUGE_INT

but for division, I don't really have an idea...

Also, what should I do if I want to multiply/divide the HUGE_INT with something like 3.5 (i.e. floating point number) instead of 3 (i.e. an integer)...

Also, do tell me if u have a more efficient algorithem than this one...
2. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Posts
10
Rep Power
0
I'm assuming you're using basic 32-bit integers, or 8-bit bytes (as letters -- 40 byte == 40 digits) to represent the number. In any case, the procedure's the same: multiply, and carry over. Be aware that if you use 16-bits to represent a data unit, you need 32-bits to hold the multiplication value.
3. No Profile Picture
Contributing User
Devshed God 1st Plane (5500 - 5999 posts)

Join Date
Oct 2000
Location
Back in the real world.
Posts
5,960
Rep Power
194
You are facing the general problems of storing and processing numbers in a machine.
- how to store floating point numbers?
- when (and how) to convert between float and int?
- multiplication is very ineffective
- division and modulus even more
- you can imagine what it takes to do powers, roots, etc.

Floating point numbers and integer numbers are handled completely independent in a CPU / FPU.
Example:
If you take this line of C code:
int i=5*0.5f;
This will translate to assembler code that converts the int (5) to a float (5.0), multiplies it with the other operand (0.5f) and then converts the result back to an int (i=2, precision lost in this case).

Sounds like you have quite some work ahead...

There is pre-built libraries to handle big numbers. iirc there is even an "arbitrary precision maths" library under the GPL. Maybe you want to get one of these...
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2002
Posts
32
Rep Power
16

#### Thanks M Hirsch...

Thanks a lot...

You've describe my problems quite right... Yes this thing is driving me nuts...

As for pre-made libraries, I know about them but this is an assignment (worth 4 points buddy, that's something after all) and so I don't have much options...
5. No Profile Picture
epl
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2001
Location
Dublin
Posts
413
Rep Power
17
you can copy / simplify a working algorithm from the java source - see BigInteger.java and MutableBigInteger.java
6. No Profile Picture
Contributing User
Devshed God 1st Plane (5500 - 5999 posts)

Join Date
Oct 2000
Location
Back in the real world.
Posts
5,960
Rep Power
194
worth 4 points
Ok, I see...
I guess you do have some mathematical background...
Donīt you have a formula tables or another book that contains explanations of basic arithmetic then? A university level algebra book should have abstract definitions for them. iirc this stuff was related to vector space theory (is this the right word?), but I could be 100% wrong. This is too long ago and theory was never my strength...

IMO you should make sure first if floating point maths is really required for getting your credits. Because this would imo more than double the complexity and also "somewhat" make 2 distinct projects of it.

In case you want / have to take care of floating point numbers too, this article could be interesting:
http://www.gamedev.net/reference/art...article203.asp
It is about optimizing code, but the first chapter describes an interesting way to represent floating point numbers using integers and how to do fp math with only integer functions.

Maybe you want to implement this instead of real FP code and overload all operators so floats are converted to int (with the right size) first.

... I just wanted to look up the precision of doubles in bits. Interesting, among the top 10 search results was a devshed thread: http://forums.devshed.com/archive/42/2003/03/2/55316 . Big thanks to dwise1_aol for this info:
Floating-point binary format is defined in IEEE Standard 754; eg at http://research.microsoft.com/~holla...ieeefloat.html .
To epl: ... Hey, you canīt say that to a student! Us "older" guys at least have to claim that we never did things like that...

M.

PS: if you find the arithmetic algorithms somewhere in an algebra book, please post back here or PM me.
Last edited by M.Hirsch; July 13th, 2003 at 07:03 PM.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2002
Posts
32
Rep Power
16
Thanks again, I'll tell u if I cam up with something....
8. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
28
Rep Power
0
if its for an assignment (speed not essential), just chop the "string" numbers up into chunks and allow for a carry over.