Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
July 9th, 2003, 01:52 AM
 justujoo
Contributing User

Join Date: Oct 2002
Posts: 32
Time spent in forums: < 1 sec
Reputation Power: 12
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...!

#2
July 13th, 2003, 01:57 PM
 ygfperson
Junior Member

Join Date: Feb 2003
Posts: 10
Time spent in forums: < 1 sec
Reputation 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
July 13th, 2003, 02:43 PM
 M.Hirsch
Contributing User

Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 190
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...
__________________
--
Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.

#4
July 13th, 2003, 02:51 PM
 justujoo
Contributing User

Join Date: Oct 2002
Posts: 32
Time spent in forums: < 1 sec
Reputation Power: 12
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
July 13th, 2003, 03:00 PM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
you can copy / simplify a working algorithm from the java source - see BigInteger.java and MutableBigInteger.java

#6
July 13th, 2003, 06:59 PM
 M.Hirsch
Contributing User

Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 190
Quote:
 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/ar.../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:
Quote:
 Floating-point binary format is defined in IEEE Standard 754; eg at http://research.microsoft.com/~holl.../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
July 14th, 2003, 05:43 AM
 justujoo
Contributing User

Join Date: Oct 2002
Posts: 32
Time spent in forums: < 1 sec
Reputation Power: 12
Thanks again, I'll tell u if I cam up with something....

#8
August 26th, 2003, 01:19 AM
 dannywild82
Junior Member

Join Date: Aug 2003
Posts: 28
Time spent in forums: 19 m 39 sec
Reputation Power: 0
if its for an assignment (speed not essential), just chop the "string" numbers up into chunks and allow for a carry over.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Multiplication/Division Algorithem