200 digit integer... how?

This is a discussion on 200 digit integer... how? within the C Programming forums, part of the General Programming Boards category; I have a project that requires working with two hundred digit numbers. I am at a loss on how to ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37

    Question 200 digit integer... how?

    I have a project that requires working with two hundred digit numbers. I am at a loss on how to do this. If someone could modify the source below I am sure I could implement it into my own project. Thanks.

    -skeptik

    /*
    * factor.c -- Prompts user to enter an integer N. It prints out
    * if it is a prime or not. If not, it prints out all of its
    * proper factors.
    */

    #include <stdio.h>

    int main(void)
    {
    int n;
    int lcv;
    int flag; /* flag initially is 1 and becomes 0 if
    we determine that n is not a prime */

    printf("Enter value of N : ");
    scanf("%d", &n);

    for (lcv=2, flag=1; lcv <= (n / 2); lcv++) {
    if ((n % lcv) == 0) {
    if (flag)
    printf("non-trivial factors of %d are:\n", n);

    flag = 0;
    printf("\t%d\n", lcv);
    }
    }
    if (flag)
    printf("%d is prime\n", n);
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    200 digit numbers are big - like you need 84 bytes worth of bits to represent a 200 decimal digit number accurately (which you'll need for this problem).

    Now you could do something like
    typedef unsigned long int bignum[21]; // this is 84 bytes

    But you would then need to implement your own routines to implement I/O, and basic math functions like addition, modulo etc.

    Or you could use a pre-written package such as
    http://www.swox.com/gmp/

    > for (lcv=2, flag=1; lcv <= (n / 2); lcv++) {
    You only need to check up to the sqrt(n), not n/2
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    200 digit ints!!?

    A 200 digit int would take 668 bits. A traditional unsigned long takes 32 bits. So you'd need 21 unsigned longs.

    You'd probably need an array of unsigned longs (where the first value is the least significant 32 bits, the next is the second least significant, etc). which you would have to MANUALLY code math routines for. Plus you'd need to program a way to read and write these huge structures.

    And, taking a MODULUS of a 668 bit number is, umm, a HUGELY time intensive project. Modulus is division, and to get a computer to divide a 668 bit number ONCE would be time consuming... to have it do it for 3x10^100 iterations would take AGES.

    As an example, even if your program could do 1,000 divisions of this huge number per second (NOT LIKELY), in the remaining lifetime of the universe, you could only finish:


    0.000000000000000000000000000000000000000000000000 0000000000000000000000000000009979 %

    of one problem.


    Heck, no matter how fast you could make the division, the simple time required to INCREMENT YOUR VARIABLE that many times would require 5x10^93 years to complete. Given that this is FAR greater than the remaining life of the universe, your program could never possibly handle a 200 digit int.

    In one year, even if you were ONLY incrementing a loop and never doing ANYTHING else, on a 2 GHz machine, you could count up to a 16 digit number, allowing you to go up to 33 digits in your prime factorization IF the modulus took no time at all. Given realistic time expectations, it would probably take at least 150 years to compute the primes of a 33 digit number by this means. And each digit more would increase the time a little more than threefold (because the number of passes through the loop increases by sqrt(10)). So 34 digits would take at least 450 years, 35 would take 1350, etc.
    Last edited by The V.; 09-28-2001 at 03:49 PM.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37
    i have tried the GMP package... and it is VERY slow. i factored

    2000000009 in 3.00 seconds with my current process

    but using the GMP functions it took 912.00 seconds!

    i am aware of the processing time that is involved in factoring huge numbers.

    thanks for the feedback.

    i guess i'll get to coding my own routines now.

    thanks.

    -skeptik

  5. #5
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    Why create an array of 21 longs? That is insane.

    If you want a 200 digit int, just create a string 200 characters long. chars and ints are very compatible in C++, so it is not that hard to do arithmetic on the string, and if you need to, convert to an int.

    You could easily create your own class called something like BIGINT that handles everything for you.



    I did one once...it is somewhere on my hard drive.
    Last edited by DavidP; 09-28-2001 at 06:35 PM.
    My Website

    "Circular logic is good because it is."

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    For that matter, why not just use TWO longs? 2^64 is ~ 10^19, which is going to take many hours to factor. If you REALLY wanted to go nuts, you could use 3 unsigned ints -- which would give you up to almost 8x10^28, or 4, which would give you 3x10^38.

    You'd need 60 years with the fastest processors on the market just processing the conditional jumps, nevermind the math, associated with factoring 3x10^38.

    So, pick 2, 3 or 4 unsigned longs, and accept that some problems are simply far beyond the capacity of a machine to compute in a practical timespan. Trying anything above 128 bit numbers is just insane, because it has NO application if you can't possibly have the time to compute it. At best, in your lifetime, you MIGHT be able to factor a 34 or 35 digit number. If you're lucky. So, set practical limiations on the algorithm, which will make it easier to code, AND make it useful.

    Consider also, that every additional element you add will slow ALL your arithmetic down, because coding math for a higher bit count than your processor will natively support means you have to do multiple math operations to simulate a single one. So having four unsigned longs will be, at best, four times as complicated to do math on -- and probably more than that.

    So you need to make the choice of how you lay out the algorithm, because there will be a tradeoff between speed and size, and if you try to handle data that is too large, not only will it be completely useless, it will slow down the smaller numbers which your algorithm might otherwise have been useful for.

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Well from reading this thread I have concluded that DavidP's answer is probably the best. Make a 200 digit string and do math that way. Keep in mind that like the unsigned long int whatever[21] method of doing things you'll have to write your own math logic but anyone who thinks that is a hard process shouldn't be allowed to program. Using an array of longs not a good idea for the reason that it will more than likely cause some brain damage when trying to really think about the number that the array is holding. Char arrays all the way!

  8. #8
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37
    hey... thanks for all the great input. i am hard at work implementing DavidP's string idea.

    i'll post the full source once completed if anyone would like to take a peek and give more input... optimization, better algorithm, etc.

    thanks a lot.

  9. #9
    Unregistered
    Guest
    Could you use bit fields to create a number big enough. Someone said that you needed 668 bits to hold a 200 digit number so would this work?
    unsigned int Huge_number: 668;
    I've never used bit fields before and don't know a whole lot about them, but I was just wondering.

  10. #10
    Registered User
    Join Date
    Aug 2001
    Posts
    16

    Are you guys...

    Are all of you guys crazy(the ones who think its nearly impossible to do)? Perhaps you just aren't looking at the problem the right way, because I'm over 99.99% sure that It would never take that long for me to make a function that completes the task, and on top of that the function would not take all that long to preform. Not to sound bad, but this is why there aren't top notch programs just lying around everywhere. Flame2lose...
    "Practice means good, Perfect Practice means Perfect"

  11. #11
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    Well, using that algorithm, of course it can't be done.

    His algorithm requires SQRT(N) loops. Now, the largest 200 digit number is 1x10^201 - 1.

    SQRT(1x10^201 - 1) ~ 3x10^100 passes through the loop.

    Now, your best commercial computer today is ~2 GHz. This means it has 2x10^9 clock cycles per second.

    Now, a loop takes more than one clock cycle to execute. For this, it is SIGNIFCANTLY more than one cycle execution, but let's assume the loop takes only one clock cycle per loop, which is the absolute minimum we could ever conceive. Then, we need 3x10^100 / 2x10^9 seconds, which works out to 1.5x10^91 seconds to perform 3x10^100 loops.

    1.5x10^91 seconds = 4.75x10^83 years.

    To try to put 4.75x10^83 years in perspective, our sun only has about 5 billion years of life left, which is 5x10^9 years.

    The age of the universe is approximately 1x10^10 years. So even had this algorithm begun executing at the moment of the big bang, it would only be the smallest fraction of the way completed now.

  12. #12
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    http://forum.swarthmore.edu/dr.math/...w10.26.98.html

    Are you sure your project requires working with 200 digit numbers?

  13. #13
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37
    I am using a Multiple Polynomial Quadratic Sieve (MPQS) factoring algorithm that works well with large integers. I've factored 56-digit numbers in under one minute on a 400-MHz Celeron with this method. So factoring large intergers is not hopeless. A 155-digit integer was factored in several months using distributed computing... something I plan on integrating into my project.

  14. #14
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    Actually, I believe 130 digits is the highest ever factored.

    And, each additional digit increases the search space by a factor of TEN, so 131 digits would take ten times as long, 132 would take 100 times, 133 would take 1,000 times, etc.

  15. #15
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37
    here's a link to the highest number ever factored...

    http://www.rsasecurity.com/rsalabs/c...ng/rsa155.html

    that's a 155 digits.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  4. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 09:43 AM
  5. newbie programmer - needs help bad.
    By hortonheat in forum C Programming
    Replies: 17
    Last Post: 10-20-2004, 05:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21