
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...
posted by: justujoo
Error 13: BRAIN.SYS not responding, process terminted...!
July 13th, 2003, 12:57 PM

I'm assuming you're using basic 32bit integers, or 8bit 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 16bits to represent a data unit, you need 32bits to hold the multiplication value.
July 13th, 2003, 01:43 PM

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 prebuilt 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...
July 13th, 2003, 01:51 PM

July 13th, 2003, 02:00 PM

you can copy / simplify a working algorithm from the java source  see BigInteger.java and MutableBigInteger.java
July 13th, 2003, 05:59 PM

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:
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 06:03 PM.
July 14th, 2003, 04:43 AM

Thanks again, I'll tell u if I cam up with something....
August 26th, 2003, 12:19 AM

if its for an assignment (speed not essential), just chop the "string" numbers up into chunks and allow for a carry over.