Checking very large prime numbers

This is a discussion on Checking very large prime numbers within the C++ Programming forums, part of the General Programming Boards category; I have to calculate very large prime numbers. I'm stuck on the first step though. Code: unsigned long long int ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    12

    Checking very large prime numbers

    I have to calculate very large prime numbers. I'm stuck on the first step though.

    Code:
    unsigned long long int n = pow(2.0,257.0) - 1;
    cout << n;
    That should be 2.32 * 10^77, but in my program it says something like 9395932912. If this isn't possible in C++, can someone tell me about any program that can check very large prime numbers?

    Thankful for help.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It can be done with C++, but you have to use "high precision math libraries", such as GMP (Gnu MultiPrecission library or some such), as although the value can be described in a double, you do not have sufficient precision in the double to describe the entire number, just a 15-digit approximation. This is fine if you are counting the weight of the universe in terms of thousands of planets and such, but if you want to check if 2^257 - 1 is a prime or not, you will need all the digits of that number, something like 85 digits or so.

    Edit: Note that the integer types normally supported by C are 32-bit, with several compilers allowing 64-bit numbers too. But you are looking for numbers that are 257 bits or more. Integer math for larger numbers isn't terribly hard to implement, but it's obviously not just a case of simple integers any longer.

    --
    Mats
    Last edited by matsp; 02-11-2008 at 07:40 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Not only do you have to use a multi-precisionm math library, but you also can't use the usual algorithms to make the determination either due to because they can take literally hours, days, months, or years etc or because they require more memory than a PC has.
    Numbers that large require complex pseudoprimality tests instead. That's difficult enough that it's the one thing I never implemented in my own bigint library.
    You definitely need something like MPL, or GMP.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  2. how to deal wth large numbers
    By bvgsrs in forum C++ Programming
    Replies: 2
    Last Post: 06-18-2007, 06:16 AM
  3. prime numbers re-posted
    By crypto_quixote in forum C Programming
    Replies: 3
    Last Post: 01-17-2006, 07:44 PM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 10:15 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM

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