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

    Join Date
    Oct 2002
    Posts
    32
    Rep 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. #2
  3. 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.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep 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...
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2002
    Posts
    32
    Rep 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...
    posted by: justujoo

    Error 13: BRAIN.SYS not responding, process terminted...!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

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

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep Power
    190
    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 06:03 PM.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2002
    Posts
    32
    Rep Power
    12
    Thanks again, I'll tell u if I cam up with something....
  14. #8
  15. 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.

IMN logo majestic logo threadwatch logo seochat tools logo